diff -r f20d97d852ce -r 58e382ae97cd rb.c
--- /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);
+}
+
+