# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1350693737 18000
# Node ID f27bdd5d40d0e9f72a44fcfee160f616a75c831f
# Parent  36018adade6d4ae9bd68c726ef0900896a725bf4
Ran more tests.  Found another leak.  Fixed it.  Now it's really good.  for (( MinDeg=2; MinDeg<=100; MinDeg++ )) ; do echo MinDeg 101 ; numwords 1000 | rev | valgrind --tool=memcheck --leak-check=full --show-reachable=yes  ./btree_mem_test 101 2>&1 | grep "ERROR SUMMARY" ; done

diff -r 36018adade6d -r f27bdd5d40d0 src/btree_mem.c
--- a/src/btree_mem.c	Fri Oct 19 18:19:39 2012 -0500
+++ b/src/btree_mem.c	Fri Oct 19 19:42:17 2012 -0500
@@ -57,12 +57,6 @@
 #define DEBUG_BLOCK(x)
 #endif
 
-void printit(int h, void * k, void * d)
-   {
-   for (int i = 0; i < h; i++)
-      printf("\t");
-   printf("%d %s\n", *((int*)k), (char *) d);
-   }
 
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -76,7 +70,7 @@
    bt->mindeg = min_degree;
    bt->cmp = cmp;
 
-   printf("Getting new root node\n");
+   DEBUG_BLOCK( printf("Getting new root node\n"); );
    bt->root = btree_mem_node_new(bt);
    if (NULL == bt->root)
       {
@@ -108,7 +102,7 @@
    if (NULL == node)
       return NULL;
 
-   printf("Allocated node %p\n", node);
+   DEBUG_BLOCK( printf("Allocated node %p\n", node); );
    int maxchild = 2*bt->mindeg;
 
    node->key  = malloc( (maxchild - 1) * sizeof(void *));
@@ -155,7 +149,7 @@
 void
 btree_mem_node_delete(struct btree_mem_node * node)
    {
-   printf("Freeing node %p\n", node);
+   DEBUG_BLOCK( printf("Freeing node %p\n", node); );
    free(node->child);
    free(node->data);
    free(node->key);
@@ -192,13 +186,13 @@
 void *
 btree_mem_insert(struct btree_mem * bt, void * key, void * data)
    {
-   DEBUG_BLOCK(  printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data);  )
+   DEBUG_BLOCK(  printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data);  );
    struct btree_mem_node * s = bt->root;
 
    // If the root node is full, split it here.
    if ((2 * bt->mindeg - 1) == s->nkeys)
       {
-      printf("Splitting root node.  Allocating new node\n");
+      DEBUG_BLOCK( printf("Splitting root node.  Allocating new node\n"); );
       s = btree_mem_node_new(bt);
       if (NULL == s)
 	 return NULL;
@@ -216,7 +210,6 @@
    int i = node->nkeys - 1;
    if (node->leaf)
       {
-      //DEBUG_BLOCK( printf("node->nkeys: %d\n", node->nkeys); )
       while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
 	 {
 	 node->key[i+1] = node->key[i];
@@ -259,7 +252,7 @@
    struct btree_mem_node * y = x->child[i];
 
    // Allocate new node.
-   printf("splitting child allocating new node\n");
+   DEBUG_BLOCK( printf("splitting child allocating new node\n"); );
    struct btree_mem_node * z = btree_mem_node_new(bt);
    if (NULL == z)
       return NULL;
@@ -364,7 +357,6 @@
       {
       if (! node->leaf) 
 	 btree_mem_node_dump(node->child[i], f, depth+1);
-      printf("node: %p nkeys %10d \t", node, node->nkeys);
       f(depth, node->key[i], node->data[i]);
       }
    if (! node->leaf) 
@@ -378,14 +370,14 @@
    if ( (NULL == bt) || (NULL == key) || (NULL == key_value) || (NULL == data_value) )
       return NULL;
 
-   DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); )
+   DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); );
    void * data = btree_mem_node_remove(bt, bt->root, key, key_value, data_value);
    if (NULL == data)
       return NULL;
 
    if ( (0 == bt->root->nkeys) && (bt->root->child[0]) )
       {
-      DEBUG_BLOCK( printf("Freeing the root node\n"); )
+      DEBUG_BLOCK( printf("Freeing the root node\n"); );
       struct btree_mem_node * n = bt->root;
       bt->root = bt->root->child[0];
       btree_mem_node_delete(n);
@@ -400,7 +392,7 @@
 btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key, void ** key_value, void ** data_value)
    {
 
-   DEBUG_BLOCK( btree_mem_node_print_keys(node); )
+   DEBUG_BLOCK( btree_mem_node_print_keys(node); );
 
    int i = node->nkeys - 1;
    while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
@@ -411,11 +403,11 @@
       // key is in node at key[i]
       *key_value = node->key[i];
       *data_value = node->data[i];
-      //      printf("Will return key_value %p (%d)   data_value %p (%s)\n", *key_value, *((int*)(*key_value)), *data_value, (char*)(*data_value));
+
       if (node->leaf)
 	 {
 	 // case 1
-	 DEBUG_BLOCK( printf("remove: case 1\n"); )
+	 DEBUG_BLOCK( printf("remove: case 1\n"); );
 	 btree_mem_node_remove_key(node, i);
 	 return *data_value;
 	 }
@@ -442,7 +434,7 @@
 	    else
 	       {
 	       // case 2b
-	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
+	       DEBUG_BLOCK( printf("remove: case 2b\n"); );
 	       kp = btree_mem_node_find_next(next);
 	       node->key[i]  = kp->key[0];
 	       node->data[i] = kp->data[0];
@@ -455,7 +447,7 @@
 	 else
 	    {
 	    // case 2c
-	    DEBUG_BLOCK( printf("remove: case 2c\n"); )
+	    DEBUG_BLOCK( printf("remove: case 2c\n"); );
 	    btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]);
 	    btree_mem_node_remove_key(node, i);	
 	    for (int j = i+1; j <= node->nkeys+1; j++)
@@ -472,14 +464,14 @@
       {
       if (node->leaf)
 	 {
-	 DEBUG_BLOCK( printf("remove: key not found\n"); )
+	 DEBUG_BLOCK( printf("remove: key not found\n"); );
 	 return NULL;
 	 }
 
       // key is in child[i+1], if anywhere
       struct btree_mem_node * c = node->child[i+1];
 
-      DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); )
+      DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); );
       if (c->nkeys == bt->mindeg - 1)
 	 {
 	 struct btree_mem_node * prev = NULL;
@@ -490,7 +482,7 @@
 	 if (i+2 <= node->nkeys)
 	    next = node->child[i+2];
 
-	 DEBUG_BLOCK( printf("remove: prev %p  next %p\n", prev, next); )
+	 DEBUG_BLOCK( printf("remove: prev %p  next %p\n", prev, next); );
 
 	 if ( (prev) && (prev->nkeys >= bt->mindeg) )
 	    {
@@ -501,7 +493,7 @@
 	    //     move prev->child[prev->nkeys] into c->child[0] shifting over existing children
 	    // prev->nkeys--;
 	    
-	    DEBUG_BLOCK( printf("remove: case 3a.1\n"); )
+	    DEBUG_BLOCK( printf("remove: case 3a.1\n"); );
 
 	    btree_mem_node_add_key(bt, c, node->key[i-1], node->data[i-1]);
 
@@ -522,7 +514,7 @@
 	    // case 3a (with next sibling)
 	    // Symmetric with the above
 
-	    DEBUG_BLOCK( printf("remove: case 3a.2\n"); )
+	    DEBUG_BLOCK( printf("remove: case 3a.2\n"); );
 	    btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]);
 
 	    node->key[i+1]  = next->key[0];
@@ -546,10 +538,7 @@
 	 else
 	    {
 	    // case 3b
-	    DEBUG_BLOCK( printf("remove: case 3b\n"); )
-		  //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
-		  //	    printf("node %p  i %d\n", node, i); fflush(stdout);
-		  //	    printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev));	    fflush(stdout);
+	    DEBUG_BLOCK( printf("remove: case 3b\n"); );
 	    if (next)
 	       btree_mem_node_merge(c, next);
 	    else
@@ -561,13 +550,13 @@
 
 	    if (next)
 	       {
-	       for (int j = i+2; j <= node->nkeys+1; j++)
+	       for (int j = i+2; j <= node->nkeys; j++)
 		  node->child[j] = node->child[j+1];
 	       btree_mem_node_delete(next);
 	       }
 	    else
 	       {
-	       for (int j = i; j <= node->nkeys+1; j++)
+	       for (int j = i; j <= node->nkeys; j++)
 		  node->child[j] = node->child[j+1];
 	       btree_mem_node_delete(c);
 	       c = prev;
diff -r 36018adade6d -r f27bdd5d40d0 src/btree_mem_test.c
--- a/src/btree_mem_test.c	Fri Oct 19 18:19:39 2012 -0500
+++ b/src/btree_mem_test.c	Fri Oct 19 19:42:17 2012 -0500
@@ -138,6 +138,8 @@
    //   wackify_tree(bt);
    print_tree(bt);
 
+
+   printf("Deleting tree\n");
    int * k;
    char * d;
    for (int key = minkey; key <= maxkey; key++)
@@ -158,9 +160,8 @@
 	 else
 	    free(d);
 	 }
+      }
    print_tree(bt);
-      }
-
    
    btree_mem_delete(bt);