Fix insertion

1 files changed, 54 insertions, 36 deletions

diff --git a/src/btree_naive.c b/src/btree_naive.c
index be6fdd3..6e96f7f 100644
--- a/src/btree_naive.c
+++ b/src/btree_naive.c
@@ -5,12 +5,14 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include <sys/types.h>
+
 /* Definitions */
 typedef unsigned char byte;
 
 struct node {
-	size_t       n; /* number of items/keys/elements */
-	size_t       c; /* number of children */
+	ssize_t       n; /* number of items/keys/elements */
+	ssize_t       c; /* number of children */
 	byte        *items;
 	struct node **children;
 };
@@ -22,7 +24,7 @@ struct btree {
 
 	/* Size stuffs */
 	size_t elem_size;
-	size_t degree;
+	ssize_t degree;
 
 	struct node *root;
 
@@ -41,21 +43,24 @@ node_maxdegree(t) (2 * t - 1)
 node_mindegree(t) (t - 1)
 
 #define \
-node_full(degree, t) (t->n == 2 * degree - 1)
+node_full(degree, t) (t->n >= 2 * degree - 1)
 
 /* Node memory */
 
 /* `node_new` allocates a new leaf node, children should be added and allocated
  * when the node is no longer a leaf node */
-struct node* node_new(const size_t degree, const size_t elem_size) {
-	const size_t max_items = 2 * degree - 1;
+struct node* node_new(const ssize_t degree, const size_t elem_size) {
+	const size_t max_items = 2 * degree;
 	struct node *retval = malloc(sizeof(struct node));
 
+	printf("Allocating node with %ld bytes: max_items:%ld elem_size:%ld\n", max_items * elem_size, max_items, elem_size);
 	retval->n        = 0;
 	retval->c        = 0;
-	retval->items    = calloc(max_items, sizeof(elem_size));
+	retval->items    = calloc(max_items, elem_size);
 	retval->children = NULL;
 
+	printf("Item address: %p\n", (void*)retval->items);
+
 	return retval;
 }
 
@@ -63,8 +68,8 @@ struct node* node_new(const size_t degree, const size_t elem_size) {
  * for it.
  * returnvalue: `false` if we we're unable to allocate space for the new
  * children. */
-bool node_transition(const size_t degree, const size_t elem_size, struct node *node) {
-	const int max_children = 2 * degree;
+bool node_transition(const ssize_t degree, const size_t elem_size, struct node *node) {
+	const int max_children = 2 * degree + 1;
 	int c;
 	/* Allocate pointers for children */
 	node->children = calloc(max_children, sizeof(struct node*));
@@ -87,41 +92,45 @@ bool node_transition(const size_t degree, const size_t elem_size, struct node *n
 		}
 	}
 
-	node->c = c;
+	/* node->c = c; */
 
 	return true;
 }
 
 void node_free(struct node *node, size_t elem_size, void (*dealloc)(void*)) {
-	size_t i;
+	ssize_t i;
 	if (node == NULL) return;
-	for (i = 0; i < node->c; i++) {
-		node_free((node->children)[i], elem_size, dealloc);
+	if (!node_leaf(node)) {
+		for (i = 0; i < node->c; i++) {
+			node_free((node->children)[i], elem_size, dealloc);
+		}
 	}
 
-	if (!node_leaf(node))
-		dealloc(node->items);
+	dealloc(node->items);
+	node->items = NULL;
 
 	free(node);
 }
 
 /* Split a child of `nonfull` of index `i` */
-void node_tree_split_child(const size_t t, const size_t elem_size, struct node *nonfull, size_t i) {
+void node_tree_split_child(
+		const size_t t,
+		const size_t elem_size,
+		struct node *nonfull,
+		size_t i) {
 	struct node *z = node_new(t, elem_size);
 	struct node *y = nonfull->children[i];
 	size_t j;
-
-	printf("Splitting tree!\n");
-	__asm__("int3");
+	const ssize_t min_elem = (t-1 <= 2) ? 2 : t-1;
 
 	/* `z` should be a branching node if `y` is */
-	if (node_leaf(y)) {
+	if (!node_leaf(y)) {
 		node_transition(t, elem_size, z);
 	}
 
 	z->n = t - 1;
 
-	for (j = 0; j < t - 1; j++) {
+	for (j = 0; j < min_elem; j++) {
 		const size_t offset_dst = elem_size * j;
 		const size_t offset_src = offset_dst + elem_size * t;
 		memcpy((z->items) + offset_dst, (y->items) + offset_src, elem_size);
@@ -141,6 +150,7 @@ void node_tree_split_child(const size_t t, const size_t elem_size, struct node *
 		nonfull->children[j + 1] = nonfull->children[j];
 	}
 	nonfull->children[i+1] = z;
+	nonfull->c++;
 
 	for (j = nonfull->n; j > i; j--) {
 		const size_t offset = j * elem_size;
@@ -150,13 +160,10 @@ void node_tree_split_child(const size_t t, const size_t elem_size, struct node *
 	}
 
 	memcpy((nonfull->items) + i * elem_size,
-			(y->items) + elem_size * t,
+			(y->items) + elem_size * (t-1),
 			elem_size);
 
 	nonfull->n++;
-
-	__asm__("int3");
-
 }
 
 /* `node_split` splits a _full_ node (c = 2t-1 items) into two nodes with t-1
@@ -175,14 +182,15 @@ struct node *node_split() {
 	return NULL;
 }
 
+/* return: Returns the new root, if a split happens */
 struct node* node_insert_nonfull(
 		struct node *root,
 		void *elem,
-		const size_t degree,
+		const ssize_t degree,
 		const size_t elem_size,
 		int (*cmp)(const void *a, const void *b)) {
 	/* TODO check correctness */
-	size_t i = root->n - 1;
+	ssize_t i = root->n - 1;
 	if (node_leaf(root)) {
 		size_t offset = elem_size * i;
 		while (i >= 0 && cmp(elem, root->items + offset) == BTREE_CMP_LT) {
@@ -191,17 +199,19 @@ struct node* node_insert_nonfull(
 			i--;
 			offset = elem_size * i;
 		}
-		offset = elem_size * (i++);
+		offset = elem_size * (++i);
 		memcpy(root->items + offset, elem, elem_size);
+		root->n++;
 
 	} else {
 		size_t offset = elem_size * i;
+		struct node *nextchild = NULL;
 		while (i >= 0 && cmp(elem, root->items + offset) == BTREE_CMP_LT) {
 			i--;
 			offset = elem_size * i;
 		}
 		i++;
-		struct node *nextchild = root->children[i];
+		nextchild = root->children[i];
 		if (node_full(degree, nextchild)) {
 			/* TODO Check if the root has changed */
 			node_tree_split_child(degree, elem_size, root, i);
@@ -211,33 +221,38 @@ struct node* node_insert_nonfull(
 		}
 		return node_insert_nonfull(nextchild, elem, degree, elem_size, cmp);
 	}
+	return NULL; /* TODO: Fix return value */
 }
 
+/* Returns the new root, if a split occurs */
 struct node* node_insert(
 		struct node *root,
 		void *elem,
-		const size_t degree,
+		const ssize_t degree,
 		const size_t elem_size,
 		int (*cmp)(const void *a, const void *b)) {
+
+	struct node *s = root;
+
 	if (node_full(degree, root)) {
-		struct node *s = node_new(degree, elem_size);
+		s = node_new(degree, elem_size);
 		node_transition(degree, elem_size, s);
 		s->children[s->c++] = root;
 		/* TODO Check if the root has changed */
 		node_tree_split_child(degree, elem_size, s, 0);
-		return node_insert_nonfull(s, elem, degree, elem_size, cmp);
+		node_insert_nonfull(s, elem, degree, elem_size, cmp);
 	}
 	else {
-		return node_insert_nonfull(root, elem, degree, elem_size, cmp);
+		node_insert_nonfull(s, elem, degree, elem_size, cmp);
 	}
-	return NULL;
+	return s;
 }
 
 void* node_search(struct node *x,
                   void *key,
                   int(*cmp)(const void *a, const void *b),
                   const size_t elem_size) {
-	size_t i            = 0;
+	ssize_t i           = 0;
 	int    last_cmp_res = cmp(key, (const void*)x->items);
 
 	while (i < x->n && last_cmp_res > 0) {
@@ -245,7 +260,7 @@ void* node_search(struct node *x,
 		last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size)));
 	}
 
-	if (i < x->n && last_cmp_res == BTREE_CMP_EQ) {
+	if ((ssize_t)i < x->n && last_cmp_res == BTREE_CMP_EQ) {
 		return (void*)(x->items + (i * elem_size));
 	} else if (node_leaf(x)) {
 		return NULL;
@@ -292,6 +307,9 @@ void btree_insert(struct btree *btree, void *elem) {
 		btree->root = node_new(btree->degree, btree->elem_size);
 		node_insert(btree->root, elem, btree->degree, btree->elem_size, btree->cmp);
 	}
+	else {
+		btree->root = node_insert(btree->root, elem, btree->degree, btree->elem_size, btree->cmp);
+	}
 }
 
 void* btree_search(struct btree *btree, void *elem) {