1.1 --- a/src/btree_mem.c	Thu Oct 18 01:04:17 2012 -0500
     1.2 +++ b/src/btree_mem.c	Thu Oct 18 20:08:51 2012 -0500
     1.3 @@ -36,19 +36,34 @@
     1.4  struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
     1.5  
     1.6  void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
     1.7 +void                    btree_mem_node_dump           (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
     1.8  
     1.9 -void *                  btree_mem_node_remove         (struct btree_mem * bt, struct btree_mem_node * node, void * key);
    1.10 +void *                  btree_mem_node_remove         (struct btree_mem * bt, struct btree_mem_node * node, void * key, 
    1.11 +						       void ** key_value, void ** data_value);
    1.12 +
    1.13 +void                    btree_mem_node_add_key        (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
    1.14  void *                  btree_mem_node_remove_key     (struct btree_mem_node * node, int i);
    1.15  void *                  btree_mem_node_first_key      (struct btree_mem_node * node);
    1.16  void *                  btree_mem_node_last_key       (struct btree_mem_node * node);
    1.17 -
    1.18 +void                    btree_mem_node_merge          (struct btree_mem_node * a, struct btree_mem_node * b);
    1.19  
    1.20  #ifdef DEBUG
    1.21  #define DEBUG_BLOCK(x) x
    1.22 +
    1.23 +void btree_mem_nonde_print_keys(struct btree_mem_node * node);
    1.24 +
    1.25  #else
    1.26  #define DEBUG_BLOCK(x)
    1.27  #endif
    1.28  
    1.29 +void printit(int h, void * k, void * d)
    1.30 +   {
    1.31 +   for (int i = 0; i < h; i++)
    1.32 +      printf("\t");
    1.33 +   printf("%d %s\n", *((int*)k), (char *) d);
    1.34 +   }
    1.35 +
    1.36 +
    1.37  ////////////////////////////////////////////////////////////////////////////////
    1.38  struct btree_mem *
    1.39  btree_mem_new(int min_degree, int (*cmp)(void *, void *))
    1.40 @@ -307,14 +322,50 @@
    1.41     }
    1.42  
    1.43  ////////////////////////////////////////////////////////////////////////////////
    1.44 +void
    1.45 +btree_mem_dump(struct btree_mem * bt, void (*f)(int, void const * const, void *))
    1.46 +   {
    1.47 +   btree_mem_node_dump(bt->root, f, 0);
    1.48 +   }
    1.49 +
    1.50 +////////////////////////////////////////////////////////////////////////////////
    1.51 +void
    1.52 +btree_mem_node_dump(struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth)
    1.53 +   {
    1.54 +
    1.55 +   if (0 == node->nkeys)
    1.56 +      {
    1.57 +      if (NULL != node->child[0])
    1.58 +	 btree_mem_node_dump(node->child[0], f, depth+1);
    1.59 +      return;
    1.60 +      }
    1.61 +
    1.62 +   for (int i = 0; i < node->nkeys; i++)
    1.63 +      {
    1.64 +      if (! node->leaf) 
    1.65 +	 btree_mem_node_dump(node->child[i], f, depth+1);
    1.66 +      printf("node: %p nkeys %10d \t", node, node->nkeys);
    1.67 +      f(depth, node->key[i], node->data[i]);
    1.68 +      }
    1.69 +   if (! node->leaf) 
    1.70 +      btree_mem_node_dump(node->child[node->nkeys], f, depth+1);
    1.71 +   }
    1.72 +
    1.73 +////////////////////////////////////////////////////////////////////////////////
    1.74  void *
    1.75 -btree_mem_remove(struct btree_mem * bt, void * key)
    1.76 +btree_mem_remove(struct btree_mem * bt, void * key, void ** key_value, void ** data_value)
    1.77     {
    1.78 -   void * data = btree_mem_node_remove(bt, bt->root, key);
    1.79 +   if ( (NULL == bt) || (NULL == key) || (NULL == key_value) || (NULL == data_value) )
    1.80 +      return NULL;
    1.81 +
    1.82 +   DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); )
    1.83 +   void * data = btree_mem_node_remove(bt, bt->root, key, key_value, data_value);
    1.84     if (NULL == data)
    1.85        return NULL;
    1.86 +
    1.87     if (0 == bt->root->nkeys)
    1.88        {
    1.89 +      DEBUG_BLOCK( printf("Freeing the root node\n"); )
    1.90        struct btree_mem_node * n = bt->root;
    1.91        bt->root = bt->root->child[0];
    1.92        free(n);
    1.93 @@ -326,9 +377,11 @@
    1.94  // Assumption: node has bt->mindeg keys or is the root.
    1.95  
    1.96  void *
    1.97 -btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key)
    1.98 +btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key, void ** key_value, void ** data_value)
    1.99     {
   1.100 -#ifdef NOTHING
   1.101 +
   1.102 +   DEBUG_BLOCK( btree_mem_node_print_keys(node); )
   1.103 +
   1.104     int i = node->nkeys - 1;
   1.105     while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
   1.106        i--;
   1.107 @@ -336,10 +389,15 @@
   1.108     if ( (i >= 0) && (bt->cmp(key, node->key[i]) == 0) )
   1.109        {
   1.110        // key is in node at key[i]
   1.111 +      *key_value = node->key[i];
   1.112 +      *data_value = node->data[i];
   1.113 +      //      printf("Will return key_value %p (%d)   data_value %p (%s)\n", *key_value, *((int*)(*key_value)), (char*)(*data_value));
   1.114        if (node->leaf)
   1.115  	 {
   1.116 -	 // Cormen: case 1
   1.117 -	 return btree_mem_node_remove_key(node, i);
   1.118 +	 // case 1
   1.119 +	 DEBUG_BLOCK( printf("remove: case 1\n"); )
   1.120 +	 btree_mem_node_remove_key(node, i);
   1.121 +	 return *data_value;
   1.122  	 }
   1.123        else
   1.124  	 {
   1.125 @@ -350,62 +408,214 @@
   1.126  	 //    (child next that follows  key in node has at least bt->mindeg keys)
   1.127  	 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )
   1.128  	    {
   1.129 +	    void * kp;
   1.130  	    if (prev->nkeys >= bt->mindeg)
   1.131  	       {
   1.132 -	       // Cormen: case 2a
   1.133 -	       void * kp = btree_mem_node_last_key(prev);
   1.134 +	       // case 2a
   1.135 +	       DEBUG_BLOCK( printf("remove: case 2a\n"); )
   1.136 +	       kp = btree_mem_node_last_key(prev);
   1.137 +	       //	       printf("remove: kp %d\n", *((int*)kp)); 
   1.138 +	       node->data[i] = btree_mem_node_remove(bt, prev, kp, key_value, data_value);
   1.139  	       }
   1.140  	    else
   1.141  	       {
   1.142 -	       // Cormen: case 2b	
   1.143 -	       void * kp = btree_mem_node_first_key(prev);
   1.144 +	       // case 2b
   1.145 +	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
   1.146 +	       kp = btree_mem_node_first_key(next);
   1.147 +	       //	       printf("remove: kp %d\n", *((int*)kp)); 
   1.148 +	       node->data[i] = btree_mem_node_remove(bt, next, kp, key_value, data_value);
   1.149  	       }
   1.150 -	    void * kp_data = btree_mem_node_remove(bt, y, kp);
   1.151 -	    void * data = node->data[i];
   1.152 +	    //	    printf("i %d\n", i);
   1.153 +	    //	       printf("remove: kp %d\n", *((int*)kp)); 
   1.154  	    node->key[i] = kp;
   1.155 -	    node->data[i] = kp_data;
   1.156 -	    return data;
   1.157 +	    //	    	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
   1.158 +	    //		    printf("returning %p\n", *data_value);
   1.159 +	    return *data_value;
   1.160  	    }
   1.161  	 else
   1.162  	    {
   1.163 -	    // Cormen: case 2c
   1.164 +	    // case 2c
   1.165 +	    DEBUG_BLOCK( printf("remove: case 2c\n"); )
   1.166 +	    btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]);
   1.167 +	    btree_mem_node_remove_key(node, i);	
   1.168 +	    btree_mem_node_merge(prev, next);
   1.169 +	    return *data_value;
   1.170  	    }
   1.171  	 }
   1.172        }
   1.173     else
   1.174        {
   1.175 +      if (node->leaf)
   1.176 +	 {
   1.177 +	 DEBUG_BLOCK( printf("remove: key not found\n"); )
   1.178 +	 return NULL;
   1.179 +	 }
   1.180 +
   1.181        // key is in child[i+1], if anywhere
   1.182 +      struct btree_mem_node * c = node->child[i+1];
   1.183 +
   1.184 +      DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); )
   1.185        if (c->nkeys == bt->mindeg - 1)
   1.186  	 {
   1.187 -	 if ()
   1.188 +	 struct btree_mem_node * prev = NULL;
   1.189 +	 if (i >= 0)
   1.190 +	    prev = node->child[i];
   1.191 +
   1.192 +	 struct btree_mem_node * next = NULL;
   1.193 +	 if (i+2 <= node->nkeys)
   1.194 +	    next = node->child[i+2];
   1.195 +
   1.196 +	 DEBUG_BLOCK( printf("remove: prev %p  next %p\n", prev, next); )
   1.197 +
   1.198 +	 if ( (prev) && (prev->nkeys >= bt->mindeg) )
   1.199  	    {
   1.200 -	    // Cormen: case 3a
   1.201 +	    // case 3a (with prev sibling)
   1.202 +	    // Move node->key[i] into c->key[0] shifting over existing keys
   1.203 +	    // Move prev->key[prev->nkeys-1] into node->key[i]
   1.204 +	    // if (prev->leaf)
   1.205 +	    //     move prev->child[prev->nkeys] into c->child[0] shifting over existing children
   1.206 +	    // prev->nkeys--;
   1.207 +	    
   1.208 +	    DEBUG_BLOCK( printf("remove: case 3a.1\n"); )
   1.209 +
   1.210 +	    btree_mem_node_add_key(bt, c, node->key[i-1], node->data[i-1]);
   1.211 +
   1.212 +	    node->key[i-1]  = prev->key[prev->nkeys-1];
   1.213 +	    node->data[i-1] = prev->data[prev->nkeys-1];
   1.214 +
   1.215 +	    if (prev->leaf)
   1.216 +	       {
   1.217 +	       for (int j = c->nkeys; j >= 0; j--)
   1.218 +		  c->child[j+1] = c->child[j];
   1.219 +	       c->child[0] = prev->child[prev->nkeys];
   1.220 +	       }
   1.221 +
   1.222 +	    prev->nkeys--;
   1.223 +	    }
   1.224 +	 else if ( (next) && (next->nkeys >= bt->mindeg) )
   1.225 +	    {
   1.226 +	    // case 3a (with next sibling)
   1.227 +	    // Symmetric with the above
   1.228 +
   1.229 +	    DEBUG_BLOCK( printf("remove: case 3a.2\n"); )
   1.230 +	    btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]);
   1.231 +
   1.232 +	    //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
   1.233 +
   1.234 +	    node->key[i+1]  = next->key[0];
   1.235 +	    node->data[i+1] = next->data[0];
   1.236 +	    for (int j = 0; j < next->nkeys - 1; j++)
   1.237 +	       {
   1.238 +	       next->key[j]  = next->key[j+1];
   1.239 +	       next->data[j] = next->data[j+1];
   1.240 +	       }
   1.241 +
   1.242 +	    if (next->leaf)
   1.243 +	       {
   1.244 +	       c->child[c->nkeys] = next->child[0];
   1.245 +	       for (int j = 0; j < next->nkeys; j++)
   1.246 +		  next->child[j] = next->child[j+1];
   1.247 +	       }
   1.248 +
   1.249 +	    next->nkeys--;
   1.250 +
   1.251  	    }
   1.252  	 else
   1.253  	    {
   1.254 -	    // Cormen: case 3b
   1.255 +	    // case 3b
   1.256 +	    DEBUG_BLOCK( printf("remove: case 3b\n"); )
   1.257 +		  //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
   1.258 +		  //	    printf("node %p  i %d\n", node, i); fflush(stdout);
   1.259 +		  //	    printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev));	    fflush(stdout);
   1.260 +	    btree_mem_node_add_key(bt, (next ? next : prev), node->key[i+1], node->data[i+1]);
   1.261 +	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
   1.262 +
   1.263 +	    if (next)
   1.264 +	       {
   1.265 +	       //	       printf("here\n");
   1.266 +	       btree_mem_node_merge(c, next);
   1.267 +	       }
   1.268 +	    else
   1.269 +	       {
   1.270 +	       //	       printf("there\n");
   1.271 +	       btree_mem_node_merge(prev, c);
   1.272 +	       }
   1.273 +
   1.274 +	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
   1.275 +
   1.276 +	    btree_mem_node_remove_key(node, i+1);
   1.277 +
   1.278 +	    if (next)
   1.279 +	       {
   1.280 +	       for (int j = i+2; j <= node->nkeys+1; j++)
   1.281 +		  node->child[j] = node->child[j+1];
   1.282 +	       }
   1.283 +	    else
   1.284 +	       {
   1.285 +	       for (int j = i; j <= node->nkeys+1; j++)
   1.286 +		  node->child[j] = node->child[j+1];
   1.287 +	       }
   1.288 +
   1.289 +	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
   1.290  	    }
   1.291  	 }
   1.292 -      return btree_mem_node_remove(bt, c, key);
   1.293 +      return btree_mem_node_remove(bt, c, key, key_value, data_value);
   1.294        }
   1.295 -#endif
   1.296     }
   1.297  
   1.298  ////////////////////////////////////////////////////////////////////////////////
   1.299 +// Assumption: node is not full
   1.300 +// Assumption: key is not already in node
   1.301 +void
   1.302 +btree_mem_node_add_key(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
   1.303 +   {
   1.304 +   int i = node->nkeys;
   1.305 +   while ( (i > 0) && (bt->cmp(key, node->key[i-1]) < 0) )
   1.306 +      i--;
   1.307 +
   1.308 +   for (int j = node->nkeys - 1; j >= i; j--)
   1.309 +      {
   1.310 +      node->key[j+1] = node->key[j];
   1.311 +      node->data[j+1] = node->data[j];
   1.312 +      }
   1.313 +
   1.314 +   node->key[i] = key;
   1.315 +   node->data[i] = data;
   1.316 +   node->nkeys++;
   1.317 +   }
   1.318 +
   1.319 +////////////////////////////////////////////////////////////////////////////////
   1.320 +// Assumption: node has at least mindeg keys.
   1.321 +// Does not remove any children.
   1.322  void *
   1.323  btree_mem_node_remove_key(struct btree_mem_node * node, int i)
   1.324     {
   1.325     void * data = node->key[i];
   1.326 -   for (int j = node->nkeys - 1; j > i; j--)
   1.327 +   for (int j = i; j < node->nkeys; j++)
   1.328        {
   1.329 -      node->key[j-1]  = node->key[j];
   1.330 -      node->data[j-1] = node->data[j];
   1.331 +      node->key[j]  = node->key[j+1];
   1.332 +      node->data[j] = node->data[j+1];
   1.333        }
   1.334     node->nkeys--;
   1.335     return data;
   1.336     }
   1.337  
   1.338  ////////////////////////////////////////////////////////////////////////////////
   1.339 +// Return the lowest valued key of the subtree rooted at node
   1.340 +void *
   1.341 +btree_mem_node_first_key(struct btree_mem_node * node)
   1.342 +   {
   1.343 +   if (0 == node->nkeys)
   1.344 +      return NULL;
   1.345 +
   1.346 +   if (node->leaf)
   1.347 +      return node->key[0];
   1.348 +
   1.349 +   return btree_mem_node_last_key(node->child[0]);
   1.350 +   }
   1.351 +
   1.352 +////////////////////////////////////////////////////////////////////////////////
   1.353 +// Return the highest valued key of the subtree rooted at node
   1.354  void *
   1.355  btree_mem_node_last_key(struct btree_mem_node * node)
   1.356     {
   1.357 @@ -418,15 +628,34 @@
   1.358     return btree_mem_node_last_key(node->child[node->nkeys]);
   1.359     }
   1.360  
   1.361 -////////////////////////////////////////////////////////////////////////////////
   1.362 -void *
   1.363 -btree_mem_node_first_key(struct btree_mem_node * node)
   1.364 +/////////////////////////////////////////////////////////////////////////////////
   1.365 +// move all keys/data from node b into node a
   1.366 +// Assumption: all keys in b come after the keys in a
   1.367 +void
   1.368 +btree_mem_node_merge(struct btree_mem_node * a, struct btree_mem_node * b)
   1.369     {
   1.370 -   if (0 == node->nkeys)
   1.371 -      return NULL;
   1.372  
   1.373 -   if (node->leaf)
   1.374 -      return node->key[0];
   1.375 +   DEBUG_BLOCK( printf("merging %p with %p\n", a, b); )
   1.376 +   int i = a->nkeys;
   1.377 +   int j = 0;
   1.378 +   for (;  j < b->nkeys; i++, j++)
   1.379 +      {
   1.380 +      a->key[i] = b->key[j];
   1.381 +      a->data[i] = b->data[j];
   1.382 +      }
   1.383 +   a->nkeys += b->nkeys;
   1.384 +   b->nkeys = 0;
   1.385 +   }
   1.386  
   1.387 -   return btree_mem_node_last_key(node->child[0]);
   1.388 +/////////////////////////////////////////////////////////////////////////////////
   1.389 +#ifdef DEBUG
   1.390 +void
   1.391 +btree_mem_node_print_keys(struct btree_mem_node * node)
   1.392 +   {
   1.393 +   printf("node: %p nkeys %10d keys: ", node, node->nkeys);
   1.394 +   for (int i = 0; i < node->nkeys; i++)
   1.395 +      printf("%d ", *((int *) node->key[i]));
   1.396 +   printf("\n");
   1.397     }
   1.398 +#endif
   1.399 +

     2.1 --- a/src/btree_mem.h	Thu Oct 18 01:04:17 2012 -0500
     2.2 +++ b/src/btree_mem.h	Thu Oct 18 20:08:51 2012 -0500
     2.3 @@ -2,7 +2,7 @@
     2.4  #define BTREE_MEM_H_
     2.5  
     2.6  
     2.7 -// #define DEBUG
     2.8 +#define DEBUG
     2.9  
    2.10  
    2.11  struct btree_mem_node;
    2.12 @@ -16,7 +16,7 @@
    2.13  
    2.14  void *             btree_mem_insert       (struct btree_mem * bt, void * key, void * data);
    2.15  void *             btree_mem_find         (struct btree_mem * bt, void * key);
    2.16 -void *             btree_mem_remove       (struct btree_mem * bt, void * key);
    2.17 +void *             btree_mem_remove       (struct btree_mem * bt, void * key, void ** key_value, void ** data_value);
    2.18  
    2.19  // Walk the tree in key order, starting with the lowest, and apply the function f to each one.  The argumemnts to f are
    2.20  // int depth in the tree, the pointer to the key, and the pointer to the data. Note that the key cannot be modified,
    2.21 @@ -26,4 +26,9 @@
    2.22  // remove and insert.
    2.23  void               btree_mem_walk_inorder (struct btree_mem * bt, void (*f)(int, void const * const, void * const));
    2.24  
    2.25 +#ifdef DEBUG
    2.26 +// btree_mem_dump takes a pointer to a function that prints a represenation of the keya nd data to the stdout.
    2.27 +void               btree_mem_dump         (struct btree_mem * bt, void (*f)(int, void const * const, void * const));
    2.28  #endif
    2.29 +
    2.30 +#endif

     3.1 --- a/src/btree_mem_test.c	Thu Oct 18 01:04:17 2012 -0500
     3.2 +++ b/src/btree_mem_test.c	Thu Oct 18 20:08:51 2012 -0500
     3.3 @@ -6,7 +6,7 @@
     3.4  #include "btree_mem.h"
     3.5  
     3.6  
     3.7 -#define MIN_DEGREE 3
     3.8 +#define MIN_DEGREE 2
     3.9  #define MAX_LINE 1024
    3.10  
    3.11  #ifdef DEBUG
    3.12 @@ -56,7 +56,7 @@
    3.13  print_tree(struct btree_mem * bt)
    3.14     {
    3.15     printf("==================================\n");
    3.16 -   btree_mem_walk_inorder(bt, print_data);
    3.17 +   btree_mem_dump(bt, print_data);
    3.18     printf("==================================\n");
    3.19     }
    3.20  
    3.21 @@ -130,5 +130,28 @@
    3.22     //   wackify_tree(bt);
    3.23     print_tree(bt);
    3.24  
    3.25 +   int * k;
    3.26 +   char * d;
    3.27 +   int key = 5;
    3.28 +   printf("removing %d\n", key);
    3.29 +   if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
    3.30 +      {
    3.31 +      printf("not found!\n");
    3.32 +      }
    3.33 +   else
    3.34 +      {
    3.35 +      if (NULL == k)
    3.36 +	 printf("k is NULL\n");
    3.37 +      else
    3.38 +	 free(k);
    3.39 +
    3.40 +      if (NULL == d)
    3.41 +	 printf("d is NULL\n");
    3.42 +      else
    3.43 +	 free(d);
    3.44 +      }
    3.45 +   print_tree(bt);
    3.46 +
    3.47 +
    3.48     exit(EXIT_SUCCESS);
    3.49     }