Adding upstream version 2.0.16.upstream/2.0.16upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1791 insertions, 0 deletions

diff --git a/src/raptor_avltree.c b/src/raptor_avltree.c
new file mode 100644
index 0000000..4001a92
--- /dev/null
+++ b/src/raptor_avltree.c
@@ -0,0 +1,1791 @@
+/* -*- Mode: c; c-basic-offset: 2 -*-
+ *
+ * raptor_avltree.c - Balanced Binary Tree / AVL Tree
+ *
+ * This file is in the public domain.
+ *
+ * Based on public domain sources posted to comp.sources.misc in 1993
+ *
+ * From: p...@vix.com (Paul Vixie)
+ * Newsgroups: comp.sources.unix
+ * Subject: v27i034: REPOST AVL Tree subroutines (replaces v11i020 from 1987), Part01/01
+ * Date: 6 Sep 1993 13:51:22 -0700
+ * Message-ID: <1.747348668.4037@gw.home.vix.com>
+ * 
+ * ----------------------------------------------------------------------
+ * Original headers below
+ */
+
+/* as_tree - tree library for as
+ * vix 14dec85 [written]
+ * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
+ * vix 06feb86 [added tree_mung()]
+ * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
+ * vix 23jun86 [added delete uar to add for replaced nodes]
+ * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
+ */
+
+
+/* This program text was created by Paul Vixie using examples from the book:
+ * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
+ * 0-13-022005-1.  This code and associated documentation is hereby placed
+ * in the public domain.
+ */
+
+
+#ifdef HAVE_CONFIG_H
+#include <raptor_config.h>
+#endif
+
+#ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+
+
+/* Raptor includes */
+#include "raptor2.h"
+#include "raptor_internal.h"
+
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+#define RAPTOR_AVLTREE_DEBUG1(msg) RAPTOR_DEBUG1(msg)
+#else
+#define RAPTOR_AVLTREE_DEBUG1(msg)
+#endif
+
+
+#define RAPTOR_AVLTREE_ENOMEM -1
+#define RAPTOR_AVLTREE_EXISTS 1
+
+
+#ifndef STANDALONE
+
+/* raptor_avltree.c */
+typedef struct raptor_avltree_node_s raptor_avltree_node;
+
+/* AVL-tree */
+struct raptor_avltree_s {
+  /* root node of tree */
+  raptor_avltree_node* root;
+
+  /* node comparison function (optional) */
+  raptor_data_compare_handler compare_handler;
+
+  /* node deletion function (optional) */
+  raptor_data_free_handler free_handler;
+
+  /* node print function (optional) */
+  raptor_data_print_handler print_handler;
+
+  /* tree bitflags - bitmask of #raptor_avltree_bitflags flags */
+  unsigned int flags;
+
+  /* number of nodes in tree */
+  unsigned int size;
+};
+
+
+/* AVL-tree node */
+struct raptor_avltree_node_s {
+  /* parent tree */
+  struct raptor_avltree_node_s *parent;
+  
+  /* left child tree */
+  struct raptor_avltree_node_s *left;
+
+  /* right child tree */
+  struct raptor_avltree_node_s *right;
+
+  /* balance factor =
+   *   height of the right tree minus the height of the left tree
+   * i.e. equal: 0  left larger: -1  right larger: 1
+   */
+  signed char balance;
+
+  /* actual data */
+  void* data;
+};
+
+
+#ifndef TRUE
+#define	TRUE		1
+#define	FALSE		0
+#endif
+
+
+/* local prototypes */
+static int raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p);
+static void* raptor_avltree_delete_internal(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p);
+static void* raptor_avltree_delete_internal2(raptor_avltree* tree, raptor_avltree_node** ppr_r, int *rebalancing_p, raptor_avltree_node** ppr_q);
+static void raptor_avltree_balance_left(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p);
+static void raptor_avltree_balance_right(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p);
+static raptor_avltree_node* raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node, const void* p_data);
+static int raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node, int depth, raptor_avltree_visit_handler visit_fn, void* user_data);
+static void raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node);
+#ifdef RAPTOR_DEBUG
+static void raptor_avltree_check_internal(raptor_avltree* tree, raptor_avltree_node* node, unsigned int* count_p);
+#endif
+
+
+/**
+ * raptor_new_avltree:
+ * @compare_handler: item comparison handler for ordering
+ * @free_handler: item free handler (or NULL)
+ * @flags: AVLTree flags - bitmask of #raptor_avltree_bitflags flags.
+ *
+ * AVL Tree Constructor
+ *
+ * Return value: new AVL Tree or NULL on failure
+ */
+raptor_avltree*
+raptor_new_avltree(raptor_data_compare_handler compare_handler,
+                   raptor_data_free_handler free_handler,
+                   unsigned int flags)
+{
+  raptor_avltree* tree;
+  
+  tree = RAPTOR_MALLOC(raptor_avltree*, sizeof(*tree));
+  if(!tree)
+    return NULL;
+
+  tree->root = NULL;
+  tree->compare_handler = compare_handler;
+  tree->free_handler = free_handler;
+  tree->print_handler = NULL;
+  tree->flags = flags;
+  tree->size = 0;
+  
+  return tree;
+}
+
+
+/**
+ * raptor_free_avltree:
+ * @tree: AVLTree object
+ *
+ * AVL Tree destructor
+ */
+void
+raptor_free_avltree(raptor_avltree* tree)
+{
+  if(!tree)
+    return;
+  
+  raptor_free_avltree_internal(tree, tree->root);
+
+  RAPTOR_FREE(raptor_avltree, tree);
+}
+
+
+static void
+raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node)
+{
+  if(node) {
+    raptor_free_avltree_internal(tree, node->left);
+
+    raptor_free_avltree_internal(tree, node->right);
+
+    if(tree->free_handler)
+      tree->free_handler(node->data);
+    tree->size--;
+    RAPTOR_FREE(raptor_avltree_node, node);
+  }
+}
+
+
+/* methods */
+
+static raptor_avltree_node*
+raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node,
+                               const void* p_data)
+{
+  if(node) {
+    int cmp= tree->compare_handler(p_data, node->data);
+
+    if(cmp > 0)
+      return raptor_avltree_search_internal(tree, node->right, p_data);
+    else if(cmp < 0)
+      return raptor_avltree_search_internal(tree, node->left, p_data);
+
+    /* found */
+    return node;
+  }
+
+  /* otherwise not found */
+  return NULL;
+}
+
+
+/**
+ * raptor_avltree_search:
+ * @tree: AVL Tree object
+ * @p_data: pointer to data item
+ *
+ * Find an item in an AVL Tree
+ *
+ * Return value: shared pointer to item (still owned by AVL Tree) or NULL on failure or if not found
+ */
+void*
+raptor_avltree_search(raptor_avltree* tree, const void* p_data)
+{
+  raptor_avltree_node* node;
+  node = raptor_avltree_search_internal(tree, tree->root, p_data);
+  return node ? node->data : NULL;
+}
+
+
+/**
+ * raptor_avltree_add:
+ * @tree: AVL Tree object
+ * @p_data: pointer to data item
+ *
+ * add an item to an AVL Tree
+ *
+ * The item added becomes owned by the AVL Tree, and will be freed by
+ * the free_handler argument given to raptor_new_avltree().
+ *
+ * Return value: 0 on success, >0 if equivalent item exists (and the old element remains in the tree), <0 on failure
+ */
+int
+raptor_avltree_add(raptor_avltree* tree, void* p_data)
+{
+  int rebalancing = FALSE;
+  int rv;
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  RAPTOR_AVLTREE_DEBUG1("Checking tree before adding\n");
+  raptor_avltree_check(tree);
+#endif
+
+  rv = raptor_avltree_sprout(tree, NULL, &tree->root, p_data,
+                             &rebalancing);
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  RAPTOR_AVLTREE_DEBUG1("Checking tree after adding\n");
+  raptor_avltree_check(tree);
+#endif
+
+  return rv;
+}
+
+
+/**
+ * raptor_avltree_remove:
+ * @tree: AVL Tree object
+ * @p_data: pointer to data item
+ *
+ * Remove an item from an AVL Tree and return it
+ *
+ * The item removed is  no longer owned by the AVL Tree and is
+ * owned by the caller.
+ *
+ * Return value: object or NULL on failure or if not found
+ */
+void*
+raptor_avltree_remove(raptor_avltree* tree, void* p_data)
+{
+  int rebalancing = FALSE;
+  void* rdata;
+  
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  RAPTOR_AVLTREE_DEBUG1("Checking tree before removing\n");
+  raptor_avltree_dump(tree,stderr);
+  raptor_avltree_check(tree);
+#endif
+  rdata = raptor_avltree_delete_internal(tree, &tree->root, p_data,
+                                         &rebalancing);
+  if(rdata)
+    tree->size--;
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  RAPTOR_AVLTREE_DEBUG1("Checking tree after removing\n");
+  raptor_avltree_dump(tree,stderr);
+  raptor_avltree_check(tree);
+#endif
+  
+  return rdata;
+}
+
+
+/**
+ * raptor_avltree_delete:
+ * @tree: AVL Tree object
+ * @p_data: pointer to data item
+ *
+ * Remove an item from an AVL Tree and free it
+ *
+ * Return value: non-0 on failure
+ */
+int
+raptor_avltree_delete(raptor_avltree* tree, void* p_data)
+{
+  void* rdata;
+
+  rdata = raptor_avltree_remove(tree, p_data);
+  if(rdata) {
+    if(tree->free_handler)
+      tree->free_handler(rdata);
+  }
+
+  return (rdata != NULL);
+}
+
+
+/**
+ * raptor_avltree_trim:
+ * @tree: AVLTree object
+ *
+ * Delete all nodes from an AVL tree but keep the shell.
+ */
+void
+raptor_avltree_trim(raptor_avltree* tree)
+{
+  if(!tree)
+    return;
+  
+  raptor_free_avltree_internal(tree, tree->root);
+  tree->root = NULL;
+}
+
+
+static int
+raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node,
+                              int depth,
+                              raptor_avltree_visit_handler visit_handler,
+                              void* user_data)
+{
+  if(!node)
+    return TRUE;
+
+  if(!raptor_avltree_visit_internal(tree, node->left, depth+1, 
+                                    visit_handler, user_data))
+    return FALSE;
+
+  if(!visit_handler(depth, node->data, user_data))
+    return FALSE;
+
+  if(!raptor_avltree_visit_internal(tree, node->right, depth+1,
+                                    visit_handler, user_data))
+    return FALSE;
+
+  return TRUE;
+}
+
+
+/**
+ * raptor_avltree_visit:
+ * @tree: AVL Tree object
+ * @visit_handler: visit function to call at each item
+ * @user_data: user data pointer fo visit function
+ *
+ * Perform an in-order visit of the items in the AVL Tree
+ *
+ * Return value: non-0 if traversal was terminated early by @visit_handler
+*/
+int
+raptor_avltree_visit(raptor_avltree* tree,
+                     raptor_avltree_visit_handler visit_handler,
+                     void* user_data)
+{
+  return raptor_avltree_visit_internal(tree, tree->root, 0,
+                                       visit_handler, user_data);
+}
+
+
+#ifdef RAPTOR_DEBUG
+static void
+raptor_avltree_print_node(raptor_avltree_node* node) 
+{
+  fprintf(stderr, "%p: parent %p  left %p  right %p  data %p",
+          RAPTOR_VOIDP(node),
+          RAPTOR_VOIDP(node->parent),
+          RAPTOR_VOIDP(node->left),
+          RAPTOR_VOIDP(node->right),
+          RAPTOR_VOIDP(node->data));
+}
+
+
+static void
+raptor_avltree_check_node(raptor_avltree* tree, raptor_avltree_node* node,
+                          const char* fn, const char* where) 
+{
+  if(node->parent) {
+    if((node->parent == node->left) || (node->parent == node->right)) {
+      if(fn && where)
+        fprintf(stderr, "%s (%s): ", fn, where);
+      fputs("ERROR bad node ", stderr);
+      raptor_avltree_print_node(node);
+      fputc('\n', stderr);
+      fflush(stderr);
+      abort();
+    }
+
+    if(node->parent->left != node && node->parent->right != node) {
+      if(fn && where)
+        fprintf(stderr, "%s (%s): ", fn, where);
+      fputs("ERROR parent node ", stderr);
+      raptor_avltree_print_node(node->parent);
+      fputs(" has no reference to child node ", stderr);
+      raptor_avltree_print_node(node);
+      fputc('\n', stderr);
+      fflush(stderr);
+      abort();
+    }
+  }
+
+  if(node->left) {
+    if(node->left->parent != node) {
+      if(fn && where)
+        fprintf(stderr, "%s (%s): ", fn, where);
+      fputs("ERROR left child node ", stderr);
+      raptor_avltree_print_node(node->left);
+      fputs(" has no reference to this[parent] node ", stderr);
+      raptor_avltree_print_node(node);
+      fputc('\n', stderr);
+      fflush(stderr);
+      abort();
+    }
+  }
+  if(node->right) {
+    if(node->right->parent != node) {
+      if(fn && where)
+        fprintf(stderr, "%s (%s): ", fn, where);
+      fputs("ERROR right child node ", stderr);
+      raptor_avltree_print_node(node->right);
+      fputs(" has no reference to this[parent] node ", stderr);
+      raptor_avltree_print_node(node);
+      fputc('\n', stderr);
+      fflush(stderr);
+      abort();
+    }
+  }
+}
+#endif
+
+
+static int
+raptor_avltree_sprout_left(raptor_avltree* tree, raptor_avltree_node** node_pp,
+                           void* p_data, int *rebalancing_p)
+{
+  raptor_avltree_node *p1, *p2, *p_parent;
+  int rc;
+
+  RAPTOR_AVLTREE_DEBUG1("LESS. raptor_avltree_sprouting left.\n");
+
+  p_parent = (*node_pp)->parent;
+  
+  rc = raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->left, p_data,
+                             rebalancing_p);
+  if(rc)
+    return rc;
+
+  if(!*rebalancing_p)
+    return FALSE;
+
+  /* left branch has grown longer */
+  RAPTOR_AVLTREE_DEBUG1("LESS: left branch has grown\n");
+  switch((*node_pp)->balance) {
+    case 1:
+      /* right branch WAS longer; balance is ok now */
+      RAPTOR_AVLTREE_DEBUG1("LESS: case 1.. balance restored implicitly\n");
+      (*node_pp)->balance = 0;
+      *rebalancing_p = FALSE;
+      break;
+
+    case 0:
+      /* balance WAS okay; now left branch longer */
+      RAPTOR_AVLTREE_DEBUG1("LESS: case 0.. balance bad but still ok\n");
+      (*node_pp)->balance = -1;
+      break;
+
+    case -1:
+      /* left branch was already too long. rebalance */
+      RAPTOR_AVLTREE_DEBUG1("LESS: case -1: rebalancing\n");
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      RAPTOR_AVLTREE_DEBUG1("Tree before rebalancing\n");
+      raptor_avltree_dump(tree, stderr);
+#endif
+      p1 = (*node_pp)->left;
+
+      if(p1->balance == -1) {
+        /* LL */
+        RAPTOR_AVLTREE_DEBUG1("LESS: single LL\n");
+        (*node_pp)->left = p1->right;
+        if((*node_pp)->left)
+          (*node_pp)->left->parent = (*node_pp);
+        p1->right = *node_pp;
+        if(p1->right)
+          p1->right->parent = p1;
+        (*node_pp)->balance = 0;
+        *node_pp = p1;
+        (*node_pp)->parent = p_parent;
+      } else {
+        /* double LR */
+        RAPTOR_AVLTREE_DEBUG1("LESS: double LR\n");
+        p2 = p1->right;
+        p1->right= p2->left;
+        if(p1->right)
+          p1->right->parent = p1;
+        p2->left = p1;
+        if(p2->left)
+          p2->left->parent = p2;
+
+        (*node_pp)->left = p2->right;
+        if((*node_pp)->left)
+          (*node_pp)->left->parent = (*node_pp);
+        p2->right = *node_pp;
+        if(p2->right)
+          p2->right->parent = p2;
+
+        if(p2->balance == -1)
+          (*node_pp)->balance = 1;
+        else
+          (*node_pp)->balance = 0;
+
+        if(p2->balance == 1)
+          p1->balance = -1;
+        else
+          p1->balance = 0;
+
+        *node_pp = p2;
+        (*node_pp)->parent = p_parent;
+      } /* end else */
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      RAPTOR_AVLTREE_DEBUG1("Tree after rebalancing\n");
+      raptor_avltree_dump(tree, stderr);
+#endif
+
+      (*node_pp)->balance = 0;
+      *rebalancing_p = FALSE;
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      if(1) {
+        unsigned int discard = 0;
+        raptor_avltree_check_internal(tree, *node_pp, &discard);
+      }
+#endif
+  } /* end switch */
+
+  return FALSE;
+}
+
+
+static int
+raptor_avltree_sprout_right(raptor_avltree* tree,
+                            raptor_avltree_node** node_pp, 
+                            void* p_data, int *rebalancing_p)
+{
+  raptor_avltree_node *p1, *p2, *p_parent;
+  int rc;
+
+  RAPTOR_AVLTREE_DEBUG1("MORE: raptor_avltree_sprouting to the right\n");
+
+  p_parent = (*node_pp)->parent;
+  
+  rc = raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->right, p_data,
+                             rebalancing_p);
+  if(rc)
+    return rc;
+
+  if(!*rebalancing_p)
+    return FALSE;
+  
+  /* right branch has grown longer */
+  RAPTOR_AVLTREE_DEBUG1("MORE: right branch has grown\n");
+  
+  switch((*node_pp)->balance) {
+    case -1:
+      RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, fixed implicitly\n");
+      (*node_pp)->balance = 0;
+      *rebalancing_p = FALSE;
+      break;
+      
+    case 0:
+      RAPTOR_AVLTREE_DEBUG1("MORE: balance was okay, now off but ok\n");
+      (*node_pp)->balance = 1;
+      break;
+      
+    case 1:
+      RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, need to rebalance\n");
+      p1 = (*node_pp)->right;
+      
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      RAPTOR_AVLTREE_DEBUG1("Tree before rebalancing\n");
+      raptor_avltree_dump(tree, stderr);
+#endif
+      if(p1->balance == 1) {
+        /* RR */
+        RAPTOR_AVLTREE_DEBUG1("MORE: single RR\n");
+        (*node_pp)->right = p1->left;
+        if((*node_pp)->right)
+          (*node_pp)->right->parent = (*node_pp);
+        p1->left = *node_pp;
+        if(p1->left)
+          p1->left->parent = p1;
+        (*node_pp)->balance = 0;
+        *node_pp = p1;
+        (*node_pp)->parent = p_parent;
+      } else {
+        /* double RL */
+        RAPTOR_AVLTREE_DEBUG1("MORE: double RL\n");
+        
+        p2 = p1->left;
+        p1->left = p2->right;
+        if(p1->left)
+          p1->left->parent = p1;
+        p2->right = p1;
+        if(p2->right)
+          p2->right->parent = p2;
+        
+        (*node_pp)->right = p2->left;
+        if((*node_pp)->right)
+          (*node_pp)->right->parent = (*node_pp);
+        p2->left = *node_pp;
+        if(p2->left)
+          p2->left->parent = p2;
+        
+        if(p2->balance == 1)
+          (*node_pp)->balance = -1;
+        else
+          (*node_pp)->balance = 0;
+        
+        if(p2->balance == -1)
+          p1->balance = 1;
+        else
+          p1->balance = 0;
+        
+        *node_pp = p2;
+        (*node_pp)->parent = p_parent;
+      } /* end else */
+      
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      RAPTOR_AVLTREE_DEBUG1("Tree after rebalancing\n");
+      raptor_avltree_dump(tree, stderr);
+#endif
+      (*node_pp)->balance = 0;
+      *rebalancing_p = FALSE;
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+      if(1) {
+        unsigned int discard = 0;
+        raptor_avltree_check_internal(tree, *node_pp, &discard);
+      }
+#endif
+  } /* end switch */
+
+  return FALSE;
+}
+
+
+/* grow a tree by sprouting with a new node
+ *
+ * Return values:
+ *   0 on success
+ *   >0 if equivalent item exists (and the old element remains in the tree)
+ *   <0 if memory is exhausted.
+ */
+static int
+raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent,
+                      raptor_avltree_node** node_pp, void* p_data,
+                      int *rebalancing_p)
+{
+  int cmp;
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  RAPTOR_AVLTREE_DEBUG1("Enter\n");
+  if ( *node_pp) { 
+      raptor_avltree_print_node(*node_pp);
+      RAPTOR_AVLTREE_DEBUG1("\n");
+  }
+  else {
+      RAPTOR_AVLTREE_DEBUG1("Nil node\n");
+  }
+#endif
+
+  /* If grounded, add the node here, set the rebalance flag and return */
+  if(!*node_pp) {
+    RAPTOR_AVLTREE_DEBUG1("grounded. adding new node, setting rebalancing flag true\n");
+    *node_pp = RAPTOR_MALLOC(raptor_avltree_node*, sizeof(**node_pp));
+    if(!*node_pp) {
+      if(tree->free_handler)
+        tree->free_handler(p_data);
+      return RAPTOR_AVLTREE_ENOMEM;
+    }
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+    RAPTOR_DEBUG2("Creating new node %p\n", RAPTOR_VOIDP(*node_pp));
+#endif
+    
+    (*node_pp)->parent = parent;
+    (*node_pp)->left = NULL;
+    (*node_pp)->right = NULL;
+    (*node_pp)->balance = 0;
+    (*node_pp)->data= p_data;
+    *rebalancing_p = TRUE;
+
+    tree->size++;
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+    raptor_avltree_check_node(tree, *node_pp, 0, 0);
+
+    RAPTOR_AVLTREE_DEBUG1("Tree now looks this way\n");
+    raptor_avltree_dump(tree,stderr);
+#endif
+    
+    return FALSE;
+  }
+
+  /* check node */
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  raptor_avltree_check_node(tree, *node_pp, 0, 0);
+#endif
+  /* compare the data */
+  cmp = tree->compare_handler(p_data, (*node_pp)->data);
+  if(cmp < 0)
+    /* if LESS, prepare to move to the left. */
+    return raptor_avltree_sprout_left(tree, node_pp, p_data, rebalancing_p);
+  else if(cmp > 0)
+    /* if MORE, prepare to move to the right. */
+    return raptor_avltree_sprout_right(tree, node_pp, p_data, rebalancing_p);
+
+  /* otherwise equivalent key */
+  *rebalancing_p = FALSE;
+
+  if(tree->flags & RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES) {
+    /* replace item with equivalent key */
+    if(tree->free_handler)
+      tree->free_handler((*node_pp)->data);
+    (*node_pp)->data= p_data;
+
+    return FALSE;
+  } else {
+    /* ignore item with equivalent key */
+    if(tree->free_handler)    
+      tree->free_handler(p_data);
+    return RAPTOR_AVLTREE_EXISTS;
+  }
+}
+
+
+static void*
+raptor_avltree_delete_internal(raptor_avltree* tree,
+                               raptor_avltree_node** node_pp,
+                               void* p_data,
+                               int *rebalancing_p)
+{
+  int cmp;
+  void* rdata = NULL;
+
+  RAPTOR_AVLTREE_DEBUG1("Enter\n");
+
+  if(*node_pp == NULL) {
+    RAPTOR_AVLTREE_DEBUG1("key not in tree\n");
+    return rdata;
+  }
+
+  if(p_data)
+    cmp = tree->compare_handler((*node_pp)->data, p_data);
+  else
+    cmp = 0;
+
+  if(cmp > 0) {
+    RAPTOR_AVLTREE_DEBUG1("too high - scan left\n");
+    rdata = raptor_avltree_delete_internal(tree, &(*node_pp)->left, p_data,
+                                           rebalancing_p);
+    if(*rebalancing_p)
+      raptor_avltree_balance_left(tree, node_pp, rebalancing_p);
+
+  } else if(cmp < 0) {
+    RAPTOR_AVLTREE_DEBUG1("too low - scan right\n");
+    rdata = raptor_avltree_delete_internal(tree, &(*node_pp)->right, p_data,
+                                           rebalancing_p);
+    if(*rebalancing_p)
+      raptor_avltree_balance_right(tree, node_pp, rebalancing_p);
+
+  } else {
+    raptor_avltree_node *pr_q;
+
+    RAPTOR_AVLTREE_DEBUG1("equal\n");
+    pr_q = *node_pp;
+    
+    rdata = pr_q->data;
+    
+    if(pr_q->right == NULL) {
+      RAPTOR_AVLTREE_DEBUG1("right subtree null\n");
+      *node_pp = pr_q->left;
+      if(*node_pp)
+        (*node_pp)->parent = pr_q->parent;
+      *rebalancing_p = TRUE;
+    } else if(pr_q->left == NULL) {
+      RAPTOR_AVLTREE_DEBUG1("right subtree non-null, left subtree null\n");
+      *node_pp = pr_q->right;
+      if(*node_pp)
+        (*node_pp)->parent = pr_q->parent;
+      *rebalancing_p = TRUE;
+    } else {
+      RAPTOR_AVLTREE_DEBUG1("neither subtree null\n");
+      rdata = raptor_avltree_delete_internal2(tree, &pr_q->left, rebalancing_p,
+                                              &pr_q);
+      if(*rebalancing_p)
+        raptor_avltree_balance_left(tree, node_pp, rebalancing_p);
+    }
+
+    RAPTOR_FREE(raptor_avltree_node, pr_q);
+  }
+
+  return rdata;
+}
+
+
+static void*
+raptor_avltree_delete_internal2(raptor_avltree* tree,
+                                raptor_avltree_node** ppr_r,
+                                int *rebalancing_p,
+                                raptor_avltree_node** ppr_q)
+{
+  void* rdata = NULL;
+  
+  RAPTOR_AVLTREE_DEBUG1("Enter\n");
+
+  if((*ppr_r)->right != NULL) {
+    rdata = raptor_avltree_delete_internal2(tree,
+                                            &(*ppr_r)->right, 
+                                            rebalancing_p,
+                                            ppr_q);
+    if(*rebalancing_p)
+      raptor_avltree_balance_right(tree, ppr_r, rebalancing_p);
+
+  } else {
+    raptor_avltree_node* ppr_r_left_new_parent;
+    rdata = (*ppr_q)->data;
+
+    (*ppr_q)->data = (*ppr_r)->data;
+    *ppr_q = *ppr_r;
+    ppr_r_left_new_parent = (*ppr_r)->parent;
+    *ppr_r = (*ppr_r)->left;
+    if(*ppr_r)
+      (*ppr_r)->parent = ppr_r_left_new_parent;
+    *rebalancing_p = TRUE;
+  }
+
+  return rdata;
+}
+
+
+static void
+raptor_avltree_balance_left(raptor_avltree* tree,
+                            raptor_avltree_node** node_pp, int *rebalancing_p)
+{
+  raptor_avltree_node *p1, *p2, *p_parent;
+  int b1, b2;
+
+  RAPTOR_AVLTREE_DEBUG1("left branch has shrunk\n");
+
+  p_parent = (*node_pp)->parent;
+  
+  switch((*node_pp)->balance) {
+    case -1:
+      RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n");
+      (*node_pp)->balance = 0;
+      break;
+
+    case 0:
+      RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n");
+      (*node_pp)->balance = 1;
+      *rebalancing_p = FALSE;
+      break;
+
+    case 1:
+      RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n");
+      p1 = (*node_pp)->right;
+      b1 = p1->balance;
+
+      if(b1 >= 0) {
+        RAPTOR_AVLTREE_DEBUG1("single RR\n");
+        (*node_pp)->right = p1->left;
+        if((*node_pp)->right)
+          (*node_pp)->right->parent = (*node_pp);
+        p1->left = *node_pp;
+        if(p1->left)
+          p1->left->parent = p1;
+        if(b1 == 0) {
+          RAPTOR_AVLTREE_DEBUG1("b1 == 0\n");
+          (*node_pp)->balance = 1;
+          p1->balance = -1;
+          *rebalancing_p = FALSE;
+        } else {
+          RAPTOR_AVLTREE_DEBUG1("b1 != 0\n");
+          (*node_pp)->balance = 0;
+          p1->balance = 0;
+        }
+        *node_pp = p1;
+        (*node_pp)->parent = p_parent;
+      } else {
+        RAPTOR_AVLTREE_DEBUG1("double RL\n");
+        p2 = p1->left;
+        b2 = p2->balance;
+        p1->left = p2->right;
+        if(p1->left)
+          p1->left->parent = p1;
+        p2->right = p1;
+        if(p2->right)
+          p2->right->parent = p2;
+        (*node_pp)->right = p2->left;
+        if((*node_pp)->right)
+          (*node_pp)->right->parent = (*node_pp);
+        p2->left = *node_pp;
+        if(p2->left)
+          p2->left->parent = p2;
+        if(b2 == 1)
+          (*node_pp)->balance = -1;
+        else
+          (*node_pp)->balance = 0;
+        if(b2 == -1)
+          p1->balance = 1;
+        else
+          p1->balance = 0;
+        *node_pp = p2;
+        (*node_pp)->parent = p_parent;
+        p2->balance = 0;
+      }
+      break;
+  } /* end switch */
+
+}
+
+
+static void
+raptor_avltree_balance_right(raptor_avltree* tree,
+                             raptor_avltree_node** node_pp, int *rebalancing_p)
+{
+  raptor_avltree_node *p1, *p2, *p_parent;
+  int b1, b2;
+
+  RAPTOR_AVLTREE_DEBUG1("right branch has shrunk\n");
+
+  p_parent = (*node_pp)->parent;
+
+  switch((*node_pp)->balance) {
+    case 1:
+      RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n");
+      (*node_pp)->balance = 0;
+      break;
+
+    case 0:
+      RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n");
+      (*node_pp)->balance = -1;
+      *rebalancing_p = FALSE;
+      break;
+
+    case -1:
+      RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n");
+      p1 = (*node_pp)->left;
+      b1 = p1->balance;
+
+      if(b1 <= 0) {
+        RAPTOR_AVLTREE_DEBUG1("single LL\n");
+        (*node_pp)->left = p1->right;
+        if((*node_pp)->left)
+          (*node_pp)->left->parent = (*node_pp);
+        p1->right = *node_pp;
+        if(p1->right)
+          p1->right->parent = p1;
+        if(b1 == 0) {
+          RAPTOR_AVLTREE_DEBUG1("b1 == 0\n");
+          (*node_pp)->balance = -1;
+          p1->balance = 1;
+          *rebalancing_p = FALSE;
+        } else {
+          RAPTOR_AVLTREE_DEBUG1("b1 != 0\n");
+          (*node_pp)->balance = 0;
+          p1->balance = 0;
+        }
+        *node_pp = p1;
+        (*node_pp)->parent = p_parent;
+      } else {
+        RAPTOR_AVLTREE_DEBUG1("double LR\n");
+        p2 = p1->right;
+        b2 = p2->balance;
+        p1->right = p2->left;
+        if(p1->right)
+          p1->right->parent = p1;
+        p2->left = p1;
+        if(p2->left)
+          p2->left->parent = p2;
+        (*node_pp)->left = p2->right;
+        if((*node_pp)->left)
+          (*node_pp)->left->parent = (*node_pp);
+        p2->right = *node_pp;
+        if(p2->right)
+          p2->right->parent = p2;
+        if(b2 == -1)
+          (*node_pp)->balance = 1;
+        else
+          (*node_pp)->balance = 0;
+        if(b2 == 1)
+          p1->balance = -1;
+        else
+          p1->balance = 0;
+        *node_pp = p2;
+        (*node_pp)->parent = p_parent;
+        p2->balance = 0;
+      }
+  } /* end switch */
+
+}
+
+
+/**
+ * raptor_avltree_size:
+ * @tree: AVL Tree object
+ *
+ * Get the number of items in the AVL Tree
+ *
+ * Return value: number of items in tree
+ */
+int
+raptor_avltree_size(raptor_avltree* tree)
+{
+  return tree->size;
+}
+
+
+/**
+ * raptor_avltree_set_print_handler:
+ * @tree: AVL Tree object
+ * @print_handler: print function
+ *
+ * Set the handler for printing an item in a tree
+ *
+ */
+void
+raptor_avltree_set_print_handler(raptor_avltree* tree,
+                                 raptor_data_print_handler print_handler)
+{
+  tree->print_handler = print_handler;
+}
+
+
+/* Follow left children until a match for range is found (if range not NULL) */
+static raptor_avltree_node*
+raptor_avltree_node_leftmost(raptor_avltree* tree, raptor_avltree_node* node,
+                             void* range)
+{
+  /*assert(node);
+  assert(!range || tree->compare_handler(range, node->data) == 0);*/
+  if(range)
+    while(node && node->left && 
+          tree->compare_handler(range, node->left->data) == 0)
+      node = node->left;
+  else
+    while(node && node->left)
+      node = node->left;
+  
+  return node;
+}
+
+
+static raptor_avltree_node*
+raptor_avltree_node_rightmost(raptor_avltree* tree, raptor_avltree_node* node,
+                              void* range)
+{
+  /*assert(node);
+  assert(!range || tree->compare_handler(range, node->data) == 0);*/
+  if(range)
+    while(node && node->right && 
+          tree->compare_handler(range, node->right->data) == 0)
+      node = node->right;
+  else
+    while(node && node->right)
+      node = node->right;
+  return node;
+}
+
+
+/* Follow right children until a match for range is found (range required) */
+static raptor_avltree_node*
+raptor_avltree_node_search_right(raptor_avltree* tree,
+                                 raptor_avltree_node* node, void* range)
+{
+  raptor_avltree_node* result;
+  
+  if(!node)
+    return NULL;
+
+  result = node->right;
+  while(result) {
+    if(tree->compare_handler(range, result->data) == 0) {
+      return result;
+    } else {
+      result = result->right;
+    }
+  }
+
+  return node;
+}
+
+
+/* Follow left children until a match for range is found (range required) */
+static raptor_avltree_node*
+raptor_avltree_node_search_left(raptor_avltree* tree,
+                                raptor_avltree_node* node, void* range)
+{
+  raptor_avltree_node* result;
+  
+  if(!node)
+    return NULL;
+
+  result = node->left;
+  while(result) {
+    if(tree->compare_handler(range, result->data) == 0) {
+      return result;
+    } else {
+      result = result->left;
+    }
+  }
+
+  return node;
+}
+
+
+static raptor_avltree_node*
+raptor_avltree_node_prev(raptor_avltree* tree, raptor_avltree_node* node,
+                         void* range)
+{
+  int up = 0;
+
+  /*assert(!range || tree->compare_handler(range, node->data) == 0);*/
+
+  if(node->left) {
+    /* Should never go left if the current node is already < range */
+    raptor_avltree_node* prev;
+    prev = raptor_avltree_node_rightmost(tree, node->left, NULL);
+    /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/
+    if(range) {
+      if(tree->compare_handler(range, prev->data) == 0) {
+        up = 0;
+        node = prev;
+      } else {
+        up = 1;
+      }
+    } else {
+      node = prev;
+      up = 0;
+    }
+  } else {
+    up = 1;
+  }
+  
+  if(up) {
+    raptor_avltree_node* last = node;
+    /* Need to go up */
+    node = node->parent;
+    while(node) {
+    
+      /* moving from right subtree to this node */
+      if(node->right && last == node->right) {
+        break;
+      }
+      
+      /* moved up to find an unvisited left subtree */
+      if(node->left && last != node->left) {
+        /* Should never go left if the current node is already > range */
+        /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/
+        node = raptor_avltree_node_rightmost(tree, node->left, range);
+        break;
+      }
+      last = node;
+      node = node->parent;
+    }
+  }
+
+  if(node && range) {
+    if(tree->compare_handler(range, node->data) == 0)
+      return node;
+    else
+      return NULL;
+  } else {
+    return node;
+  }
+}
+
+
+/* Follow right children until a match for range is found (if range not NULL) */
+static raptor_avltree_node*
+raptor_avltree_node_next(raptor_avltree* tree, raptor_avltree_node* node,
+                         void* range)
+{
+  int up = 0;
+
+  /*assert(!range || tree->compare_handler(range, node->data) == 0);*/
+
+  if(node->right) {
+    /* Should never go right if the current node is already > range */
+    raptor_avltree_node* next;
+    next = raptor_avltree_node_leftmost(tree, node->right, NULL);
+    /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/
+    if(range) {
+      if(tree->compare_handler(range, next->data) == 0) {
+        up = 0;
+        node = next;
+      } else {
+        up = 1;
+      }
+    } else {
+      node = next;
+      up = 0;
+    }
+  } else {
+    up = 1;
+  }
+  
+  if(up) {
+    raptor_avltree_node* last = node;
+    /* Need to go up */
+    node = node->parent;
+    while(node) {
+    
+      /* moving from left subtree to this node */
+      if(node->left && last == node->left) {
+        break;
+      }
+      
+      /* moved up to find an unvisited right subtree */
+      if(node->right && last != node->right) {
+        /* Should never go right if the current node is already > range */
+        /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/
+        node = raptor_avltree_node_leftmost(tree, node->right, range);
+        break;
+      }
+      last = node;
+      node = node->parent;
+    }
+  }
+
+  if(node && range) {
+    if(tree->compare_handler(range, node->data) == 0)
+      return node;
+    else
+      return NULL;
+  } else {
+    return node;
+  }
+}
+
+
+struct raptor_avltree_iterator_s {
+  raptor_avltree* tree;
+  raptor_avltree_node* root;
+  raptor_avltree_node* current;
+  void* range;
+  raptor_data_free_handler range_free_handler;
+  int direction;
+  int is_finished;
+};
+
+
+/**
+ * raptor_new_avltree_iterator:
+ * @tree: #raptor_avltree object
+ * @range: range
+ * @range_free_handler: function to free @range object
+ * @direction: <0 to go 'backwards' otherwise 'forwards'
+ *
+ * Get an in-order iterator for the start of a range, or the entire contents
+ *
+ * If range is NULL, the entire tree is walked in order.  If range
+ * specifies a range (i.e. the tree comparison function will 'match'
+ * (return 0 for) range and /several/ nodes), the iterator will be
+ * placed at the leftmost child matching range, and
+ * raptor_avltree_iterator_next will iterate over all nodes (and only
+ * nodes) that match range.
+ * 
+ * Return value: a new #raptor_avltree_iterator object or NULL on failure
+ **/
+raptor_avltree_iterator*
+raptor_new_avltree_iterator(raptor_avltree* tree, void* range,
+                            raptor_data_free_handler range_free_handler,
+                            int direction)
+{
+  raptor_avltree_iterator* iterator;
+
+  iterator = RAPTOR_CALLOC(raptor_avltree_iterator*, 1, sizeof(*iterator));
+  if(!iterator)
+    return NULL;
+
+  iterator->is_finished = 0;
+  iterator->current = NULL;
+
+  iterator->tree = tree;
+  iterator->range = range;
+  iterator->range_free_handler = range_free_handler;
+  iterator->direction = direction;
+
+  if(range) {
+    /* find the topmost match (range is contained entirely in tree
+     * rooted here) 
+     */
+    iterator->current = raptor_avltree_search_internal(tree, tree->root, range);
+  } else {
+    iterator->current = tree->root;
+  }
+
+  iterator->root = iterator->current;
+  
+  if(iterator->current) {
+    if(iterator->direction < 0) {
+      /* go down to find END of range (or tree) */
+      while(1) {
+        raptor_avltree_node* pred;
+        iterator->current = raptor_avltree_node_rightmost(tree,
+                                                          iterator->current,
+                                                          range);
+        /* move left until a match is found */
+        pred = raptor_avltree_node_search_left(tree, iterator->current->right,
+                                               range);
+        
+        if(pred && tree->compare_handler(range, pred->data) == 0)
+          iterator->current = pred;
+        else
+          break;
+      }
+    } else {
+      /* go down to find START of range (or tree) */
+      while(1) {
+        raptor_avltree_node* pred;
+        iterator->current = raptor_avltree_node_leftmost(tree,
+                                                         iterator->current,
+                                                         range);
+        /* move right until a match is found */
+        pred = raptor_avltree_node_search_right(tree, iterator->current->left,
+                                                range);
+        
+        if(pred && tree->compare_handler(range, pred->data) == 0)
+          iterator->current = pred;
+        else
+          break;
+      }
+    }
+  }
+
+  return iterator;
+}
+
+
+/**
+ * raptor_free_avltree_iterator:
+ * @iterator: AVL Tree iterator object
+ *
+ * AVL Tree Iterator destructor
+ */
+void
+raptor_free_avltree_iterator(raptor_avltree_iterator* iterator) 
+{
+  if(!iterator)
+    return;
+  
+  if(iterator->range && iterator->range_free_handler)
+    iterator->range_free_handler(iterator->range);
+
+  RAPTOR_FREE(raptor_avltree_iterator, iterator);
+}
+
+
+/**
+ * raptor_avltree_iterator_is_end:
+ * @iterator: AVL Tree iterator object
+ *
+ * Test if an iteration is finished
+ *
+ * Return value: non-0 if iteration is finished
+ */
+int
+raptor_avltree_iterator_is_end(raptor_avltree_iterator* iterator)
+{
+  raptor_avltree_node *node = iterator->current;
+  
+  if(iterator->is_finished)
+    return 1;
+  iterator->is_finished = (node == NULL);
+
+  return iterator->is_finished;
+}
+
+
+/**
+ * raptor_avltree_iterator_next:
+ * @iterator: AVL Tree iterator object
+ *
+ * Move iteration to next/prev object
+ *
+ * Return value: non-0 if iteration is finished
+ */
+int
+raptor_avltree_iterator_next(raptor_avltree_iterator* iterator)
+{
+  raptor_avltree_node *node = iterator->current;
+  
+  if(!node || iterator->is_finished)
+    return 1;
+  
+  if(iterator->direction < 0)
+    iterator->current = raptor_avltree_node_prev(iterator->tree, node,
+                                                 iterator->range);
+  else
+    iterator->current = raptor_avltree_node_next(iterator->tree, node,
+                                                 iterator->range);
+  /* Stay within rooted subtree */
+  if(iterator->root->parent == iterator->current)
+    iterator->current = NULL;
+
+  iterator->is_finished = (iterator->current == NULL);
+
+  return iterator->is_finished;
+}
+
+
+/**
+ * raptor_avltree_iterator_get:
+ * @iterator: AVL Tree iterator object
+ *
+ * Get current iteration object
+ *
+ * Return value: object or NULL if iteration is finished
+ */
+void*
+raptor_avltree_iterator_get(raptor_avltree_iterator* iterator)
+{
+  raptor_avltree_node *node = iterator->current;
+
+  if(iterator->is_finished)
+    return NULL;
+
+  iterator->is_finished = (node == NULL);
+  if(iterator->is_finished)
+    return NULL;
+  
+  return node->data;
+}
+
+
+/**
+ * raptor_avltree_print:
+ * @tree: AVL Tree
+ * @stream: stream to print to
+ *
+ * Print the items in the tree in order to a stream (for debugging)
+ * 
+ * Return value: non-0 on failure
+ */
+int
+raptor_avltree_print(raptor_avltree* tree, FILE* stream)
+{
+  int i;
+  int rv = 0;
+  raptor_avltree_iterator* iter = NULL;
+
+  fprintf(stream, "AVL Tree size %u\n", tree->size);
+  for(i = 0, (iter = raptor_new_avltree_iterator(tree, NULL, NULL, 1));
+      iter && !rv;
+      i++, (rv = raptor_avltree_iterator_next(iter))) {
+    void* data = raptor_avltree_iterator_get(iter);
+    if(!data)
+      continue;
+    fprintf(stream, "%d) ", i);
+    if(tree->print_handler)
+      tree->print_handler(data, stream);
+    else
+      fprintf(stream, "Data Node %p\n", RAPTOR_VOIDP(data));
+  }
+  /*assert(i == tree->size);*/
+
+  if(iter)
+    raptor_free_avltree_iterator(iter);
+
+  return 0;
+}
+
+
+#ifdef RAPTOR_DEBUG
+
+static int
+raptor_avltree_dump_internal(raptor_avltree* tree, raptor_avltree_node* node,
+                             int depth, FILE* stream)
+{
+  int i;
+  if(!node)
+    return TRUE;
+
+  for(i = 0; i < depth; i++)
+    fputs("  ", stream);
+  fprintf(stream, "Node %p: parent %p  left %p  right %p  data %p\n",
+          RAPTOR_VOIDP(node),
+          RAPTOR_VOIDP(node->parent),
+          RAPTOR_VOIDP(node->left),
+          RAPTOR_VOIDP(node->right),
+          RAPTOR_VOIDP(node->data));
+  if(tree->print_handler) {
+    for(i= 0; i < depth; i++)
+      fputs("  ", stream);
+    tree->print_handler(node->data, stream);
+  }
+  
+  if(!raptor_avltree_dump_internal(tree, node->left, depth+1, stream))
+    return FALSE;
+
+  if(!raptor_avltree_dump_internal(tree, node->right, depth+1, stream))
+    return FALSE;
+
+  return TRUE;
+}
+
+
+/* debugging tree dump with pointers and depth indenting */
+int
+raptor_avltree_dump(raptor_avltree* tree, FILE* stream)
+{
+  fprintf(stream, "Dumping avltree %p size %u\n", RAPTOR_VOIDP(tree),
+          tree->size);
+
+  return raptor_avltree_dump_internal(tree, tree->root, 0, stream);
+}
+
+
+static void
+raptor_avltree_check_internal(raptor_avltree* tree, raptor_avltree_node* node,
+                              unsigned int* count_p)
+{
+  if(!node)
+    return;
+
+  (*count_p)++;
+  
+  raptor_avltree_check_node(tree, node, NULL, NULL);
+
+  raptor_avltree_check_internal(tree, node->left, count_p);
+
+  raptor_avltree_check_internal(tree, node->right, count_p);
+}
+
+
+/* debugging tree check - parent/child pointers and counts */
+void
+raptor_avltree_check(raptor_avltree* tree)
+{
+  unsigned int count = 0;
+  
+  raptor_avltree_check_internal(tree, tree->root, &count);
+  if(count != tree->size) {
+    fprintf(stderr, "Tree %p nodes count is %u.  actual count %u\n",
+            RAPTOR_VOIDP(tree), tree->size, count);
+    abort();
+  }
+}
+
+#endif
+
+#endif
+
+
+#ifdef STANDALONE
+
+#include <string.h>
+
+typedef struct 
+{
+  FILE *fh;
+  int count;
+  const char** results;
+  int failed;
+} visit_state;
+  
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+static int
+print_string(int depth, void* data, void *user_data) 
+{
+  visit_state* vs = (visit_state*)user_data;
+  
+  fprintf(vs->fh, "%3d: %s\n", vs->count, (char*) data);
+  vs->count++;
+  return 1;
+}
+#endif
+
+static int
+check_string(int depth, void* data, void *user_data) 
+{
+  visit_state* vs = (visit_state*)user_data;
+  const char* result = vs->results[vs->count];
+  
+  if(strcmp((const char*)data, result)) {
+    fprintf(vs->fh, "%3d: Expected '%s' but found '%s'\n", vs->count,
+            result, (char*)data);
+    vs->failed = 1;
+  }
+  vs->count++;
+  
+  return 1;
+}
+
+static int
+compare_strings(const void *l, const void *r)
+{
+  return strcmp((const char*)l, (const char*)r);
+}
+
+
+/* one more prototype */
+int main(int argc, char *argv[]);
+
+int
+main(int argc, char *argv[])
+{
+  raptor_world *world;
+  const char *program = raptor_basename(argv[0]);
+#define ITEM_COUNT 8
+  const char *items[ITEM_COUNT+1] = { "ron", "amy", "jen", "bij", "jib", "daj", "jim", "def", NULL };
+#define DELETE_COUNT 2
+  const char *delete_items[DELETE_COUNT+1] = { "jen", "jim", NULL };
+#define RESULT_COUNT (ITEM_COUNT-DELETE_COUNT)
+  const char *results[RESULT_COUNT+1] = { "amy", "bij", "daj", "def", "jib", "ron", NULL};
+
+  raptor_avltree* tree;
+  raptor_avltree_iterator* iter;
+  visit_state vs;
+  int i;
+
+  world = raptor_new_world();
+  if(!world || raptor_world_open(world))
+    exit(1);
+  
+  tree = raptor_new_avltree(compare_strings,
+                            NULL, /* no free as they are static pointers above */
+                            0);
+  if(!tree) {
+    fprintf(stderr, "%s: Failed to create tree\n", program);
+    exit(1);
+  }
+  for(i = 0; items[i]; i++) {
+    int rc;
+    void* node;
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+    fprintf(stderr, "%s: Adding tree item '%s'\n", program, items[i]);
+#endif
+  
+    rc = raptor_avltree_add(tree, (void*)items[i]);
+    if(rc) {
+      fprintf(stderr,
+              "%s: Adding tree item %d '%s' failed, returning error %d\n",
+              program, i, items[i], rc);
+      exit(1);
+    }
+
+#ifdef RAPTOR_DEBUG
+    raptor_avltree_check(tree);
+#endif
+
+    node = raptor_avltree_search(tree, (void*)items[i]);
+    if(!node) {
+      fprintf(stderr,
+              "%s: Tree did NOT contain item %d '%s' as expected\n",
+              program, i, items[i]);
+      exit(1);
+    }
+  }
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  fprintf(stderr, "%s: Printing tree\n", program);
+  vs.fh = stderr;
+  vs.count = 0;
+  raptor_avltree_visit(tree, print_string, &vs);
+
+  fprintf(stderr, "%s: Dumping tree\n", program);
+  raptor_avltree_dump(tree, stderr);
+#endif
+
+
+
+  for(i = 0; delete_items[i]; i++) {
+    int rc;
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+    fprintf(stderr, "%s: Deleting tree item '%s'\n", program, delete_items[i]);
+#endif
+  
+    rc = raptor_avltree_delete(tree, (void*)delete_items[i]);
+    if(!rc) {
+      fprintf(stderr,
+              "%s: Deleting tree item %d '%s' failed, returning error %d\n",
+              program, i, delete_items[i], rc);
+      exit(1);
+    }
+
+#ifdef RAPTOR_DEBUG
+    raptor_avltree_check(tree);
+#endif
+  }
+
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  fprintf(stderr, "%s: Walking tree forwards via iterator\n", program);
+#endif
+  iter = raptor_new_avltree_iterator(tree, NULL, NULL, 1);
+  for(i = 0; 1; i++) {
+    const char* data = (const char*)raptor_avltree_iterator_get(iter);
+    const char* result = results[i];
+    if((!data && data != result) || (data && strcmp(data, result))) {
+      fprintf(stderr, "%3d: Forwards iterator expected '%s' but found '%s'\n",
+              i, result, data);
+      exit(1);
+    }
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+    fprintf(stderr, "%3d: Got '%s'\n", i, data);
+#endif
+    if(raptor_avltree_iterator_next(iter))
+      break;
+    if(i > RESULT_COUNT) {
+      fprintf(stderr, "Forward iterator did not end on result %i as expected\n", i);
+      exit(1);
+    }
+  }
+  raptor_free_avltree_iterator(iter);
+
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  fprintf(stderr, "%s: Checking tree\n", program);
+#endif
+  vs.count = 0;
+  vs.results = results;
+  vs.failed = 0;
+  raptor_avltree_visit(tree, check_string, &vs);
+  if(vs.failed) {
+    fprintf(stderr, "%s: Checking tree failed\n", program);
+    exit(1);
+  }
+
+  
+  for(i = 0; results[i]; i++) {
+    const char* result = results[i];
+    char* data = (char*)raptor_avltree_remove(tree, (void*)result);
+    if(!data) {
+      fprintf(stderr, "%s: remove %i failed at item '%s'\n", program, i,
+              result);
+      exit(1);
+    }
+    if(strcmp(data, result)) {
+      fprintf(stderr, "%s: remove %i returned %s not %s as expected\n", program,
+              i, data, result);
+      exit(1);
+    }
+  }
+  
+
+#if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1
+  fprintf(stderr, "%s: Freeing tree\n", program);
+#endif
+  raptor_free_avltree(tree);
+
+  raptor_free_world(world);
+
+  /* keep gcc -Wall happy */
+  return(0);
+}
+
+#endif