# HG changeset patch # User Eris Caffee # Date 1350458267 18000 # Node ID ef2c6a831fb977ca3e0a950824d5596a1d89ef69 # Parent 36561a63330a2006c2d50692fdffea18f485b12f Btree taking shape. Insert seems to be working diff -r 36561a63330a -r ef2c6a831fb9 CMakeLists.txt --- a/CMakeLists.txt Tue Oct 16 19:57:23 2012 -0500 +++ b/CMakeLists.txt Wed Oct 17 02:17:47 2012 -0500 @@ -27,7 +27,7 @@ if (CMAKE_COMPILER_IS_GNUCXX) - add_definitions(-pedantic -Wall -std=gnu99) + add_definitions(-pedantic -Wall -std=gnu99 -O0) endif () diff -r 36561a63330a -r ef2c6a831fb9 src/btree_mem.c --- a/src/btree_mem.c Tue Oct 16 19:57:23 2012 -0500 +++ b/src/btree_mem.c Wed Oct 17 02:17:47 2012 -0500 @@ -1,3 +1,8 @@ +/* + This is a fairly straightforward implementation of a B-Tree in memory modeled after + Cormen, et al., Introduction to Algorithms, Chapter 18 + */ + #include #include @@ -5,7 +10,6 @@ #include "btree_mem.h" -// In btree_mem_node, child[0].keys <= key[0] < child[1].keys <= key[1] < child[2].keys ... struct btree_mem_node { int nkeys; @@ -15,13 +19,17 @@ bool leaf; }; -struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt); -void btree_mem_node_delete (struct btree_mem_node * node); +struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt); +void btree_mem_node_delete (struct btree_mem_node * node); -struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i); +struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i); -void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data); -struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y); +void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data); +void * btree_mem_node_insert_nonfull (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data); + +struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i); + +void btree_mem_node_walk_inorder (struct btree_mem_node * node, void (*f)(int, void *, void *), int depth); //////////////////////////////////////////////////////////////////////////////// struct btree_mem * @@ -41,6 +49,7 @@ return NULL; } + bt->root->leaf = true; return bt; } @@ -88,6 +97,14 @@ return NULL; } + for (int i = 0; i < maxchild - 1; i++) + { + node->key[i] = NULL; + node->data[i] = NULL; + node->child[i] = NULL; + } + node->child[maxchild-1] = NULL; + node->nkeys = 0; node->leaf = false; @@ -136,39 +153,82 @@ void * btree_mem_insert(struct btree_mem * bt, void * key, void * data) { - return btree_mem_node_insert(bt, bt->root, key, data); + struct btree_mem_node * s = bt->root; + + printf("inserting >%d< >%s<\n", *((int *) key), (char *) data); + // If the root node is full, split it here. + if ((2 * bt->mindeg - 1) == s->nkeys) + { + printf("Root node is full: splitting\n"); + s = btree_mem_node_new(bt); + if (NULL == s) + return NULL; + s->child[0] = bt->root; + bt->root = s; + btree_mem_split_child(bt, s, 0); + } + return btree_mem_node_insert_nonfull(bt, s, key, data); } //////////////////////////////////////////////////////////////////////////////// void * -btree_mem_node_insert(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data) +btree_mem_node_insert_nonfull(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data) { - struct btree_node * r = bt->root; - if ((2 * bt->mindeg - 1) == node->nkeys) + int i = node->nkeys - 1; + if (node->leaf) { - struct btree_node * s = btree_mem_node_new(bt); - if (NULL == s) - return NULL; - bt->root = s; - s->child[0] = r; - btree_mem_split_child(bt, s, 1, r); - r = s; + printf("node is leaf: inserting\n"); + while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) ) + { + node->key[i+1] = node->key[i]; + i--; + } + node->key[i+1] = key; + node->data[i+1] = data; + node->nkeys++; + return key; } - return btree_mem_node_insert(bt, s, key, data); + else + { + printf("node is not leaf: recursing\n"); + while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) ) + i--; + i++; + printf("i %d\n", i); + + /* // Does the child exist? If not we need to allocate it */ + /* if (NULL == node->child[i]) */ + /* { */ + /* node->child[i] = btree_mem_node_new(bt); */ + /* if (NULL == node->child[i]) */ + /* return NULL; */ + /* } */ + + if (node->child[i]->nkeys == (2 * bt->mindeg - 1)) + { + printf("splitting before recursion\n"); + if (NULL == btree_mem_split_child(bt, node, i)) + return NULL; + if (bt->cmp(key, node->key[i]) > 0) + i++; + } + return btree_mem_node_insert_nonfull(bt, node->child[i], key, data); + } } //////////////////////////////////////////////////////////////////////////////// // x - a non-full node -// y - a full node that is a child of x -// i - The index of y in x's child list. That is x->child[i] == y. +// i - The index of a full node y in x's child list. // // Split y in half, adding the newly created node z as a new child of x. // z will be placed after y in the child list. struct btree_mem_node * -btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y) +btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i) { + struct btree_mem_node * y = x->child[i]; + // Allocate new node. struct btree_mem_node * z = btree_mem_node_new(bt); if (NULL == z) @@ -184,20 +244,20 @@ } if (! y->leaf) { - for (int j = 0; j < bt->mindeg) + for (int j = 0; j < bt->mindeg; j++) z->child[j] = y->child[j + bt->mindeg]; } - // Update y's nkeys. We don't bother NULLing out the now unused key and data pointers. + // Update y's nkeys. y->nkeys = bt->mindeg - 1; // Make a hole in x's child list for the new node z. - for (int j = x->nkeys; j > i; j--) + for (int j = x->nkeys; j >= i + 1; j--) x->child[j+1] = x->child[j]; - x->child[i] = z; + x->child[i+1] = z; // Make a hole in x's key list for the new node z. - for (int j = x->nkeys - 1; j > i-1; j--) + for (int j = x->nkeys - 1; j >= i; j--) { x->key[j+1] = x->key[j]; x->data[j+1] = x->data[j]; @@ -205,8 +265,16 @@ x->key[i] = y->key[bt->mindeg-1]; x->data[i] = y->data[bt->mindeg-1]; + x->nkeys += 1; - x->nkeys += 1; + /* // NULL out the now unused key and data pointers in y. */ + /* for (int j = bt->mindeg; j < (2*bt->mindeg - 1); j++) */ + /* { */ + /* y->key[j] = NULL; */ + /* y->data[j] = NULL; */ + /* y->child[j] = NULL; */ + /* } */ + /* y->child[2*bt->mindeg - 1] = NULL; */ return z; } @@ -218,3 +286,41 @@ } +//////////////////////////////////////////////////////////////////////////////// +void +btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *)) + { + btree_mem_node_walk_inorder(bt->root, f, 0); + } + +//////////////////////////////////////////////////////////////////////////////// +void +btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void *, void *), int depth) + { + + // for (int i = 0; i < depth; i++) + // printf("\t"); + // printf("nkeys %d\n", node->nkeys); + // printf("walking\n"); + if (0 == node->nkeys) + { + // printf("no keys\n"); + if (NULL != node->child[0]) + { + // printf(": walking child\n"); + btree_mem_node_walk_inorder(node->child[0], f, depth+1); + } + return; + } + + // printf("walking %d keys\n", node->nkeys); + for (int i = 0; i < node->nkeys; i++) + { + if (! node->leaf) + btree_mem_node_walk_inorder(node->child[i], f, depth+1); + f(depth, node->key[i], node->data[i]); + } + if (! node->leaf) + btree_mem_node_walk_inorder(node->child[node->nkeys], f, depth+1); + } + diff -r 36561a63330a -r ef2c6a831fb9 src/btree_mem.h --- a/src/btree_mem.h Tue Oct 16 19:57:23 2012 -0500 +++ b/src/btree_mem.h Wed Oct 17 02:17:47 2012 -0500 @@ -18,4 +18,6 @@ void * btree_mem_find(struct btree_mem * bt, void * key); void * btree_mem_remove(struct btree_mem * bt, void * key); +void btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *)); + #endif diff -r 36561a63330a -r ef2c6a831fb9 src/btree_mem_test.c --- a/src/btree_mem_test.c Tue Oct 16 19:57:23 2012 -0500 +++ b/src/btree_mem_test.c Wed Oct 17 02:17:47 2012 -0500 @@ -10,14 +10,50 @@ return strcmp(a, b); } + +void +print_data(int depth, void * key, void * data) + { + for (int i = 0; i < depth; i++) + printf("\t"); + printf("%d %s\n", *((int*)key), (char *) data); + } + +void +print_tree(struct btree_mem * bt) + { + printf("==================================\n"); + btree_mem_walk_inorder(bt, print_data); + printf("==================================\n"); + } + int main(int argc, char ** argv) { - struct btree_mem * bt = btree_mem_new(2, cmp); +#define MINDEGREE 3 + struct btree_mem * bt = btree_mem_new(MINDEGREE, cmp); if (NULL == bt) { fprintf(stderr, "Unable to create new btree_mem\n"); exit(EXIT_FAILURE); } + +#define MAXKEYS 20 + int keys[MAXKEYS] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, + 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }; + char * data[MAXKEYS] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", + "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" }; + + for (int i = 0; i < MAXKEYS; i++) + { + print_tree(bt); + if (NULL == btree_mem_insert(bt, keys+i, data[i])) + { + fprintf(stderr, "btree_mem_insert failed\n"); + exit(EXIT_FAILURE); + } + } + print_tree(bt); + exit(EXIT_SUCCESS); }