Mercurial > repos > libtu-3 / changeset

--- a/LICENSE	Sun Mar 07 22:45:24 2004 +0100
+++ b/LICENSE	Wed Mar 10 17:08:26 2004 +0100
@@ -1,7 +1,7 @@
 
-You may distribute and modify this library under the terms of either
-the Clarified Artistic License or the GNU LGPL, version 2.1 or later,
-both reproduced below.
+The Red-Black tree code is under the GNU LGPL. The rest of the files
+you may distribute and modify under either under the Clarified Artistic
+License or the GNU LGPL, version 2.1 or later, both reproduced below.
 
 
 -------------------

--- a/Makefile	Sun Mar 07 22:45:24 2004 +0100
+++ b/Makefile	Wed Mar 10 17:08:26 2004 +0100
@@ -12,7 +12,7 @@
 CFLAGS += $(C89_SOURCE) $(POSIX_SOURCE) 
 
 SOURCES=misc.c output.c util.c optparser.c parser.c tokenizer.c \
-        map.c obj.c objlist.c errorlog.c symlist.c
+        map.c obj.c objlist.c errorlog.c symlist.c rb.c
 
 ifdef LIBTU_NO_ERRMSG
 DEFINES += -DLIBTU_NO_ERRMSG

--- a/README	Sun Mar 07 22:45:24 2004 +0100
+++ b/README	Wed Mar 10 17:08:26 2004 +0100
@@ -5,10 +5,12 @@
 <tuomov at iki.fi>
 
 
-Libtu is a small utility library for programs written in C. You may
-distribute and modify it under the terms of either the Clarified
-Artistic License or the GNU LGPL, version 2.1 or later, both reproduced
-in the file LICENSE.
+Libtu is a small utility library for programs written in C. 
+
+Most of this library may be distributed and modified under either under
+the Clarified Artistic License or the GNU LGPL, version 2.1 or later, 
+both reproduced in the file LICENSE. The red-black tree code is under
+the GNU LGPL; see README.rb for details.
 
 To build the library, first edit system.mk to customize it for your
 system if necessary. Then 'make depend && make'.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/README.rb	Wed Mar 10 17:08:26 2004 +0100
@@ -0,0 +1,113 @@
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library 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
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+---------------------------------------------------------------------------
+Jim Plank
+plank@cs.utk.edu
+http://www.cs.utk.edu/~plank
+
+Department of Computer Science
+University of Tennessee
+107 Ayres Hall
+Knoxville, TN 37996
+
+615-974-4397
+$Revision: 1.2 $
+---------------------------------------------------------------------------
+
+Rb.c and rb.h are files for doing general red-black trees.
+
+The directory ansi contains ansi-standard c code for rb-trees (there
+are some gross pointer casts there but don't worry about them.  They
+work).  The directory non-ansi contains straight c code for rb-trees.
+The ansi version can also be used by c++ (it has been tested).
+
+Rb.h contains the typedef for red-black tree structures.  Basically, 
+red-black trees are balanced trees whose external nodes are sorted
+by a key, and connected in a linked list.  The following is how
+you use rb.c and rb.h:
+
+Include rb.h in your source.
+
+Make_rb() returns the head of a red-black tree.  It serves two functions:
+Its p.root pointer points to the root of the red-black tree.  Its 
+c.list.flink and c.list.blink pointers point to the first and last 
+external nodes of the tree.  When the tree is empty, all these pointers
+point to itself.
+
+The external nodes can be traversed in sorted order with their
+c.list.flink and c.list.blink pointers.  The macros rb_first, rb_last,
+rb_next, rb_prev, and rb_traverse can be used to traverse external node lists.
+
+External nodes hold two pieces of information: the key and the value
+(in k.key and v.val, respectively).   The key can be a character 
+string, an integer, or a general pointer.  Val is typed as a character
+pointer, but can be any pointer.  If the key is a character string, 
+then one can insert it, and a value into a tree with rb_insert().  If
+it is an integer, then rb_inserti() should be used.  If it is a general 
+pointer, then rb_insertg() must be used, with a comparison function 
+passed as the fourth argument.  This function takes two keys as arguments,
+and returns a negative value, positive value, or 0, depending on whether
+the first key is less than, greater than or equal to the second.  Thus,
+one could use rb_insertg(t, s, v, strcmp) to insert the value v with 
+a character string s into the tree t.
+
+Rb_find_key(t, k) returns the external node in t whose value is equal
+k or whose value is the smallest value greater than k.  (Here, k is
+a string).  If there is no value greater than or equal to k, then 
+t is returned.  Rb_find_ikey(t,k) works when k is an integer, and 
+Rb_find_gkey(t,k,cmp) works for general pointers.
+
+Rb_find_key_n(t, k, n) is the same as rb_find_key, except that it
+returns whether or not k was found in n (n is an int *).  Rb_find_ikey_n
+and Rb_find_gkey_n are the analogous routines for integer and general
+keys.
+
+Rb_insert_b(e, k, v) makes a new external node with key k and val v, and 
+inserts it before the external node e.  If e is the head of a tree, 
+then the new node is inserted at the end of the external node list.
+If this insertion violates sorted order, no error is flagged.  It is 
+assumed that the user knows what he/she is doing.  Rb_insert_a(e,k,v)
+inserts the new node after e (if e = t, it inserts the new node at the
+beginning of the list).
+
+Rb_insert() is therefore really a combination of Rb_find_key() and
+Rb_insert_b().
+
+Rb_delete_node(e) deletes the external node e from a tree (and thus from 
+the linked list of external nodes).  The node is free'd as well, so
+don't retain pointers to it.
+
+Red-black trees are spiffy because find_key, insert, and delete are all
+done in log(n) time.  Thus, they can be freely used instead of hash-tables,
+with the benifit of having the elements in sorted order at all times, and
+with the guarantee of operations being in log(n) time.
+
+Other routines:
+
+Rb_print_tree() will grossly print out a red-black tree with string keys.
+Rb_iprint_tree() will do the same with trees with integer keys.
+Rb_nblack(e) will report the number of black nodes on the path from external
+  node e to the root.  The path length is less than twice this value.
+Rb_plength(e) reports the length of the path from e to the root.
+
+
+You can find a general description of red-black trees in any basic algorithms
+text.  E.g. ``Introduction to Algorithms'', by Cormen, Leiserson and Rivest
+(McGraw Hill).  An excellent and complete description of red-black trees
+can also be found in Chapter 1 of Heather Booth's PhD disseratation:
+``Some Fast Algorithms on Graphs and Trees'', Princeton University, 1990.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rb-test.c	Wed Mar 10 17:08:26 2004 +0100
@@ -0,0 +1,98 @@
+/*
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library 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
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/* Revision 1.2.  Jim Plank */
+
+#include "rb.h"
+#include <stdio.h>
+
+/* an example -- this allocates a red-black tree for integers.  For a 
+ * user-specified number of iterations, it does the following:
+
+ * delete a random element in the tree.
+ * make two new random elements, and insert them into the tree
+ 
+ * At the end, it prints the sorted list of elements, and then prints
+ * stats of the number of black nodes in any path in the tree, and 
+ * the minimum and maximum path lengths.
+  
+ * Rb_find_ikey and rb_inserti could have been used, but instead
+ * rb_find_gkey and rb_insertg were used to show how they work.
+  
+ */
+
+int icomp(char *i, char *j)
+{
+  int I, J;
+  
+  I = (int) i;
+  J = (int) j;
+  if (I == J) return 0;
+  if (I > J) return -1; else return 1;
+}
+
+main(int argc, char **argv)
+{
+  int i, j, tb, nb, mxp, mnp, p;
+  int iterations;
+  Rb_node argt, t;
+  int *a;
+
+  if (argc != 2) {
+    fprintf(stderr, "usage: main #iterations\n");
+    exit(1);
+  }
+  argt = make_rb();
+  srandom(time(0));
+  iterations = atoi(argv[1]);
+  a = (int *) malloc (iterations*sizeof(int));
+
+  for (i = 0; i < atoi(argv[1]); i++) {
+    if (i > 0) {
+      j = random()%i;
+      
+      rb_delete_node(rb_find_gkey(argt, (char *) (a[j]), icomp));
+      a[j] = random() % 1000;
+      rb_insertg(argt, (char *) (a[j]), NULL, icomp);
+    }
+    a[i] = random() % 1000;
+    rb_insertg(argt, (char *) (a[i]), NULL, icomp);
+  }
+  tb = 0;
+  mxp = 0;
+  mnp = 0;
+  rb_traverse(t, argt) {
+    printf("%d ", t->k.ikey);
+    nb = rb_nblack(t);
+    p = rb_plength(t);
+    if (tb == 0) {
+      tb = nb;
+    } else if (tb != nb) {
+      printf("Conflict: tb=%d, nb=%d\n", tb, nb);
+      exit(1);
+    }
+    mxp = (mxp == 0 || mxp < p) ? p : mxp;
+    mnp = (mnp == 0 || mxp > p) ? p : mnp;
+  }
+  printf("\n");  
+
+  printf("Nblack = %d\n", tb);
+  printf("Max    = %d\n", mxp);
+  printf("Min    = %d\n", mnp);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rb.c	Wed Mar 10 17:08:26 2004 +0100
@@ -0,0 +1,616 @@
+/*
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library 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
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* Revision 1.2.  Jim Plank */
+
+/* Original code by Jim Plank (plank@cs.utk.edu) */
+/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
+ 
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include "rb.h"
+ 
+static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il);
+static Rb_node lprev(Rb_node n);
+static Rb_node rprev(Rb_node n);
+static void recolor(Rb_node n);
+static void single_rotate(Rb_node y, int l);
+static void rb_print_tree(Rb_node t, int level);
+static void rb_iprint_tree(Rb_node t, int level);
+
+ 
+#define isred(n) (n->s.red)
+#define isblack(n) (!isred(n))
+#define isleft(n) (n->s.left)
+#define isright(n) (!isleft(n))
+#define isint(n) (n->s.internal)
+#define isext(n) (!isint(n))
+#define ishead(n) (n->s.head)
+#define isroot(n) (n->s.root)
+#define setred(n) n->s.red = 1
+#define setblack(n) n->s.red = 0
+#define setleft(n) n->s.left = 1
+#define setright(n) n->s.left = 0
+#define sethead(n) n->s.head = 1
+#define setroot(n) n->s.root = 1
+#define setint(n) n->s.internal = 1
+#define setext(n) n->s.internal = 0
+#define setnormal(n) { n->s.root = 0; n ->s.head = 0; }
+#define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \
+                                : n->p.parent->c.child.left)
+ 
+static void insert(Rb_node item, Rb_node list)	/* Inserts to the end of a list */
+{
+  Rb_node last_node;
+ 
+  last_node = list->c.list.blink;
+ 
+  list->c.list.blink = item;
+  last_node->c.list.flink = item;
+  item->c.list.blink = last_node;
+  item->c.list.flink = list;
+}
+ 
+static void delete_item(Rb_node item)		/* Deletes an arbitrary iterm */
+{
+  item->c.list.flink->c.list.blink = item->c.list.blink;
+  item->c.list.blink->c.list.flink = item->c.list.flink;
+}
+
+#define mk_new_ext(new, kkkey, vvval) {\
+  new = (Rb_node) malloc(sizeof(struct rb_node));\
+  new->v.val = vvval;\
+  new->k.key = kkkey;\
+  setext(new);\
+  setblack(new);\
+  setnormal(new);\
+}
+ 
+static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il)
+{
+  Rb_node newnode;
+ 
+  newnode = (Rb_node) malloc(sizeof(struct rb_node));
+  setint(newnode);
+  setred(newnode);
+  setnormal(newnode);
+  newnode->c.child.left = l;
+  newnode->c.child.right = r;
+  newnode->p.parent = p;
+  newnode->k.lext = l;
+  newnode->v.rext = r;
+  l->p.parent = newnode;
+  r->p.parent = newnode;
+  setleft(l);
+  setright(r);
+  if (ishead(p)) {
+    p->p.root = newnode;
+    setroot(newnode);
+  } else if (il) {
+    setleft(newnode);
+    p->c.child.left = newnode;
+  } else {
+    setright(newnode);
+    p->c.child.right = newnode;
+  }
+  recolor(newnode);
+}  
+  
+   
+Rb_node lprev(Rb_node n)
+{
+  if (ishead(n)) return n;
+  while (!isroot(n)) {
+    if (isright(n)) return n->p.parent;
+    n = n->p.parent;
+  }
+  return n->p.parent;
+}
+ 
+Rb_node rprev(Rb_node n)
+{
+  if (ishead(n)) return n;
+  while (!isroot(n)) {
+    if (isleft(n)) return n->p.parent;
+    n = n->p.parent;
+  }
+  return n->p.parent;
+}
+ 
+Rb_node make_rb()
+{
+  Rb_node head;
+ 
+  head = (Rb_node) malloc (sizeof(struct rb_node));
+  head->c.list.flink = head;
+  head->c.list.blink = head;
+  head->p.root = head;
+  head->k.key = "";
+  sethead(head);
+  return head;
+}
+ 
+Rb_node rb_find_key_n(Rb_node n, char *key, int *fnd)
+{
+  int cmp;
+ 
+  *fnd = 0;
+  if (!ishead(n)) {
+    fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
+    exit(1);
+  }
+  if (n->p.root == n) return n;
+  cmp = strcmp(key, n->c.list.blink->k.key);
+  if (cmp == 0) {
+    *fnd = 1;
+    return n->c.list.blink; 
+  }
+  if (cmp > 0) return n; 
+  else n = n->p.root;
+  while (1) {
+    if (isext(n)) return n;
+    cmp = strcmp(key, n->k.lext->k.key);
+    if (cmp == 0) {
+      *fnd = 1;
+      return n->k.lext;
+    }
+    if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
+  }
+}
+ 
+Rb_node rb_find_key(Rb_node n, char *key)
+{
+  int fnd;
+  return rb_find_key_n(n, key, &fnd);
+}
+ 
+Rb_node rb_find_ikey_n(Rb_node n, int ikey, int *fnd)
+{
+  *fnd = 0;
+  if (!ishead(n)) {
+    fprintf(stderr, "rb_find_ikey_n called on non-head 0x%x\n", n);
+    exit(1);
+  }
+  if (n->p.root == n) return n;
+  if (ikey == n->c.list.blink->k.ikey) {
+    *fnd = 1;
+    return n->c.list.blink; 
+  }
+  if (ikey > n->c.list.blink->k.ikey) return n; 
+  else n = n->p.root;
+  while (1) {
+    if (isext(n)) return n;
+    if (ikey == n->k.lext->k.ikey) {
+      *fnd = 1;
+      return n->k.lext;
+    }
+    n = (ikey < n->k.lext->k.ikey) ? n->c.child.left : n->c.child.right;
+  }
+}
+ 
+Rb_node rb_find_ikey(Rb_node n, int ikey)
+{
+  int fnd;
+  return rb_find_ikey_n(n, ikey, &fnd);
+}
+ 
+Rb_node rb_find_gkey_n(Rb_node n, char *key,int (*fxn)(char *, char *), int *fnd)
+{
+  int cmp;
+ 
+  *fnd = 0;
+  if (!ishead(n)) {
+    fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
+    exit(1);
+  }
+  if (n->p.root == n) return n;
+  cmp = (*fxn)(key, n->c.list.blink->k.key);
+  if (cmp == 0) {
+    *fnd = 1;
+    return n->c.list.blink; 
+  }
+  if (cmp > 0) return n; 
+  else n = n->p.root;
+  while (1) {
+    if (isext(n)) return n;
+    cmp = (*fxn)(key, n->k.lext->k.key);
+    if (cmp == 0) {
+      *fnd = 1;
+      return n->k.lext;
+    }
+    if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
+  }
+}
+ 
+Rb_node rb_find_gkey(Rb_node n, char *key, int (*fxn)(char *, char *))
+{
+  int fnd;
+  return rb_find_gkey_n(n, key, fxn, &fnd);
+}
+ 
+Rb_node rb_insert_b(Rb_node n, char *key, char *val)
+{
+  Rb_node newleft, newright, newnode, list, p;
+ 
+  if (ishead(n)) {
+    if (n->p.root == n) {         /* Tree is empty */
+      mk_new_ext(newnode, key, val);
+      insert(newnode, n);
+      n->p.root = newnode;
+      newnode->p.parent = n;
+      setroot(newnode);
+      return newnode;
+    } else {
+      mk_new_ext(newright, key, val);
+      insert(newright, n);
+      newleft = newright->c.list.blink;
+      setnormal(newleft);
+      mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft));
+      p = rprev(newright);
+      if (!ishead(p)) p->k.lext = newright;
+      return newright;
+    }
+  } else {
+    mk_new_ext(newleft, key, val);
+    insert(newleft, n);
+    setnormal(n);
+    mk_new_int(newleft, n, n->p.parent, isleft(n));
+    p = lprev(newleft);
+    if (!ishead(p)) p->v.rext = newleft;
+    return newleft;    
+  }
+}
+ 
+static void recolor(Rb_node n)
+{  
+  Rb_node p, gp, s;
+  int done = 0;
+ 
+  while(!done) {
+    if (isroot(n)) {
+      setblack(n);
+      return;
+    }
+ 
+    p = n->p.parent;
+ 
+    if (isblack(p)) return;
+    
+    if (isroot(p)) {
+      setblack(p);
+      return;
+    }
+ 
+    gp = p->p.parent;
+    s = sibling(p);
+    if (isred(s)) {
+      setblack(p);
+      setred(gp);
+      setblack(s);
+      n = gp;
+    } else {
+      done = 1;
+    }
+  }
+  /* p's sibling is black, p is red, gp is black */
+  
+  if ((isleft(n) == 0) == (isleft(p) == 0)) {
+    single_rotate(gp, isleft(n));
+    setblack(p);
+    setred(gp);
+  } else {
+    single_rotate(p, isleft(n));
+    single_rotate(gp, isleft(n));
+    setblack(n);
+    setred(gp);
+  }
+}
+ 
+static void single_rotate(Rb_node y, int l)
+{
+  int rl, ir;
+  Rb_node x, yp;
+  char *tmp;
+ 
+  ir = isroot(y);
+  yp = y->p.parent;
+  if (!ir) {
+    rl = isleft(y);
+  }
+  
+  if (l) {
+    x = y->c.child.left;
+    y->c.child.left = x->c.child.right;
+    setleft(y->c.child.left);
+    y->c.child.left->p.parent = y;
+    x->c.child.right = y;
+    setright(y);  
+  } else {
+    x = y->c.child.right;
+    y->c.child.right = x->c.child.left;
+    setright(y->c.child.right);
+    y->c.child.right->p.parent = y;
+    x->c.child.left = y;
+    setleft(y);  
+  }
+ 
+  x->p.parent = yp;
+  y->p.parent = x;
+  if (ir) {
+    yp->p.root = x;
+    setnormal(y);
+    setroot(x);
+  } else {
+    if (rl) {
+      yp->c.child.left = x;
+      setleft(x);
+    } else {
+      yp->c.child.right = x;
+      setright(x);
+    }
+  }
+}
+    
+void rb_delete_node(Rb_node n)
+{
+  Rb_node s, p, gp;
+  char ir;
+ 
+  if (isint(n)) {
+    fprintf(stderr, "Cannot delete an internal node: 0x%x\n", n);
+    exit(1);
+  }
+  if (ishead(n)) {
+    fprintf(stderr, "Cannot delete the head of an rb_tree: 0x%x\n", n);
+    exit(1);
+  }
+  delete_item(n); /* Delete it from the list */
+  p = n->p.parent;  /* The only node */
+  if (isroot(n)) {
+    p->p.root = p;
+    free(n);
+    return;
+  } 
+  s = sibling(n);    /* The only node after deletion */
+  if (isroot(p)) {
+    s->p.parent = p->p.parent;
+    s->p.parent->p.root = s;
+    setroot(s);
+    free(p);
+    free(n);
+    return;
+  }
+  gp = p->p.parent;  /* Set parent to sibling */
+  s->p.parent = gp;
+  if (isleft(p)) {
+    gp->c.child.left = s;
+    setleft(s);
+  } else {
+    gp->c.child.right = s;
+    setright(s);
+  }
+  ir = isred(p);
+  free(p);
+  free(n);
+  
+  if (isext(s)) {      /* Update proper rext and lext values */
+    p = lprev(s); 
+    if (!ishead(p)) p->v.rext = s;
+    p = rprev(s);
+    if (!ishead(p)) p->k.lext = s;
+  } else if (isblack(s)) {
+    fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
+    exit(1);
+  } else {
+    p = lprev(s);
+    if (!ishead(p)) p->v.rext = s->c.child.left;
+    p = rprev(s);
+    if (!ishead(p)) p->k.lext = s->c.child.right;
+    setblack(s);
+    return;
+  }
+ 
+  if (ir) return;
+ 
+  /* Recolor */
+  
+  n = s;
+  p = n->p.parent;
+  s = sibling(n);
+  while(isblack(p) && isblack(s) && isint(s) && 
+        isblack(s->c.child.left) && isblack(s->c.child.right)) {
+    setred(s);
+    n = p;
+    if (isroot(n)) return;
+    p = n->p.parent;
+    s = sibling(n);
+  }
+  
+  if (isblack(p) && isred(s)) {  /* Rotation 2.3b */
+    single_rotate(p, isright(n));
+    setred(p);
+    setblack(s);
+    s = sibling(n);
+  }
+    
+  { Rb_node x, z; char il;
+    
+    if (isext(s)) {
+      fprintf(stderr, "DELETION ERROR: sibling not internal\n");
+      exit(1);
+    }
+ 
+    il = isleft(n);
+    x = il ? s->c.child.left : s->c.child.right ;
+    z = sibling(x);
+ 
+    if (isred(z)) {  /* Rotation 2.3f */
+      single_rotate(p, !il);
+      setblack(z);
+      if (isred(p)) setred(s); else setblack(s);
+      setblack(p);
+    } else if (isblack(x)) {   /* Recoloring only (2.3c) */
+      if (isred(s) || isblack(p)) {
+        fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
+        exit(1);
+      }
+      setblack(p);
+      setred(s);
+      return;
+    } else if (isred(p)) { /* 2.3d */
+      single_rotate(s, il);
+      single_rotate(p, !il);
+      setblack(x);
+      setred(s);
+      return;
+    } else {  /* 2.3e */
+      single_rotate(s, il);
+      single_rotate(p, !il);
+      setblack(x);
+      return;
+    }
+  }
+}
+ 
+ 
+void rb_print_tree(Rb_node t, int level)
+{
+  int i;
+  if (ishead(t) && t->p.parent == t) {
+    printf("tree 0x%x is empty\n", t);
+  } else if (ishead(t)) {
+    printf("Head: 0x%x.  Root = 0x%x\n", t, t->p.root);
+    rb_print_tree(t->p.root, 0);
+  } else {
+    if (isext(t)) {
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Ext node 0x%x: %c,%c: p=0x%x, k=%s\n", 
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key);
+    } else {
+      rb_print_tree(t->c.child.left, level+2);
+      rb_print_tree(t->c.child.right, level+2);
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n", 
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left, 
+              t->c.child.right, 
+              t->p.parent, t->k.lext->k.key, t->v.rext->k.key);
+    }
+  }
+}
+ 
+void rb_iprint_tree(Rb_node t, int level)
+{
+  int i;
+  if (ishead(t) && t->p.parent == t) {
+    printf("tree 0x%x is empty\n", t);
+  } else if (ishead(t)) {
+    printf("Head: 0x%x.  Root = 0x%x, < = 0x%x, > = 0x%x\n", 
+            t, t->p.root, t->c.list.blink, t->c.list.flink);
+    rb_iprint_tree(t->p.root, 0);
+  } else {
+    if (isext(t)) {
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Ext node 0x%x: %c,%c: p=0x%x, <=0x%x, >=0x%x k=%d\n", 
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, 
+              t->c.list.blink, t->c.list.flink, t->k.ikey);
+    } else {
+      rb_iprint_tree(t->c.child.left, level+2);
+      rb_iprint_tree(t->c.child.right, level+2);
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%d,%d)\n", 
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left, 
+              t->c.child.right, 
+              t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
+    }
+  }
+}
+      
+int rb_nblack(Rb_node n)
+{
+  int nb;
+  if (ishead(n) || isint(n)) {
+    fprintf(stderr, "ERROR: rb_nblack called on a non-external node 0x%x\n",
+            n);
+    exit(1);
+  }
+  nb = 0;
+  while(!ishead(n)) {
+    if (isblack(n)) nb++;
+    n = n->p.parent;
+  }
+  return nb;
+}
+ 
+int rb_plength(Rb_node n)
+{
+  int pl;
+  if (ishead(n) || isint(n)) {
+    fprintf(stderr, "ERROR: rb_plength called on a non-external node 0x%x\n",
+            n);
+    exit(1);
+  }
+  pl = 0;
+  while(!ishead(n)) {
+    pl++;
+    n = n->p.parent;
+  }
+  return pl;
+}
+ 
+void rb_free_tree(Rb_node n)
+{
+  if (!ishead(n)) {
+    fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
+    exit(1);
+  }
+ 
+  while(rb_first(n) != rb_nil(n)) {
+    rb_delete_node(rb_first(n));
+  }
+  free(n);
+}
+ 
+char *rb_val(Rb_node n)
+{
+  return n->v.val;
+}
+ 
+Rb_node rb_insert_a(Rb_node nd, char *key, char *val)
+{
+  rb_insert_b(nd->c.list.flink, key, val);
+}
+
+Rb_node rb_insert(Rb_node tree, char *key, char *val)
+{
+  rb_insert_b(rb_find_key(tree, key), key, val);
+}
+
+Rb_node rb_inserti(Rb_node tree, int ikey, char *val)
+{
+  rb_insert_b(rb_find_ikey(tree, ikey), (char *) ikey, val);
+}
+
+Rb_node rb_insertg(Rb_node tree, char *key, char *val,
+                          int (*func)(char *, char *))
+{
+  rb_insert_b(rb_find_gkey(tree, key, func), key, val);
+}
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rb.h	Wed Mar 10 17:08:26 2004 +0100
@@ -0,0 +1,134 @@
+/*
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library 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
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+/* Revision 1.2.  Jim Plank */
+
+/* Original code by Jim Plank (plank@cs.utk.edu) */
+/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
+ 
+typedef struct {
+  unsigned red : 1 ;
+  unsigned internal : 1 ;
+  unsigned left : 1 ;
+  unsigned root : 1 ;
+  unsigned head : 1 ;
+} status;
+ 
+/* Main rb_node.  You only ever use the fields
+
+   c.list.flink
+   c.list.blink
+
+   k.key or k.ikey
+   v.val
+*/
+
+
+typedef struct rb_node {
+  union {
+    struct {
+      struct rb_node *flink;
+      struct rb_node *blink;
+    } list;
+    struct {
+      struct rb_node *left;
+      struct rb_node *right;
+    } child;
+  } c;
+  union {
+    struct rb_node *parent;
+    struct rb_node *root;
+  } p;
+  status s;
+  union {
+    int ikey;
+    char *key;
+    struct rb_node *lext;
+  } k;
+  union {
+    char *val;
+    struct rb_node *rext;
+  } v;
+} *Rb_node;
+
+
+extern Rb_node make_rb();   /* Creates a new rb-tree */
+
+
+
+/* Creates a node with key key and val val and inserts it into the tree.
+   rb_insert uses strcmp() as comparison funcion.  rb_inserti uses <>=,
+   rb_insertg uses func() */
+
+extern Rb_node rb_insert(Rb_node tree, char *key, char *val);
+extern Rb_node rb_inserti(Rb_node tree, int ikey, char *val);
+extern Rb_node rb_insertg(Rb_node tree, char *key, char *val,
+                          int (*func)(char *, char *));
+
+
+/* returns an external node in t whose value is equal
+  k or whose value is the smallest value greater than k. */
+
+extern Rb_node rb_find_key(Rb_node root, char *key);
+extern Rb_node rb_find_ikey(Rb_node root, int ikey);
+extern Rb_node rb_find_gkey(Rb_node root, char *key, 
+                              int (*func)(char *, char *));
+
+
+/* Works just like the find_key versions only it returns whether or not
+   it found the key in the integer variable found */
+
+extern Rb_node rb_find_key_n(Rb_node root, char *key, int *found);
+extern Rb_node rb_find_ikey_n(Rb_node root, int ikey, int *found);
+extern Rb_node rb_find_gkey_n(Rb_node root, char *key, 
+                              int (*func)(char *, char *), int *found);
+
+
+/* Creates a node with key key and val val and inserts it into the 
+   tree before/after node nd.  Does not check to ensure that you are 
+   keeping the correct order */
+
+extern Rb_node rb_insert_b(Rb_node nd, char *key, char *val);
+extern Rb_node rb_insert_a(Rb_node nd, char *key, char *val);
+
+
+extern void rb_delete_node(Rb_node node);  /* Deletes and frees a node (but 
+                                              not the key or val) */
+extern void rb_free_tree(Rb_node root);  /* Deletes and frees an entire tree */
+
+extern char *rb_val(Rb_node node);  /* Returns node->v.val -- this is to shut
+                                       lint up */
+
+extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from
+                                    n to the root */
+int rb_plength(Rb_node n);       /* returns the # of nodes in path from
+				    n to the root */
+ 
+#define rb_first(n) (n->c.list.flink)
+#define rb_last(n) (n->c.list.blink)
+#define rb_next(n) (n->c.list.flink)
+#define rb_prev(n) (n->c.list.blink)
+#define rb_empty(t) (t->c.list.flink == t)
+#ifndef rb_nil
+#define rb_nil(t) (t)
+#endif
+ 
+#define rb_traverse(ptr, lst) \
+  for(ptr = rb_first(lst); ptr != rb_nil(lst); ptr = rb_next(ptr))
+