Joey's btree module.

diff --git a/ccan/btree/_info b/ccan/btree/_info
new file mode 100644 (file)
index 0000000..2b81daf
--- /dev/null
+++ b/ccan/btree/_info
@@ -0,0 +1,250 @@
+#include <string.h>
+#include "config.h"
+
+/**
+ * btree - Efficient sorted associative container based on B-trees.
+ *
+ * This module provides an efficient in-memory lookup container that keeps a
+ * set of pointers sorted using a user-defined search function.
+ *
+ * This module supports insertion, removal, lookup, and traversal using an
+ * iterator system.  Note that insertion and removal into/from a btree will
+ * invalidate all iterators pointing to it (including the one passed to the
+ * insertion or removal function).
+ *
+ * btree currently doesn't have convenience functions for the simple tasks of
+ * "look up by key", "insert a key", and "remove a key".  To insert or remove,
+ * you first have use btree_find* to position an iterator on the
+ * insertion/removal point, then call btree_insert_at or btree_remove_at using
+ * that iterator.  Since a btree can hold multiple items with the same key,
+ * it isn't clear how the convenience functions should work yet.  I'm open to
+ * suggestions.
+ *
+ * A B-tree (not to be confused with a binary tree) is a data structure that
+ * performs insertion, removal, and lookup in O(log n) time per operation.
+ * Although B-trees are typically used for databases and filesystems, this is
+ * an in-memory implementation.
+ *
+ * Unlike functions like qsort, bsearch, and tsearch, btree does not take a
+ * comparison function.  It takes a binary search function, which is
+ * theoretically equivalent but faster.  Writing a binary search function
+ * is more difficult than writing a comparison function, so a macro is provided
+ * to make it much easier than doing either manually.
+ *
+ * Example:
+ * #include <ccan/btree/btree.h>
+ * 
+ * #include <errno.h>
+ * #include <stdlib.h>
+ * #include <stdio.h>
+ * #include <string.h>
+ * 
+ * struct word {
+ *     char *word;
+ *     char *letter_set;
+ * };
+ * 
+ * //Define the ordering function order_by_letter_set
+ * btree_search_implement
+ * (
+ *     order_by_letter_set,
+ *     struct word *,
+ *     int c = strcmp(a->letter_set, b->letter_set),
+ *     c == 0,
+ *     c < 0
+ * )
+ * 
+ * struct word *new_word(const char *line);
+ * char *chomp(char *str);
+ * char *make_letter_set(char *str);
+ * 
+ * void insert_word(struct btree *btree, struct word *word)
+ * {
+ *     btree_iterator iter;
+ *     
+ *     //Position iterator after existing words with this letter set.
+ *     btree_find_last(btree, word, iter);
+ *     
+ *     //Insert new word at iterator position.
+ *     btree_insert_at(iter, word);
+ * }
+ * 
+ * void print_anagrams(struct btree *btree, char *line)
+ * {
+ *     btree_iterator iter, end;
+ *     struct word key = {
+ *             NULL,
+ *             make_letter_set(line)
+ *     };
+ *     
+ *     //Find first matching word.
+ *     if (!btree_find_first(btree, &key, iter)) {
+ *             printf("\t(none)\n");
+ *             return;
+ *     }
+ *     
+ *     btree_find_last(btree, &key, end);
+ *     
+ *     //Traverse matching words.
+ *     for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
+ *            btree_next(iter))
+ *     {
+ *             struct word *word = iter->item;
+ *             printf("\t%s\n", word->word);
+ *     }
+ * }
+ * 
+ * int destroy_word(struct word *word, void *ctx)
+ * {
+ *     (void) ctx;
+ *     
+ *     free(word->word);
+ *     free(word->letter_set);
+ *     free(word);
+ *     
+ *     return 1;
+ * }
+ * 
+ * struct btree *read_dictionary(const char *filename)
+ * {
+ *     FILE *f;
+ *     char line[256];
+ *     
+ *     //Construct new btree with the ordering function order_by_letter_set .
+ *     struct btree *btree = btree_new(order_by_letter_set);
+ *     
+ *     f = fopen(filename, "r");
+ *     if (!f)
+ *             goto fail;
+ *     
+ *     //Set the destroy callback so btree_free will automatically
+ *     //free our items.  Setting btree->destroy is optional.
+ *     btree->destroy = (btree_action_t)destroy_word;
+ *     
+ *     while (fgets(line, sizeof(line), f)) {
+ *             struct word *word = new_word(line);
+ *             if (!word)
+ *                     continue;
+ *             insert_word(btree, word);
+ *     }
+ *     
+ *     if (ferror(f)) {
+ *             fclose(f);
+ *             goto fail;
+ *     }
+ *     if (fclose(f))
+ *             goto fail;
+ *     
+ *     return btree;
+ * 
+ * fail:
+ *     btree_delete(btree);
+ *     fprintf(stderr, "%s: %s\n", filename, strerror(errno));
+ *     return NULL;
+ * }
+ * 
+ * int main(int argc, char *argv[])
+ * {
+ *     struct btree *btree;
+ *     char line[256];
+ *     
+ *     if (argc != 2) {
+ *             fprintf(stderr,
+ *                     "Usage: %s dictionary-file\n"
+ *                     "Example:\n"
+ *                     "\t%s /usr/share/dict/words\n"
+ *                     "\n"
+ *                     , argv[0], argv[0]);
+ *             return 1;
+ *     }
+ *     
+ *     printf("Indexing...\n");
+ *     btree = read_dictionary(argv[1]);
+ *     printf("Dictionary has %ld words\n", (long)btree->count);
+ *     
+ *     for (;;) {
+ *             printf("> ");
+ *             if (!fgets(line, sizeof(line), stdin))
+ *                     break;
+ *             chomp(line);
+ *             if (!*line)
+ *                     break;
+ *             
+ *             printf("Anagrams of \"%s\":\n", line);
+ *             print_anagrams(btree, line);
+ *     }
+ *     
+ *     printf("Cleaning up...\n");
+ *     btree_delete(btree);
+ *     
+ *     return 0;
+ * }
+ * 
+ * struct word *new_word(const char *line)
+ * {
+ *     struct word *word;
+ *     char *letter_set = make_letter_set(strdup(line));
+ *     
+ *     //Discard lines with no letters
+ *     if (!*letter_set) {
+ *             free(letter_set);
+ *             return NULL;
+ *     }
+ *     
+ *     word = malloc(sizeof(struct word));
+ *     word->word = chomp(strdup(line));
+ *     word->letter_set = letter_set;
+ *     
+ *     return word;
+ * }
+ * 
+ * //Remove trailing newline (if present).
+ * char *chomp(char *str)
+ * {
+ *     char *end = strchr(str, '\0') - 1;
+ *     if (*str && *end == '\n')
+ *             *end = 0;
+ *     return str;
+ * }
+ * 
+ * //Remove all characters but letters, make letters lowercase, and sort them.
+ * char *make_letter_set(char *str)
+ * {
+ *     size_t count[26] = {0};
+ *     size_t i, j;
+ *     char *o = str;
+ *     
+ *     for (i=0; str[i]; i++) {
+ *             char c = str[i];
+ *             if (c >= 'A' && c <= 'Z')
+ *                     c += 'a'-'A';
+ *             if (c >= 'a' && c <= 'z')
+ *                     count[c - 'a']++;
+ *     }
+ *     
+ *     for (i = 0; i < 26; i++) {
+ *             for (j = 0; j < count[i]; j++)
+ *                     *o++ = 'a' + i;
+ *     }
+ *     *o = '\0';
+ *     
+ *     return str;
+ * }
+ *
+ * Author: Joey Adams
+ * Version: 0.1.0
+ * Licence: BSD
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               /* Nothing */
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/ccan/btree/btree.c b/ccan/btree/btree.c
new file mode 100644 (file)
index 0000000..31982ec
--- /dev/null
+++ b/ccan/btree/btree.c
@@ -0,0 +1,727 @@
+/*
+       Copyright (c) 2010  Joseph A. Adams
+       All rights reserved.
+       
+       Redistribution and use in source and binary forms, with or without
+       modification, are permitted provided that the following conditions
+       are met:
+       1. Redistributions of source code must retain the above copyright
+          notice, this list of conditions and the following disclaimer.
+       2. Redistributions in binary form must reproduce the above copyright
+          notice, this list of conditions and the following disclaimer in the
+          documentation and/or other materials provided with the distribution.
+       3. The name of the author may not be used to endorse or promote products
+          derived from this software without specific prior written permission.
+       
+       THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+       IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+       OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+       IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+       INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+       NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+       DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+       THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+       (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+       THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include "btree.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#define MAX (BTREE_ITEM_MAX)
+#define MIN (BTREE_ITEM_MAX >> 1)
+
+static struct btree_node *node_alloc(int internal);
+static void node_delete(struct btree_node *node, struct btree *btree);
+
+static void branch_begin(btree_iterator iter);
+static void branch_end(btree_iterator iter);
+static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
+
+/*
+ * If iter->node has parent, returns 1 and ascends the iterator such that
+ * iter->node->branch[iter->k] will be what iter->node was.
+ *
+ * If iter->node does not have a parent (is a root), returns 0 and leaves the
+ * iterator untouched.
+ */
+#define ascend(iter) ((iter)->node->parent \
+       ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
+       : 0)
+
+static void node_insert(const void *x, struct btree_node *xr,
+                               struct btree_node *p, unsigned int k);
+static void node_split(const void **x, struct btree_node **xr,
+                               struct btree_node *p, unsigned int k);
+
+static void node_remove_leaf_item(struct btree_node *node, unsigned int k);
+void node_restore(struct btree_node *node, unsigned int k);
+
+static int node_walk_backward(const struct btree_node *node,
+                               btree_action_t action, void *ctx);
+static int node_walk_forward(const struct btree_node *node,
+                               btree_action_t action, void *ctx);
+
+
+/************************* Public functions *************************/
+
+struct btree *btree_new(btree_search_t search)
+{
+       struct btree *btree = calloc(1, sizeof(struct btree));
+       struct btree_node *node = node_alloc(0);
+               node->parent = NULL;
+               node->count = 0;
+               node->depth = 0;
+       btree->root = node;
+       btree->search = search;
+       return btree;
+}
+
+void btree_delete(struct btree *btree)
+{
+       node_delete(btree->root, btree);
+       free(btree);
+}
+
+int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
+{
+       struct btree_node *node;
+       
+       iter->btree = (struct btree *)btree;
+       begin_end_lr(iter, btree->root, lr);
+       
+       /* Set iter->item if any items exist. */
+       node = iter->node;
+       if (node->count) {
+               iter->item = (void*)node->item[iter->k - lr];
+               return 1;
+       }
+       
+       return 0;
+}
+
+int btree_deref(btree_iterator iter)
+{
+       if (iter->k >= iter->node->count) {
+               struct btree_iterator_s tmp = *iter;
+               do {
+                       if (!ascend(iter)) {
+                               *iter = tmp;
+                               return 0;
+                       }
+               } while (iter->k >= iter->node->count);
+       }
+       
+       iter->item = (void*)iter->node->item[iter->k];
+       return 1;
+}
+
+int btree_prev(btree_iterator iter)
+{
+       if (iter->node->depth) {
+               branch_end(iter);
+       } else if (iter->k == 0) {
+               struct btree_iterator_s tmp = *iter;
+               do {
+                       if (!ascend(iter)) {
+                               *iter = tmp;
+                               return 0;
+                       }
+               } while (iter->k == 0);
+       }
+       
+       iter->item = (void*)iter->node->item[--iter->k];
+       return 1;
+}
+
+int btree_next(btree_iterator iter)
+{
+       int ret = btree_deref(iter);
+       if (ret) {
+               iter->k++;
+               if (iter->node->depth)
+                       branch_begin(iter);
+       }
+       return ret;
+}
+
+int btree_find_lr(const struct btree *btree, const void *key,
+                               btree_iterator iter, int lr)
+{
+       struct btree_node *node = btree->root;
+       unsigned int k;
+       unsigned int depth;
+       int found = 0;
+       
+       iter->btree = (struct btree *)btree;
+       iter->item = NULL;
+       
+       depth = node->depth;
+       for (;;) {
+               int f = 0;
+               k = btree->search(key, node->item, node->count, lr, &f);
+               
+               if (f) {
+                       iter->item = (void*)node->item[k - lr];
+                       found = 1;
+               }
+               if (!depth--)
+                       break;
+               
+               node = node->branch[k];
+       }
+       
+       iter->node = node;
+       iter->k = k;
+       
+       return found;
+}
+
+int btree_walk_backward(const struct btree *btree,
+                               btree_action_t action, void *ctx)
+{
+       return node_walk_backward(btree->root, action, ctx);
+}
+
+int btree_walk_forward(const struct btree *btree,
+                               btree_action_t action, void *ctx)
+{
+       return node_walk_forward(btree->root, action, ctx);
+}
+
+void btree_insert_at(btree_iterator iter, const void *item)
+{
+       const void *x = item;
+       struct btree_node *xr = NULL;
+       struct btree_node *p;
+       struct btree *btree = iter->btree;
+       
+       /* btree_insert_at always sets iter->item to item. */
+       iter->item = (void*)item;
+       
+       /*
+        * If node is not a leaf, fall to the end of the left branch of item[k]
+        * so that it will be a leaf. This does not modify the iterator's logical
+        * position.
+        */
+       if (iter->node->depth)
+               branch_end(iter);
+       
+       /*
+        * First try inserting item into this node.
+        * If it's too big, split it, and repeat by
+        * trying to insert the median and right subtree into parent.
+        */
+       if (iter->node->count < MAX) {
+               node_insert(x, xr, iter->node, iter->k);
+               goto finished;
+       } else {
+               for (;;) {
+                       node_split(&x, &xr, iter->node, iter->k);
+                       
+                       if (!ascend(iter))
+                               break;
+                       
+                       if (iter->node->count < MAX) {
+                               node_insert(x, xr, iter->node, iter->k);
+                               goto finished;
+                       }
+               }
+               
+               /*
+                * If splitting came all the way up to the root, create a new root whose
+                * left branch is the current root, median is x, and right branch is the
+                * half split off from the root.
+                */
+               assert(iter->node == btree->root);
+               p = node_alloc(1);
+               p->parent = NULL;
+               p->count = 1;
+               p->depth = btree->root->depth + 1;
+               p->item[0] = x;
+               p->branch[0] = btree->root;
+                       btree->root->parent = p;
+                       btree->root->k = 0;
+               p->branch[1] = xr;
+                       xr->parent = p;
+                       xr->k = 1;
+               btree->root = p;
+       }
+       
+finished:
+       btree->count++;
+       iter->node = NULL;
+}
+
+int btree_remove_at(btree_iterator iter)
+{
+       struct btree *btree = iter->btree;
+       struct btree_node *root;
+       
+       if (!btree_deref(iter))
+               return 0;
+       
+       if (!iter->node->depth) {
+               node_remove_leaf_item(iter->node, iter->k);
+               if (iter->node->count >= MIN || !iter->node->parent)
+                       goto finished;
+       } else {
+               /*
+                * We can't remove an item from an internal node, so we'll replace it
+                * with its successor (which will always be in a leaf), then remove
+                * the original copy of the successor.
+                */
+               
+               /* Save pointer to condemned item. */
+               const void **x = &iter->node->item[iter->k];
+               
+               /* Descend to successor. */
+               iter->k++;
+               branch_begin(iter);
+               
+               /* Replace condemned item with successor. */
+               *x = iter->node->item[0];
+               
+               /* Remove successor. */
+               node_remove_leaf_item(iter->node, 0);
+       }
+       
+       /*
+        * Restore nodes that fall under their minimum count.  This may
+        * propagate all the way up to the root.
+        */
+       for (;;) {
+               if (iter->node->count >= MIN)
+                       goto finished;
+               if (!ascend(iter))
+                       break;
+               node_restore(iter->node, iter->k);
+       }
+       
+       /*
+        * If combining came all the way up to the root, and it has no more
+        * dividers, delete it and make its only branch the root.
+        */
+       root = iter->node;
+       assert(root == btree->root);
+       assert(root->depth > 0);
+       if (root->count == 0) {
+               btree->root = root->branch[0];
+               btree->root->parent = NULL;
+               free(root);
+       }
+       
+finished:
+       btree->count--;
+       iter->node = NULL;
+       return 1;
+}
+
+/*
+ * ascends iterator a until it matches iterator b's depth.
+ *
+ * Returns -1 if they end up on the same k (meaning a < b).
+ * Returns 0 otherwise.
+ */
+static int elevate(btree_iterator a, btree_iterator b)
+{
+       while (a->node->depth < b->node->depth)
+               ascend(a);
+       
+       if (a->k == b->k)
+               return -1;
+       return 0;
+}
+
+int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
+{
+       btree_iterator a = {*iter_a}, b = {*iter_b};
+       int ad, bd;
+       
+       ad = btree_deref(a);
+       bd = btree_deref(b);
+       
+       /* Check cases where one or both iterators are at the end. */
+       if (!ad)
+               return bd ? 1 : 0;
+       if (!bd)
+               return ad ? -1 : 0;
+       
+       /* Bring iterators to the same depth. */
+       if (a->node->depth < b->node->depth) {
+               if (elevate(a, b))
+                       return -1;
+       } else if (a->node->depth > b->node->depth) {
+               if (elevate(b, a))
+                       return 1;
+       }
+       
+       /* Bring iterators to the same node. */
+       while (a->node != b->node) {
+               ascend(a);
+               ascend(b);
+       }
+       
+       /* Now we can compare by k directly. */
+       if (a->k < b->k)
+               return -1;
+       if (a->k > b->k)
+               return 1;
+       
+       return 0;
+}
+
+
+/************************* Private functions *************************/
+
+static struct btree_node *node_alloc(int internal)
+{
+       struct btree_node *node;
+       size_t isize = internal
+               ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
+               : 0;
+       node = malloc(sizeof(struct btree_node) + isize);
+       return node;
+}
+
+static void node_delete(struct btree_node *node, struct btree *btree)
+{
+       unsigned int i, count = node->count;
+       
+       if (!node->depth) {
+               if (btree->destroy) {
+                       for (i=0; i<count; i++)
+                               btree->destroy((void*)node->item[i], btree->destroy_ctx);
+               }
+       } else {
+               for (i=0; i<count; i++) {
+                       node_delete(node->branch[i], btree);
+                       if (btree->destroy)
+                               btree->destroy((void*)node->item[i], btree->destroy_ctx);
+               }
+               node_delete(node->branch[count], btree);
+       }
+       
+       free(node);
+}
+
+/* Set iter to beginning of branch pointed to by iter. */
+static void branch_begin(btree_iterator iter)
+{
+       struct btree_node *node = iter->node->branch[iter->k];
+       unsigned int depth = node->depth;
+       while (depth--)
+               node = node->branch[0];
+       iter->node = node;
+       iter->k = 0;
+}
+
+/* Set iter to end of branch pointed to by iter. */
+static void branch_end(btree_iterator iter)
+{
+       struct btree_node *node = iter->node->branch[iter->k];
+       unsigned int depth = node->depth;
+       while (depth--)
+               node = node->branch[node->count];
+       iter->node = node;
+       iter->k = node->count;
+}
+
+/* Traverse to the beginning or end of node, depending on lr. */
+static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
+{
+       iter->node = node;
+       iter->k = lr ? node->count : 0;
+       if (node->depth)
+               (lr ? branch_end : branch_begin)(iter);
+}
+
+/*
+ * Inserts item x and right branch xr into node p at position k.
+ *
+ * Assumes p exists and has enough room.
+ * Ignores xr if p is a leaf.
+ */
+static void node_insert(const void *x, struct btree_node *xr,
+                               struct btree_node *p, unsigned int k)
+{
+       unsigned int i;
+       
+       for (i = p->count; i-- > k;)
+               p->item[i+1] = p->item[i];
+       p->item[k] = x;
+       
+       if (p->depth) {
+               k++;
+               for (i = p->count+1; i-- > k;) {
+                       p->branch[i+1] = p->branch[i];
+                       p->branch[i+1]->k = i+1;
+               }
+               p->branch[k] = xr;
+               xr->parent = p;
+               xr->k = k;
+       }
+       
+       p->count++;
+}
+
+/*
+ * Inserts item *x and subtree *xr into node p at position k, splitting it into
+ * nodes p and *xr with median item *x.
+ *
+ * Assumes p->count == MAX.
+ * Ignores original *xr if p is a leaf, but always sets it.
+ */
+static void node_split(const void **x, struct btree_node **xr,
+                               struct btree_node *p, unsigned int k)
+{
+       unsigned int i, split;
+       struct btree_node *l = p, *r;
+       
+       /*
+        * If k <= MIN, item will be inserted into left subtree, so give l
+        * fewer items initially.
+        * Otherwise, item will be inserted into right subtree, so give r
+        * fewer items initially.
+        */
+       if (k <= MIN)
+               split = MIN;
+       else
+               split = MIN + 1;
+       
+       /*
+        * If l->depth is 0, allocate a leaf node.
+        * Otherwise, allocate an internal node.
+        */
+       r = node_alloc(l->depth);
+       
+       /* l and r will be siblings, so they will have the same parent and depth. */
+       r->parent = l->parent;
+       r->depth = l->depth;
+       
+       /*
+        * Initialize items/branches of right side.
+        * Do not initialize r's leftmost branch yet because we don't know
+        * whether it will be l's current rightmost branch or if *xr will
+        * take its place.
+        */
+       for (i = split; i < MAX; i++)
+               r->item[i-split] = l->item[i];
+       if (r->depth) {
+               for (i = split+1; i <= MAX; i++) {
+                       r->branch[i-split] = l->branch[i];
+                       r->branch[i-split]->parent = r;
+                       r->branch[i-split]->k = i-split;
+               }
+       }
+       
+       /* Update counts. */
+       l->count = split;
+       r->count = MAX - split;
+       
+       /*
+        * The nodes are now split, but the key isn't inserted yet.
+        *
+        * Insert key into left or right half,
+        * depending on which side it fell on.
+        */
+       if (k <= MIN)
+               node_insert(*x, *xr, l, k);
+       else
+               node_insert(*x, *xr, r, k - split);
+       
+       /*
+        * Give l's rightmost branch to r because l's rightmost item
+        * is going up to become the median.
+        */
+       if (r->depth) {
+               r->branch[0] = l->branch[l->count];
+               r->branch[0]->parent = r;
+               r->branch[0]->k = 0;
+       }
+       
+       /*
+        * Take up l's rightmost item to make it the median.
+        * That item's right branch is now r.
+        */
+       *x = l->item[--l->count];
+       *xr = r;
+}
+
+/*
+ * Removes item k from node p, shifting successor items back and
+ * decrementing the count.
+ *
+ * Assumes node p has the item k and is a leaf.
+ */
+static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
+{
+       unsigned int i;
+       for (i = k+1; i < node->count; i++)
+               node->item[i-1] = node->item[i];
+       node->count--;
+}
+
+static void move_left(struct btree_node *node, unsigned int k);
+static void move_right(struct btree_node *node, unsigned int k);
+static void combine(struct btree_node *node, unsigned int k);
+
+/*
+ * Fixes node->branch[k]'s problem of having one less than MIN items.
+ * May or may not cause node to fall below MIN items, depending on whether
+ * two branches are combined or not.
+ */
+void node_restore(struct btree_node *node, unsigned int k)
+{
+       if (k == 0) {
+               if (node->branch[1]->count > MIN)
+                       move_left(node, 0);
+               else
+                       combine(node, 0);
+       } else if (k == node->count) {
+               if (node->branch[k-1]->count > MIN)
+                       move_right(node, k-1);
+               else
+                       combine(node, k-1);
+       } else if (node->branch[k-1]->count > MIN) {
+               move_right(node, k-1);
+       } else if (node->branch[k+1]->count > MIN) {
+               move_left(node, k);
+       } else {
+               combine(node, k-1);
+       }
+}
+
+static void move_left(struct btree_node *node, unsigned int k)
+{
+       struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
+       unsigned int i;
+       
+       l->item[l->count] = node->item[k];
+       node->item[k] = r->item[0];
+       for (i = 1; i < r->count; i++)
+               r->item[i-1] = r->item[i];
+       
+       if (r->depth) {
+               mv = r->branch[0];
+               l->branch[l->count+1] = mv;
+               mv->parent = l;
+               mv->k = l->count+1;
+               
+               for (i = 1; i <= r->count; i++) {
+                       r->branch[i-1] = r->branch[i];
+                       r->branch[i-1]->k = i-1;
+               }
+       }
+       
+       l->count++;
+       r->count--;
+}
+
+static void move_right(struct btree_node *node, unsigned int k)
+{
+       struct btree_node *l = node->branch[k], *r = node->branch[k+1];
+       unsigned int i;
+       
+       for (i = r->count; i--;)
+               r->item[i+1] = r->item[i];
+       r->item[0] = node->item[k];
+       node->item[k] = l->item[l->count-1];
+       
+       if (r->depth) {
+               for (i = r->count+1; i--;) {
+                       r->branch[i+1] = r->branch[i];
+                       r->branch[i+1]->k = i+1;
+               }
+               r->branch[0] = l->branch[l->count];
+               r->branch[0]->parent = r;
+               r->branch[0]->k = 0;
+       }
+       
+       l->count--;
+       r->count++;
+}
+
+/* Combine node->branch[k] and node->branch[k+1]. */
+static void combine(struct btree_node *node, unsigned int k)
+{
+       struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
+       const void **o = &l->item[l->count];
+       unsigned int i;
+       
+       //append node->item[k] followed by right node's items to left node
+       *o++ = node->item[k];
+       for (i=0; i<r->count; i++)
+               *o++ = r->item[i];
+       
+       //if applicable, append right node's branches to left node
+       if (r->depth) {
+               for (i=0; i<=r->count; i++) {
+                       mv = r->branch[i];
+                       l->branch[l->count + i + 1] = mv;
+                       mv->parent = l;
+                       mv->k = l->count + i + 1;
+               }
+       }
+       
+       //remove k and its right branch from parent node
+       for (i = k+1; i < node->count; i++) {
+               node->item[i-1] = node->item[i];
+               node->branch[i] = node->branch[i+1];
+               node->branch[i]->k = i;
+       }
+       
+       //don't forget to update the left and parent node's counts and to free the right node
+       l->count += r->count + 1;
+       node->count--;
+       free(r);
+}
+
+static int node_walk_backward(const struct btree_node *node,
+                               btree_action_t action, void *ctx)
+{
+       unsigned int i, count = node->count;
+       
+       if (!node->depth) {
+               for (i=count; i--;)
+                       if (!action((void*)node->item[i], ctx))
+                               return 0;
+       } else {
+               if (!node_walk_backward(node->branch[count], action, ctx))
+                       return 0;
+               for (i=count; i--;) {
+                       if (!action((void*)node->item[i], ctx))
+                               return 0;
+                       if (!node_walk_backward(node->branch[i], action, ctx))
+                               return 0;
+               }
+       }
+       
+       return 1;
+}
+
+static int node_walk_forward(const struct btree_node *node,
+                               btree_action_t action, void *ctx)
+{
+       unsigned int i, count = node->count;
+       
+       if (!node->depth) {
+               for (i=0; i<count; i++)
+                       if (!action((void*)node->item[i], ctx))
+                               return 0;
+       } else {
+               for (i=0; i<count; i++) {
+                       if (!node_walk_forward(node->branch[i], action, ctx))
+                               return 0;
+                       if (!action((void*)node->item[i], ctx))
+                               return 0;
+               }
+               if (!node_walk_forward(node->branch[count], action, ctx))
+                       return 0;
+       }
+       
+       return 1;
+}

diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h
new file mode 100644 (file)
index 0000000..babfea7
--- /dev/null
+++ b/ccan/btree/btree.h
@@ -0,0 +1,238 @@
+/*
+       Copyright (c) 2010  Joseph A. Adams
+       All rights reserved.
+       
+       Redistribution and use in source and binary forms, with or without
+       modification, are permitted provided that the following conditions
+       are met:
+       1. Redistributions of source code must retain the above copyright
+          notice, this list of conditions and the following disclaimer.
+       2. Redistributions in binary form must reproduce the above copyright
+          notice, this list of conditions and the following disclaimer in the
+          documentation and/or other materials provided with the distribution.
+       3. The name of the author may not be used to endorse or promote products
+          derived from this software without specific prior written permission.
+       
+       THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+       IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+       OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+       IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+       INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+       NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+       DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+       THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+       (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+       THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CCAN_BTREE_H
+#define CCAN_BTREE_H
+
+/*
+Note:  The following should work but are not well-tested yet:
+
+btree_walk...
+btree_cmp_iters
+*/
+
+#include <stdint.h>
+#include <stddef.h>
+
+/*
+ * Maximum number of items per node.
+ * The maximum number of branches is BTREE_ITEM_MAX + 1.
+ */
+#define BTREE_ITEM_MAX 20
+
+struct btree_node {
+       struct btree_node *parent;
+       
+       /* Number of items (rather than branches). */
+       unsigned char count;
+       
+       /* 0 if node is a leaf, 1 if it has leaf children, etc. */
+       unsigned char depth;
+       
+       /* node->parent->branch[node->k] == this */
+       unsigned char k;
+       
+       const void *item[BTREE_ITEM_MAX];
+       
+       /*
+        * Allocated to BTREE_ITEM_MAX+1 items if this is
+        * an internal node, 0 items if it is a leaf.
+        */
+       struct btree_node *branch[];
+};
+
+typedef struct btree_iterator_s {
+       struct btree *btree;
+       struct btree_node *node;
+       unsigned int k;
+       
+       /*
+        * The relationship between item and (node, k) depends on what function
+        * set it.  It is mainly for convenience.
+        */
+       void *item;
+} btree_iterator[1];
+
+/*
+ * Instead of a compare function, this library accepts a binary search function
+ * to know how to order the items.
+ */
+typedef unsigned int btree_search_proto(
+       const void *key,
+       const void * const *base,
+       unsigned int count,
+       int lr,
+       int *found
+);
+typedef btree_search_proto *btree_search_t;
+
+/*
+ * Callback used by btree_delete() and btree_walk...().
+ *
+ * If it returns 0, it causes btree_walk...() to stop traversing and return 0.
+ * Thus, in normal circumstances, this callback should return 1.
+ *
+ * Callback shall not insert/remove items from the btree being traversed,
+ * nor shall anything modify it during a walk.
+ */
+typedef int (*btree_action_t)(void *item, void *ctx);
+
+struct btree {
+       struct btree_node *root;
+       size_t count; /* Total number of items in B-tree */
+       
+       btree_search_t search;
+       
+       /*
+        * These are set to NULL by default.
+        *
+        * When destroy is not NULL, it is called on each item in order when
+        * btree_delete() is called.
+        *
+        * When destroy is NULL, btree_delete runs faster because it does not have
+        * to visit each and every item.
+        */
+       btree_action_t destroy;
+       void *destroy_ctx;
+};
+
+struct btree *btree_new(btree_search_t search);
+void btree_delete(struct btree *btree);
+
+
+/* lr must be 0 or 1, nothing else. */
+int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr);
+int btree_find_lr(const struct btree *btree, const void *key,
+                               btree_iterator iter, int lr);
+
+int btree_walk_backward(const struct btree *btree,
+                               btree_action_t action, void *ctx);
+int btree_walk_forward(const struct btree *btree,
+                               btree_action_t action, void *ctx);
+
+#define btree_begin(btree, iter) btree_begin_end_lr(btree, iter, 0)
+#define btree_end(btree, iter) btree_begin_end_lr(btree, iter, 1)
+
+int btree_prev(btree_iterator iter);
+int btree_next(btree_iterator iter);
+
+#define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
+
+/*
+ * If key was found, btree_find_first will return 1, iter->item will be the
+ * first matching item, and iter will point to the beginning of the matching
+ * items.
+ *
+ * If key was not found, btree_find_first will return 0, iter->item will be
+ * undefined, and iter will point to where the key should go if inserted.
+ */
+#define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
+
+/*
+ * If key was found, btree_find_last will return 1, iter->item will be the
+ * last matching item, and iter will point to the end of the matching
+ * items.
+ *
+ * If key was not found, btree_find_last will return 0, iter->item will be
+ * undefined, and iter will point to where the key should go if inserted.
+ */
+#define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
+
+/* btree_find is an alias of btree_find_first. */
+#define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
+
+/*
+ * If iter points to an item, btree_deref returns 1 and sets iter->item to the
+ * item it points to.
+ *
+ * Otherwise (if iter points to the end of the btree), btree_deref returns 0
+ * and leaves iter untouched.
+ */
+int btree_deref(btree_iterator iter);
+
+/*
+ * Inserts the item before the one pointed to by iter.
+ *
+ * Insertion invalidates all iterators to the btree, including the one
+ * passed to btree_insert_at.  Nevertheless, iter->item will be set to
+ * the item inserted.
+ */
+void btree_insert_at(btree_iterator iter, const void *item);
+
+/*
+ * Removes the item pointed to by iter.  Returns 1 if iter pointed
+ * to an item.  Returns 0 if iter pointed to the end, in which case
+ * it leaves iter intact.
+ *
+ * Removal invalidates all iterators to the btree, including the one
+ * passed to btree_remove_at.  Nevertheless, iter->item will be set to
+ * the item removed.
+ */
+int btree_remove_at(btree_iterator iter);
+
+/*
+ * Compares positions of two iterators.
+ *
+ * Returns -1 if a is before b, 0 if a is at the same position as b,
+ * and +1 if a is after b.
+ */
+int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
+
+#define btree_search_implement(name, type, setup, equals, lessthan) \
+unsigned int name(const void *__key, \
+               const void * const *__base, unsigned int __count, \
+               int __lr, int *__found) \
+{ \
+       unsigned int __start = 0; \
+       while (__count) { \
+               unsigned int __middle = __count >> 1; \
+               type a = (type)__key; \
+               type b = (type)__base[__start + __middle]; \
+               { \
+                       setup; \
+                       if (equals) \
+                               goto __equals; \
+                       if (lessthan) \
+                               goto __lessthan; \
+               } \
+       __greaterthan: \
+               __start += __middle + 1; \
+               __count -= __middle + 1; \
+               continue; \
+       __equals: \
+               *__found = 1; \
+               if (__lr) \
+                       goto __greaterthan; \
+               /* else, fall through to __lessthan */ \
+       __lessthan: \
+               __count = __middle; \
+               continue; \
+       } \
+       return __start; \
+}
+
+#endif /* #ifndef CCAN_BTREE_H */

diff --git a/ccan/btree/test/run-benchmark.c b/ccan/btree/test/run-benchmark.c
new file mode 100644 (file)
index 0000000..62e59f8
--- /dev/null
+++ b/ccan/btree/test/run-benchmark.c
@@ -0,0 +1,348 @@
+/* Include the main header first, to test it works */
+#include <ccan/btree/btree.h>
+/* Include the C files directly. */
+#include <ccan/btree/btree.c>
+#include <ccan/tap/tap.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+uint32_t rand32_state = 0;
+
+/*
+ * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
+ * Uses the BCPL linear congruential generator method.
+ */
+static uint32_t rand32(void)
+{
+       rand32_state *= (uint32_t)0x7FF8A3ED;
+       rand32_state += (uint32_t)0x2AA01D31;
+       return rand32_state;
+}
+
+static void scramble(void *base, size_t nmemb, size_t size)
+{
+       char *i = base;
+       char *o;
+       size_t sd;
+       for (;nmemb>1;nmemb--) {
+               o = i + size*(rand32()%nmemb);
+               for (sd=size;sd--;) {
+                       char tmp = *o;
+                       *o++ = *i;
+                       *i++ = tmp;
+               }
+       }
+}
+
+struct test_item {
+       size_t key;
+       uint32_t value;
+};
+
+/* For ordering a btree of test_item pointers. */
+static btree_search_implement (
+       order_by_key,
+       const struct test_item *,
+       ,
+       a == b,
+       a < b
+)
+
+/* For qsorting an array of test_item pointers. */
+static int compare_test_item(const void *ap, const void *bp)
+{
+       const struct test_item *a = *(const struct test_item * const*)ap;
+       const struct test_item *b = *(const struct test_item * const*)bp;
+       if (a == b)
+               return 0;
+       if (a < b)
+               return -1;
+       return 1;
+}
+
+/*
+ * If lr == 0, make sure iter points to the item given.
+ * If lr == 1, make sure iter points to after the item given.
+ */
+static int check_iter(btree_iterator iter_orig, const void *item, int lr)
+{
+       btree_iterator iter = {*iter_orig};
+       if (iter->item != item)
+               return 0;
+       if (lr) {
+               if (!btree_prev(iter))
+                       return 0;
+       } else {
+               if (!btree_deref(iter))
+                       return 0;
+       }
+       if (iter->item != item)
+               return 0;
+       if (iter->node->item[iter->k] != iter->item)
+               return 0;
+       
+       return 1;
+}
+
+/*
+ * Returns 1 on insert, 0 on duplicate,
+ * -1 on bad iterator returned by find, and
+ * -2 on bad iterator returned by insert.
+ */
+static int insert_test_item(struct btree *btree, struct test_item *item)
+{
+       btree_iterator iter;
+       int lr;
+       
+       /* Find the first or last matching item, randomly choosing between the two. */
+       lr = rand32() & 1;
+       if (btree_find_lr(btree, item, iter, lr)) {
+               if (!check_iter(iter, item, lr))
+                       return -1;
+               return 0;
+       }
+       
+       btree_insert_at(iter, item);
+       
+       if (iter->item != item)
+               return -2;
+       
+       return 1;
+}
+
+/*
+ * Returns 1 on remove, 0 on missing,
+ * -1 on bad iterator returned by find, and
+ * -2 on bad iterator returned by remove.
+ */
+static int remove_test_item(struct btree *btree, struct test_item *item)
+{
+       btree_iterator iter;
+       
+       if (!btree_find(btree, item, iter))
+               return 0;
+       
+       if (!check_iter(iter, item, 0))
+               return -1;
+       
+       btree_remove_at(iter);
+       
+       if (iter->item != item)
+               return -2;
+       
+       return 1;
+}
+
+static struct {
+       size_t success;
+       
+       size_t excess;
+       size_t duplicate;
+       size_t missing;
+       size_t incorrect;
+       size_t failed;
+       
+       size_t bad_iter_find;
+       size_t bad_iter_insert;
+       size_t bad_iter_remove;
+       size_t bad_iter_next;
+} stats;
+
+static void clear_stats(void) {
+       memset(&stats, 0, sizeof(stats));
+}
+
+static int print_stats(const char *success_label, size_t expected_success) {
+       int failed = 0;
+       
+       printf("      %s:  \t%zu\n", success_label, stats.success);
+       if (stats.success != expected_success)
+               failed = 1;
+       
+       if (stats.excess)
+               failed = 1, printf("      Excess:     \t%zu\n", stats.excess);
+       if (stats.duplicate)
+               failed = 1, printf("      Duplicate:  \t%zu\n", stats.duplicate);
+       if (stats.missing)
+               failed = 1, printf("      Missing:    \t%zu\n", stats.missing);
+       if (stats.incorrect)
+               failed = 1, printf("      Incorrect:  \t%zu\n", stats.incorrect);
+       if (stats.failed)
+               failed = 1, printf("      Failed:     \t%zu\n", stats.failed);
+       
+       if (stats.bad_iter_find || stats.bad_iter_insert ||
+           stats.bad_iter_remove || stats.bad_iter_next) {
+               failed = 1;
+               printf("      Bad iterators yielded by:\n");
+               if (stats.bad_iter_find)
+                       printf("          btree_find_lr(): %zu\n", stats.bad_iter_find);
+               if (stats.bad_iter_insert)
+                       printf("          btree_insert_at(): %zu\n", stats.bad_iter_insert);
+               if (stats.bad_iter_remove)
+                       printf("          btree_remove_at(): %zu\n", stats.bad_iter_remove);
+               if (stats.bad_iter_next)
+                       printf("          btree_next(): %zu\n", stats.bad_iter_next);
+       }
+       
+       return !failed;
+}
+
+static void benchmark(size_t max_per_trial, size_t round_count, int random_counts)
+{
+       struct test_item **test_item;
+       struct test_item *test_item_array;
+       size_t i, count;
+       size_t round = 0;
+       
+       test_item = malloc(max_per_trial * sizeof(*test_item));
+       test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
+       
+       if (!test_item || !test_item_array) {
+               fail("Not enough memory for %zu keys per trial\n",
+                       max_per_trial);
+               return;
+       }
+       
+       /* Initialize test_item pointers. */
+       for (i=0; i<max_per_trial; i++)
+               test_item[i] = &test_item_array[i];
+       
+       /*
+        * If round_count is not zero, run round_count trials.
+        * Otherwise, run forever.
+        */
+       for (round = 1; round_count==0 || round <= round_count; round++) {
+               struct btree *btree;
+               btree_iterator iter;
+               
+               printf("Round %zu\n", round);
+               
+               if (random_counts)
+                       count = rand32() % (max_per_trial+1);
+               else
+                       count = max_per_trial;
+               
+               /*
+                * Initialize test items by giving them sequential keys and
+                * random values. Scramble them so the order of insertion
+                * will be random.
+                */
+               for (i=0; i<count; i++) {
+                       test_item[i]->key = i;
+                       test_item[i]->value = rand32();
+               }
+               scramble(test_item, count, sizeof(*test_item));
+               
+               btree = btree_new(order_by_key);
+               
+               clear_stats();
+               printf("   Inserting %zu items...\n", count);
+               for (i=0; i<count; i++) {
+                       switch (insert_test_item(btree, test_item[i])) {
+                               case 1: stats.success++; break;
+                               case 0: stats.duplicate++; break;
+                               case -1: stats.bad_iter_find++; break;
+                               case -2: stats.bad_iter_insert++; break;
+                               default: stats.failed++; break;
+                       }
+               }
+               ok1(print_stats("Inserted", count));
+               
+               scramble(test_item, count, sizeof(*test_item));
+               
+               printf("   Finding %zu items...\n", count);
+               clear_stats();
+               for (i=0; i<count; i++) {
+                       int lr = rand32() & 1;
+                       
+                       if (!btree_find_lr(btree, test_item[i], iter, lr)) {
+                               stats.missing++;
+                               continue;
+                       }
+                       
+                       if (!check_iter(iter, test_item[i], lr)) {
+                               stats.bad_iter_find++;
+                               continue;
+                       }
+                       
+                       stats.success++;
+               }
+               ok1(print_stats("Retrieved", count));
+               
+               qsort(test_item, count, sizeof(*test_item), compare_test_item);
+               
+               printf("   Traversing forward through %zu items...\n", count);
+               clear_stats();
+               i = 0;
+               for (btree_begin(btree, iter); btree_next(iter);) {
+                       if (i >= count) {
+                               stats.excess++;
+                               continue;
+                       }
+                       
+                       if (iter->item == test_item[i])
+                               stats.success++;
+                       else
+                               stats.incorrect++;
+                       
+                       i++;
+               }
+               ok1(print_stats("Retrieved", count));
+               
+               printf("   Traversing backward through %zu items...\n", count);
+               clear_stats();
+               i = count;
+               for (btree_end(btree, iter); btree_prev(iter);) {
+                       if (!i) {
+                               stats.excess++;
+                               continue;
+                       }
+                       i--;
+                       
+                       if (iter->item == test_item[i])
+                               stats.success++;
+                       else
+                               stats.incorrect++;
+               }
+               ok1(print_stats("Retrieved", count));
+               
+               ok1(btree->count == count);
+               
+               //static int remove_test_item(struct btree *btree, struct test_item *item);
+               scramble(test_item, count, sizeof(*test_item));
+               
+               printf("   Deleting %zu items...\n", count);
+               clear_stats();
+               for (i=0; i<count; i++) {
+                       int s = remove_test_item(btree, test_item[i]);
+                       if (s != 1)
+                               printf("remove_test_item failed\n");
+                       switch (s) {
+                               case 1: stats.success++; break;
+                               case 0: stats.missing++; break;
+                               case -1: stats.bad_iter_find++; break;
+                               case -2: stats.bad_iter_remove++; break;
+                               default: stats.failed++; break;
+                       }
+               }
+               ok1(btree->count == 0);
+               ok1(print_stats("Deleted", count));
+               ok1(btree->root->depth == 0 && btree->root->count == 0);
+               
+               btree_delete(btree);
+       }
+       
+       free(test_item);
+       free(test_item_array);
+}
+
+int main(void)
+{
+       plan_tests(32);
+       
+       benchmark(300000, 4, 0);
+       
+       return exit_status();
+}

diff --git a/ccan/btree/test/run-random-access.c b/ccan/btree/test/run-random-access.c
new file mode 100644 (file)
index 0000000..ab9d33e
--- /dev/null
+++ b/ccan/btree/test/run-random-access.c
@@ -0,0 +1,387 @@
+/* Include the main header first, to test it works */
+#include <ccan/btree/btree.h>
+/* Include the C files directly. */
+#include <ccan/btree/btree.c>
+#include <ccan/tap/tap.h>
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static uint32_t rand32_state = 0;
+
+/*
+ * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
+ * Uses the BCPL linear congruential generator method.
+ */
+static uint32_t rand32(void)
+{
+       rand32_state *= (uint32_t)0x7FF8A3ED;
+       rand32_state += (uint32_t)0x2AA01D31;
+       return rand32_state;
+}
+
+/*
+ * Whether or not to add/remove multiple equal keys to the tree.
+ *
+ * Tests are run with multi set to 0 and 1.
+ */
+static int multi = 0;
+
+static struct {
+       struct {
+               size_t success;
+               size_t failure;
+       } insert, remove, find, traverse;
+} stats;
+
+static int check_stats(void) {
+       return
+               stats.insert.failure == 0 &&
+               stats.remove.failure == 0 &&
+               stats.find.failure == 0 &&
+               stats.traverse.failure == 0;
+}
+
+static int print_stats(void) {
+       printf("Insert:  %zu succeeded, %zu failed\n",
+               stats.insert.success, stats.insert.failure);
+       
+       printf("Remove:  %zu succeeded, %zu failed\n",
+               stats.remove.success, stats.remove.failure);
+       
+       printf("Find:  %zu succeeded, %zu failed\n",
+               stats.find.success, stats.find.failure);
+       
+       printf("Traverse:  %zu succeeded, %zu failed\n",
+               stats.traverse.success, stats.traverse.failure);
+       
+       return check_stats();
+}
+
+static void clear_stats(void)
+{
+       memset(&stats, 0, sizeof(stats));
+}
+
+static int test_node_consistency(struct btree_node *node, struct btree_node *parent, size_t *count)
+{
+       unsigned int i, j, e = node->count;
+       
+       /* Verify parent, depth, and k */
+       if (node->parent != parent)
+               return 0;
+       if (parent) {
+               if (node->depth != parent->depth - 1)
+                       return 0;
+               if (node != parent->branch[node->k])
+                       return 0;
+       }
+       
+       /* Nodes must not be empty (unless the entire tree is empty). */
+       if (e == 0)
+               return 0;
+       
+       if (node->depth) {
+               /* Make sure child branches aren't duplicated or NULL. */
+               for (i=0; i<=e; i++) {
+                       if (node->branch[i] == NULL)
+                               return 0;
+                       for (j=i+1; j<=e; j++)
+                               if (node->branch[i] == node->branch[j])
+                                       return 0;
+               }
+               
+               /* Recursively check children. */
+               for (i=0; i<=e; i++) {
+                       if (!test_node_consistency(node->branch[i], node, count))
+                               return 0;
+               }
+       }
+       
+       *count += node->count;
+       return 1;
+}
+
+static int test_consistency(const struct btree *btree)
+{
+       size_t count = 0;
+       if (!btree->root)
+               return 0;
+       if (btree->root->count == 0) {
+               if (btree->count != 0)
+                       return 0;
+               return 1;
+       }
+       if (btree->count == 0)
+               return 0;
+       if (!test_node_consistency(btree->root, NULL, &count))
+               return 0;
+       if (btree->count != count)
+               return 0;
+       return 1;
+}
+
+static int test_traverse(struct btree *btree, size_t key[], size_t count)
+{
+       btree_iterator iter;
+       size_t i, j;
+       
+       if (!test_consistency(btree))
+               return 0;
+       
+       /* Forward */
+       i = 0;
+       btree_begin(btree, iter);
+       for (;;) {
+               while (i < count && key[i] == 0)
+                       i++;
+               if (i >= count) {
+                       if (btree_next(iter))
+                               return 0;
+                       break;
+               }
+               for (j = 0; j < key[i] && btree_next(iter); j++) {
+                       if (iter->item != &key[i])
+                               return 0;
+               }
+               if (j != key[i])
+                       return 0;
+               i++;
+       }
+       
+       /* Backward */
+       i = count;
+       btree_end(btree, iter);
+       for (;;) {
+               while (i > 0 && key[i-1] == 0)
+                       i--;
+               if (i <= 0) {
+                       if (btree_prev(iter))
+                               return 0;
+                       break;
+               }
+               for (j = 0; j < key[i-1] && btree_prev(iter); j++) {
+                       if (iter->item != &key[i-1])
+                               return 0;
+               }
+               if (j != key[i-1])
+                       return 0;
+               i--;
+       }
+       
+       return 1;
+}
+
+/*
+ * Finds and counts items matching &key[k], then makes sure the count
+ * equals key[k].  Also verifies that btree_find_... work as advertised.
+ */
+static int find(struct btree *btree, size_t key[], size_t k)
+{
+       btree_iterator iter, tmp;
+       size_t count;
+       int found;
+       
+       memset(iter, 0, sizeof(iter));
+       memset(tmp, 0, sizeof(tmp));
+       
+       found = btree_find_first(btree, &key[k], iter);
+       if (iter->btree != btree)
+               return 0;
+       if (found != !!key[k])
+               return 0;
+       if (key[k] && iter->item != &key[k])
+               return 0;
+       
+       /* Make sure btree_find works exactly the same as btree_find_first. */
+       if (btree_find(btree, &key[k], tmp) != found)
+               return 0;
+       if (memcmp(iter, tmp, sizeof(*iter)))
+               return 0;
+       
+       /* Make sure previous item doesn't match. */
+       *tmp = *iter;
+       if (btree_prev(tmp)) {
+               if (tmp->item == &key[k])
+                       return 0;
+       }
+       
+       /* Count going forward. */
+       for (count=0; btree_deref(iter) && iter->item == &key[k]; count++, btree_next(iter))
+               {}
+       if (count != key[k])
+               return 0;
+       
+       /* Make sure next item doesn't match. */
+       *tmp = *iter;
+       if (btree_deref(tmp)) {
+               if (tmp->item == &key[k])
+                       return 0;
+       }
+       
+       /* Make sure iter is now equal to the end of matching items. */
+       btree_find_last(btree, &key[k], tmp);
+       if (tmp->btree != btree)
+               return 0;
+       if (btree_cmp_iters(iter, tmp))
+               return 0;
+       
+       /* Count going backward. */
+       for (count=0; btree_prev(iter); count++) {
+               if (iter->item != &key[k]) {
+                       btree_next(iter);
+                       break;
+               }
+       }
+       if (count != key[k])
+               return 0;
+       
+       /* Make sure iter is now equal to the beginning of matching items. */
+       btree_find_first(btree, &key[k], tmp);
+       if (tmp->btree != btree)
+               return 0;
+       if (btree_cmp_iters(iter, tmp))
+               return 0;
+       
+       return 1;
+}
+
+static int test_find(struct btree *btree, size_t key[], size_t count)
+{
+       size_t k = rand32() % count;
+       return find(btree, key, k);
+}
+
+static int test_remove(struct btree *btree, size_t key[], size_t count)
+{
+       size_t prev_count = btree->count;
+       size_t k = rand32() % count;
+       btree_iterator iter;
+       
+       if (!find(btree, key, k))
+               return 0;
+       
+       btree_find(btree, &key[k], iter);
+       
+       //remove (if present), and make sure removal status is correct
+       if (key[k]) {
+               if (btree_remove_at(iter) != 1)
+                       return 0;
+               if (btree->count != prev_count - 1)
+                       return 0;
+               key[k]--;
+               
+               if (!find(btree, key, k))
+                       return 0;
+       }
+       
+       return 1;
+}
+
+static int test_insert(struct btree *btree, size_t key[], size_t count)
+{
+       size_t k = rand32() % count;
+       btree_iterator iter;
+       size_t prev_count = btree->count;
+       int found;
+       
+       if (!find(btree, key, k))
+               return 0;
+       
+       /* Make sure key's presense is consistent with our array. */
+       found = btree_find_first(btree, &key[k], iter);
+       if (key[k]) {
+               if (!found || iter->item != &key[k])
+                       return 0;
+               if (!btree_deref(iter))
+                       return 0;
+               if (iter->k >= iter->node->count || iter->node->item[iter->k] != &key[k])
+                       return 0;
+       } else {
+               if (found)
+                       return 0;
+       }
+       
+       /* Insert if item hasn't been yet (or if we're in multi mode). */
+       if (!key[k] || multi) {
+               btree_insert_at(iter, &key[k]);
+               key[k]++;
+               if (btree->count != prev_count + 1)
+                       return 0;
+       }
+       
+       /* Check result iterator's ->item field. */
+       if (iter->item != &key[k])
+               return 0;
+       
+       if (!find(btree, key, k))
+               return 0;
+       
+       /* Make sure key is present and correct now. */
+       found = btree_find_first(btree, &key[k], iter);
+       if (!found || iter->item != &key[k])
+               return 0;
+       
+       return 1;
+}
+
+static btree_search_implement(order_by_ptr, size_t*, , a == b, a < b)
+
+static void stress(size_t count, size_t trials)
+{
+       struct btree *btree = btree_new(order_by_ptr);
+       size_t *key = calloc(count, sizeof(*key));
+       size_t i;
+       
+       clear_stats();
+       
+       for (i=0; i<trials; i++) {
+               unsigned int n = rand32() % 65536;
+               unsigned int rib = btree->count * 43688 / count;
+                       //remove/insert boundary
+               if (n >= 65534) {
+                       if (test_traverse(btree, key, count))
+                               stats.traverse.success++;
+                       else
+                               stats.traverse.failure++;
+               } else if (n >= 46388) {
+                       if (test_find(btree, key, count))
+                               stats.find.success++;
+                       else
+                               stats.find.failure++;
+               } else if (n < rib) {
+                       if (test_remove(btree, key, count))
+                               stats.remove.success++;
+                       else
+                               stats.remove.failure++;
+               } else {
+                       if (test_insert(btree, key, count))
+                               stats.insert.success++;
+                       else
+                               stats.insert.failure++;
+               }
+       }
+       
+       free(key);
+       btree_delete(btree);
+       
+       print_stats();
+       ok1(check_stats());
+}
+
+int main(void)
+{
+       plan_tests(2);
+       
+       multi = 0;
+       printf("Running with multi = %d\n", multi);
+       stress(100000, 500000);
+       
+       multi = 1;
+       printf("Running with multi = %d\n", multi);
+       stress(100000, 500000);
+       
+       return exit_status();
+}

diff --git a/ccan/btree/test/run-search-implement.c b/ccan/btree/test/run-search-implement.c
new file mode 100644 (file)
index 0000000..631e5bf
--- /dev/null
+++ b/ccan/btree/test/run-search-implement.c
@@ -0,0 +1,161 @@
+/* Include the main header first, to test it works */
+#include <ccan/btree/btree.h>
+/* Include the C files directly. */
+#include <ccan/btree/btree.c>
+#include <ccan/tap/tap.h>
+
+#include <string.h>
+
+#ifndef ARRAY_SIZE
+#define ARRAY_SIZE(array) (sizeof(array) / sizeof(*(array)))
+#endif
+
+struct foo {
+       const char *string;
+       int number;
+};
+
+struct foo foo_structs[] = {
+       {"apple", 1},
+       {"banana", 2},
+       {"banana", 4},
+       {"cherry", 4},
+       {"doughnut", 5},
+};
+
+struct foo *foo_base[ARRAY_SIZE(foo_structs)];
+const unsigned int foo_count = ARRAY_SIZE(foo_structs);
+
+static void init_foo_pointers(void)
+{
+       unsigned int i;
+       
+       for (i = 0; i < foo_count; i++)
+               foo_base[i] = &foo_structs[i];
+}
+
+/* Make sure forward declarations work */
+btree_search_proto order_by_string, order_by_number;
+
+static void test_order_by_string(void)
+{
+       struct {
+               const char *key;
+               int lr;
+               unsigned int expect_offset;
+               int expect_found;
+       } test[] = {
+               {"anchovies", 0, 0, 0},
+               {"anchovies", 1, 0, 0},
+               {"apple", 0, 0, 1},
+               {"apple", 1, 1, 1},
+               {"banana", 0, 1, 1},
+               {"banana", 1, 3, 1},
+               {"blueberry", 0, 3, 0},
+               {"blueberry", 1, 3, 0},
+               {"doughnut", 0, 4, 1},
+               {"doughnut", 1, 5, 1},
+       };
+       
+       size_t i;
+       for (i=0; i<ARRAY_SIZE(test); i++) {
+               struct foo foo = {test[i].key, 0};
+               unsigned int offset;
+               int found = 0;
+               
+               offset = order_by_string(&foo, (void*)foo_base, foo_count,
+                                               test[i].lr, &found);
+               
+               ok1(offset == test[i].expect_offset && found == test[i].expect_found);
+       }
+}
+
+static void test_empty(void)
+{
+       unsigned int offset;
+       int found;
+       struct foo key = {"apple", -1};
+       
+       offset = order_by_string(&key, NULL, 0, 0, &found);
+       ok1(offset == 0);
+       
+       offset = order_by_string(&key, NULL, 0, 1, &found);
+       ok1(offset == 0);
+       
+       offset = order_by_number(&key, NULL, 0, 0, &found);
+       ok1(offset == 0);
+       
+       offset = order_by_number(&key, NULL, 0, 1, &found);
+       ok1(offset == 0);
+}
+
+static void test_order_by_number(void)
+{
+       struct {
+               int key;
+               int lr;
+               unsigned int expect_offset;
+               int expect_found;
+       } test[] = {
+               {-2, 0, 0, 0},
+               {-2, 1, 0, 0},
+               {-1, 0, 0, 0},
+               {-1, 1, 0, 0},
+               {0, 0, 0, 0},
+               {0, 1, 0, 0},
+               {1, 0, 0, 1},
+               {1, 1, 1, 1},
+               {2, 0, 1, 1},
+               {2, 1, 2, 1},
+               {4, 0, 2, 1},
+               {4, 1, 4, 1},
+               {3, 0, 2, 0},
+               {3, 1, 2, 0},
+               {5, 0, 4, 1},
+               {5, 1, 5, 1},
+               {6, 0, 5, 0},
+               {6, 1, 5, 0},
+               {7, 0, 5, 0},
+               {7, 1, 5, 0},
+       };
+       
+       size_t i;
+       for (i=0; i<ARRAY_SIZE(test); i++) {
+               struct foo foo = {"", test[i].key};
+               unsigned int offset;
+               int found = 0;
+               
+               offset = order_by_number(&foo, (void*)foo_base, foo_count,
+                                               test[i].lr, &found);
+               
+               ok1(offset == test[i].expect_offset && found == test[i].expect_found);
+       }
+}
+
+int main(void)
+{
+       plan_tests(34);
+       init_foo_pointers();
+       
+       test_order_by_string();
+       test_order_by_number();
+       test_empty();
+       
+       return exit_status();
+}
+
+btree_search_implement (
+       order_by_string,
+       const struct foo *,
+       int c = strcmp(a->string, b->string),
+       c == 0,
+       c < 0
+)
+
+btree_search_implement (
+       order_by_number,
+       const struct foo *,
+       ,
+       a->number == b->number,
+       a->number < b->number
+)

diff --git a/ccan/btree/test/run-trivial.c b/ccan/btree/test/run-trivial.c
new file mode 100644 (file)
index 0000000..6992bf6
--- /dev/null
+++ b/ccan/btree/test/run-trivial.c
@@ -0,0 +1,357 @@
+/* Include the main header first, to test it works */
+#include <ccan/btree/btree.h>
+/* Include the C files directly. */
+#include <ccan/btree/btree.c>
+#include <ccan/tap/tap.h>
+
+#include <string.h>
+
+struct test_item {
+       int key;
+       int value;
+};
+
+static btree_search_implement(
+       order_by_key,
+       struct test_item *,
+       ,
+       a->key == b->key,
+       a->key < b->key
+)
+
+static int insert_test_item(struct btree *btree, int key, int value)
+{
+       struct test_item key_item = {key, -101};
+       struct test_item *item;
+       btree_iterator iter;
+       
+       if (btree_find_first(btree, &key_item, iter)) {
+               /* Don't insert new item, but do update its value. */
+               item = iter->item;
+               item->value = value;
+               return 0;
+       }
+       
+       item = malloc(sizeof(*item));
+       item->key = key;
+       item->value = value;
+       
+       btree_insert_at(iter, item);
+       
+       return 1;
+}
+
+static int lookup_test_item(const struct btree *btree, int key)
+{
+       struct test_item key_item = {key, -102};
+       struct test_item *item;
+       btree_iterator iter;
+       
+       if (!btree_find_first(btree, &key_item, iter))
+               return -100;
+       
+       item = iter->item;
+       return item->value;
+}
+
+static int destroy_test_item(void *item, void *ctx) {
+       (void) ctx;
+       free(item);
+       return 1;
+}
+
+struct test_insert_entry {
+       int key;
+       int value;
+       int expected_return;
+};
+
+struct test_traverse_entry {
+       int key;
+       int value;
+};
+
+static void print_indent(unsigned int indent) {
+       while (indent--)
+               fputs("\t", stdout);
+}
+
+static void btree_node_trace(struct btree_node *node, unsigned int indent)
+{
+       unsigned int i;
+       for (i=0; i<node->count; i++) {
+               if (node->depth)
+                       btree_node_trace(node->branch[i], indent+1);
+               print_indent(indent);
+               puts(node->item[i]);
+       }
+       if (node->depth)
+               btree_node_trace(node->branch[node->count], indent+1);
+}
+
+static void btree_trace(struct btree *btree)
+{
+       btree_node_trace(btree->root, 0);
+}
+
+static void test_insert(struct btree *btree)
+{
+       struct test_insert_entry ent[] = {
+               {3, 1, 1}, {4, 1, 1}, {5, 9, 1}, {2, 6, 1}, {5, 3, 0}, {5, 8, 0},
+               {9, 7, 1}, {9, 3, 0}, {2, 3, 0}, {8, 4, 1}, {6, 2, 1}, {6, 4, 0},
+               {3, 3, 0}, {8, 3, 0}, {2, 7, 0}, {9, 5, 0}, {0, 2, 1}, {8, 8, 0},
+               {4, 1, 0}, {9, 7, 0}, {1, 6, 1}, {9, 3, 0}, {9, 9, 0}, {3, 7, 0},
+               {5, 1, 0}, {0, 5, 0}, {8, 2, 0}, {0, 9, 0}, {7, 4, 1}, {9, 4, 0},
+               {4, 5, 0}, {9, 2, 0}
+       };
+       size_t i, count = sizeof(ent) / sizeof(*ent);
+       
+       for (i = 0; i < count; i++) {
+               int ret = insert_test_item(btree, ent[i].key, ent[i].value);
+               ok1(ret == ent[i].expected_return);
+       }
+}
+
+static void test_find_traverse(struct btree *btree)
+{
+       struct test_traverse_entry ent[] = {
+               {0, 9}, {1, 6}, {2, 7}, {3, 7}, {4, 5},
+               {5, 1}, {6, 4}, {7, 4}, {8, 2}, {9, 2}
+       };
+       size_t i, count = sizeof(ent) / sizeof(*ent);
+       btree_iterator iter;
+       
+       i = 0;
+       for (btree_begin(btree, iter); btree_next(iter);) {
+               struct test_item *item = iter->item;
+               
+               if (i >= count) {
+                       fail("Too many items in btree according to forward traversal");
+                       break;
+               }
+               
+               ok1(lookup_test_item(btree, item->key) == item->value);
+               ok1(item->key == ent[i].key && item->value == ent[i].value);
+               
+               i++;
+       }
+       
+       if (i != count)
+               fail("Not enough items in btree according to forward traversal");
+       
+       i = count;
+       for (btree_end(btree, iter); btree_prev(iter);) {
+               struct test_item *item = iter->item;
+               
+               if (!i--) {
+                       fail("Too many items in btree according to backward traversal");
+                       break;
+               }
+               
+               ok1(lookup_test_item(btree, item->key) == item->value);
+               ok1(item->key == ent[i].key && item->value == ent[i].value);
+       }
+       
+       if (i != 0)
+               fail("Not enough items in btree according to backward traversal");
+}
+
+static btree_search_proto order_by_string;
+
+static btree_search_implement(
+       order_by_string, //function name
+       const char*, //key type
+       int c = strcmp(a, b), //setup
+       c == 0, // a == b predicate
+       c < 0 // a < b predicate
+)
+
+//used in the test case to sort the test strings
+static int compare_by_string(const void *ap, const void *bp)
+{
+       const char * const *a = ap;
+       const char * const *b = bp;
+       return strcmp(*a, *b);
+}
+
+static void test_traverse(struct btree *btree, const char *sorted[], size_t count)
+{
+       btree_iterator iter, iter2;
+       size_t i;
+       
+       i = 0;
+       for (btree_begin(btree, iter); btree_next(iter);) {
+               if (i >= count) {
+                       fail("Too many items in btree according to forward traversal");
+                       break;
+               }
+               
+               ok1(iter->item == sorted[i]);
+               
+               btree_find_first(btree, sorted[i], iter2);
+               ok1(iter2->item == sorted[i]);
+               
+               i++;
+       }
+       
+       if (i != count)
+               fail("Not enough items in btree according to forward traversal");
+       
+       i = count;
+       for (btree_end(btree, iter); btree_prev(iter);) {
+               if (!i--) {
+                       fail("Too many items in btree according to backward traversal");
+                       break;
+               }
+               
+               ok1(iter->item == sorted[i]);
+               
+               btree_find_first(btree, sorted[i], iter2);
+               ok1(iter2->item == sorted[i]);
+       }
+       
+       if (i != 0)
+               fail("Not enough items in btree according to backward traversal");
+}
+
+#if 0
+//(tries to) remove the key from both the btree and the test array.  Returns 1 on success, 0 on failure.
+//success is when an item is removed from the btree and the array, or when none is removed from either
+//failure is when an item is removed from the btree but not the array or vice versa
+//after removing, it tries removing again to make sure that removal returns 0
+static int test_remove(struct btree *btree, struct btree_item items[], size_t *count, const char *key)
+{
+       size_t i;
+       
+       for (i = *count; i--;) {
+               if (!strcmp(items[i].key, key)) {
+                       //item found in array
+                       memmove(&items[i], &items[i+1], (*count-(i+1))*sizeof(*items));
+                       (*count)--;
+                       
+                       //puts("----------");
+                       //btree_trace(btree);
+                       
+                       //removal should succeed, as the key should be there
+                       //this is not a contradiction; the test is performed twice
+                       return btree_remove(btree, key) && !btree_remove(btree, key);
+               }
+       }
+       
+       //removal should fail, as the key should not be there
+       //this is not redundant; the test is performed twice
+       return !btree_remove(btree, key) && !btree_remove(btree, key);
+}
+#endif
+
+static void test_search_implement(void)
+{
+       struct btree *btree = btree_new(order_by_string);
+       size_t i;
+       
+       const char *unsorted[] = {
+               "md4",
+               "isaac",
+               "noerr",
+               "talloc_link",
+               "asearch",
+               "tap",
+               "crcsync",
+               "wwviaudio",
+               "array_size",
+               "alignof",
+               "str",
+               "read_write_all",
+               "grab_file",
+               "out",
+               "daemonize",
+               "array",
+               "crc",
+               "str_talloc",
+               "build_assert",
+               "talloc",
+               "alloc",
+               "endian",
+               "btree",
+               "typesafe_cb",
+               "check_type",
+               "list",
+               "ciniparser",
+               "ilog",
+               "ccan_tokenizer",
+               "tdb",
+               "block_pool",
+               "sparse_bsearch",
+               "container_of",
+               "stringmap",
+               "hash",
+               "short_types",
+               "ogg_to_pcm",
+               "antithread",
+       };
+       size_t count = sizeof(unsorted) / sizeof(*unsorted);
+       const char *sorted[count];
+       
+       memcpy(sorted, unsorted, sizeof(sorted));
+       qsort(sorted, count, sizeof(*sorted), compare_by_string);
+       
+       for (i=0; i<count; i++) {
+               btree_iterator iter;
+               
+               if (btree_find_first(btree, unsorted[i], iter))
+                       fail("btree_insert thinks the test array has duplicates, but it doesn't");
+               else
+                       btree_insert_at(iter, unsorted[i]);
+       }
+       btree_trace(btree);
+       
+       test_traverse(btree, sorted, count);
+       
+       /*
+       //try removing items that should be in the tree
+       ok1(test_remove(btree, sorted, &count, "btree"));
+       ok1(test_remove(btree, sorted, &count, "ccan_tokenizer"));
+       ok1(test_remove(btree, sorted, &count, "endian"));
+       ok1(test_remove(btree, sorted, &count, "md4"));
+       ok1(test_remove(btree, sorted, &count, "asearch"));
+       ok1(test_remove(btree, sorted, &count, "alloc"));
+       ok1(test_remove(btree, sorted, &count, "build_assert"));
+       ok1(test_remove(btree, sorted, &count, "typesafe_cb"));
+       ok1(test_remove(btree, sorted, &count, "sparse_bsearch"));
+       ok1(test_remove(btree, sorted, &count, "stringmap"));
+       
+       //try removing items that should not be in the tree
+       ok1(test_remove(btree, sorted, &count, "java"));
+       ok1(test_remove(btree, sorted, &count, "openoffice"));
+       ok1(test_remove(btree, sorted, &count, "firefox"));
+       ok1(test_remove(btree, sorted, &count, "linux"));
+       ok1(test_remove(btree, sorted, &count, ""));
+       
+       //test the traversal again to make sure things are okay
+       test_traverse(btree, sorted, count);
+       
+       //remove the rest of the items, then make sure tree is empty
+       while (count)
+               ok1(test_remove(btree, sorted, &count, sorted[count-1].key));
+       ok1(btree->root == NULL);
+       */
+       
+       btree_delete(btree);
+}
+
+int main(void)
+{
+       struct btree *btree;
+       
+       plan_tests(224);
+       
+       btree = btree_new(order_by_key);
+       btree->destroy = destroy_test_item;
+       test_insert(btree);
+       test_find_traverse(btree);
+       btree_delete(btree);
+       
+       test_search_implement();
+       
+       return exit_status();
+}