Add template for btrees

3 files changed, 141 insertions, 0 deletions

diff --git a/src/btree.h b/src/btree.h
new file mode 100644
index 0000000..95acf22
--- /dev/null
+++ b/src/btree.h
@@ -0,0 +1,43 @@
+#ifndef BTREE_H
+#define BTREE_H
+
+#include <stddef.h>
+
+#define BTREE_DEGREE_DEFAULT 4
+
+#define BTREE_SIZE_MIN 8
+#define BTREE_SIZE_MAX 4096
+
+#define BTREE_CMP_LT        ( -1 )
+#define BTREE_CMP_EQ        (  0 )
+#define BTREE_CMP_GT        (  1 )
+
+struct btree;
+
+/* elem_size: the size of the elements, typically `sizeof(struct <your struct>)`
+ * t: degree of the btree, if you're in doubt, use `BTREE_SIZE_DEFAULT`
+ * cmp: comparison function, in order to support any operations on the tree.
+ *
+ * This function just calls `btree_new_with_allocator` with `free` and `malloc`
+ * as initializers.
+ */
+struct btree *btree_new(size_t elem_size,
+                        size_t t,
+                        int(*cmp)(const void *a, const void *b));
+
+/* Same as `btree_new`, except that it actually initializes a btree, but with
+ * the given allocators.
+ */
+struct btree *btree_new_with_allocator(size_t elem_size,
+                        size_t t,
+                        int(*cmp)(const void *a, const void *b),
+                        void *(*alloc)(size_t),
+                        void  (*dealloc)(void*));
+
+void btree_free(struct btree *btree);
+
+void *btree_search(struct btree *btree, void *elem);
+void *btree_insert(struct btree *btree, void *elem);
+void *btree_delete(struct btree *btree, void *elem);
+
+#endif
diff --git a/src/btree_naive.c b/src/btree_naive.c
new file mode 100644
index 0000000..bc881f1
--- /dev/null
+++ b/src/btree_naive.c
@@ -0,0 +1,58 @@
+#include "btree.h"
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+typedef unsigned char byte;
+
+struct node {
+	size_t n; /* number of items */
+	bool leaf;
+	byte *items;
+	struct node *children;
+};
+
+struct btree {
+	/* Memory stuffs */
+	void *(*alloc)(size_t);
+	void (*dealloc)(void*);
+
+	/* Size stuffs */
+	size_t elem_size;
+	size_t degree;
+
+	/* comparison */
+	int (*cmp)(const void *a, const void *b);
+};
+
+struct btree *btree_new(size_t elem_size,
+                        size_t t,
+                        int(*cmp)(const void *a, const void *b)) {
+	return btree_new_with_allocator(elem_size, t, cmp, malloc, free);
+}
+
+struct btree *btree_new_with_allocator(size_t elem_size,
+                        size_t t,
+                        int(*cmp)(const void *a, const void *b),
+                        void *(*alloc)(size_t),
+                        void (*dealloc)(void*)) {
+	struct btree *new_tree = malloc(sizeof(struct btree));
+
+	new_tree->alloc        = alloc;
+	new_tree->dealloc      = dealloc;
+
+	new_tree->elem_size    = elem_size;
+	new_tree->degree       = t;
+
+	new_tree->cmp          = cmp;
+}
+
+void btree_free(struct btree *btree) {
+	/*btree->dealloc(btree->root);*/
+	free(btree);
+	btree = NULL;
+}
+
+void *btree_search(struct btree *btree, void *elem) {}
+void *btree_insert(struct btree *btree, void *elem) {}
+void *btree_delete(struct btree *btree, void *elem) {}
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..7e460c8
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,40 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "btree.h"
+
+enum gender {
+	gender_male,
+	gender_female,
+	gender_other
+};
+
+struct userdat {
+	const char *name;
+	unsigned short age;
+	enum gender gender;
+};
+
+int userdat_cmp(const void *a, const void *b) {
+	const struct userdat *ua = a;
+	const struct userdat *ub = b;
+
+	if (ua->age == ub->age) {
+		     if (ua->gender > ub->gender) { return BTREE_CMP_GT; }
+		else if (ua->gender < ub->gender) { return BTREE_CMP_LT; }
+		                                  { return BTREE_CMP_EQ; }
+
+	} else if (ua->age > ub->age) {
+		return BTREE_CMP_GT;
+	} return BTREE_CMP_LT;
+}
+
+int main() {
+	struct btree *tree = btree_new(sizeof(struct userdat),
+	                               BTREE_DEGREE_DEFAULT,
+	                               &userdat_cmp);
+
+	btree_free(tree);
+
+	return 0;
+}