From f5574373c6a499659bd4a0ca11c1f8484c7b02be Mon Sep 17 00:00:00 2001 From: 0scar Date: Fri, 8 Oct 2021 14:55:09 +0200 Subject: Fix child shuffling --- src/btree_naive.c | 88 +++++++++++++++++++++++++++++-------------------------- 1 file changed, 46 insertions(+), 42 deletions(-) (limited to 'src/btree_naive.c') diff --git a/src/btree_naive.c b/src/btree_naive.c index 6e96f7f..3216e00 100644 --- a/src/btree_naive.c +++ b/src/btree_naive.c @@ -51,16 +51,13 @@ node_full(degree, t) (t->n >= 2 * degree - 1) * when the node is no longer a leaf node */ 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)); + struct node *retval = calloc(1, 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->n = 0; + retval->c = 0; retval->items = calloc(max_items, elem_size); retval->children = NULL; - printf("Item address: %p\n", (void*)retval->items); - return retval; } @@ -92,8 +89,6 @@ bool node_transition(const ssize_t degree, const size_t elem_size, struct node * } } - /* node->c = c; */ - return true; } @@ -110,18 +105,28 @@ void node_free(struct node *node, size_t elem_size, void (*dealloc)(void*)) { node->items = NULL; free(node); + node = NULL; } -/* Split a child of `nonfull` of index `i` */ + +/* `node_tree_split_child` splits a _full_ node (c = 2t-1 items) into two nodes + * with t-1 items each. + * The median key/item/element moves up to the original nodes parent, to signify + * the split. If the parent is full too, we need to split it before inserting + * the median key. + * This can potentially split full nodes all the way up throughout the tree. */ +/* Instead of waiting to find out wether we should split the nodes, we split the + * full nodes we encounter on the way down, including the leafs themselves. + * By doing this, we are assured that whenever we split a node, its parent has + * room for the median key. */ void node_tree_split_child( const size_t t, const size_t elem_size, struct node *nonfull, - size_t i) { + ssize_t i) { struct node *z = node_new(t, elem_size); struct node *y = nonfull->children[i]; - size_t j; - const ssize_t min_elem = (t-1 <= 2) ? 2 : t-1; + ssize_t j; /* `z` should be a branching node if `y` is */ if (!node_leaf(y)) { @@ -130,14 +135,17 @@ void node_tree_split_child( z->n = t - 1; - for (j = 0; j < min_elem; j++) { + /* Move last `t-1` items to new node `z` */ + for (j = 0; j < t-1; j++) { const size_t offset_dst = elem_size * j; - const size_t offset_src = offset_dst + elem_size * t; + const size_t offset_src = elem_size * (t+j); memcpy((z->items) + offset_dst, (y->items) + offset_src, elem_size); } + /* Set unused item-memory to zero? */ + /* Move children t..2t, if applicable*/ if (!node_leaf(y)) { - for (j = 0; j < t; j++) { + for (j = 0; j < t+1; j++) { z->children[j] = y->children[j + t]; } y->c = t; @@ -146,37 +154,30 @@ void node_tree_split_child( y->n = t - 1; - for (j = nonfull->n + 1; j > i+1; j--) { - nonfull->children[j + 1] = nonfull->children[j]; + /* Move children +1 */ + for (j = nonfull->n; j > i; j--) { + nonfull->children[j+1] = nonfull->children[j]; } + + /* new child */ nonfull->children[i+1] = z; nonfull->c++; - for (j = nonfull->n; j > i; j--) { + /* moving keys i..n */ + for (j = nonfull->n; j >= i; j--) { const size_t offset = j * elem_size; memcpy((nonfull->items) + offset + elem_size, (nonfull->items) + offset, elem_size); } + /* Lastly, copy the median element to nonfull-parent*/ memcpy((nonfull->items) + i * elem_size, - (y->items) + elem_size * (t-1), - elem_size); + (y->items) + (t-1) * elem_size, + elem_size); nonfull->n++; } - -/* `node_split` splits a _full_ node (c = 2t-1 items) into two nodes with t-1 - * items each. - * The median key/item/element moves up to the original nodes parent, to signify - * the split. - * If the parent is full too, we need to split it before inserting the median - * key. - * This can potentially split full nodes all the way up throughout the tree. */ -/* Instead of waiting to find out wether we should split the nodes, we split the - * full nodes we encounter on the way down, including the leafs themselves. - * By doing this, we are assured that whenever we split a node, its parent has - * room for the median key. */ struct node *node_split() { /* TODO implement */ return NULL; @@ -193,7 +194,7 @@ struct node* node_insert_nonfull( 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) { + while (i >= 0 && cmp(elem, root->items + offset) < 0) { memcpy(root->items + offset + elem_size, root->items + offset, elem_size); i--; @@ -206,7 +207,7 @@ struct node* node_insert_nonfull( } else { size_t offset = elem_size * i; struct node *nextchild = NULL; - while (i >= 0 && cmp(elem, root->items + offset) == BTREE_CMP_LT) { + while (i >= 0 && cmp(elem, root->items + offset) < 0) { i--; offset = elem_size * i; } @@ -215,7 +216,7 @@ struct node* node_insert_nonfull( if (node_full(degree, nextchild)) { /* TODO Check if the root has changed */ node_tree_split_child(degree, elem_size, root, i); - if (cmp(elem, root->items + elem_size * i) == BTREE_CMP_GT) { + if (cmp(elem, root->items + elem_size * i) > 0) { nextchild = root->children[++i]; } } @@ -252,15 +253,18 @@ void* node_search(struct node *x, void *key, int(*cmp)(const void *a, const void *b), const size_t elem_size) { - ssize_t i = 0; - int last_cmp_res = cmp(key, (const void*)x->items); - - while (i < x->n && last_cmp_res > 0) { + /* We set to one, since we pre-emptively do a comparison with the assumption + * that there's already one in the items */ + ssize_t i = 0; + int last_cmp_res; + + while (i < x->n + && (last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size)))) + > 0) { i++; - last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size))); } - if ((ssize_t)i < x->n && last_cmp_res == BTREE_CMP_EQ) { + if ((ssize_t)i < x->n && last_cmp_res == 0) { return (void*)(x->items + (i * elem_size)); } else if (node_leaf(x)) { return NULL; @@ -326,7 +330,7 @@ void node_print(struct node *root, const size_t elem_size, const int indent, voi for (t = 0; t < indent - 1; t++) { fputs(" ┃ ", stdout); } if (indent > 0) { fputs(" ┣┯", stdout); } - printf("printing node %p, c:%ld n:%ld\n", (void*)root, root->c, root->n); + printf("printing node \x1b[33m%0lx\x1b[0m, c:%ld n:%ld\t\t\x1b[30m%p\x1b[0m\n", (size_t)root % 0x10000, root->c, root->n, (void*)root); if (node_leaf(root)) { for (i = 0; i < root->n - 1; i++) { -- cgit v1.3