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);
+	}
+}