1.1 --- a/CMakeLists.txt	Tue Oct 16 19:57:23 2012 -0500
     1.2 +++ b/CMakeLists.txt	Wed Oct 17 02:17:47 2012 -0500
     1.3 @@ -27,7 +27,7 @@
     1.4  
     1.5  
     1.6  if (CMAKE_COMPILER_IS_GNUCXX)
     1.7 -  add_definitions(-pedantic -Wall -std=gnu99)
     1.8 +  add_definitions(-pedantic -Wall -std=gnu99 -O0)
     1.9  endif ()
    1.10  
    1.11  

     2.1 --- a/src/btree_mem.c	Tue Oct 16 19:57:23 2012 -0500
     2.2 +++ b/src/btree_mem.c	Wed Oct 17 02:17:47 2012 -0500
     2.3 @@ -1,3 +1,8 @@
     2.4 +/*
     2.5 +  This is a fairly straightforward implementation of a B-Tree in memory modeled after 
     2.6 +  Cormen, et al., Introduction to Algorithms, Chapter 18
     2.7 + */
     2.8 +
     2.9  #include <stdio.h>
    2.10  
    2.11  #include <stdlib.h>
    2.12 @@ -5,7 +10,6 @@
    2.13  
    2.14  #include "btree_mem.h"
    2.15  
    2.16 -// In btree_mem_node, child[0].keys <= key[0] < child[1].keys <= key[1] < child[2].keys ...
    2.17  struct btree_mem_node
    2.18     {
    2.19     int nkeys;
    2.20 @@ -15,13 +19,17 @@
    2.21     bool leaf;
    2.22     };
    2.23  
    2.24 -struct btree_mem_node * btree_mem_node_new    (struct btree_mem * bt);
    2.25 -void                    btree_mem_node_delete (struct btree_mem_node * node);
    2.26 +struct btree_mem_node * btree_mem_node_new            (struct btree_mem * bt);
    2.27 +void                    btree_mem_node_delete         (struct btree_mem_node * node);
    2.28  
    2.29 -struct btree_mem_node * btree_mem_node_find   (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);
    2.30 +struct btree_mem_node * btree_mem_node_find           (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);
    2.31  
    2.32 -void *                  btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
    2.33 -struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y);
    2.34 +void *                  btree_mem_node_insert         (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
    2.35 +void *                  btree_mem_node_insert_nonfull (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
    2.36 +
    2.37 +struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
    2.38 +
    2.39 +void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void *, void *), int depth);
    2.40  
    2.41  ////////////////////////////////////////////////////////////////////////////////
    2.42  struct btree_mem *
    2.43 @@ -41,6 +49,7 @@
    2.44        return NULL;
    2.45        }
    2.46  
    2.47 +   bt->root->leaf = true;
    2.48     return bt;
    2.49     }
    2.50  
    2.51 @@ -88,6 +97,14 @@
    2.52        return NULL;
    2.53        }
    2.54  
    2.55 +   for (int i = 0; i < maxchild - 1; i++)
    2.56 +      {
    2.57 +      node->key[i] = NULL;
    2.58 +      node->data[i] = NULL;
    2.59 +      node->child[i] = NULL;
    2.60 +      }
    2.61 +   node->child[maxchild-1] = NULL;
    2.62 +
    2.63     node->nkeys = 0;
    2.64     node->leaf = false;
    2.65  
    2.66 @@ -136,39 +153,82 @@
    2.67  void *
    2.68  btree_mem_insert(struct btree_mem * bt, void * key, void * data)
    2.69     {
    2.70 -   return btree_mem_node_insert(bt, bt->root, key, data);
    2.71 +   struct btree_mem_node * s = bt->root;
    2.72 +
    2.73 +   printf("inserting >%d< >%s<\n", *((int *) key), (char *) data);
    2.74 +   // If the root node is full, split it here.
    2.75 +   if ((2 * bt->mindeg - 1) == s->nkeys)
    2.76 +      {
    2.77 +      printf("Root node is full: splitting\n");
    2.78 +      s = btree_mem_node_new(bt);
    2.79 +      if (NULL == s)
    2.80 +	 return NULL;
    2.81 +      s->child[0] = bt->root;
    2.82 +      bt->root = s;
    2.83 +      btree_mem_split_child(bt, s, 0);
    2.84 +      }
    2.85 +   return btree_mem_node_insert_nonfull(bt, s, key, data);
    2.86     }
    2.87  
    2.88  ////////////////////////////////////////////////////////////////////////////////
    2.89  void *
    2.90 -btree_mem_node_insert(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
    2.91 +btree_mem_node_insert_nonfull(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
    2.92     {
    2.93 -   struct btree_node * r = bt->root;
    2.94 -   if ((2 * bt->mindeg - 1) == node->nkeys)
    2.95 +   int i = node->nkeys - 1;
    2.96 +   if (node->leaf)
    2.97        {
    2.98 -      struct btree_node * s = btree_mem_node_new(bt);
    2.99 -      if (NULL == s)
   2.100 -	 return NULL;
   2.101 -      bt->root = s;
   2.102 -      s->child[0] = r;
   2.103 -      btree_mem_split_child(bt, s, 1, r);
   2.104 -      r = s;
   2.105 +      printf("node is leaf: inserting\n");
   2.106 +      while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
   2.107 +	 {
   2.108 +	 node->key[i+1] = node->key[i];
   2.109 +	 i--;
   2.110 +	 }
   2.111 +      node->key[i+1] = key;
   2.112 +      node->data[i+1] = data;
   2.113 +      node->nkeys++;
   2.114 +      return key;
   2.115        }
   2.116 -   return btree_mem_node_insert(bt, s, key, data);
   2.117 +   else
   2.118 +      {
   2.119 +      printf("node is not leaf: recursing\n");
   2.120 +      while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
   2.121 +	 i--;
   2.122 +      i++;
   2.123 +      printf("i %d\n", i);
   2.124 +
   2.125 +      /* // Does the child exist?  If not we need to allocate it */
   2.126 +      /* if (NULL == node->child[i]) */
   2.127 +      /* 	 { */
   2.128 +      /* 	 node->child[i] = btree_mem_node_new(bt); */
   2.129 +      /* 	 if (NULL == node->child[i]) */
   2.130 +      /* 	    return NULL; */
   2.131 +      /* 	 } */
   2.132 +
   2.133 +      if (node->child[i]->nkeys == (2 * bt->mindeg - 1))
   2.134 +	 {
   2.135 +	 printf("splitting before recursion\n");
   2.136 +	 if (NULL == btree_mem_split_child(bt, node, i))
   2.137 +	    return NULL;
   2.138 +	 if (bt->cmp(key, node->key[i]) > 0)
   2.139 +	    i++;
   2.140 +	 }
   2.141 +      return btree_mem_node_insert_nonfull(bt, node->child[i], key, data);
   2.142 +      }
   2.143     }
   2.144  
   2.145  ////////////////////////////////////////////////////////////////////////////////
   2.146  // x - a non-full node
   2.147 -// y - a full node that is a child of x
   2.148 -// i - The index of y in x's child list.  That is x->child[i] == y.
   2.149 +// i - The index of a full node y in x's child list.
   2.150  //
   2.151  // Split y in half, adding the newly created node z as a new child of x.
   2.152  // z will be placed after y in the child list.
   2.153  
   2.154  struct btree_mem_node *
   2.155 -btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y)
   2.156 +btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i)
   2.157     {
   2.158  
   2.159 +   struct btree_mem_node * y = x->child[i];
   2.160 +
   2.161     // Allocate new node.
   2.162     struct btree_mem_node * z = btree_mem_node_new(bt);
   2.163     if (NULL == z)
   2.164 @@ -184,20 +244,20 @@
   2.165        }
   2.166     if (! y->leaf)
   2.167        {
   2.168 -      for (int j = 0; j < bt->mindeg)
   2.169 +      for (int j = 0; j < bt->mindeg; j++)
   2.170  	 z->child[j] = y->child[j + bt->mindeg];
   2.171        }
   2.172  
   2.173 -   // Update y's nkeys.  We don't bother NULLing out the now unused key and data pointers.
   2.174 +   // Update y's nkeys.
   2.175     y->nkeys = bt->mindeg - 1;
   2.176  
   2.177     // Make a hole in x's child list for the new node z.
   2.178 -   for (int j = x->nkeys; j > i; j--)
   2.179 +   for (int j = x->nkeys; j >= i + 1; j--)
   2.180        x->child[j+1] = x->child[j];
   2.181 -   x->child[i] = z;
   2.182 +   x->child[i+1] = z;
   2.183  
   2.184     // Make a hole in x's key list for the new node z.
   2.185 -   for (int j = x->nkeys - 1; j > i-1; j--)
   2.186 +   for (int j = x->nkeys - 1; j >= i; j--)
   2.187        {
   2.188        x->key[j+1] = x->key[j];
   2.189        x->data[j+1] = x->data[j];
   2.190 @@ -205,8 +265,16 @@
   2.191     x->key[i] = y->key[bt->mindeg-1];
   2.192     x->data[i] = y->data[bt->mindeg-1];
   2.193  
   2.194 +   x->nkeys += 1;
   2.195  
   2.196 -   x->nkeys += 1;
   2.197 +   /* // NULL out the now unused key and data pointers in y. */
   2.198 +   /* for (int j = bt->mindeg; j < (2*bt->mindeg - 1); j++) */
   2.199 +   /*    { */
   2.200 +   /*    y->key[j] = NULL; */
   2.201 +   /*    y->data[j] = NULL; */
   2.202 +   /*    y->child[j] = NULL; */
   2.203 +   /*    } */
   2.204 +   /* y->child[2*bt->mindeg - 1] = NULL; */
   2.205  
   2.206     return z;
   2.207     }
   2.208 @@ -218,3 +286,41 @@
   2.209     
   2.210     }
   2.211  
   2.212 +////////////////////////////////////////////////////////////////////////////////
   2.213 +void
   2.214 +btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *))
   2.215 +   {
   2.216 +   btree_mem_node_walk_inorder(bt->root, f, 0);
   2.217 +   }
   2.218 +
   2.219 +////////////////////////////////////////////////////////////////////////////////
   2.220 +void
   2.221 +btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void *, void *), int depth)
   2.222 +   {
   2.223 +
   2.224 +   //   for (int i = 0; i < depth; i++)
   2.225 +   //      printf("\t");
   2.226 +   //   printf("nkeys %d\n", node->nkeys);
   2.227 +   //   printf("walking\n");
   2.228 +   if (0 == node->nkeys)
   2.229 +      {
   2.230 +      //      printf("no keys\n");
   2.231 +      if (NULL != node->child[0])
   2.232 +	 {
   2.233 +	 //	 printf(": walking child\n");
   2.234 +	 btree_mem_node_walk_inorder(node->child[0], f, depth+1);
   2.235 +	 }
   2.236 +      return;
   2.237 +      }
   2.238 +
   2.239 +   //   printf("walking %d keys\n", node->nkeys);
   2.240 +   for (int i = 0; i < node->nkeys; i++)
   2.241 +      {
   2.242 +      if (! node->leaf) 
   2.243 +	 btree_mem_node_walk_inorder(node->child[i], f, depth+1);
   2.244 +      f(depth, node->key[i], node->data[i]);
   2.245 +      }
   2.246 +   if (! node->leaf) 
   2.247 +      btree_mem_node_walk_inorder(node->child[node->nkeys], f, depth+1);
   2.248 +   }
   2.249 +

     3.1 --- a/src/btree_mem.h	Tue Oct 16 19:57:23 2012 -0500
     3.2 +++ b/src/btree_mem.h	Wed Oct 17 02:17:47 2012 -0500
     3.3 @@ -18,4 +18,6 @@
     3.4  void * btree_mem_find(struct btree_mem * bt, void * key);
     3.5  void * btree_mem_remove(struct btree_mem * bt, void * key);
     3.6  
     3.7 +void btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *));
     3.8 +
     3.9  #endif

     4.1 --- a/src/btree_mem_test.c	Tue Oct 16 19:57:23 2012 -0500
     4.2 +++ b/src/btree_mem_test.c	Wed Oct 17 02:17:47 2012 -0500
     4.3 @@ -10,14 +10,50 @@
     4.4     return strcmp(a, b);
     4.5     }
     4.6  
     4.7 +
     4.8 +void
     4.9 +print_data(int depth, void * key, void * data)
    4.10 +   {
    4.11 +   for (int i = 0; i < depth; i++)
    4.12 +      printf("\t");
    4.13 +   printf("%d %s\n", *((int*)key), (char *) data);
    4.14 +   }
    4.15 +
    4.16 +void
    4.17 +print_tree(struct btree_mem * bt)
    4.18 +   {
    4.19 +   printf("==================================\n");
    4.20 +   btree_mem_walk_inorder(bt, print_data);
    4.21 +   printf("==================================\n");
    4.22 +   }
    4.23 +
    4.24  int
    4.25  main(int argc, char ** argv)
    4.26     {
    4.27 -   struct btree_mem * bt = btree_mem_new(2, cmp);
    4.28 +#define MINDEGREE 3
    4.29 +   struct btree_mem * bt = btree_mem_new(MINDEGREE, cmp);
    4.30     if (NULL == bt)
    4.31        {
    4.32        fprintf(stderr, "Unable to create new btree_mem\n");
    4.33        exit(EXIT_FAILURE);
    4.34        }
    4.35 +
    4.36 +#define MAXKEYS 20
    4.37 +   int keys[MAXKEYS] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    4.38 +			 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
    4.39 +   char * data[MAXKEYS] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
    4.40 +			    "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
    4.41 +
    4.42 +   for (int i = 0; i < MAXKEYS; i++)
    4.43 +      {
    4.44 +      print_tree(bt);
    4.45 +      if (NULL == btree_mem_insert(bt, keys+i, data[i]))
    4.46 +	 {
    4.47 +	 fprintf(stderr, "btree_mem_insert failed\n");
    4.48 +	 exit(EXIT_FAILURE);
    4.49 +	 }
    4.50 +      }
    4.51 +   print_tree(bt);
    4.52 +
    4.53     exit(EXIT_SUCCESS);
    4.54     }