avl: new module
authorRusty Russell <rusty@rustcorp.com.au>
Wed, 20 Oct 2010 05:40:16 +0000 (16:10 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Wed, 20 Oct 2010 05:40:16 +0000 (16:10 +1030)
ccan/avl/_info [new file with mode: 0644]
ccan/avl/avl.c [new file with mode: 0644]
ccan/avl/avl.h [new file with mode: 0644]
ccan/avl/test/run.c [new file with mode: 0644]

diff --git a/ccan/avl/_info b/ccan/avl/_info
new file mode 100644 (file)
index 0000000..0f1d89a
--- /dev/null
@@ -0,0 +1,81 @@
+#include <string.h>
+#include "config.h"
+
+/**
+ * avl - Key-value dictionary based on AVL trees
+ *
+ * A simple, well-tested implementation of AVL trees for mapping
+ * unique keys to values.  This implementation supports insertion,
+ * removal, lookup, and traversal.
+ *
+ * An AVL tree is a self-balancing binary tree that performs
+ * insertion, removal, and lookup in O(log n) time per operation.
+ *
+ * Example:
+ * #include <ccan/avl/avl.h>
+ * 
+ * #include <stdio.h>
+ * #include <stdlib.h>
+ * #include <string.h>
+ * 
+ * struct tally {
+ *     long count;
+ * };
+ * #define new_tally() calloc(1, sizeof(struct tally))
+ * 
+ * static void chomp(char *str)
+ * {
+ *     char *end = strchr(str, 0);
+ *     if (end > str && end[-1] == '\n')
+ *             end[-1] = 0;
+ * }
+ * 
+ * int main(void)
+ * {
+ *     AVL          *avl = avl_new((AvlCompare) strcmp);
+ *     AvlIter       i;
+ *     struct tally *tally;
+ *     char          line[256];
+ *     
+ *     while (fgets(line, sizeof(line), stdin))
+ *     {
+ *             chomp(line);
+ *             
+ *             tally = avl_lookup(avl, line);
+ *             if (tally == NULL)
+ *                     avl_insert(avl, strdup(line), tally = new_tally());
+ *             
+ *             tally->count++;
+ *     }
+ *     
+ *     avl_foreach(i, avl) {
+ *             char         *line  = i.key;
+ *             struct tally *tally = i.value;
+ *             
+ *             printf("% 5ld: %s\n", tally->count, line);
+ *             
+ *             free(line);
+ *             free(tally);
+ *     }
+ *     
+ *     avl_free(avl);
+ *     
+ *     return 0;
+ * }
+ *
+ * Licence: ISC
+ * Author: Joey Adams <joeyadams3.14159@gmail.com>
+ */
+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/avl/avl.c b/ccan/avl/avl.c
new file mode 100644 (file)
index 0000000..ccecda7
--- /dev/null
@@ -0,0 +1,442 @@
+/*
+ * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "avl.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+static AvlNode *mkNode(const void *key, const void *value);
+static void freeNode(AvlNode *node);
+
+static AvlNode *lookup(const AVL *avl, AvlNode *node, const void *key);
+
+static bool insert(AVL *avl, AvlNode **p, const void *key, const void *value);
+static bool remove(AVL *avl, AvlNode **p, const void *key, AvlNode **ret);
+static bool removeExtremum(AvlNode **p, int side, AvlNode **ret);
+
+static int sway(AvlNode **p, int sway);
+static void balance(AvlNode **p, int side);
+
+static bool checkBalances(AvlNode *node, int *height);
+static bool checkOrder(AVL *avl);
+static size_t countNode(AvlNode *node);
+
+/*
+ * Utility macros for converting between
+ * "balance" values (-1 or 1) and "side" values (0 or 1).
+ *
+ * bal(0)   == -1
+ * bal(1)   == +1
+ * side(-1) == 0
+ * side(+1) == 1
+ */
+#define bal(side) ((side) == 0 ? -1 : 1)
+#define side(bal) ((bal)  == 1 ?  1 : 0)
+
+static int sign(int cmp)
+{
+       if (cmp < 0)
+               return -1;
+       if (cmp == 0)
+               return 0;
+       return 1;
+}
+
+AVL *avl_new(AvlCompare compare)
+{
+       AVL *avl = malloc(sizeof(*avl));
+       
+       assert(avl != NULL);
+       
+       avl->compare = compare;
+       avl->root = NULL;
+       avl->count = 0;
+       return avl;
+}
+
+void avl_free(AVL *avl)
+{
+       freeNode(avl->root);
+       free(avl);
+}
+
+void *avl_lookup(const AVL *avl, const void *key)
+{
+       AvlNode *found = lookup(avl, avl->root, key);
+       return found ? (void*) found->value : NULL;
+}
+
+AvlNode *avl_lookup_node(const AVL *avl, const void *key)
+{
+       return lookup(avl, avl->root, key);
+}
+
+size_t avl_count(const AVL *avl)
+{
+       return avl->count;
+}
+
+bool avl_insert(AVL *avl, const void *key, const void *value)
+{
+       size_t old_count = avl->count;
+       insert(avl, &avl->root, key, value);
+       return avl->count != old_count;
+}
+
+bool avl_remove(AVL *avl, const void *key)
+{
+       AvlNode *node = NULL;
+       
+       remove(avl, &avl->root, key, &node);
+       
+       if (node == NULL) {
+               return false;
+       } else {
+               free(node);
+               return true;
+       }
+}
+
+static AvlNode *mkNode(const void *key, const void *value)
+{
+       AvlNode *node = malloc(sizeof(*node));
+       
+       assert(node != NULL);
+       
+       node->key = key;
+       node->value = value;
+       node->lr[0] = NULL;
+       node->lr[1] = NULL;
+       node->balance = 0;
+       return node;
+}
+
+static void freeNode(AvlNode *node)
+{
+       if (node) {
+               freeNode(node->lr[0]);
+               freeNode(node->lr[1]);
+               free(node);
+       }
+}
+
+static AvlNode *lookup(const AVL *avl, AvlNode *node, const void *key)
+{
+       int cmp;
+       
+       if (node == NULL)
+               return NULL;
+       
+       cmp = avl->compare(key, node->key);
+       
+       if (cmp < 0)
+               return lookup(avl, node->lr[0], key);
+       if (cmp > 0)
+               return lookup(avl, node->lr[1], key);
+       return node;
+}
+
+/*
+ * Insert a key/value into a subtree, rebalancing if necessary.
+ *
+ * Return true if the subtree's height increased.
+ */
+static bool insert(AVL *avl, AvlNode **p, const void *key, const void *value)
+{
+       if (*p == NULL) {
+               *p = mkNode(key, value);
+               avl->count++;
+               return true;
+       } else {
+               AvlNode *node = *p;
+               int      cmp  = sign(avl->compare(key, node->key));
+               
+               if (cmp == 0) {
+                       node->key = key;
+                       node->value = value;
+                       return false;
+               }
+               
+               if (!insert(avl, &node->lr[side(cmp)], key, value))
+                       return false;
+               
+               /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */
+               return sway(p, cmp) != 0;
+       }
+}
+
+/*
+ * Remove the node matching the given key.
+ * If present, return the removed node through *ret .
+ * The returned node's lr and balance are meaningless.
+ *
+ * Return true if the subtree's height decreased.
+ */
+static bool remove(AVL *avl, AvlNode **p, const void *key, AvlNode **ret)
+{
+       if (*p == NULL) {
+               return false;
+       } else {
+               AvlNode *node = *p;
+               int      cmp  = sign(avl->compare(key, node->key));
+               
+               if (cmp == 0) {
+                       *ret = node;
+                       avl->count--;
+                       
+                       if (node->lr[0] != NULL && node->lr[1] != NULL) {
+                               AvlNode *replacement;
+                               int      side;
+                               bool     shrunk;
+                               
+                               /* Pick a subtree to pull the replacement from such that
+                                * this node doesn't have to be rebalanced. */
+                               side = node->balance <= 0 ? 0 : 1;
+                               
+                               shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement);
+                               
+                               replacement->lr[0]   = node->lr[0];
+                               replacement->lr[1]   = node->lr[1];
+                               replacement->balance = node->balance;
+                               *p = replacement;
+                               
+                               if (!shrunk)
+                                       return false;
+                               
+                               replacement->balance -= bal(side);
+                               
+                               /* If tree's balance became 0, it means the tree's height shrank due to removal. */
+                               return replacement->balance == 0;
+                       }
+                       
+                       if (node->lr[0] != NULL)
+                               *p = node->lr[0];
+                       else
+                               *p = node->lr[1];
+                       
+                       return true;
+                       
+               } else {
+                       if (!remove(avl, &node->lr[side(cmp)], key, ret))
+                               return false;
+                       
+                       /* If tree's balance became 0, it means the tree's height shrank due to removal. */
+                       return sway(p, -cmp) == 0;
+               }
+       }
+}
+
+/*
+ * Remove either the left-most (if side == 0) or right-most (if side == 1)
+ * node in a subtree, returning the removed node through *ret .
+ * The returned node's lr and balance are meaningless.
+ *
+ * The subtree must not be empty (i.e. *p must not be NULL).
+ *
+ * Return true if the subtree's height decreased.
+ */
+static bool removeExtremum(AvlNode **p, int side, AvlNode **ret)
+{
+       AvlNode *node = *p;
+       
+       if (node->lr[side] == NULL) {
+               *ret = node;
+               *p = node->lr[1 - side];
+               return true;
+       }
+       
+       if (!removeExtremum(&node->lr[side], side, ret))
+               return false;
+       
+       /* If tree's balance became 0, it means the tree's height shrank due to removal. */
+       return sway(p, -bal(side)) == 0;
+}
+
+/*
+ * Rebalance a node if necessary.  Think of this function
+ * as a higher-level interface to balance().
+ *
+ * sway must be either -1 or 1, and indicates what was added to
+ * the balance of this node by a prior operation.
+ *
+ * Return the new balance of the subtree.
+ */
+static int sway(AvlNode **p, int sway)
+{
+       if ((*p)->balance != sway)
+               (*p)->balance += sway;
+       else
+               balance(p, side(sway));
+       
+       return (*p)->balance;
+}
+
+/*
+ * Perform tree rotations on an unbalanced node.
+ *
+ * side == 0 means the node's balance is -2 .
+ * side == 1 means the node's balance is +2 .
+ */
+static void balance(AvlNode **p, int side)
+{
+       AvlNode  *node  = *p,
+                *child = node->lr[side];
+       int opposite    = 1 - side;
+       int bal         = bal(side);
+       
+       if (child->balance != -bal) {
+               /* Left-left (side == 0) or right-right (side == 1) */
+               node->lr[side]      = child->lr[opposite];
+               child->lr[opposite] = node;
+               *p = child;
+               
+               child->balance -= bal;
+               node->balance = -child->balance;
+               
+       } else {
+               /* Left-right (side == 0) or right-left (side == 1) */
+               AvlNode *grandchild = child->lr[opposite];
+               
+               node->lr[side]           = grandchild->lr[opposite];
+               child->lr[opposite]      = grandchild->lr[side];
+               grandchild->lr[side]     = child;
+               grandchild->lr[opposite] = node;
+               *p = grandchild;
+               
+               node->balance       = 0;
+               child->balance      = 0;
+               
+               if (grandchild->balance == bal)
+                       node->balance  = -bal;
+               else if (grandchild->balance == -bal)
+                       child->balance = bal;
+               
+               grandchild->balance = 0;
+       }
+}
+
+
+/************************* avl_check_invariants() *************************/
+
+bool avl_check_invariants(AVL *avl)
+{
+       int    dummy;
+       
+       return checkBalances(avl->root, &dummy)
+           && checkOrder(avl)
+           && countNode(avl->root) == avl->count;
+}
+
+static bool checkBalances(AvlNode *node, int *height)
+{
+       if (node) {
+               int h0, h1;
+               
+               if (!checkBalances(node->lr[0], &h0))
+                       return false;
+               if (!checkBalances(node->lr[1], &h1))
+                       return false;
+               
+               if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1)
+                       return false;
+               
+               *height = (h0 > h1 ? h0 : h1) + 1;
+               return true;
+       } else {
+               *height = 0;
+               return true;
+       }
+}
+
+static bool checkOrder(AVL *avl)
+{
+       AvlIter     i;
+       const void *last     = NULL;
+       bool        last_set = false;
+       
+       avl_foreach(i, avl) {
+               if (last_set && avl->compare(last, i.key) >= 0)
+                       return false;
+               last     = i.key;
+               last_set = true;
+       }
+       
+       return true;
+}
+
+static size_t countNode(AvlNode *node)
+{
+       if (node)
+               return 1 + countNode(node->lr[0]) + countNode(node->lr[1]);
+       else
+               return 0;
+}
+
+
+/************************* Traversal *************************/
+
+void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir)
+{
+       AvlNode *node = avl->root;
+       
+       iter->stack_index = 0;
+       iter->direction   = dir;
+       
+       if (node == NULL) {
+               iter->key      = NULL;
+               iter->value    = NULL;
+               iter->node     = NULL;
+               return;
+       }
+       
+       while (node->lr[dir] != NULL) {
+               iter->stack[iter->stack_index++] = node;
+               node = node->lr[dir];
+       }
+       
+       iter->key   = (void*) node->key;
+       iter->value = (void*) node->value;
+       iter->node  = node;
+}
+
+void avl_iter_next(AvlIter *iter)
+{
+       AvlNode     *node = iter->node;
+       AvlDirection dir  = iter->direction;
+       
+       if (node == NULL)
+               return;
+       
+       node = node->lr[1 - dir];
+       if (node != NULL) {
+               while (node->lr[dir] != NULL) {
+                       iter->stack[iter->stack_index++] = node;
+                       node = node->lr[dir];
+               }
+       } else if (iter->stack_index > 0) {
+               node = iter->stack[--iter->stack_index];
+       } else {
+               iter->key      = NULL;
+               iter->value    = NULL;
+               iter->node     = NULL;
+               return;
+       }
+       
+       iter->node  = node;
+       iter->key   = (void*) node->key;
+       iter->value = (void*) node->value;
+}
diff --git a/ccan/avl/avl.h b/ccan/avl/avl.h
new file mode 100644 (file)
index 0000000..c78e8df
--- /dev/null
@@ -0,0 +1,119 @@
+/*
+ * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef CCAN_AVL_H
+#define CCAN_AVL_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+typedef struct AVL           AVL;
+typedef struct AvlNode       AvlNode;
+typedef struct AvlIter       AvlIter;
+
+typedef int (*AvlCompare)(const void *, const void *);
+
+AVL *avl_new(AvlCompare compare);
+       /* Create a new AVL tree sorted with the given comparison function. */
+
+void avl_free(AVL *avl);
+       /* Free an AVL tree. */
+
+void *avl_lookup(const AVL *avl, const void *key);
+       /* O(log n). Lookup a value at a key.  Return NULL if the key is not present. */
+
+#define avl_member(avl, key) (!!avl_lookup_node(avl, key))
+       /* O(log n). See if a key is present. */
+
+size_t avl_count(const AVL *avl);
+       /* O(1). Return the number of elements in the tree. */
+
+bool avl_insert(AVL *avl, const void *key, const void *value);
+       /*
+        * O(log n). Insert a key/value pair, or replace it if already present.
+        *
+        * Return false if the insertion replaced an existing key/value.
+        */
+
+bool avl_remove(AVL *avl, const void *key);
+       /*
+        * O(log n). Remove a key/value pair (if present).
+        *
+        * Return true if it was removed.
+        */
+
+bool avl_check_invariants(AVL *avl);
+       /* For testing purposes.  This function will always return true :-) */
+
+
+/************************* Traversal *************************/
+
+#define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
+       /*
+        * O(n). Traverse an AVL tree in order.
+        *
+        * Example:
+        *
+        * AvlIter i;
+        *
+        * avl_foreach(i, avl)
+        *     printf("%s -> %s\n", i.key, i.value);
+        */
+
+#define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
+       /* O(n). Traverse an AVL tree in reverse order. */
+
+typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
+
+struct AvlIter {
+       void         *key;
+       void         *value;
+       AvlNode      *node;
+       
+       /* private */
+       AvlNode      *stack[100];
+       int           stack_index;
+       AvlDirection  direction;
+};
+
+void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
+void avl_iter_next(AvlIter *iter);
+#define avl_traverse(iter, avl, direction)        \
+       for (avl_iter_begin(&(iter), avl, direction); \
+            (iter).node != NULL;                     \
+            avl_iter_next(&iter))
+
+
+/***************** Internal data structures ******************/
+
+struct AVL {
+       AvlCompare  compare;
+       AvlNode    *root;
+       size_t      count;
+};
+
+struct AvlNode {
+       const void *key;
+       const void *value;
+       
+       AvlNode    *lr[2];
+       int         balance; /* -1, 0, or 1 */
+};
+
+AvlNode *avl_lookup_node(const AVL *avl, const void *key);
+       /* O(log n). Lookup an AVL node by key.  Return NULL if not present. */
+
+#endif
diff --git a/ccan/avl/test/run.c b/ccan/avl/test/run.c
new file mode 100644 (file)
index 0000000..9976465
--- /dev/null
@@ -0,0 +1,487 @@
+/*
+ * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <ccan/avl/avl.h>
+
+#define remove remove_
+#include <ccan/avl/avl.c>
+#undef remove
+
+#include <ccan/tap/tap.h>
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define ANIMATE_RANDOM_ACCESS 0
+
+#if ANIMATE_RANDOM_ACCESS
+
+#include <sys/time.h>
+
+typedef int64_t msec_t;
+
+static msec_t time_ms(void)
+{
+       struct timeval tv;
+       gettimeofday(&tv, NULL);
+       return (msec_t)tv.tv_sec * 1000 + tv.tv_usec / 1000;
+}
+
+#endif
+
+uint32_t rand32_state = 0;
+
+/*
+ * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
+ * Uses the BCPL linear congruential generator method.
+ *
+ * Note: this method (or maybe just this implementation) seems to
+ *       go back and forth between odd and even exactly, which can
+ *       affect low-cardinality testing if the cardinality given is even.
+ */
+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;
+               }
+       }
+}
+
+static struct {
+       size_t success;
+       size_t passed_invariants_checks;
+       
+       size_t excess;
+       size_t duplicate;
+       size_t missing;
+       size_t incorrect;
+       size_t failed;
+       size_t failed_invariants_checks;
+} stats;
+
+static void clear_stats(void)
+{
+       memset(&stats, 0, sizeof(stats));
+}
+
+static bool 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.passed_invariants_checks)
+               printf("      Passed invariants checks: %zu\n", stats.passed_invariants_checks);
+       
+       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.failed_invariants_checks)
+               failed = 1, printf("      Failed invariants checks: %zu\n", stats.failed_invariants_checks);
+       
+       return !failed;
+}
+
+struct test_item {
+       uint32_t key;
+       uint32_t value;
+       size_t   insert_id; /* needed because qsort is not a stable sort */
+};
+
+static int compare_uint32_t(const void *ap, const void *bp)
+{
+       uint32_t a = *(const uint32_t *)ap;
+       uint32_t b = *(const uint32_t *)bp;
+       
+       if (a < b)
+               return -1;
+       if (a > b)
+               return 1;
+       return 0;
+}
+
+static int compare_test_item(const void *ap, const void *bp)
+{
+       const struct test_item *a = *(void**)ap, *b = *(void**)bp;
+       
+       if (a->key < b->key)
+               return -1;
+       if (a->key > b->key)
+               return 1;
+       
+       if (a->insert_id < b->insert_id)
+               return -1;
+       if (a->insert_id > b->insert_id)
+               return 1;
+       
+       return 0;
+}
+
+static bool test_insert_item(AVL *avl, struct test_item *item)
+{
+       avl_insert(avl, &item->key, &item->value);
+       return true;
+}
+
+static bool test_lookup_item(const AVL *avl, const struct test_item *item)
+{
+       return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
+}
+
+static bool test_remove_item(AVL *avl, struct test_item *item)
+{
+       return avl_remove(avl, &item->key);
+}
+
+static void test_foreach(AVL *avl, struct test_item **test_items, int count)
+{
+       AvlIter iter;
+       int     i;
+       
+       i = 0;
+       avl_foreach(iter, avl) {
+               if (i >= count) {
+                       stats.excess++;
+                       continue;
+               }
+               if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
+                       stats.success++;
+               else
+                       stats.incorrect++;
+               i++;
+       }
+}
+
+static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
+{
+       AvlIter iter;
+       int     i;
+       
+       i = count - 1;
+       avl_foreach_reverse(iter, avl) {
+               if (i < 0) {
+                       stats.excess++;
+                       continue;
+               }
+               if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
+                       stats.success++;
+               else
+                       stats.incorrect++;
+               i--;
+       }
+}
+
+static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
+{
+       struct test_item **test_item;
+       struct test_item *test_item_array;
+       size_t i, o, 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++) {
+               AVL *avl;
+               
+               if (cardinality)
+                       printf("Round %zu (cardinality = %d)\n", round, cardinality);
+               else
+                       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   = rand32();
+                       test_item[i]->value = rand32();
+                       
+                       if (cardinality)
+                               test_item[i]->key %= cardinality;
+               }
+               scramble(test_item, count, sizeof(*test_item));
+               
+               avl = avl_new(compare_uint32_t);
+               
+               clear_stats();
+               printf("   Inserting %zu items...\n", count);
+               for (i=0; i<count; i++) {
+                       if (test_insert_item(avl, test_item[i])) {
+                               stats.success++;
+                               test_item[i]->insert_id = i;
+                       } else {
+                               printf("invariants check failed at insertion %zu\n", i);
+                               stats.failed++;
+                       }
+                       
+                       /* Periodically do an invariants check */
+                       if (count / 10 > 0 && i % (count / 10) == 0) {
+                               if (avl_check_invariants(avl))
+                                       stats.passed_invariants_checks++;
+                               else
+                                       stats.failed_invariants_checks++;
+                       }
+               }
+               ok1(print_stats("Inserted", count));
+               ok1(avl_check_invariants(avl));
+               
+               /* remove early duplicates, as they are shadowed in insertions. */
+               qsort(test_item, count, sizeof(*test_item), compare_test_item);
+               for (i = 0, o = 0; i < count;) {
+                       uint32_t k = test_item[i]->key;
+                       do i++; while (i < count && test_item[i]->key == k);
+                       test_item[o++] = test_item[i-1];
+               }
+               count = o;
+               ok1(avl_count(avl) == count);
+               
+               scramble(test_item, count, sizeof(*test_item));
+               
+               printf("   Finding %zu items...\n", count);
+               clear_stats();
+               for (i=0; i<count; i++) {
+                       if (!test_lookup_item(avl, test_item[i]))
+                               stats.missing++;
+                       else
+                               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();
+               test_foreach(avl, test_item, count);
+               ok1(print_stats("Traversed", count));
+               
+               printf("   Traversing backward through %zu items...\n", count);
+               clear_stats();
+               test_foreach_reverse(avl, test_item, count);
+               ok1(print_stats("Traversed", count));
+               
+               scramble(test_item, count, sizeof(*test_item));
+               
+               printf("   Deleting %zu items...\n", count);
+               clear_stats();
+               for (i=0; i<count; i++) {
+                       if (test_remove_item(avl, test_item[i]))
+                               stats.success++;
+                       else
+                               stats.missing++;
+                       
+                       /* Periodically do an invariants check */
+                       if (count / 10 > 0 && i % (count / 10) == 0) {
+                               if (avl_check_invariants(avl))
+                                       stats.passed_invariants_checks++;
+                               else
+                                       stats.failed_invariants_checks++;
+                       }
+               }
+               ok1(print_stats("Deleted", count));
+               ok1(avl_count(avl) == 0);
+               ok1(avl_check_invariants(avl));
+               
+               avl_free(avl);
+       }
+       
+       free(test_item);
+       free(test_item_array);
+}
+
+static int compare_ptr(const void *a, const void *b)
+{
+       if (a < b)
+               return -1;
+       if (a > b)
+               return 1;
+       return 0;
+}
+
+struct fail_total {
+       int64_t fail;
+       int64_t total;
+};
+
+static bool print_pass_fail(struct fail_total *pf, const char *label)
+{
+       long long fail  = pf->fail,
+                 total = pf->total;
+       
+       printf("%s:\t%lld / %lld\n", label, total - fail, total);
+       
+       return fail == 0;
+}
+
+static void test_random_access(uint32_t max, int64_t ops)
+{
+       char       *in_tree;
+       AVL        *avl;
+       int64_t     i;
+       struct {
+               struct fail_total
+                       inserts, lookups, removes, checks;
+       } s;
+       
+       #if ANIMATE_RANDOM_ACCESS
+       msec_t last_update, now;
+       msec_t interval = 100;
+       #endif
+       
+       memset(&s, 0, sizeof(s));
+       
+       in_tree = malloc(max);
+       memset(in_tree, 0, max);
+       
+       avl = avl_new(compare_ptr);
+       
+       #if ANIMATE_RANDOM_ACCESS
+       now = time_ms();
+       last_update = now - interval;
+       #endif
+       
+       for (i = 0; i < ops; i++) {
+               char *item = &in_tree[rand32() % max];
+               char *found;
+               bool  inserted, removed;
+               
+               #if ANIMATE_RANDOM_ACCESS
+               now = time_ms();
+               if (now >= last_update + interval) {
+                       last_update = now;
+                       printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
+                       fflush(stdout);
+               }
+               #endif
+               
+               switch (rand32() % 3) {
+                       case 0:
+                               inserted = avl_insert(avl, item, item);
+                               
+                               if ((*item == 0 && !inserted) ||
+                                   (*item == 1 && inserted))
+                                       s.inserts.fail++;
+                               
+                               if (inserted)
+                                       *item = 1;
+                               
+                               s.inserts.total++;
+                               break;
+                       
+                       case 1:
+                               found = avl_lookup(avl, item);
+                               
+                               if ((*item == 0 && found != NULL) ||
+                                   (*item == 1 && found != item) ||
+                                   (avl_member(avl, item) != !!found))
+                                       s.lookups.fail++;
+                               
+                               s.lookups.total++;
+                               break;
+                       
+                       case 2:
+                               removed = avl_remove(avl, item);
+                               
+                               if ((*item == 0 && removed) ||
+                                   (*item == 1 && !removed))
+                                       s.removes.fail++;
+                               
+                               if (removed)
+                                       *item = 0;
+                               
+                               s.removes.total++;
+                               break;
+               }
+               
+               /* Periodically do an invariants check */
+               if (ops / 10 > 0 && i % (ops / 10) == 0) {
+                       if (!avl_check_invariants(avl))
+                               s.checks.fail++;
+                       s.checks.total++;
+               }
+       }
+       
+       #if ANIMATE_RANDOM_ACCESS
+       printf("\r\033[K");
+       #endif
+       
+       avl_free(avl);
+       free(in_tree);
+       
+       ok1(print_pass_fail(&s.inserts, "Inserts"));
+       ok1(print_pass_fail(&s.lookups, "Lookups"));
+       ok1(print_pass_fail(&s.removes, "Removes"));
+       ok1(print_pass_fail(&s.checks,  "Invariants checks"));
+}
+
+int main(void)
+{
+       plan_tests(18 * 3 + 4);
+       
+       benchmark(100000, 2, false, 0);
+       benchmark(100000, 2, false, 12345);
+       benchmark(100000, 2, false, 100001);
+       
+       printf("Running random access test\n");
+       test_random_access(12345, 1234567);
+       
+       return exit_status();
+}