# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1350688779 18000
# Node ID 36018adade6d4ae9bd68c726ef0900896a725bf4
# Parent  e56a76090d8039c6b98fb790fc8b0c700f03b22b
valgrind reporting no memory leaks now.

diff -r e56a76090d80 -r 36018adade6d src/btree_mem.c
--- a/src/btree_mem.c	Fri Oct 19 16:07:18 2012 -0500
+++ b/src/btree_mem.c	Fri Oct 19 18:19:39 2012 -0500
@@ -35,6 +35,7 @@
 
 struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
 
+void                    btree_mem_node_walk_nodes_preorder (struct btree_mem_node * node, void (*f)(struct btree_mem_node *));
 void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
 void                    btree_mem_node_dump           (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
 
@@ -75,6 +76,7 @@
    bt->mindeg = min_degree;
    bt->cmp = cmp;
 
+   printf("Getting new root node\n");
    bt->root = btree_mem_node_new(bt);
    if (NULL == bt->root)
       {
@@ -93,6 +95,8 @@
 btree_mem_delete(struct btree_mem * bt)
    {
    // TODO: walk down the tree and delete all nodes.
+
+   btree_mem_node_walk_nodes_preorder(bt->root, btree_mem_node_delete);
    free(bt);
    }
 
@@ -104,6 +108,7 @@
    if (NULL == node)
       return NULL;
 
+   printf("Allocated node %p\n", node);
    int maxchild = 2*bt->mindeg;
 
    node->key  = malloc( (maxchild - 1) * sizeof(void *));
@@ -150,6 +155,7 @@
 void
 btree_mem_node_delete(struct btree_mem_node * node)
    {
+   printf("Freeing node %p\n", node);
    free(node->child);
    free(node->data);
    free(node->key);
@@ -192,6 +198,7 @@
    // If the root node is full, split it here.
    if ((2 * bt->mindeg - 1) == s->nkeys)
       {
+      printf("Splitting root node.  Allocating new node\n");
       s = btree_mem_node_new(bt);
       if (NULL == s)
 	 return NULL;
@@ -252,6 +259,7 @@
    struct btree_mem_node * y = x->child[i];
 
    // Allocate new node.
+   printf("splitting child allocating new node\n");
    struct btree_mem_node * z = btree_mem_node_new(bt);
    if (NULL == z)
       return NULL;
@@ -294,6 +302,18 @@
 
 ////////////////////////////////////////////////////////////////////////////////
 void
+btree_mem_node_walk_nodes_preorder(struct btree_mem_node * node, void (*f)(struct btree_mem_node *))
+   {
+   if (! node->leaf) 
+      {
+      for (int i = 0; i < node->nkeys; i++)
+	 btree_mem_node_walk_nodes_preorder(node->child[i], f);
+      }
+   f(node);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
 btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void const * const, void *))
    {
    btree_mem_node_walk_inorder(bt->root, f, 0);
@@ -368,7 +388,7 @@
       DEBUG_BLOCK( printf("Freeing the root node\n"); )
       struct btree_mem_node * n = bt->root;
       bt->root = bt->root->child[0];
-      free(n);
+      btree_mem_node_delete(n);
       }
    return data;
    }
@@ -441,6 +461,7 @@
 	    for (int j = i+1; j <= node->nkeys+1; j++)
 	       node->child[j] = node->child[j+1];
 	    btree_mem_node_merge(prev, next);
+	    btree_mem_node_delete(next);
 	    void *kv, *dv;
 	    btree_mem_node_remove(bt, prev, key, &kv, &dv);
 	    return *data_value;
@@ -542,11 +563,14 @@
 	       {
 	       for (int j = i+2; j <= node->nkeys+1; j++)
 		  node->child[j] = node->child[j+1];
+	       btree_mem_node_delete(next);
 	       }
 	    else
 	       {
 	       for (int j = i; j <= node->nkeys+1; j++)
 		  node->child[j] = node->child[j+1];
+	       btree_mem_node_delete(c);
+	       c = prev;
 	       }
 	    }
 	 }
@@ -582,7 +606,7 @@
 btree_mem_node_remove_key(struct btree_mem_node * node, int i)
    {
    void * data = node->key[i];
-   for (int j = i; j < node->nkeys; j++)
+   for (int j = i; j < node->nkeys-1; j++)
       {
       node->key[j]  = node->key[j+1];
       node->data[j] = node->data[j+1];
diff -r e56a76090d80 -r 36018adade6d src/btree_mem.h
--- a/src/btree_mem.h	Fri Oct 19 16:07:18 2012 -0500
+++ b/src/btree_mem.h	Fri Oct 19 18:19:39 2012 -0500
@@ -2,7 +2,7 @@
 #define BTREE_MEM_H_
 
 
-#define DEBUG
+// #define DEBUG
 
 
 struct btree_mem_node;
diff -r e56a76090d80 -r 36018adade6d src/btree_mem_test.c
--- a/src/btree_mem_test.c	Fri Oct 19 16:07:18 2012 -0500
+++ b/src/btree_mem_test.c	Fri Oct 19 18:19:39 2012 -0500
@@ -142,7 +142,6 @@
    char * d;
    for (int key = minkey; key <= maxkey; key++)
       {
-      printf("removing %d\n", key);
       if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
 	 {
 	 printf("not found!\n");
@@ -152,24 +151,18 @@
 	 if (NULL == k)
 	    printf("k is NULL\n");
 	 else
-	    {
-	    printf("freeing k %p\n", k);
 	    free(k);
-	    }
 
 	 if (NULL == d)
 	    printf("d is NULL\n");
 	 else
-	    {
-	    printf("freeing d %p\n", d);
 	    free(d);
-	    }
 	 }
    print_tree(bt);
       }
 
    
-
+   btree_mem_delete(bt);
 
    exit(EXIT_SUCCESS);
    }