1.1 --- a/src/btree_mem.c	Fri Oct 19 16:07:18 2012 -0500
     1.2 +++ b/src/btree_mem.c	Fri Oct 19 18:19:39 2012 -0500
     1.3 @@ -35,6 +35,7 @@
     1.4  
     1.5  struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
     1.6  
     1.7 +void                    btree_mem_node_walk_nodes_preorder (struct btree_mem_node * node, void (*f)(struct btree_mem_node *));
     1.8  void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
     1.9  void                    btree_mem_node_dump           (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
    1.10  
    1.11 @@ -75,6 +76,7 @@
    1.12     bt->mindeg = min_degree;
    1.13     bt->cmp = cmp;
    1.14  
    1.15 +   printf("Getting new root node\n");
    1.16     bt->root = btree_mem_node_new(bt);
    1.17     if (NULL == bt->root)
    1.18        {
    1.19 @@ -93,6 +95,8 @@
    1.20  btree_mem_delete(struct btree_mem * bt)
    1.21     {
    1.22     // TODO: walk down the tree and delete all nodes.
    1.23 +
    1.24 +   btree_mem_node_walk_nodes_preorder(bt->root, btree_mem_node_delete);
    1.25     free(bt);
    1.26     }
    1.27  
    1.28 @@ -104,6 +108,7 @@
    1.29     if (NULL == node)
    1.30        return NULL;
    1.31  
    1.32 +   printf("Allocated node %p\n", node);
    1.33     int maxchild = 2*bt->mindeg;
    1.34  
    1.35     node->key  = malloc( (maxchild - 1) * sizeof(void *));
    1.36 @@ -150,6 +155,7 @@
    1.37  void
    1.38  btree_mem_node_delete(struct btree_mem_node * node)
    1.39     {
    1.40 +   printf("Freeing node %p\n", node);
    1.41     free(node->child);
    1.42     free(node->data);
    1.43     free(node->key);
    1.44 @@ -192,6 +198,7 @@
    1.45     // If the root node is full, split it here.
    1.46     if ((2 * bt->mindeg - 1) == s->nkeys)
    1.47        {
    1.48 +      printf("Splitting root node.  Allocating new node\n");
    1.49        s = btree_mem_node_new(bt);
    1.50        if (NULL == s)
    1.51  	 return NULL;
    1.52 @@ -252,6 +259,7 @@
    1.53     struct btree_mem_node * y = x->child[i];
    1.54  
    1.55     // Allocate new node.
    1.56 +   printf("splitting child allocating new node\n");
    1.57     struct btree_mem_node * z = btree_mem_node_new(bt);
    1.58     if (NULL == z)
    1.59        return NULL;
    1.60 @@ -294,6 +302,18 @@
    1.61  
    1.62  ////////////////////////////////////////////////////////////////////////////////
    1.63  void
    1.64 +btree_mem_node_walk_nodes_preorder(struct btree_mem_node * node, void (*f)(struct btree_mem_node *))
    1.65 +   {
    1.66 +   if (! node->leaf) 
    1.67 +      {
    1.68 +      for (int i = 0; i < node->nkeys; i++)
    1.69 +	 btree_mem_node_walk_nodes_preorder(node->child[i], f);
    1.70 +      }
    1.71 +   f(node);
    1.72 +   }
    1.73 +
    1.74 +////////////////////////////////////////////////////////////////////////////////
    1.75 +void
    1.76  btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void const * const, void *))
    1.77     {
    1.78     btree_mem_node_walk_inorder(bt->root, f, 0);
    1.79 @@ -368,7 +388,7 @@
    1.80        DEBUG_BLOCK( printf("Freeing the root node\n"); )
    1.81        struct btree_mem_node * n = bt->root;
    1.82        bt->root = bt->root->child[0];
    1.83 -      free(n);
    1.84 +      btree_mem_node_delete(n);
    1.85        }
    1.86     return data;
    1.87     }
    1.88 @@ -441,6 +461,7 @@
    1.89  	    for (int j = i+1; j <= node->nkeys+1; j++)
    1.90  	       node->child[j] = node->child[j+1];
    1.91  	    btree_mem_node_merge(prev, next);
    1.92 +	    btree_mem_node_delete(next);
    1.93  	    void *kv, *dv;
    1.94  	    btree_mem_node_remove(bt, prev, key, &kv, &dv);
    1.95  	    return *data_value;
    1.96 @@ -542,11 +563,14 @@
    1.97  	       {
    1.98  	       for (int j = i+2; j <= node->nkeys+1; j++)
    1.99  		  node->child[j] = node->child[j+1];
   1.100 +	       btree_mem_node_delete(next);
   1.101  	       }
   1.102  	    else
   1.103  	       {
   1.104  	       for (int j = i; j <= node->nkeys+1; j++)
   1.105  		  node->child[j] = node->child[j+1];
   1.106 +	       btree_mem_node_delete(c);
   1.107 +	       c = prev;
   1.108  	       }
   1.109  	    }
   1.110  	 }
   1.111 @@ -582,7 +606,7 @@
   1.112  btree_mem_node_remove_key(struct btree_mem_node * node, int i)
   1.113     {
   1.114     void * data = node->key[i];
   1.115 -   for (int j = i; j < node->nkeys; j++)
   1.116 +   for (int j = i; j < node->nkeys-1; j++)
   1.117        {
   1.118        node->key[j]  = node->key[j+1];
   1.119        node->data[j] = node->data[j+1];

     2.1 --- a/src/btree_mem.h	Fri Oct 19 16:07:18 2012 -0500
     2.2 +++ b/src/btree_mem.h	Fri Oct 19 18:19:39 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;

     3.1 --- a/src/btree_mem_test.c	Fri Oct 19 16:07:18 2012 -0500
     3.2 +++ b/src/btree_mem_test.c	Fri Oct 19 18:19:39 2012 -0500
     3.3 @@ -142,7 +142,6 @@
     3.4     char * d;
     3.5     for (int key = minkey; key <= maxkey; key++)
     3.6        {
     3.7 -      printf("removing %d\n", key);
     3.8        if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
     3.9  	 {
    3.10  	 printf("not found!\n");
    3.11 @@ -152,24 +151,18 @@
    3.12  	 if (NULL == k)
    3.13  	    printf("k is NULL\n");
    3.14  	 else
    3.15 -	    {
    3.16 -	    printf("freeing k %p\n", k);
    3.17  	    free(k);
    3.18 -	    }
    3.19  
    3.20  	 if (NULL == d)
    3.21  	    printf("d is NULL\n");
    3.22  	 else
    3.23 -	    {
    3.24 -	    printf("freeing d %p\n", d);
    3.25  	    free(d);
    3.26 -	    }
    3.27  	 }
    3.28     print_tree(bt);
    3.29        }
    3.30  
    3.31     
    3.32 -
    3.33 +   btree_mem_delete(bt);
    3.34  
    3.35     exit(EXIT_SUCCESS);
    3.36     }