Useful add-on libraries

1 files changed, 1083 insertions, 0 deletions

diff --git a/avl-1.4.0/rb.c b/avl-1.4.0/rb.c
new file mode 100644
index 0000000..b0ec05d
--- /dev/null
+++ b/avl-1.4.0/rb.c
@@ -0,0 +1,1083 @@
+/* libavl - manipulates AVL trees.
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.
+
+   The author may be contacted at <pfaffben@pilot.msu.edu> on the
+   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
+   through more mundane means. */
+
+/* This is file rb.c in libavl. */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+#if SELF_TEST 
+#include <limits.h>
+#include <time.h>
+#endif
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "rb.h"
+
+#if !PSPP && !__GCC__
+#define inline
+#endif
+
+#if __GNUC__ >= 2
+#define unused __attribute__ ((unused))
+#else
+#define unused
+#endif
+
+#ifdef HAVE_XMALLOC
+void *xmalloc (size_t);
+#else /* !HAVE_XMALLOC */
+/* Allocates SIZE bytes of space using malloc().  Aborts if out of
+   memory. */
+static void *
+xmalloc (size_t size)
+{
+  void *vp;
+
+  if (size == 0)
+    return NULL;
+  vp = malloc (size);
+
+  assert (vp != NULL);
+  if (vp == NULL)
+    {
+      fprintf (stderr, "virtual memory exhausted\n");
+      exit (EXIT_FAILURE);
+    }
+  return vp;
+}
+#endif /* !HAVE_XMALLOC */
+
+/* Creates a red-black tree in arena OWNER (which can be NULL).  The
+   arena is owned by the caller, not by the red-black tree.  CMP is a
+   order function for the data to be stored in the tree.  PARAM is
+   arbitrary data that becomes an argument to the comparison
+   function. */
+rb_tree *
+rb_create (MAYBE_ARENA avl_comparison_func cmp, void *param)
+{
+  rb_tree *tree;
+
+  assert (cmp != NULL);
+  tree = xmalloc (sizeof (rb_tree));
+
+  tree->root.link[0] = NULL;
+  tree->root.link[1] = NULL; 
+  tree->cmp = cmp;
+  tree->count = 0;
+  tree->param = param;
+
+  return tree;
+}
+
+/* Destroy tree TREE.  Function FREE_FUNC is called for every node in
+   the tree as it is destroyed.  
+
+   No effect if the tree has an arena owner and free_func is NULL.
+   The caller owns the arena and must destroy it itself.
+
+   Do not attempt to reuse the tree after it has been freed.  Create a
+   new one.  */
+void
+rb_destroy (rb_tree *tree, avl_node_func free_func)
+{
+  assert (tree != NULL);
+  
+  {
+    /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
+       (postorder traversal). */
+      
+      /* T1. */
+    rb_node *an[RB_MAX_HEIGHT];	/* Stack A: nodes. */
+    unsigned long ab = 0;		/* Stack A: bits. */
+    int ap = 0;			/* Stack A: height. */
+    rb_node *p = tree->root.link[0];
+
+    for (;;)
+      {
+	/* T2. */
+	while (p != NULL)
+	  {
+	    /* T3. */
+	    ab &= ~(1ul << ap);
+	    an[ap++] = p;
+	    p = p->link[0];
+	  }
+
+	/* T4. */
+	for (;;)
+	  {
+	    if (ap == 0)
+	      goto done;
+
+	    p = an[--ap];
+	    if ((ab & (1ul << ap)) == 0)
+	      {
+		ab |= (1ul << ap++);
+		p = p->link[1];
+		break;
+	      }
+      
+	    if (free_func)
+	      free_func (p->data, tree->param);
+	    free (p);
+	  }
+      }
+  }
+
+ done:
+  free (tree);
+}
+
+/* rb_destroy() with FREE_FUNC hardcoded as free(). */
+void
+rb_free (rb_tree *tree)
+{
+  rb_destroy (tree, (avl_node_func) free);
+}
+
+/* Return the number of nodes in TREE. */
+int
+rb_count (const rb_tree *tree)
+{
+  assert (tree != NULL);
+  return tree->count;
+}
+
+/* Copy the contents of TREE to a new tree in arena OWNER.  If COPY is
+   non-NULL, then each data item is passed to function COPY, and the
+   return values are inserted into the new tree; otherwise, the items
+   are copied verbatim from the old tree to the new tree.  Returns the
+   new tree. */
+rb_tree *
+rb_copy (MAYBE_ARENA const rb_tree *tree, avl_copy_func copy)
+{
+  /* This is a combination of Knuth's Algorithm 2.3.1C (copying a
+     binary tree) and Algorithm 2.3.1T as modified by exercise 12
+     (preorder traversal). */
+
+  rb_tree *new_tree;
+
+  /* PT1. */
+  const rb_node *pa[RB_MAX_HEIGHT];	/* Stack PA: nodes. */
+  const rb_node **pp = pa;		/* Stack PA: stack pointer. */
+  const rb_node *p = &tree->root;
+  
+  /* QT1. */
+  rb_node *qa[RB_MAX_HEIGHT];	/* Stack QA: nodes. */
+  rb_node **qp = qa;		/* Stack QA: stack pointer. */
+  rb_node *q;
+  
+  assert (tree != NULL);
+  new_tree = rb_create (tree->cmp, tree->param);
+  new_tree->count = tree->count;
+  q = &new_tree->root;
+
+  for (;;)
+    {
+      /* C4. */
+      if (p->link[0] != NULL)
+	{
+	  rb_node *r = xmalloc (sizeof (rb_node));
+	  r->link[0] = r->link[1] = NULL;
+	  q->link[0] = r;
+	}
+
+      /* C5: Find preorder successors of P and Q.  */
+      goto start;
+      for (;;)
+	{
+	  /* PT2. */
+	  while (p != NULL)
+	    {
+	      goto escape;
+	    start:
+	      /* PT3. */
+	      *pp++ = p;
+	      *qp++ = q;
+	      p = p->link[0];
+	      q = q->link[0];
+	    }
+      
+	  /* PT4. */
+	  if (pp == pa)
+	    {
+	      assert (qp == qa);
+	      return new_tree;
+	    }
+	      
+	  p = *--pp;
+	  q = *--qp;
+
+	  /* PT5. */
+	  p = p->link[1];
+	  q = q->link[1];
+	}
+    escape:
+
+      /* C2. */
+      if (p->link[1])
+	{
+	  rb_node *r = xmalloc (sizeof (rb_node));
+	  r->link[0] = r->link[1] = NULL;
+	  q->link[1] = r;
+	}
+
+      /* C3. */
+      q->color = p->color;
+      if (copy == NULL)
+	q->data = p->data;
+      else
+	q->data = copy (p->data, tree->param);
+    }
+}
+
+/* Walk tree TREE in inorder, calling WALK_FUNC at each node.  Passes
+   PARAM to WALK_FUNC.  */
+void
+rb_walk (const rb_tree *tree, avl_node_func walk_func, void *param)
+{
+  /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
+  assert (tree && walk_func);
+  
+  {
+    /* T1. */
+    const rb_node *an[RB_MAX_HEIGHT];	/* Stack A: nodes. */
+    const rb_node **ap = an;		/* Stack A: stack pointer. */
+    const rb_node *p = tree->root.link[0];
+
+    for (;;)
+      {
+	/* T2. */
+	while (p != NULL)
+	  {
+	    /* T3. */
+	    *ap++ = p;
+	    p = p->link[0];
+	  }
+      
+	/* T4. */
+	if (ap == an)
+	  return;
+	p = *--ap;
+
+	/* T5. */
+	walk_func (p->data, param);
+	p = p->link[1];
+      }
+  }
+}
+
+/* Each call to this function for a given TREE and TRAV return the
+   next item in the tree in inorder.  Initialize the first element of
+   TRAV (init) to 0 before calling the first time.  Returns NULL when
+   out of elements.  */
+void *
+rb_traverse (const rb_tree *tree, rb_traverser *trav)
+{
+  assert (tree && trav);
+
+  /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
+  if (trav->init == 0)
+    {
+      /* T1. */
+      trav->init = 1;
+      trav->nstack = 0;
+      trav->p = tree->root.link[0];
+    }
+  else
+    /* T5. */
+    trav->p = trav->p->link[1];
+
+  for (;;)
+    {
+      /* T2. */
+      while (trav->p != NULL)
+	{
+	  /* T3. */
+	  trav->stack[trav->nstack++] = trav->p;
+	  trav->p = trav->p->link[0];
+	}
+      
+      /* T4. */
+      if (trav->nstack == 0)
+	{
+	  trav->init = 0;
+	  return NULL;
+	}
+      trav->p = trav->stack[--trav->nstack];
+
+      /* T5. */
+      return trav->p->data;
+    }
+}
+
+/* Search TREE for an item matching ITEM.  If found, returns a pointer
+   to the address of the item.  If none is found, ITEM is inserted
+   into the tree, and a pointer to the address of ITEM is returned.
+   In either case, the pointer returned can be changed by the caller,
+   or the returned data item can be directly edited, but the key data
+   in the item must not be changed. */
+void **
+rb_probe (rb_tree *tree, void *item)
+{
+  /* Algorithm based on RB-Insert from section 14.3 of _Introduction
+     to Algorithms_, Cormen et al., MIT Press 1990, ISBN
+     0-262-03141-8. */
+
+  rb_node *ap[RB_MAX_HEIGHT];		/* Stack A: Nodes. */
+  char ad[RB_MAX_HEIGHT];		/* Stack A: Directions. */
+  int ak = 1;				/* Stack A: Pointer. */
+
+  rb_node *t, *x, *y, *n;
+  
+  assert (tree != NULL);
+  t = &tree->root;
+  x = t->link[0];
+
+  if (x == NULL)
+    {
+      tree->count++;
+      assert (tree->count == 1);
+      x = t->link[0] = xmalloc (sizeof (rb_node));
+      x->data = item;
+      x->link[0] = x->link[1] = NULL;
+      x->color = RB_BLACK;
+      return &x->data;
+    }
+
+  ad[0] = 0;
+  ap[0] = &tree->root;
+
+  for (;;)
+    {
+      int diff = tree->cmp (item, x->data, tree->param);
+
+      if (diff < 0)
+	{
+	  ap[ak] = x;
+	  ad[ak++] = 0;
+	  y = x->link[0];
+	  if (y == NULL)
+	    {
+	      n = x = x->link[0] = xmalloc (sizeof (rb_node));
+	      break;
+	    }
+	}
+      else if (diff > 0)
+	{
+	  ap[ak] = x;
+	  ad[ak++] = 1;
+	  y = x->link[1];
+	  if (y == NULL)
+	    {
+	      n = x = x->link[1] = xmalloc (sizeof (rb_node));
+	      break;
+	    }
+	}
+      else
+	return &x->data;
+
+      x = y;
+    }
+  
+  tree->count++;
+  x->data = item;
+  x->link[0] = x->link[1] = NULL;
+  x->color = RB_RED;
+
+  for (;;)
+    {
+      if (ak < 3 || ap[ak - 1]->color != RB_RED)
+	break;
+      
+      if (ad[ak - 2] == 0)
+	{
+	  y = ap[ak - 2]->link[1];
+	  if (y != NULL && y->color == RB_RED)
+	    {
+	      /* Case 1. */
+	      ap[ak - 1]->color = y->color = RB_BLACK;
+	      ap[ak - 2]->color = RB_RED;
+	      ak -= 2;
+	    }
+	  else
+	    {
+	      if (ad[ak - 1] == 1)
+		{
+		  /* Case 2. */
+		  x = ap[ak - 1];
+		  y = x->link[1];
+		  x->link[1] = y->link[0];
+		  y->link[0] = x;
+		  ap[ak - 2]->link[0] = y;
+		}
+	      else
+		y = ap[ak - 1];
+
+	      /* Case 3. */
+	      x = ap[ak - 2];
+	      x->color = RB_RED;
+	      y->color = RB_BLACK;
+
+	      x->link[0] = y->link[1];
+	      y->link[1] = x;
+	      ap[ak - 3]->link[(int) ad[ak - 3]] = y;
+
+	      break;
+	    }
+	}
+      else
+	{
+	  y = ap[ak - 2]->link[0];
+	  if (y != NULL && y->color == RB_RED)
+	    {
+	      /* Case 1. */
+	      ap[ak - 1]->color = y->color = RB_BLACK;
+	      ap[ak - 2]->color = RB_RED;
+	      ak -= 2;
+	    }
+	  else
+	    {
+	      if (ad[ak - 1] == 0)
+		{
+		  /* Case 2. */
+		  x = ap[ak - 1];
+		  y = x->link[0];
+		  x->link[0] = y->link[1];
+		  y->link[1] = x;
+		  ap[ak - 2]->link[1] = y;
+		}
+	      else
+		y = ap[ak - 1];
+
+	      /* Case 3. */
+	      x = ap[ak - 2];
+	      x->color = RB_RED;
+	      y->color = RB_BLACK;
+
+	      x->link[1] = y->link[0];
+	      y->link[0] = x;
+	      ap[ak - 3]->link[(int) ad[ak - 3]] = y;
+	      break;
+	    }
+	}
+    }
+
+  tree->root.link[0]->color = RB_BLACK;
+  
+  return &n->data;
+}
+  
+/* Search TREE for an item matching ITEM, and return it if found. */
+void *
+rb_find (const rb_tree *tree, const void *item)
+{
+  const rb_node *p;
+
+  assert (tree != NULL);
+  for (p = tree->root.link[0]; p; )
+    {
+      int diff = tree->cmp (item, p->data, tree->param);
+
+      if (diff < 0)
+	p = p->link[0];
+      else if (diff > 0)
+	p = p->link[1];
+      else
+	return p->data;
+    }
+
+  return NULL;
+}
+
+/* Search TREE for an item close to the value of ITEM, and return it.
+   This function will return a null pointer only if TREE is empty. */
+void *
+rb_find_close (const rb_tree *tree, const void *item)
+{
+  const rb_node *p;
+
+  assert (tree != NULL);
+  p = tree->root.link[0];
+  if (p == NULL)
+    return NULL;
+  
+  for (;;)
+    {
+      int diff = tree->cmp (item, p->data, tree->param);
+      int t;
+
+      if (diff < 0)
+	t = 0;
+      else if (diff > 0)
+	t = 1;
+      else
+	return p->data;
+
+      if (p->link[t])
+	p = p->link[t];
+      else
+	return p->data;
+    }
+}
+
+/* Searches red-black tree TREE for an item matching ITEM.  If found,
+   the item is removed from the tree and the actual item found is
+   returned to the caller.  If no item matching ITEM exists in the
+   tree, returns NULL. */
+void *
+rb_delete (rb_tree *tree, const void *item)
+{
+  /* Algorithm based on RB-Delete and RB-Delete-Fixup from section
+     14.4 of _Introduction to Algorithms_, Cormen et al., MIT Press
+     1990, ISBN 0-262-03141-8. */
+
+  rb_node *pa[RB_MAX_HEIGHT];		/* Stack P: Nodes. */
+  char a[RB_MAX_HEIGHT];		/* Stack P: Bits. */
+  int k = 1;				/* Stack P: Pointer. */
+  
+  rb_node *w, *x, *y, *z;
+
+  assert (tree != NULL);
+
+  a[0] = 0;
+  pa[0] = &tree->root;
+  z = tree->root.link[0];
+  for (;;)
+    {
+      int diff;
+
+      if (z == NULL)
+	return NULL;
+
+      diff = tree->cmp (item, z->data, tree->param);
+      if (diff == 0)
+	break;
+
+      pa[k] = z;
+      if (diff < 0)
+	{
+	  z = z->link[0];
+	  a[k] = 0;
+	}
+      else if (diff > 0)
+	{
+	  z = z->link[1];
+	  a[k] = 1;
+	}
+      k++;
+    }
+  tree->count--;
+  
+  item = z->data;
+
+  /* RB-Delete: Line 1. */
+  if (z->link[0] == NULL || z->link[1] == NULL)
+    {
+      /* Line 2. */
+      y = z;
+
+      /* Lines 4-6. */
+      if (y->link[0] != NULL)
+	x = y->link[0];
+      else
+	x = y->link[1];
+
+      pa[k - 1]->link[(int) a[k - 1]] = x;
+    }
+  else
+    {
+      pa[k] = z;
+      a[k++] = 1;
+
+      /* Line 3. */
+      y = z->link[1];
+      while (y->link[0])
+	{
+	  pa[k] = y;
+	  a[k++] = 0;
+	  y = y->link[0];
+	}
+
+      /* Lines 4-6. */
+      x = y->link[1];
+
+      /* Lines 13-15. */
+      z->data = y->data;
+      pa[k - 1]->link[(int) a[k - 1]] = x;
+    }
+
+  /* Line 16. */
+  if (y->color == RB_RED)
+    {
+      free (y);
+      return (void *) item;
+    }
+
+  free (y);
+
+  /* Numbers below are line numbers from RB-Delete-Fixup. */
+  while (k > 1 && (x == NULL || x->color == RB_BLACK))			/* 1 */
+    {
+      if (a[k - 1] == 0)						/* 2 */
+	{
+	  w = pa[k - 1]->link[1];					/* 3 */
+
+	  if (w->color == RB_RED)					/* 4 */
+	    {
+	      /* Case 1. */
+	      w->color = RB_BLACK;					/* 5 */
+	      pa[k - 1]->color = RB_RED;				/* 6 */
+
+	      pa[k - 1]->link[1] = w->link[0];				/* 7 */
+	      w->link[0] = pa[k - 1];
+	      pa[k - 2]->link[(int) a[k - 2]] = w;
+
+	      pa[k] = pa[k - 1];
+	      a[k] = 0;
+	      pa[k - 1] = w;
+	      k++;
+
+	      w = pa[k - 1]->link[1];					/* 8 */
+	    }
+
+	  if ((w->link[0] == NULL || w->link[0]->color == RB_BLACK)	/* 9 */
+	      && (w->link[1] == NULL || w->link[1]->color == RB_BLACK))
+	    {
+	      /* Case 2. */
+	      w->color = RB_RED;				       /* 10 */
+
+	      x = pa[k - 1];					       /* 11 */
+	      k--;
+	    }
+	  else
+	    {
+	      if (w->link[1] == NULL || w->link[1]->color == RB_BLACK) /* 12 */
+		{
+		  /* Case 3. */
+		  w->link[0]->color = RB_BLACK;			       /* 13 */
+		  w->color = RB_RED;				       /* 14 */
+
+		  y = w->link[0];				       /* 15 */
+		  w->link[0] = y->link[1];
+		  y->link[1] = w;
+
+		  w = pa[k - 1]->link[1] = y;			       /* 16 */
+		}
+
+	      /* Case 4. */
+	      w->color = pa[k - 1]->color;			       /* 17 */
+	      pa[k - 1]->color = RB_BLACK;			       /* 18 */
+	      w->link[1]->color = RB_BLACK;			       /* 19 */
+
+	      pa[k - 1]->link[1] = w->link[0];			       /* 20 */
+	      w->link[0] = pa[k - 1];
+	      pa[k - 2]->link[(int) a[k - 2]] = w;
+
+	      x = tree->root.link[0];				       /* 21 */
+	      break;
+	    }
+	}
+      else
+	{
+	  w = pa[k - 1]->link[0];
+	  if (w->color == RB_RED)
+	    {
+	      /* Case 1. */
+	      w->color = RB_BLACK;
+	      pa[k - 1]->color = RB_RED;
+
+	      pa[k - 1]->link[0] = w->link[1];
+	      w->link[1] = pa[k - 1];
+	      pa[k - 2]->link[(int) a[k - 2]] = w;
+
+	      pa[k] = pa[k - 1];
+	      a[k] = 1;
+	      pa[k - 1] = w;
+	      k++;
+
+	      w = pa[k - 1]->link[0];
+	    }
+
+	  if ((w->link[0] == NULL || w->link[0]->color == RB_BLACK)
+	      && (w->link[1] == NULL || w->link[1]->color == RB_BLACK))
+	    {
+	      /* Case 2. */
+	      w->color = RB_RED;
+	      x = pa[k - 1];
+	      k--;
+	    }
+	  else
+	    {
+	      if (w->link[0] == NULL || w->link[0]->color == RB_BLACK)
+		{
+		  /* Case 3. */
+		  w->link[1]->color = RB_BLACK;
+		  w->color = RB_RED;
+
+		  y = w->link[1];
+		  w->link[1] = y->link[0];
+		  y->link[0] = w;
+
+		  w = pa[k - 1]->link[0] = y;
+		}
+	      
+	      /* Case 4. */
+	      w->color = pa[k - 1]->color;
+	      pa[k - 1]->color = RB_BLACK;
+	      w->link[0]->color = RB_BLACK;
+
+	      pa[k - 1]->link[0] = w->link[1];
+	      w->link[1] = pa[k - 1];
+	      pa[k - 2]->link[(int) a[k - 2]] = w;
+
+	      x = tree->root.link[0];
+	      break;
+	    }
+	}
+    }
+
+  if (x != NULL)
+    x->color = RB_BLACK;					       /* 23 */
+  
+  return (void *) item;
+}
+
+/* Inserts ITEM into TREE.  Returns NULL if the item was inserted,
+   otherwise a pointer to the duplicate item. */
+void *
+rb_insert (rb_tree *tree, void *item)
+{
+  void **p;
+  
+  assert (tree != NULL);
+  
+  p = rb_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+/* If ITEM does not exist in TREE, inserts it and returns NULL.  If a
+   matching item does exist, it is replaced by ITEM and the item
+   replaced is returned.  The caller is responsible for freeing the
+   item returned. */
+void *
+rb_replace (rb_tree *tree, void *item)
+{
+  void **p;
+
+  assert (tree != NULL);
+  
+  p = rb_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+
+/* Delete ITEM from TREE when you know that ITEM must be in TREE.  For
+   debugging purposes. */
+void *
+(rb_force_delete) (rb_tree *tree, void *item)
+{
+  void *found = rb_delete (tree, item);
+  assert (found != NULL);
+  return found;
+}
+
+#if SELF_TEST
+
+/* Used to flag delayed aborting. */
+int done = 0;
+
+/* Print the structure of node NODE of a red-black tree, which is
+   LEVEL levels from the top of the tree.  Uses different delimiters
+   to visually distinguish levels. */
+void
+print_structure (rb_node *node, int level)
+{
+  char lc[] = "([{<`/";
+  char rc[] = ")]}>'\\";
+
+  assert (level <= 10);
+  
+  if (node == NULL)
+    {
+      printf (" nil");
+      fflush (stdout);
+      return;
+    }
+  printf (" %c%d%c",
+	  lc[level % 6], (int) node->data,
+	  node->color == RB_BLACK ? 'b' : 'r');
+  fflush (stdout);
+  if (node->link[0] || node->link[1])
+    print_structure (node->link[0], level + 1);
+  if (node->link[1])
+    print_structure (node->link[1], level + 1);
+  printf ("%c", rc[level % 6]);
+  fflush (stdout);
+}
+
+/* Compare two integers A and B and return a strcmp()-type result. */
+int
+compare_ints (const void *a, const void *b, void *param unused)
+{
+  return ((int) a) - ((int) b);
+}
+
+/* Print the value of integer A. */
+void
+print_int (void *a, void *param unused)
+{
+  printf (" %d", (int) a);
+}
+
+/* Linearly print contents of TREE. */
+void
+print_contents (rb_tree *tree)
+{
+  rb_walk (tree, print_int, NULL);
+  printf ("\n");
+}
+
+/* Examine NODE in a red-black tree.  *COUNT is increased by the
+   number of nodes in the tree, including the current one.  Returns
+   the number of black nodes (including this node) in a path from this
+   node to any leaf. */
+int
+recurse_tree (rb_node *node, int *count, int ge, int le)
+{
+  if (node) 
+    {
+      const int d = (int) node->data;
+      int nl = 1;
+      int nr = 1;
+      
+      (*count)++;
+
+      if (!(d >= ge) || !(d <= le))
+	{
+	  printf (" Node %d is out of order in the tree.\n", d);
+	  done = 1;
+	}
+
+      if (node->link[0])
+	nl = recurse_tree (node->link[0], count, ge, d - 1);
+      if (node->link[1])
+	nr = recurse_tree (node->link[1], count, d + 1, le);
+	  
+      if (node->color != RB_RED && node->color != RB_BLACK)
+	{
+	  printf (" Node %d is neither red nor black (%d).\n", d, node->color);
+	  done = 1;
+	}
+
+      if (node->color == RB_RED
+	  && node->link[0] && node->link[0]->color == RB_RED)
+	{
+	  printf (" Red node %d has red left child %d\n",
+		  d, (int) node->link[0]->data);
+	  done = 1;
+	}
+      
+      if (node->color == RB_RED
+	  && node->link[1] && node->link[1]->color == RB_RED)
+	{
+	  printf (" Red node %d has red right child %d\n",
+		  d, (int) node->link[1]->data);
+	  done = 1;
+	}
+      
+      if (nl != nr)
+	{
+	  printf (" Node %d has two different black-heights: left bh=%d, "
+		  "right bh=%d\n", d, nl, nr);
+	  done = 1;
+	}
+
+      return (node->color == RB_BLACK) + nl;
+    }
+  else return 1;
+}
+
+/* Check that everything about TREE is kosher. */
+void
+verify_tree (rb_tree *tree)
+{
+  int count = 0;
+  recurse_tree (tree->root.link[0], &count, INT_MIN, INT_MAX);
+  if (count != tree->count)
+    {
+      printf (" Tree has %d nodes, but tree count is %d.\n",
+	      count, tree->count);
+      done = 1;
+    }
+  if (done)
+    abort ();
+}
+
+/* Arrange the N elements of ARRAY in random order. */
+void
+shuffle (int *array, int n)
+{
+  int i;
+  
+  for (i = 0; i < n; i++)
+    {
+      int j = i + rand () % (n - i);
+      int t = array[j];
+      array[j] = array[i];
+      array[i] = t;
+    }
+}
+
+/* Compares red-black trees rooted at A and B, making sure that they
+   are identical. */
+void
+compare_trees (rb_node *a, rb_node *b)
+{
+  if (a == NULL || b == NULL)
+    {
+      assert (a == NULL && b == NULL);
+      return;
+    }
+  if (a->data != b->data || a->color != b->color
+      || ((a->link[0] != NULL) ^ (b->link[0] != NULL))
+      || ((a->link[1] != NULL) ^ (b->link[1] != NULL)))
+    {
+      printf (" Copied nodes differ: %d b=%d a->color=%d b->color=%d a:",
+	      (int) a->data, (int) b->data, a->color, b->color);
+      if (a->link[0])
+	printf ("l");
+      if (a->link[1])
+	printf ("r");
+      printf (" b:");
+      if (b->link[0])
+	printf ("l");
+      if (b->link[1])
+	printf ("r");
+      printf ("\n");
+      abort ();
+    }
+  if (a->link[0] != NULL)
+    compare_trees (a->link[0], b->link[0]);
+  if (a->link[1] != NULL)
+    compare_trees (a->link[1], b->link[1]);
+}
+
+/* Simple stress test procedure for the red-black tree routines.  Does
+   the following:
+
+   * Generate a random number seed.  By default this is generated from
+   the current time.  You can also pass a seed value on the command
+   line if you want to test the same case.  The seed value is
+   displayed.
+
+   * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
+   into it, in random order.  Verify the tree structure after each
+   insertion.
+   
+   * Remove each integer from the tree, in a different random order.
+   After each deletion, verify the tree structure; also, make a copy
+   of the tree into a new tree, verify the copy and compare it to the
+   original, then destroy the copy.
+
+   * Destroy the tree, increment the random seed value, and start over.
+
+   If you make any modifications to the red-black tree routines, then
+   you might want to insert some calls to print_structure() at
+   strategic places in order to be able to see what's really going on.
+   Also, memory debuggers like Checker or Purify are very handy. */
+#define TREE_SIZE 16
+#define N_ITERATIONS 1024
+int
+main (int argc, char **argv)
+{
+  int array[TREE_SIZE];
+  int seed;
+  int iteration;
+  
+  if (argc == 2)
+    seed = atoi (argv[1]);
+  else
+    seed = time (0) * 257 % 32768;
+
+  fputs ("Testing rb...\n", stdout);
+  
+  for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
+    {
+      rb_tree *tree;
+      int i;
+      
+      printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
+      fflush (stdout);
+      
+      srand (seed++);
+
+      for (i = 0; i < TREE_SIZE; i++)
+	array[i] = i;
+      shuffle (array, TREE_SIZE);
+      
+      tree = rb_create (compare_ints, NULL);
+      for (i = 0; i < TREE_SIZE; i++)
+	rb_force_insert (tree, (void *) (array[i]));
+      verify_tree (tree);
+
+      shuffle (array, TREE_SIZE);
+      for (i = 0; i < TREE_SIZE; i++)
+	{
+	  rb_tree *copy;
+
+	  rb_delete (tree, (void *) (array[i]));
+	  verify_tree (tree);
+
+	  copy = rb_copy (tree, NULL);
+	  verify_tree (copy);
+	  compare_trees (tree->root.link[0], copy->root.link[0]);
+	  rb_destroy (copy, NULL);
+
+	  if (i % 128 == 0)
+	    {
+	      putchar ('.');
+	      fflush (stdout);
+	    }
+	}
+      fputs (" good.\n", stdout);
+
+      rb_destroy (tree, NULL);
+    }
+  
+  return 0;
+}
+#endif /* SELF_TEST */
+
+/*
+  Local variables:
+  compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./rb-test rb.c"
+  End:
+*/