diff options
Diffstat (limited to 'src/tree.c')
-rw-r--r-- | src/tree.c | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..5edda76 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,205 @@ +#include "config.h" + +#include <assert.h> +#include <errno.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "logerr.h" +#include "util.h" + +#include "tree.h" + + + +struct Tree { + const void *const value; + const struct Tree *left; + const struct Tree *right; + const size_t value_size; + size_t height; +}; + + + +int +tree_new(const size_t value_size, const struct Tree **const out) { + int rc = -1; + + const struct Tree *ret = NULL; + + ret = malloc(sizeof(*ret)); + if (ret == NULL) { + logerr("malloc(): %s", strerror(errno)); + goto out; + } + + memcpy((void *)ret, &(struct Tree) { + .value = NULL, + .left = NULL, + .right = NULL, + .value_size = value_size, + .height = 0U, + }, sizeof(*ret)); + *out = ret; + rc = 0; +out: + if (rc) { + if (ret != NULL) { + freeit((void *)&ret); + } + } + return rc; +} + +void +tree_free(const struct Tree **const t) { + const struct Tree *const tree = *t; + assert(tree != NULL); + + const struct Tree *left = tree->left; + const struct Tree *right = tree->right; + + if (left != NULL) { + tree_free(&left); + } + + if (right != NULL) { + tree_free(&right); + } + + freeit((void *)t); +} + +static void +insert_node( + const struct Tree *const t, + const struct Tree *node, + const void *const value +) { + struct Tree *const t_mut = (struct Tree *const)t; + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + tree_free(&node); + } else if (cmp > 0) { + if (t->left == NULL) { + t_mut->left = (void *)node; + } else { + insert_node(t->left, node, value); + } + struct Tree *const t_left_mut = (struct Tree *const)t->left; + t_left_mut->height++; + } else { + if (t->right == NULL) { + t_mut->right = node; + } else { + insert_node(t->right, node, value); + } + struct Tree *const t_right_mut = (struct Tree *const)t->right; + t_right_mut->height++; + } +} + +int +tree_insert(const struct Tree *const t, const void *const value) { + int rc = -1; + + const struct Tree *new = NULL; + struct Tree *const t_mut = (struct Tree *const)t; + + if (t->value == NULL) { + memcpy((void *)t->value, value, t->value_size); + t_mut->height++; + goto out; + } + + if (tree_new(t->value_size, &new)) { + logerr("tree_new()"); + goto out; + } + + insert_node(t, new, value); + + rc = 0; +out: + if (rc) { + if (new != NULL) { + tree_free(&new); + } + } + return rc; +} + +static bool +remove_ref( + const struct Tree *t, + const void *const value, + const struct Tree **const parent_ptr +) { + if (t->value == NULL) { + return false; + } + + struct Tree *const t_mut = (struct Tree *const)t; + + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + if ((t->left == NULL) && (t->right == NULL)) { + if (parent_ptr != NULL) { + *parent_ptr = NULL; + } + } else if (t->left != NULL) { + if (parent_ptr != NULL) { + *parent_ptr = t->left; + } + } else if (t->right != NULL) { + if (parent_ptr != NULL) { + *parent_ptr = t->right; + } + } else { + // FIXME: pivot + assert(false); + } + tree_free(&t); + return true; + } else if (cmp > 0) { + if (t->left == NULL) { + return false; + } + return remove_ref(t->left, value, &t_mut->left); + } else { + if (t->right == NULL) { + return false; + } + return remove_ref(t->right, value, &t_mut->right); + } +} + +bool +tree_remove(const struct Tree *const t, const void *const value) { + return remove_ref(t, value, NULL); +} + +bool +tree_contains(const struct Tree *const t, const void *const value) { + if (t->value == NULL) { + return false; + } + + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + return true; + } else if (cmp > 0) { + if (t->left == NULL) { + return false; + } + return tree_contains(t->left, value); + } else { + if (t->right == NULL) { + return false; + } + return tree_contains(t->right, value); + } +} |