summaryrefslogtreecommitdiff
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tree.c')
-rw-r--r--src/tree.c205
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);
+ }
+}