# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1350680838 18000
# Node ID e56a76090d8039c6b98fb790fc8b0c700f03b22b
# Parent  ce502d2caaea5520314d8ba935f53bc801e8c896
Deletion seems to be working.  Still need to clean up memory usage, though.

diff -r ce502d2caaea -r e56a76090d80 src/btree_mem.c
--- a/src/btree_mem.c	Fri Oct 19 00:10:34 2012 -0500
+++ b/src/btree_mem.c	Fri Oct 19 16:07:18 2012 -0500
@@ -43,8 +43,8 @@
 
 void                    btree_mem_node_add_key        (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
 void *                  btree_mem_node_remove_key     (struct btree_mem_node * node, int i);
-void *                  btree_mem_node_first_key      (struct btree_mem_node * node);
-void *                  btree_mem_node_last_key       (struct btree_mem_node * node);
+struct btree_mem_node * btree_mem_node_find_prev      (struct btree_mem_node * node);
+struct btree_mem_node * btree_mem_node_find_next      (struct btree_mem_node * node);
 void                    btree_mem_node_merge          (struct btree_mem_node * a, struct btree_mem_node * b);
 
 #ifdef DEBUG
@@ -408,22 +408,26 @@
 	 //    (child next that follows  key in node has at least bt->mindeg keys)
 	 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )
 	    {
-	    void * kp;
+	    struct btree_mem_node * kp;
 	    if (prev->nkeys >= bt->mindeg)
 	       {
 	       // case 2a
-	       DEBUG_BLOCK( printf("remove: case 2a\n"); )
-	       kp = btree_mem_node_last_key(prev);
+	       DEBUG_BLOCK( printf("remove: case 2a\n"); );
+	       kp = btree_mem_node_find_prev(prev);
+	       node->key[i]  = kp->key[kp->nkeys-1];
+	       node->data[i] = kp->data[kp->nkeys];
 	       void *kv, *dv;
-	       node->data[i] = btree_mem_node_remove(bt, prev, kp, kv, dv);
+	       node->data[i] = btree_mem_node_remove(bt, prev, kp->key[kp->nkeys-1], kv, dv);
 	       }
 	    else
 	       {
 	       // case 2b
 	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
-	       kp = btree_mem_node_first_key(next);
+	       kp = btree_mem_node_find_next(next);
+	       node->key[i]  = kp->key[0];
+	       node->data[i] = kp->data[0];
 	       void *kv, *dv;
-	       node->data[i] = btree_mem_node_remove(bt, next, kp, kv, dv);
+	       node->data[i] = btree_mem_node_remove(bt, next, kp->key[0], kv, dv);
 	       }
 	    node->key[i] = kp;
 	    return *data_value;
@@ -483,7 +487,7 @@
 	    node->key[i-1]  = prev->key[prev->nkeys-1];
 	    node->data[i-1] = prev->data[prev->nkeys-1];
 
-	    if (prev->leaf)
+	    if (! prev->leaf)
 	       {
 	       for (int j = c->nkeys; j >= 0; j--)
 		  c->child[j+1] = c->child[j];
@@ -508,7 +512,7 @@
 	       next->data[j] = next->data[j+1];
 	       }
 
-	    if (next->leaf)
+	    if (! next->leaf)
 	       {
 	       c->child[c->nkeys] = next->child[0];
 	       for (int j = 0; j < next->nkeys; j++)
@@ -525,13 +529,12 @@
 		  //	    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);
-	    btree_mem_node_add_key(bt, (next ? next : prev), node->key[i+1], node->data[i+1]);
-
 	    if (next)
 	       btree_mem_node_merge(c, next);
 	    else
 	       btree_mem_node_merge(prev, c);
 
+	    btree_mem_node_add_key(bt, (next ? c : prev), node->key[i+1], node->data[i+1]);
 
 	    btree_mem_node_remove_key(node, i+1);
 
@@ -589,23 +592,23 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Return the lowest valued key of the subtree rooted at node
-void *
-btree_mem_node_first_key(struct btree_mem_node * node)
+// Return the node of the lowest valued key of the subtree rooted at node
+struct btree_mem_node *
+btree_mem_node_find_prev(struct btree_mem_node * node)
    {
    if (0 == node->nkeys)
       return NULL;
 
    if (node->leaf)
-      return node->key[0];
+      return node;
 
-   return btree_mem_node_last_key(node->child[0]);
+   return btree_mem_node_find_prev(node->child[0]);
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Return the highest valued key of the subtree rooted at node
-void *
-btree_mem_node_last_key(struct btree_mem_node * node)
+// Return the node of the highest valued key of the subtree rooted at node
+struct btree_mem_node *
+btree_mem_node_find_next(struct btree_mem_node * node)
    {
    if (0 == node->nkeys)
       return NULL;
@@ -613,7 +616,7 @@
    if (node->leaf)
       return node->key[node->nkeys-1];
 
-   return btree_mem_node_last_key(node->child[node->nkeys]);
+   return btree_mem_node_find_next(node->child[node->nkeys]);
    }
 
 /////////////////////////////////////////////////////////////////////////////////