1.1 --- a/src/btree_mem.c	Fri Oct 19 00:10:34 2012 -0500
     1.2 +++ b/src/btree_mem.c	Fri Oct 19 16:07:18 2012 -0500
     1.3 @@ -43,8 +43,8 @@
     1.4  
     1.5  void                    btree_mem_node_add_key        (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
     1.6  void *                  btree_mem_node_remove_key     (struct btree_mem_node * node, int i);
     1.7 -void *                  btree_mem_node_first_key      (struct btree_mem_node * node);
     1.8 -void *                  btree_mem_node_last_key       (struct btree_mem_node * node);
     1.9 +struct btree_mem_node * btree_mem_node_find_prev      (struct btree_mem_node * node);
    1.10 +struct btree_mem_node * btree_mem_node_find_next      (struct btree_mem_node * node);
    1.11  void                    btree_mem_node_merge          (struct btree_mem_node * a, struct btree_mem_node * b);
    1.12  
    1.13  #ifdef DEBUG
    1.14 @@ -408,22 +408,26 @@
    1.15  	 //    (child next that follows  key in node has at least bt->mindeg keys)
    1.16  	 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )
    1.17  	    {
    1.18 -	    void * kp;
    1.19 +	    struct btree_mem_node * kp;
    1.20  	    if (prev->nkeys >= bt->mindeg)
    1.21  	       {
    1.22  	       // case 2a
    1.23 -	       DEBUG_BLOCK( printf("remove: case 2a\n"); )
    1.24 -	       kp = btree_mem_node_last_key(prev);
    1.25 +	       DEBUG_BLOCK( printf("remove: case 2a\n"); );
    1.26 +	       kp = btree_mem_node_find_prev(prev);
    1.27 +	       node->key[i]  = kp->key[kp->nkeys-1];
    1.28 +	       node->data[i] = kp->data[kp->nkeys];
    1.29  	       void *kv, *dv;
    1.30 -	       node->data[i] = btree_mem_node_remove(bt, prev, kp, kv, dv);
    1.31 +	       node->data[i] = btree_mem_node_remove(bt, prev, kp->key[kp->nkeys-1], kv, dv);
    1.32  	       }
    1.33  	    else
    1.34  	       {
    1.35  	       // case 2b
    1.36  	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
    1.37 -	       kp = btree_mem_node_first_key(next);
    1.38 +	       kp = btree_mem_node_find_next(next);
    1.39 +	       node->key[i]  = kp->key[0];
    1.40 +	       node->data[i] = kp->data[0];
    1.41  	       void *kv, *dv;
    1.42 -	       node->data[i] = btree_mem_node_remove(bt, next, kp, kv, dv);
    1.43 +	       node->data[i] = btree_mem_node_remove(bt, next, kp->key[0], kv, dv);
    1.44  	       }
    1.45  	    node->key[i] = kp;
    1.46  	    return *data_value;
    1.47 @@ -483,7 +487,7 @@
    1.48  	    node->key[i-1]  = prev->key[prev->nkeys-1];
    1.49  	    node->data[i-1] = prev->data[prev->nkeys-1];
    1.50  
    1.51 -	    if (prev->leaf)
    1.52 +	    if (! prev->leaf)
    1.53  	       {
    1.54  	       for (int j = c->nkeys; j >= 0; j--)
    1.55  		  c->child[j+1] = c->child[j];
    1.56 @@ -508,7 +512,7 @@
    1.57  	       next->data[j] = next->data[j+1];
    1.58  	       }
    1.59  
    1.60 -	    if (next->leaf)
    1.61 +	    if (! next->leaf)
    1.62  	       {
    1.63  	       c->child[c->nkeys] = next->child[0];
    1.64  	       for (int j = 0; j < next->nkeys; j++)
    1.65 @@ -525,13 +529,12 @@
    1.66  		  //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
    1.67  		  //	    printf("node %p  i %d\n", node, i); fflush(stdout);
    1.68  		  //	    printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev));	    fflush(stdout);
    1.69 -	    btree_mem_node_add_key(bt, (next ? next : prev), node->key[i+1], node->data[i+1]);
    1.70 -
    1.71  	    if (next)
    1.72  	       btree_mem_node_merge(c, next);
    1.73  	    else
    1.74  	       btree_mem_node_merge(prev, c);
    1.75  
    1.76 +	    btree_mem_node_add_key(bt, (next ? c : prev), node->key[i+1], node->data[i+1]);
    1.77  
    1.78  	    btree_mem_node_remove_key(node, i+1);
    1.79  
    1.80 @@ -589,23 +592,23 @@
    1.81     }
    1.82  
    1.83  ////////////////////////////////////////////////////////////////////////////////
    1.84 -// Return the lowest valued key of the subtree rooted at node
    1.85 -void *
    1.86 -btree_mem_node_first_key(struct btree_mem_node * node)
    1.87 +// Return the node of the lowest valued key of the subtree rooted at node
    1.88 +struct btree_mem_node *
    1.89 +btree_mem_node_find_prev(struct btree_mem_node * node)
    1.90     {
    1.91     if (0 == node->nkeys)
    1.92        return NULL;
    1.93  
    1.94     if (node->leaf)
    1.95 -      return node->key[0];
    1.96 +      return node;
    1.97  
    1.98 -   return btree_mem_node_last_key(node->child[0]);
    1.99 +   return btree_mem_node_find_prev(node->child[0]);
   1.100     }
   1.101  
   1.102  ////////////////////////////////////////////////////////////////////////////////
   1.103 -// Return the highest valued key of the subtree rooted at node
   1.104 -void *
   1.105 -btree_mem_node_last_key(struct btree_mem_node * node)
   1.106 +// Return the node of the highest valued key of the subtree rooted at node
   1.107 +struct btree_mem_node *
   1.108 +btree_mem_node_find_next(struct btree_mem_node * node)
   1.109     {
   1.110     if (0 == node->nkeys)
   1.111        return NULL;
   1.112 @@ -613,7 +616,7 @@
   1.113     if (node->leaf)
   1.114        return node->key[node->nkeys-1];
   1.115  
   1.116 -   return btree_mem_node_last_key(node->child[node->nkeys]);
   1.117 +   return btree_mem_node_find_next(node->child[node->nkeys]);
   1.118     }
   1.119  
   1.120  /////////////////////////////////////////////////////////////////////////////////