# HG changeset patch
# User Eris Caffee<discordia@eldalin.com>
# Date 1350435443 18000
# Node ID 36561a63330a2006c2d50692fdffea18f485b12f
# Parent  5d8158ad2d61992f6f7b738dfabb766987773cab
initial btree in memory

diff -r 5d8158ad2d61 -r 36561a63330a CMakeLists.txt
--- a/CMakeLists.txt	Thu Oct 04 23:07:48 2012 -0500
+++ b/CMakeLists.txt	Tue Oct 16 19:57:23 2012 -0500
@@ -118,3 +118,8 @@
   ${trie_sedgewick_SRCS}
   )
 
+set (btree_mem_SRCS src/btree_mem.h src/btree_mem.c)
+add_executable (btree_mem_test
+  src/btree_mem_test.c
+  ${btree_mem_SRCS}
+  )
\ No newline at end of file
diff -r 5d8158ad2d61 -r 36561a63330a src/btree_mem.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/btree_mem.c	Tue Oct 16 19:57:23 2012 -0500
@@ -0,0 +1,220 @@
+#include <stdio.h>
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include "btree_mem.h"
+
+// In btree_mem_node, child[0].keys <= key[0] < child[1].keys <= key[1] < child[2].keys ...
+struct btree_mem_node
+   {
+   int nkeys;
+   void ** key;
+   void ** data;
+   struct btree_mem_node ** child;
+   bool leaf;
+   };
+
+struct btree_mem_node * btree_mem_node_new    (struct btree_mem * bt);
+void                    btree_mem_node_delete (struct btree_mem_node * node);
+
+struct btree_mem_node * btree_mem_node_find   (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);
+
+void *                  btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
+struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y);
+
+////////////////////////////////////////////////////////////////////////////////
+struct btree_mem *
+btree_mem_new(int min_degree, int (*cmp)(void *, void *))
+   {
+   struct btree_mem * bt = malloc(sizeof(struct btree_mem));
+   if (NULL == bt)
+      return NULL;
+
+   bt->mindeg = min_degree;
+   bt->cmp = cmp;
+
+   bt->root = btree_mem_node_new(bt);
+   if (NULL == bt->root)
+      {
+      free(bt);
+      return NULL;
+      }
+
+   return bt;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// IMPORTANT NOTE: All keys and data must be removed first or else memory
+// will leak.
+void
+btree_mem_delete(struct btree_mem * bt)
+   {
+   // TODO: walk down the tree and delete all nodes.
+   free(bt);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct btree_mem_node *
+btree_mem_node_new(struct btree_mem * bt)
+   {
+   struct btree_mem_node * node = malloc(sizeof(struct btree_mem_node));
+   if (NULL == node)
+      return NULL;
+
+   int maxchild = 2*bt->mindeg;
+
+   node->key  = malloc( (maxchild - 1) * sizeof(void *));
+   if (NULL == node->key)
+      {
+      free(node);
+      return NULL;
+      }
+
+   node->data = malloc( (maxchild - 1) * sizeof(void *));
+   if (NULL == node->data)
+      {
+      free(node->key);
+      free(node);
+      return NULL;
+      }
+
+   node->child = malloc( maxchild * sizeof(struct btree_mem_node *));
+   if (NULL == node->data)
+      {
+      free(node->data);
+      free(node->key);
+      free(node);
+      return NULL;
+      }
+
+   node->nkeys = 0;
+   node->leaf = false;
+
+   return node;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// IMPORTANT NOTE: All keys and data must be removed first or else memory
+// will leak.
+void
+btree_mem_node_delete(struct btree_mem_node * node)
+   {
+   free(node->child);
+   free(node->data);
+   free(node->key);
+   free(node);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+btree_mem_find(struct btree_mem * bt, void * key)
+   {
+   int i;
+   struct btree_mem_node * node = btree_mem_node_find(bt, bt->root, key, &i);
+   if (NULL == node)
+      return NULL;
+   return node->data[i];
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct btree_mem_node *
+btree_mem_node_find(struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i)
+   {
+   *i = 0;
+   while (( *i < node->nkeys) && (bt->cmp(key, node->key[*i]) > 0) )
+      (*i)++;
+   if ( (*i < node->nkeys) && (bt->cmp(key, node->key[*i]) == 0) )
+      return node;
+   if (node->leaf)
+      return NULL;
+   else
+      return btree_mem_node_find(bt, node->child[*i], key, i);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+btree_mem_insert(struct btree_mem * bt, void * key, void * data)
+   {
+   return btree_mem_node_insert(bt, bt->root, key, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+btree_mem_node_insert(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
+   {
+   struct btree_node * r = bt->root;
+   if ((2 * bt->mindeg - 1) == node->nkeys)
+      {
+      struct btree_node * s = btree_mem_node_new(bt);
+      if (NULL == s)
+	 return NULL;
+      bt->root = s;
+      s->child[0] = r;
+      btree_mem_split_child(bt, s, 1, r);
+      r = s;
+      }
+   return btree_mem_node_insert(bt, s, key, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// x - a non-full node
+// y - a full node that is a child of x
+// i - The index of y in x's child list.  That is x->child[i] == y.
+//
+// Split y in half, adding the newly created node z as a new child of x.
+// z will be placed after y in the child list.
+
+struct btree_mem_node *
+btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y)
+   {
+
+   // Allocate new node.
+   struct btree_mem_node * z = btree_mem_node_new(bt);
+   if (NULL == z)
+      return NULL;
+
+   // Load z with the second half of y's data;
+   z->leaf = y->leaf;
+   z->nkeys = bt->mindeg - 1;
+   for (int j = 0; j < bt->mindeg - 1; j++)
+      {
+      z->key[j] = y->key[j + bt->mindeg];
+      z->data[j] = y->data[j + bt->mindeg];
+      }
+   if (! y->leaf)
+      {
+      for (int j = 0; j < bt->mindeg)
+	 z->child[j] = y->child[j + bt->mindeg];
+      }
+
+   // Update y's nkeys.  We don't bother NULLing out the now unused key and data pointers.
+   y->nkeys = bt->mindeg - 1;
+
+   // Make a hole in x's child list for the new node z.
+   for (int j = x->nkeys; j > i; j--)
+      x->child[j+1] = x->child[j];
+   x->child[i] = z;
+
+   // Make a hole in x's key list for the new node z.
+   for (int j = x->nkeys - 1; j > i-1; j--)
+      {
+      x->key[j+1] = x->key[j];
+      x->data[j+1] = x->data[j];
+      }
+   x->key[i] = y->key[bt->mindeg-1];
+   x->data[i] = y->data[bt->mindeg-1];
+
+
+   x->nkeys += 1;
+
+   return z;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+btree_mem_remove(struct btree_mem * bt, void * key)
+   {
+   
+   }
+
diff -r 5d8158ad2d61 -r 36561a63330a src/btree_mem.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/btree_mem.h	Tue Oct 16 19:57:23 2012 -0500
@@ -0,0 +1,21 @@
+#ifndef BTREE_MEM_H_
+#define BTREE_MEM_H_
+
+
+struct btree_mem_node;
+
+struct btree_mem
+   {
+   int mindeg;
+   struct btree_mem_node * root;
+   int (*cmp)(void *, void *);
+   };
+
+struct btree_mem * btree_mem_new(int min_degree, int (*cmp)(void *, void *));
+void btree_mem_delete(struct btree_mem * bt);
+
+void * btree_mem_insert(struct btree_mem * bt, void * key, void * data);
+void * btree_mem_find(struct btree_mem * bt, void * key);
+void * btree_mem_remove(struct btree_mem * bt, void * key);
+
+#endif
diff -r 5d8158ad2d61 -r 36561a63330a src/btree_mem_test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/btree_mem_test.c	Tue Oct 16 19:57:23 2012 -0500
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "btree_mem.h"
+
+int
+cmp(void * a, void * b)
+   {
+   return strcmp(a, b);
+   }
+
+int
+main(int argc, char ** argv)
+   {
+   struct btree_mem * bt = btree_mem_new(2, cmp);
+   if (NULL == bt)
+      {
+      fprintf(stderr, "Unable to create new btree_mem\n");
+      exit(EXIT_FAILURE);
+      }
+   exit(EXIT_SUCCESS);
+   }