1.1 --- a/src/btree_mem.c	Wed Oct 17 02:17:47 2012 -0500
     1.2 +++ b/src/btree_mem.c	Thu Oct 18 01:04:17 2012 -0500
     1.3 @@ -4,7 +4,6 @@
     1.4   */
     1.5  
     1.6  #include <stdio.h>
     1.7 -
     1.8  #include <stdlib.h>
     1.9  #include <stdbool.h>
    1.10  
    1.11 @@ -19,6 +18,13 @@
    1.12     bool leaf;
    1.13     };
    1.14  
    1.15 +struct btree_mem
    1.16 +   {
    1.17 +   int mindeg;
    1.18 +   struct btree_mem_node * root;
    1.19 +   int (*cmp)(void *, void *);
    1.20 +   };
    1.21 +
    1.22  struct btree_mem_node * btree_mem_node_new            (struct btree_mem * bt);
    1.23  void                    btree_mem_node_delete         (struct btree_mem_node * node);
    1.24  
    1.25 @@ -29,7 +35,19 @@
    1.26  
    1.27  struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
    1.28  
    1.29 -void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void *, void *), int depth);
    1.30 +void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
    1.31 +
    1.32 +void *                  btree_mem_node_remove         (struct btree_mem * bt, struct btree_mem_node * node, void * key);
    1.33 +void *                  btree_mem_node_remove_key     (struct btree_mem_node * node, int i);
    1.34 +void *                  btree_mem_node_first_key      (struct btree_mem_node * node);
    1.35 +void *                  btree_mem_node_last_key       (struct btree_mem_node * node);
    1.36 +
    1.37 +
    1.38 +#ifdef DEBUG
    1.39 +#define DEBUG_BLOCK(x) x
    1.40 +#else
    1.41 +#define DEBUG_BLOCK(x)
    1.42 +#endif
    1.43  
    1.44  ////////////////////////////////////////////////////////////////////////////////
    1.45  struct btree_mem *
    1.46 @@ -153,13 +171,12 @@
    1.47  void *
    1.48  btree_mem_insert(struct btree_mem * bt, void * key, void * data)
    1.49     {
    1.50 +   DEBUG_BLOCK(  printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data);  )
    1.51     struct btree_mem_node * s = bt->root;
    1.52  
    1.53 -   printf("inserting >%d< >%s<\n", *((int *) key), (char *) data);
    1.54     // If the root node is full, split it here.
    1.55     if ((2 * bt->mindeg - 1) == s->nkeys)
    1.56        {
    1.57 -      printf("Root node is full: splitting\n");
    1.58        s = btree_mem_node_new(bt);
    1.59        if (NULL == s)
    1.60  	 return NULL;
    1.61 @@ -177,10 +194,11 @@
    1.62     int i = node->nkeys - 1;
    1.63     if (node->leaf)
    1.64        {
    1.65 -      printf("node is leaf: inserting\n");
    1.66 +      //DEBUG_BLOCK( printf("node->nkeys: %d\n", node->nkeys); )
    1.67        while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
    1.68  	 {
    1.69  	 node->key[i+1] = node->key[i];
    1.70 +	 node->data[i+1] = node->data[i];
    1.71  	 i--;
    1.72  	 }
    1.73        node->key[i+1] = key;
    1.74 @@ -190,23 +208,12 @@
    1.75        }
    1.76     else
    1.77        {
    1.78 -      printf("node is not leaf: recursing\n");
    1.79        while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
    1.80  	 i--;
    1.81        i++;
    1.82 -      printf("i %d\n", i);
    1.83 -
    1.84 -      /* // Does the child exist?  If not we need to allocate it */
    1.85 -      /* if (NULL == node->child[i]) */
    1.86 -      /* 	 { */
    1.87 -      /* 	 node->child[i] = btree_mem_node_new(bt); */
    1.88 -      /* 	 if (NULL == node->child[i]) */
    1.89 -      /* 	    return NULL; */
    1.90 -      /* 	 } */
    1.91  
    1.92        if (node->child[i]->nkeys == (2 * bt->mindeg - 1))
    1.93  	 {
    1.94 -	 printf("splitting before recursion\n");
    1.95  	 if (NULL == btree_mem_split_child(bt, node, i))
    1.96  	    return NULL;
    1.97  	 if (bt->cmp(key, node->key[i]) > 0)
    1.98 @@ -267,53 +274,28 @@
    1.99  
   1.100     x->nkeys += 1;
   1.101  
   1.102 -   /* // NULL out the now unused key and data pointers in y. */
   1.103 -   /* for (int j = bt->mindeg; j < (2*bt->mindeg - 1); j++) */
   1.104 -   /*    { */
   1.105 -   /*    y->key[j] = NULL; */
   1.106 -   /*    y->data[j] = NULL; */
   1.107 -   /*    y->child[j] = NULL; */
   1.108 -   /*    } */
   1.109 -   /* y->child[2*bt->mindeg - 1] = NULL; */
   1.110 -
   1.111     return z;
   1.112     }
   1.113  
   1.114  ////////////////////////////////////////////////////////////////////////////////
   1.115 -void *
   1.116 -btree_mem_remove(struct btree_mem * bt, void * key)
   1.117 -   {
   1.118 -   
   1.119 -   }
   1.120 -
   1.121 -////////////////////////////////////////////////////////////////////////////////
   1.122  void
   1.123 -btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *))
   1.124 +btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void const * const, void *))
   1.125     {
   1.126     btree_mem_node_walk_inorder(bt->root, f, 0);
   1.127     }
   1.128  
   1.129  ////////////////////////////////////////////////////////////////////////////////
   1.130  void
   1.131 -btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void *, void *), int depth)
   1.132 +btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth)
   1.133     {
   1.134  
   1.135 -   //   for (int i = 0; i < depth; i++)
   1.136 -   //      printf("\t");
   1.137 -   //   printf("nkeys %d\n", node->nkeys);
   1.138 -   //   printf("walking\n");
   1.139     if (0 == node->nkeys)
   1.140        {
   1.141 -      //      printf("no keys\n");
   1.142        if (NULL != node->child[0])
   1.143 -	 {
   1.144 -	 //	 printf(": walking child\n");
   1.145  	 btree_mem_node_walk_inorder(node->child[0], f, depth+1);
   1.146 -	 }
   1.147        return;
   1.148        }
   1.149  
   1.150 -   //   printf("walking %d keys\n", node->nkeys);
   1.151     for (int i = 0; i < node->nkeys; i++)
   1.152        {
   1.153        if (! node->leaf) 
   1.154 @@ -324,3 +306,127 @@
   1.155        btree_mem_node_walk_inorder(node->child[node->nkeys], f, depth+1);
   1.156     }
   1.157  
   1.158 +////////////////////////////////////////////////////////////////////////////////
   1.159 +void *
   1.160 +btree_mem_remove(struct btree_mem * bt, void * key)
   1.161 +   {
   1.162 +   void * data = btree_mem_node_remove(bt, bt->root, key);
   1.163 +   if (NULL == data)
   1.164 +      return NULL;
   1.165 +   if (0 == bt->root->nkeys)
   1.166 +      {
   1.167 +      struct btree_mem_node * n = bt->root;
   1.168 +      bt->root = bt->root->child[0];
   1.169 +      free(n);
   1.170 +      }
   1.171 +   return data;
   1.172 +   }
   1.173 +
   1.174 +////////////////////////////////////////////////////////////////////////////////
   1.175 +// Assumption: node has bt->mindeg keys or is the root.
   1.176 +
   1.177 +void *
   1.178 +btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key)
   1.179 +   {
   1.180 +#ifdef NOTHING
   1.181 +   int i = node->nkeys - 1;
   1.182 +   while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
   1.183 +      i--;
   1.184 +
   1.185 +   if ( (i >= 0) && (bt->cmp(key, node->key[i]) == 0) )
   1.186 +      {
   1.187 +      // key is in node at key[i]
   1.188 +      if (node->leaf)
   1.189 +	 {
   1.190 +	 // Cormen: case 1
   1.191 +	 return btree_mem_node_remove_key(node, i);
   1.192 +	 }
   1.193 +      else
   1.194 +	 {
   1.195 +	 struct btree_mem_node * prev = node->child[i];
   1.196 +	 struct btree_mem_node * next = node->child[i+1];
   1.197 +
   1.198 +	 // if (child prev that precedes key in node has at least bt->mindeg keys) ||
   1.199 +	 //    (child next that follows  key in node has at least bt->mindeg keys)
   1.200 +	 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )
   1.201 +	    {
   1.202 +	    if (prev->nkeys >= bt->mindeg)
   1.203 +	       {
   1.204 +	       // Cormen: case 2a
   1.205 +	       void * kp = btree_mem_node_last_key(prev);
   1.206 +	       }
   1.207 +	    else
   1.208 +	       {
   1.209 +	       // Cormen: case 2b	
   1.210 +	       void * kp = btree_mem_node_first_key(prev);
   1.211 +	       }
   1.212 +	    void * kp_data = btree_mem_node_remove(bt, y, kp);
   1.213 +	    void * data = node->data[i];
   1.214 +	    node->key[i] = kp;
   1.215 +	    node->data[i] = kp_data;
   1.216 +	    return data;
   1.217 +	    }
   1.218 +	 else
   1.219 +	    {
   1.220 +	    // Cormen: case 2c
   1.221 +	    }
   1.222 +	 }
   1.223 +      }
   1.224 +   else
   1.225 +      {
   1.226 +      // key is in child[i+1], if anywhere
   1.227 +      if (c->nkeys == bt->mindeg - 1)
   1.228 +	 {
   1.229 +	 if ()
   1.230 +	    {
   1.231 +	    // Cormen: case 3a
   1.232 +	    }
   1.233 +	 else
   1.234 +	    {
   1.235 +	    // Cormen: case 3b
   1.236 +	    }
   1.237 +	 }
   1.238 +      return btree_mem_node_remove(bt, c, key);
   1.239 +      }
   1.240 +#endif
   1.241 +   }
   1.242 +
   1.243 +////////////////////////////////////////////////////////////////////////////////
   1.244 +void *
   1.245 +btree_mem_node_remove_key(struct btree_mem_node * node, int i)
   1.246 +   {
   1.247 +   void * data = node->key[i];
   1.248 +   for (int j = node->nkeys - 1; j > i; j--)
   1.249 +      {
   1.250 +      node->key[j-1]  = node->key[j];
   1.251 +      node->data[j-1] = node->data[j];
   1.252 +      }
   1.253 +   node->nkeys--;
   1.254 +   return data;
   1.255 +   }
   1.256 +
   1.257 +////////////////////////////////////////////////////////////////////////////////
   1.258 +void *
   1.259 +btree_mem_node_last_key(struct btree_mem_node * node)
   1.260 +   {
   1.261 +   if (0 == node->nkeys)
   1.262 +      return NULL;
   1.263 +
   1.264 +   if (node->leaf)
   1.265 +      return node->key[node->nkeys-1];
   1.266 +
   1.267 +   return btree_mem_node_last_key(node->child[node->nkeys]);
   1.268 +   }
   1.269 +
   1.270 +////////////////////////////////////////////////////////////////////////////////
   1.271 +void *
   1.272 +btree_mem_node_first_key(struct btree_mem_node * node)
   1.273 +   {
   1.274 +   if (0 == node->nkeys)
   1.275 +      return NULL;
   1.276 +
   1.277 +   if (node->leaf)
   1.278 +      return node->key[0];
   1.279 +
   1.280 +   return btree_mem_node_last_key(node->child[0]);
   1.281 +   }

     2.1 --- a/src/btree_mem.h	Wed Oct 17 02:17:47 2012 -0500
     2.2 +++ b/src/btree_mem.h	Thu Oct 18 01:04:17 2012 -0500
     2.3 @@ -2,22 +2,28 @@
     2.4  #define BTREE_MEM_H_
     2.5  
     2.6  
     2.7 +// #define DEBUG
     2.8 +
     2.9 +
    2.10  struct btree_mem_node;
    2.11 +struct btree_mem;
    2.12  
    2.13 -struct btree_mem
    2.14 -   {
    2.15 -   int mindeg;
    2.16 -   struct btree_mem_node * root;
    2.17 -   int (*cmp)(void *, void *);
    2.18 -   };
    2.19 +// Constructor and destructor
    2.20 +// When calling btree_mem_new, the min_degree should be the minimum degree of the B-Tree (using Cormen et al's terminology)
    2.21 +// and the cmp function should take pointers to two keys a and b and return -1 if a<b, 0 if a==b, and 1 if a>b
    2.22 +struct btree_mem * btree_mem_new          (int min_degree, int (*cmp)(void *, void *));
    2.23 +void               btree_mem_delete       (struct btree_mem * bt);
    2.24  
    2.25 -struct btree_mem * btree_mem_new(int min_degree, int (*cmp)(void *, void *));
    2.26 -void btree_mem_delete(struct btree_mem * bt);
    2.27 +void *             btree_mem_insert       (struct btree_mem * bt, void * key, void * data);
    2.28 +void *             btree_mem_find         (struct btree_mem * bt, void * key);
    2.29 +void *             btree_mem_remove       (struct btree_mem * bt, void * key);
    2.30  
    2.31 -void * btree_mem_insert(struct btree_mem * bt, void * key, void * data);
    2.32 -void * btree_mem_find(struct btree_mem * bt, void * key);
    2.33 -void * btree_mem_remove(struct btree_mem * bt, void * key);
    2.34 -
    2.35 -void btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *));
    2.36 +// Walk the tree in key order, starting with the lowest, and apply the function f to each one.  The argumemnts to f are
    2.37 +// int depth in the tree, the pointer to the key, and the pointer to the data. Note that the key cannot be modified,
    2.38 +// but the data can. Be careful with that.  You are given a pointer to the data, not a pointer to the pointer.  
    2.39 +// In other words, as long as your manipulation of the data does not change it's address, or the size of the data
    2.40 +// memory block, then you should be safe.  If you need to actually replace the data entirely, though, you should 
    2.41 +// remove and insert.
    2.42 +void               btree_mem_walk_inorder (struct btree_mem * bt, void (*f)(int, void const * const, void * const));
    2.43  
    2.44  #endif

     3.1 --- a/src/btree_mem_test.c	Wed Oct 17 02:17:47 2012 -0500
     3.2 +++ b/src/btree_mem_test.c	Thu Oct 18 01:04:17 2012 -0500
     3.3 @@ -2,23 +2,56 @@
     3.4  #include <stdlib.h>
     3.5  #include <string.h>
     3.6  
     3.7 +
     3.8  #include "btree_mem.h"
     3.9  
    3.10 +
    3.11 +#define MIN_DEGREE 3
    3.12 +#define MAX_LINE 1024
    3.13 +
    3.14 +#ifdef DEBUG
    3.15 +#define DEBUG_BLOCK(x) x
    3.16 +#else
    3.17 +#define DEBUG_BLOCK(x)
    3.18 +#endif
    3.19 +
    3.20 +
    3.21 +////////////////////////////////////////////////////////////////////////////////
    3.22  int
    3.23 -cmp(void * a, void * b)
    3.24 +key_cmp(void * a, void * b)
    3.25     {
    3.26 -   return strcmp(a, b);
    3.27 +   if (*((int *) a) < *((int *) b))
    3.28 +      return -1;
    3.29 +   else if  (*((int *) a) == *((int *) b))
    3.30 +      return 0;
    3.31 +   return 1;
    3.32     }
    3.33  
    3.34  
    3.35 +////////////////////////////////////////////////////////////////////////////////
    3.36  void
    3.37 -print_data(int depth, void * key, void * data)
    3.38 +print_data(int depth, void const * const key, void * data)
    3.39     {
    3.40     for (int i = 0; i < depth; i++)
    3.41        printf("\t");
    3.42     printf("%d %s\n", *((int*)key), (char *) data);
    3.43     }
    3.44  
    3.45 +////////////////////////////////////////////////////////////////////////////////
    3.46 +void
    3.47 +wackify_data(int depth, void const * const key, void * data)
    3.48 +   {
    3.49 +   strcpy(data, "wack");
    3.50 +   }
    3.51 +
    3.52 +////////////////////////////////////////////////////////////////////////////////
    3.53 +void
    3.54 +wackify_tree(struct btree_mem * bt)
    3.55 +   {
    3.56 +   btree_mem_walk_inorder(bt, wackify_data);
    3.57 +   }
    3.58 +
    3.59 +////////////////////////////////////////////////////////////////////////////////
    3.60  void
    3.61  print_tree(struct btree_mem * bt)
    3.62     {
    3.63 @@ -27,32 +60,74 @@
    3.64     printf("==================================\n");
    3.65     }
    3.66  
    3.67 +////////////////////////////////////////////////////////////////////////////////
    3.68 +void
    3.69 +usage(char * progname)
    3.70 +   {
    3.71 +   printf("Usage: %s [mindegree]\n"
    3.72 +	  "mindegree is the minimum degree of the B-Tree to create. (As defined"
    3.73 +	  "by Cormen, et al., Introduction to Algorithms, Ch. 18.) The default"
    3.74 +	  "value is %d\n"
    3.75 +	  "\n"
    3.76 +	  "Data for the tree will be read from stdin.  The first field on the line"
    3.77 +	  "should be an integer and will be used as the key.  The remainder of the"
    3.78 +	  "line will be read as a single string that will be stored as the data."
    3.79 +	  , progname, MIN_DEGREE);
    3.80 +   }
    3.81 +
    3.82 +////////////////////////////////////////////////////////////////////////////////
    3.83  int
    3.84  main(int argc, char ** argv)
    3.85     {
    3.86 -#define MINDEGREE 3
    3.87 -   struct btree_mem * bt = btree_mem_new(MINDEGREE, cmp);
    3.88 +   int degree = MIN_DEGREE;
    3.89 +
    3.90 +   if (argc > 1)
    3.91 +      {
    3.92 +      char * end;
    3.93 +      degree = strtol(argv[1], &end, 10);
    3.94 +      if (*end != '\0')
    3.95 +	 {
    3.96 +	 fprintf(stderr, "Degree must be an integer greater than or equal to %d\n", MIN_DEGREE);
    3.97 +	 usage(argv[0]);
    3.98 +	 exit(EXIT_FAILURE);
    3.99 +	 }
   3.100 +      }
   3.101 +
   3.102 +   struct btree_mem * bt = btree_mem_new(degree, key_cmp);
   3.103     if (NULL == bt)
   3.104        {
   3.105        fprintf(stderr, "Unable to create new btree_mem\n");
   3.106        exit(EXIT_FAILURE);
   3.107        }
   3.108  
   3.109 -#define MAXKEYS 20
   3.110 -   int keys[MAXKEYS] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   3.111 -			 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
   3.112 -   char * data[MAXKEYS] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
   3.113 -			    "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
   3.114 -
   3.115 -   for (int i = 0; i < MAXKEYS; i++)
   3.116 +   DEBUG_BLOCK( print_tree(bt); )
   3.117 +   int i;
   3.118 +   char s[MAX_LINE+1];
   3.119 +   while (1 == scanf("%d ", &i))
   3.120        {
   3.121 -      print_tree(bt);
   3.122 -      if (NULL == btree_mem_insert(bt, keys+i, data[i]))
   3.123 +      int * ip = malloc(sizeof(int));
   3.124 +      if (NULL == ip)
   3.125 +	 {
   3.126 +	 perror("malloc");
   3.127 +	 exit(EXIT_FAILURE);
   3.128 +	 }
   3.129 +      *ip = i;
   3.130 +      fgets(s, MAX_LINE, stdin);
   3.131 +      if (s[strlen(s)-1] != '\n')
   3.132 +	 {
   3.133 +	 fprintf(stderr, "input line exceeds maximum length of %d\n", MAX_LINE);
   3.134 +	 exit(EXIT_FAILURE);
   3.135 +	 }
   3.136 +      s[strlen(s)-1] = '\0';
   3.137 +      char * data = (s == NULL) ? NULL : strdup(s);
   3.138 +      if (NULL == btree_mem_insert(bt, ip, data))
   3.139  	 {
   3.140  	 fprintf(stderr, "btree_mem_insert failed\n");
   3.141  	 exit(EXIT_FAILURE);
   3.142  	 }
   3.143 +      DEBUG_BLOCK( print_tree(bt); )
   3.144        }
   3.145 +   //   wackify_tree(bt);
   3.146     print_tree(bt);
   3.147  
   3.148     exit(EXIT_SUCCESS);