1.1 --- a/src/btree_mem.c	Thu Oct 18 20:08:51 2012 -0500
     1.2 +++ b/src/btree_mem.c	Fri Oct 19 00:10:34 2012 -0500
     1.3 @@ -50,7 +50,7 @@
     1.4  #ifdef DEBUG
     1.5  #define DEBUG_BLOCK(x) x
     1.6  
     1.7 -void btree_mem_nonde_print_keys(struct btree_mem_node * node);
     1.8 +void btree_mem_node_print_keys(struct btree_mem_node * node);
     1.9  
    1.10  #else
    1.11  #define DEBUG_BLOCK(x)
    1.12 @@ -363,7 +363,7 @@
    1.13     if (NULL == data)
    1.14        return NULL;
    1.15  
    1.16 -   if (0 == bt->root->nkeys)
    1.17 +   if ( (0 == bt->root->nkeys) && (bt->root->child[0]) )
    1.18        {
    1.19        DEBUG_BLOCK( printf("Freeing the root node\n"); )
    1.20        struct btree_mem_node * n = bt->root;
    1.21 @@ -391,7 +391,7 @@
    1.22        // key is in node at key[i]
    1.23        *key_value = node->key[i];
    1.24        *data_value = node->data[i];
    1.25 -      //      printf("Will return key_value %p (%d)   data_value %p (%s)\n", *key_value, *((int*)(*key_value)), (char*)(*data_value));
    1.26 +      //      printf("Will return key_value %p (%d)   data_value %p (%s)\n", *key_value, *((int*)(*key_value)), *data_value, (char*)(*data_value));
    1.27        if (node->leaf)
    1.28  	 {
    1.29  	 // case 1
    1.30 @@ -414,22 +414,18 @@
    1.31  	       // case 2a
    1.32  	       DEBUG_BLOCK( printf("remove: case 2a\n"); )
    1.33  	       kp = btree_mem_node_last_key(prev);
    1.34 -	       //	       printf("remove: kp %d\n", *((int*)kp)); 
    1.35 -	       node->data[i] = btree_mem_node_remove(bt, prev, kp, key_value, data_value);
    1.36 +	       void *kv, *dv;
    1.37 +	       node->data[i] = btree_mem_node_remove(bt, prev, kp, kv, dv);
    1.38  	       }
    1.39  	    else
    1.40  	       {
    1.41  	       // case 2b
    1.42  	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
    1.43  	       kp = btree_mem_node_first_key(next);
    1.44 -	       //	       printf("remove: kp %d\n", *((int*)kp)); 
    1.45 -	       node->data[i] = btree_mem_node_remove(bt, next, kp, key_value, data_value);
    1.46 +	       void *kv, *dv;
    1.47 +	       node->data[i] = btree_mem_node_remove(bt, next, kp, kv, dv);
    1.48  	       }
    1.49 -	    //	    printf("i %d\n", i);
    1.50 -	    //	       printf("remove: kp %d\n", *((int*)kp)); 
    1.51  	    node->key[i] = kp;
    1.52 -	    //	    	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
    1.53 -	    //		    printf("returning %p\n", *data_value);
    1.54  	    return *data_value;
    1.55  	    }
    1.56  	 else
    1.57 @@ -438,7 +434,11 @@
    1.58  	    DEBUG_BLOCK( printf("remove: case 2c\n"); )
    1.59  	    btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]);
    1.60  	    btree_mem_node_remove_key(node, i);	
    1.61 +	    for (int j = i+1; j <= node->nkeys+1; j++)
    1.62 +	       node->child[j] = node->child[j+1];
    1.63  	    btree_mem_node_merge(prev, next);
    1.64 +	    void *kv, *dv;
    1.65 +	    btree_mem_node_remove(bt, prev, key, &kv, &dv);
    1.66  	    return *data_value;
    1.67  	    }
    1.68  	 }
    1.69 @@ -500,8 +500,6 @@
    1.70  	    DEBUG_BLOCK( printf("remove: case 3a.2\n"); )
    1.71  	    btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]);
    1.72  
    1.73 -	    //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
    1.74 -
    1.75  	    node->key[i+1]  = next->key[0];
    1.76  	    node->data[i+1] = next->data[0];
    1.77  	    for (int j = 0; j < next->nkeys - 1; j++)
    1.78 @@ -528,20 +526,12 @@
    1.79  		  //	    printf("node %p  i %d\n", node, i); fflush(stdout);
    1.80  		  //	    printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev));	    fflush(stdout);
    1.81  	    btree_mem_node_add_key(bt, (next ? next : prev), node->key[i+1], node->data[i+1]);
    1.82 -	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
    1.83  
    1.84  	    if (next)
    1.85 -	       {
    1.86 -	       //	       printf("here\n");
    1.87  	       btree_mem_node_merge(c, next);
    1.88 -	       }
    1.89  	    else
    1.90 -	       {
    1.91 -	       //	       printf("there\n");
    1.92  	       btree_mem_node_merge(prev, c);
    1.93 -	       }
    1.94  
    1.95 -	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
    1.96  
    1.97  	    btree_mem_node_remove_key(node, i+1);
    1.98  
    1.99 @@ -555,8 +545,6 @@
   1.100  	       for (int j = i; j <= node->nkeys+1; j++)
   1.101  		  node->child[j] = node->child[j+1];
   1.102  	       }
   1.103 -
   1.104 -	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
   1.105  	    }
   1.106  	 }
   1.107        return btree_mem_node_remove(bt, c, key, key_value, data_value);
   1.108 @@ -629,13 +617,11 @@
   1.109     }
   1.110  
   1.111  /////////////////////////////////////////////////////////////////////////////////
   1.112 -// move all keys/data from node b into node a
   1.113 +// move all keys/data/children from node b into node a
   1.114  // Assumption: all keys in b come after the keys in a
   1.115  void
   1.116  btree_mem_node_merge(struct btree_mem_node * a, struct btree_mem_node * b)
   1.117     {
   1.118 -
   1.119 -   DEBUG_BLOCK( printf("merging %p with %p\n", a, b); )
   1.120     int i = a->nkeys;
   1.121     int j = 0;
   1.122     for (;  j < b->nkeys; i++, j++)
   1.123 @@ -643,6 +629,13 @@
   1.124        a->key[i] = b->key[j];
   1.125        a->data[i] = b->data[j];
   1.126        }
   1.127 +
   1.128 +   if (! a->leaf)
   1.129 +      {
   1.130 +      for (i = a->nkeys + 1 , j = 0; j <= b->nkeys; i++, j++)
   1.131 +	 a->child[i] = b->child[j];
   1.132 +      }
   1.133 +
   1.134     a->nkeys += b->nkeys;
   1.135     b->nkeys = 0;
   1.136     }

     2.1 --- a/src/btree_mem_test.c	Thu Oct 18 20:08:51 2012 -0500
     2.2 +++ b/src/btree_mem_test.c	Fri Oct 19 00:10:34 2012 -0500
     2.3 @@ -1,7 +1,7 @@
     2.4  #include <stdio.h>
     2.5  #include <stdlib.h>
     2.6  #include <string.h>
     2.7 -
     2.8 +#include <limits.h>
     2.9  
    2.10  #include "btree_mem.h"
    2.11  
    2.12 @@ -100,7 +100,9 @@
    2.13        exit(EXIT_FAILURE);
    2.14        }
    2.15  
    2.16 -   DEBUG_BLOCK( print_tree(bt); )
    2.17 +   DEBUG_BLOCK( print_tree(bt); );
    2.18 +   int minkey = INT_MAX;
    2.19 +   int maxkey = INT_MIN;
    2.20     int i;
    2.21     char s[MAX_LINE+1];
    2.22     while (1 == scanf("%d ", &i))
    2.23 @@ -120,6 +122,12 @@
    2.24  	 }
    2.25        s[strlen(s)-1] = '\0';
    2.26        char * data = (s == NULL) ? NULL : strdup(s);
    2.27 +
    2.28 +
    2.29 +      if (*ip < minkey) minkey = *ip;
    2.30 +      if (*ip > maxkey) maxkey = *ip;
    2.31 +
    2.32 +      printf("Inserting k %p, d %p\n", ip, data);
    2.33        if (NULL == btree_mem_insert(bt, ip, data))
    2.34  	 {
    2.35  	 fprintf(stderr, "btree_mem_insert failed\n");
    2.36 @@ -132,25 +140,35 @@
    2.37  
    2.38     int * k;
    2.39     char * d;
    2.40 -   int key = 5;
    2.41 -   printf("removing %d\n", key);
    2.42 -   if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
    2.43 +   for (int key = minkey; key <= maxkey; key++)
    2.44        {
    2.45 -      printf("not found!\n");
    2.46 +      printf("removing %d\n", key);
    2.47 +      if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
    2.48 +	 {
    2.49 +	 printf("not found!\n");
    2.50 +	 }
    2.51 +      else
    2.52 +	 {
    2.53 +	 if (NULL == k)
    2.54 +	    printf("k is NULL\n");
    2.55 +	 else
    2.56 +	    {
    2.57 +	    printf("freeing k %p\n", k);
    2.58 +	    free(k);
    2.59 +	    }
    2.60 +
    2.61 +	 if (NULL == d)
    2.62 +	    printf("d is NULL\n");
    2.63 +	 else
    2.64 +	    {
    2.65 +	    printf("freeing d %p\n", d);
    2.66 +	    free(d);
    2.67 +	    }
    2.68 +	 }
    2.69 +   print_tree(bt);
    2.70        }
    2.71 -   else
    2.72 -      {
    2.73 -      if (NULL == k)
    2.74 -	 printf("k is NULL\n");
    2.75 -      else
    2.76 -	 free(k);
    2.77  
    2.78 -      if (NULL == d)
    2.79 -	 printf("d is NULL\n");
    2.80 -      else
    2.81 -	 free(d);
    2.82 -      }
    2.83 -   print_tree(bt);
    2.84 +   
    2.85  
    2.86  
    2.87     exit(EXIT_SUCCESS);