Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/misc/volume28/librb/part01

Text File | 1992-02-22 | 29.2 KB | 1,134 lines

Newsgroups: comp.sources.misc
From: [e-mail] (James Plank)
Subject:  v28i062:  librb - red-black tree data structure routines, Part01/01
Message-ID: <[e-mail]>
X-Md4-Signature: 12b8683edf1c299d2a26b27305f4467d
Date: Mon, 24 Feb 1992 02:53:45 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (James Plank)
Posting-number: Volume 28, Issue 62
Archive-name: librb/part01
Environment: UNIX

I've had this code hanging around for a while and a bunch of people at
Princeton have found it useful, so I figured I'd post it.  It's a library
of routines for doing red-black trees, which is basically a sorted data
structure in which all the operations are log(n) time.  I've used them
to replace hash tables because with rb-tree's, I don't need to do any
hash-table initialization, they can be of arbitrary size, they have a
better worst-case behavior, and they're sorted.

This code has been around since June and has been beaten on by many
people, so it should be very stable.  Check out the README for all
the details.  If you have any questions or comments about this, please
let me know.

Take it Easy,

Jim Plank
[e-mail] or
[e-mail]
-------------------
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to [e-mail] if you want that tool.
# Contents:  README list.c list.h main.c makefile rb.c rb.h
# Wrapped by kent@sparky on Sun Feb 23 20:39:24 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 1)."'
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
  echo shar: Extracting \"'README'\" \(4998 characters\)
  sed "s/^X//" >'README' <<'END_OF_FILE'
X$Revision: 1.1 $
X
XRb.c, Rb.h, List.h, and list.c are files for doing red-black trees and
Xdoubly linked lists, respectively.
X
XRb.h, Rb.c:
X
XRb.h contains the typedef for red-black tree structures.  Basically,
Xred-black trees are balanced trees whose external nodes are sorted
Xby a key, and connected in a linked list.  The following is how
Xyou use rb.c and rb.h:
X
XInclude rb.h in your source.
X
XMake_rb() returns the head of a red-black tree.  It serves two functions:
XIts p.root pointer points to the root of the red-black tree.  Its
Xc.list.flink and c.list.blink pointers point to the first and last
Xexternal nodes of the tree.  When the tree is empty, all these pointers
Xpoint to itself.
X
XThe external nodes can be traversed in sorted order with their
Xc.list.flink and c.list.blink pointers.  The macros rb_first, rb_last,
Xrb_next, rb_prev, and rb_traverse can be used to traverse external node lists.
X
XExternal nodes hold two pieces of information: the key and the value
X(in k.key and v.val, respectively).   The key can be a character
Xstring, an integer, or a general pointer.  Val is typed as a character
Xpointer, but can be any pointer.  If the key is a character string,
Xthen one can insert it, and a value into a tree with rb_insert().  If
Xit is an integer, then rb_inserti() should be used.  If it is a general
Xpointer, then rb_insertg() must be used, with a comparison function
Xpassed as the fourth argument.  This function takes two keys as arguments,
Xand returns a negative value, positive value, or 0, depending on whether
Xthe first key is less than, greater than or equal to the second.  Thus,
Xone could use rb_insertg(t, s, v, strcmp) to insert the value v with
Xa character string s into the tree t.
X
XRb_find_key(t, k) returns the external node in t whose value is equal
Xk or whose value is the smallest value greater than k.  (Here, k is
Xa string).  If there is no value greater than or equal to k, then
Xt is returned.  Rb_find_ikey(t,k) works when k is an integer, and
XRb_find_gkey(t,k,cmp) works for general pointers.
X
XRb_find_key_n(t, k, n) is the same as rb_find_key, except that it
Xreturns whether or not k was found in n (n is an int *).  Rb_find_ikey_n
Xand Rb_find_gkey_n are the analogous routines for integer and general
Xkeys.
X
XRb_insert_b(e, k, v) makes a new external node with key k and val v, and
Xinserts it before the external node e.  If e is the head of a tree,
Xthen the new node is inserted at the end of the external node list.
XIf this insertion violates sorted order, no error is flagged.  It is
Xassumed that the user knows what he/she is doing.  Rb_insert_a(e,k,v)
Xinserts the new node after e (if e = t, it inserts the new node at the
Xbeginning of the list).
X
XRb_insert() is therefore really a combination of Rb_find_key() and
XRb_insert_b().
X
XRb_delete_node(e) deletes the external node e from a tree (and thus from
Xthe linked list of external nodes).  The node is free'd as well, so
Xdon't retain pointers to it.
X
XRed-black trees are spiffy because find_key, insert, and delete are all
Xdone in log(n) time.  Thus, they can be freely used instead of hash-tables,
Xwith the benifit of having the elements in sorted order at all times, and
Xwith the guarantee of operations being in log(n) time.
X
XOther routines:
X
XRb_print_tree() will grossly print out a red-black tree with string keys.
XRb_iprint_tree() will do the same with trees with integer keys.
XRb_nblack(e) will report the number of black nodes on the path from external
X  node e to the root.  The path length is less than twice this value.
XRb_plength(e) reports the length of the path from e to the root.
X
X
XList.c and list.h
X
XThese are routines for generic doubly linked lists.  Doubly linked lists
Xare any structs whose first two fields are flink and blink pointers.
XMk_list(t) returns an empty list with the type t.  The empty list is
Xa struct whose flink and blink point to itself.  Insert() and delete_item()
Xinsert and delete nodes from a list -- unlike the rb routines, no allocation
Xis done here.  In insert(), the node to be inserted is assumed to be allocated,
Xand in delete_item(), the deleted node is not free'd.
X
XGet_node() allocates a node from a node list.  The head element in the linked
Xlist has info about how big of a node to allocate.  Free_node() deallocates
Xa node.  In actuality, free_node doesn't call free, but chains the node onto
Xa queue of nodes.  That way, get_node first returns nodes from this queue,
Xand malloc need not be called.  This is quite a possible memory leak.  To
Xbe safe, you can malloc and free your own nodes, instead of calling get_node()
Xand free_node().
X
XList.c and list.h are kind of gross, and should be generally avoided because
Xof allocation problems.  Try dlist.c & dlist.h for doubly linked lists which
Xare more like the red-black tree structs.
X
XIf you have any questions or comments about this, please let me know.
X
XTake it Easy,
X
XJim Plank
[e-mail] or
[e-mail]
X
X35 Olden St
XPrinceton University
XPrinceton, NJ 80544-2087
END_OF_FILE
  if test 4998 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
  fi
  # end of 'README'
fi
if test -f 'list.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'list.c'\"
else
  echo shar: Extracting \"'list.c'\" \(2214 characters\)
  sed "s/^X//" >'list.c' <<'END_OF_FILE'
X/*
X * $Source: /n/fs/vd/jsp/src/rb/RCS/list.c,v $
X * $Revision: 1.1 $
X * $Date: 92/02/12 15:43:24 $
X * $Author: jsp $
X */
X
X#include <stdio.h>    /* Basic includes and definitions */
X#include "list.h"
X
X#define boolean int
X#define TRUE 1
X#define FALSE 0
X
X
X/*---------------------------------------------------------------------*
X * PROCEDURES FOR MANIPULATING DOUBLY LINKED LISTS
X * Each list contains a sentinal node, so that
X * the first item in list l is l->flink.  If l is
X * empty, then l->flink = l->blink = l.
X * The sentinal contains extra information so that these operations
X * can work on lists of any size and type.
X * Memory management is done explicitly to avoid the slowness of
X * malloc and free.  The node size and the free list are contained
X * in the sentinal node.
X *---------------------------------------------------------------------*/
X
Xtypedef struct int_list {  /* Information held in the sentinal node */
X  struct int_list *flink;
X  struct int_list *blink;
X  int size;
X  List free_list;
X} *Int_list;
X
Xinsert(item, list)    /* Inserts to the end of a list */
XList item;
XList list;
X{
X  List last_node;
X
X  last_node = list->blink;
X
X  list->blink = item;
X  last_node->flink = item;
X  item->blink = last_node;
X  item->flink = list;
X}
X
Xdelete_item(item)        /* Deletes an arbitrary iterm */
XList item;
X{
X  item->flink->blink = item->blink;
X  item->blink->flink = item->flink;
X}
X
XList make_list(size)    /* Creates a new list */
Xint size;
X{
X  Int_list l;
X
X  l = (Int_list) malloc(sizeof(struct int_list));
X  l->flink = l;
X  l->blink = l;
X  l->size = size;
X  l->free_list = (List) malloc (sizeof(struct list));
X  l->free_list->flink = l->free_list;
X  return (List) l;
X}
X
XList get_node(list)   /* Allocates a node to be inserted into the list */
XList list;
X{
X  Int_list l;
X  List to_return;
X
X  l = (Int_list) list;
X  if (l->free_list->flink == l->free_list) {
X    return (List) malloc(l->size);
X  } else {
X    to_return = l->free_list;
X    l->free_list = to_return->flink;
X    return to_return;
X  }
X}
X
Xfree_node(node, list)    /* Deallocates a node from the list */
XList node;
XList list;
X{
X  Int_list l;
X
X  l = (Int_list) list;
X  node->flink = l->free_list;
X  l->free_list = node;
X}
END_OF_FILE
  if test 2214 -ne `wc -c <'list.c'`; then
    echo shar: \"'list.c'\" unpacked with wrong size!
  fi
  # end of 'list.c'
fi
if test -f 'list.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'list.h'\"
else
  echo shar: Extracting \"'list.h'\" \(1025 characters\)
  sed "s/^X//" >'list.h' <<'END_OF_FILE'
X/*
X * $Source: /n/fs/vd/jsp/src/rb/RCS/list.h,v $
X * $Revision: 1.1 $
X * $Date: 92/02/12 15:43:13 $
X * $Author: jsp $
X */
X
X/* This is the header file for the list manipulation routines in list.c.
X * Any struct can be turned into a list as long as its first two fields are
X * flink and blink. */
X
Xtypedef struct list {
X  struct list *flink;
X  struct list *blink;
X} *List;
X
X/* Nil, first, next, and prev are macro expansions for list traversal
X * primitives. */
X
X#define nil(l) (l)
X#define first(l) (l->flink)
X#define last(l) (l->blink)
X#define next(n) (n->flink)
X#define prev(n) (n->blink)
X
X#define mklist(t) ((t *) make_list (sizeof(t)))
X
X/* These are the routines for manipluating lists */
X
X/* void insert(node list);     Inserts a node to the end of a list */
X/* void delete_item(node);     Deletes an arbitrary node */
X/* List make_list(node_size);  Creates a new list */
X/* List get_node(list);        Allocates a node to be inserted into the list */
X/* void free_node(node, list); Deallocates a node from the list */
X
END_OF_FILE
  if test 1025 -ne `wc -c <'list.h'`; then
    echo shar: \"'list.h'\" unpacked with wrong size!
  fi
  # end of 'list.h'
fi
if test -f 'main.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'main.c'\"
else
  echo shar: Extracting \"'main.c'\" \(1810 characters\)
  sed "s/^X//" >'main.c' <<'END_OF_FILE'
X#include "rb.h"
X#include <stdio.h>
X
X/* an example -- this allocates a red-black tree for integers.  For a
X * user-specified number of iterations, it does the following:
X
X * delete a random element in the tree.
X * make two new random elements, and insert them into the tree
X
X * At the end, it prints the sorted list of elements, and then prints
X * stats of the number of black nodes in any path in the tree, and
X * the minimum and maximum path lengths.
X
X * Rb_find_ikey and rb_inserti could have been used, but instead
X * rb_find_gkey and rb_insertg were used to show how they work.
X
X */
X
Xint icomp(i, j)
Xint i, j;
X{
X  if (i == j) return 0;
X  if (i > j) return -1; else return 1;
X}
X
Xmain(argc, argv)
Xint argc;
Xchar **argv;
X{
X  int i, j, tb, nb, mxp, mnp, p;
X  int iterations;
X  Rb_node argt, t;
X  int *a;
X
X  if (argc != 2) {
X    fprintf(stderr, "usage: main #iterations\n");
X    exit(1);
X  }
X  argt = make_rb();
X  srandom(time(0));
X  iterations = atoi(argv[1]);
X  a = (int *) malloc (iterations*sizeof(int));
X
X  for (i = 0; i < atoi(argv[1]); i++) {
X    if (i > 0) {
X      j = random()%i;
X
X      rb_delete_node(rb_find_gkey(argt, a[j], icomp));
X      a[j] = random() % 1000;
X      rb_insertg(argt, a[j], 0, icomp);
X    }
X    a[i] = random() % 1000;
X    rb_insertg(argt, a[i], 0, icomp);
X  }
X  tb = 0;
X  mxp = 0;
X  mnp = 0;
X  for (t = rb_first(argt); t != nil(argt); t = rb_next(t)) {
X    printf("%d ", t->k.ikey);
X    nb = rb_nblack(t);
X    p = rb_plength(t);
X    if (tb == 0) {
X      tb = nb;
X    } else if (tb != nb) {
X      printf("Conflict: tb=%d, nb=%d\n", tb, nb);
X      exit(1);
X    }
X    mxp = (mxp == 0 || mxp < p) ? p : mxp;
X    mnp = (mnp == 0 || mxp > p) ? p : mnp;
X  }
X  printf("\n");
X
X  printf("Nblack = %d\n", tb);
X  printf("Max    = %d\n", mxp);
X  printf("Min    = %d\n", mnp);
X}
END_OF_FILE
  if test 1810 -ne `wc -c <'main.c'`; then
    echo shar: \"'main.c'\" unpacked with wrong size!
  fi
  # end of 'main.c'
fi
if test -f 'makefile' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'makefile'\"
else
  echo shar: Extracting \"'makefile'\" \(431 characters\)
  sed "s/^X//" >'makefile' <<'END_OF_FILE'
XCC = cc
XCFLAGS    =    -g
X
XOBJS = rb.o list.o
X
XMOBJS = main.o librb.a
X
Xall: librb.a main
X
Xlibrb.a: $(OBJS)
X    ar ru librb.a $(OBJS)
X    ranlib librb.a
X    rm *.o
X
Xdepend:
X    makedep .
X
Xmain: $(MOBJS)
X    $(CC) $(CFLAGS) -o main $(MOBJS)
X
X.c.o:
X    $(CC) -c $(CFLAGS) $*.c
X
Xclean:
X    rm *.o librb.a main
X
X# +mkdep+
Xlist.o: \
X          ./list.h \
X          list.c
X
Xmain.o: \
X          ./rb.h \
X          main.c
X
Xrb.o: \
X          ./rb.h \
X          rb.c
X
END_OF_FILE
  if test 431 -ne `wc -c <'makefile'`; then
    echo shar: \"'makefile'\" unpacked with wrong size!
  fi
  # end of 'makefile'
fi
if test -f 'rb.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'rb.c'\"
else
  echo shar: Extracting \"'rb.c'\" \(11987 characters\)
  sed "s/^X//" >'rb.c' <<'END_OF_FILE'
X#include "rb.h"
X#include <stdio.h>
X
X#define isred(n) (n->s.red)
X#define isblack(n) (!isred(n))
X#define isleft(n) (n->s.left)
X#define isright(n) (!isleft(n))
X#define isint(n) (n->s.internal)
X#define isext(n) (!isint(n))
X#define ishead(n) (n->s.head)
X#define isroot(n) (n->s.root)
X#define setred(n) n->s.red = 1
X#define setblack(n) n->s.red = 0
X#define setleft(n) n->s.left = 1
X#define setright(n) n->s.left = 0
X#define sethead(n) n->s.head = 1
X#define setroot(n) n->s.root = 1
X#define setint(n) n->s.internal = 1
X#define setext(n) n->s.internal = 0
X#define setnormal(n) { n->s.root = 0; n ->s.head = 0; }
X#define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \
X                                : n->p.parent->c.child.left)
X
X#define mk_new_ext(new, kkkey, vvval) {\
X  new = (Rb_node) malloc(sizeof(struct rb_node));\
X  new->v.val = vvval;\
X  new->k.key = kkkey;\
X  setext(new);\
X  setblack(new);\
X  setnormal(new);\
X}
X
Xmk_new_int(l, r, p, il)
XRb_node l, r, p;
Xint il;
X{
X  Rb_node new;
X
X  new = (Rb_node) malloc(sizeof(struct rb_node));
X  setint(new);
X  setred(new);
X  setnormal(new);
X  new->c.child.left = l;
X  new->c.child.right = r;
X  new->p.parent = p;
X  new->k.lext = l;
X  new->v.rext = r;
X  l->p.parent = new;
X  r->p.parent = new;
X  setleft(l);
X  setright(r);
X  if (ishead(p)) {
X    p->p.root = new;
X    setroot(new);
X  } else if (il) {
X    setleft(new);
X    p->c.child.left = new;
X  } else {
X    setright(new);
X    p->c.child.right = new;
X  }
X  recolor(new);
X}
X
X
XRb_node lprev(n)
XRb_node n;
X{
X  if (ishead(n)) return n;
X  while (!isroot(n)) {
X    if (isright(n)) return n->p.parent;
X    n = n->p.parent;
X  }
X  return n->p.parent;
X}
X
XRb_node rprev(n)
XRb_node n;
X{
X  if (ishead(n)) return n;
X  while (!isroot(n)) {
X    if (isleft(n)) return n->p.parent;
X    n = n->p.parent;
X  }
X  return n->p.parent;
X}
X
XRb_node make_rb()
X{
X  Rb_node head;
X
X  head = (Rb_node) malloc (sizeof(struct rb_node));
X  head->c.list.flink = head;
X  head->c.list.blink = head;
X  head->p.root = head;
X  head->k.key = "";
X  sethead(head);
X  return head;
X}
X
XRb_node rb_find_key_n(n, key, fnd)
XRb_node n;
Xchar *key;
Xint *fnd;
X{
X  int cmp;
X
X  *fnd = 0;
X  if (!ishead(n)) {
X    fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
X    exit(1);
X  }
X  if (n->p.root == n) return n;
X  cmp = strcmp(key, n->c.list.blink->k.key);
X  if (cmp == 0) {
X    *fnd = 1;
X    return n->c.list.blink;
X  }
X  if (cmp > 0) return n;
X  else n = n->p.root;
X  while (1) {
X    if (isext(n)) return n;
X    cmp = strcmp(key, n->k.lext->k.key);
X    if (cmp == 0) {
X      *fnd = 1;
X      return n->k.lext;
X    }
X    if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
X  }
X}
X
XRb_node rb_find_key(n, key)
XRb_node n;
Xchar *key;
X{
X  int fnd;
X  return rb_find_key_n(n, key, &fnd);
X}
X
XRb_node rb_find_ikey_n(n, ikey, fnd)
XRb_node n;
Xint ikey;
Xint *fnd;
X{
X  *fnd = 0;
X  if (!ishead(n)) {
X    fprintf(stderr, "rb_find_ikey_n called on non-head 0x%x\n", n);
X    exit(1);
X  }
X  if (n->p.root == n) return n;
X  if (ikey == n->c.list.blink->k.ikey) {
X    *fnd = 1;
X    return n->c.list.blink;
X  }
X  if (ikey > n->c.list.blink->k.ikey) return n;
X  else n = n->p.root;
X  while (1) {
X    if (isext(n)) return n;
X    if (ikey == n->k.lext->k.ikey) {
X      *fnd = 1;
X      return n->k.lext;
X    }
X    n = (ikey < n->k.lext->k.ikey) ? n->c.child.left : n->c.child.right;
X  }
X}
X
XRb_node rb_find_ikey(n, ikey)
XRb_node n;
Xint ikey;
X{
X  int fnd;
X  return rb_find_ikey_n(n, ikey, &fnd);
X}
X
XRb_node rb_find_gkey_n(n, key, fxn, fnd)
XRb_node n;
Xchar *key;
Xint (*fxn)();
Xint *fnd;
X{
X  int cmp;
X
X  *fnd = 0;
X  if (!ishead(n)) {
X    fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
X    exit(1);
X  }
X  if (n->p.root == n) return n;
X  cmp = (*fxn)(key, n->c.list.blink->k.key);
X  if (cmp == 0) {
X    *fnd = 1;
X    return n->c.list.blink;
X  }
X  if (cmp > 0) return n;
X  else n = n->p.root;
X  while (1) {
X    if (isext(n)) return n;
X    cmp = (*fxn)(key, n->k.lext->k.key);
X    if (cmp == 0) {
X      *fnd = 1;
X      return n->k.lext;
X    }
X    if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
X  }
X}
X
XRb_node rb_find_gkey(n, key, fxn)
XRb_node n;
Xchar *key;
Xint (*fxn)();
X{
X  int *fnd;
X  return rb_find_gkey_n(n, key, fxn, &fnd);
X}
XRb_node rb_insert_b(n, key, val)
XRb_node n;
Xchar *key;
Xchar *val;
X{
X  Rb_node newleft, newright, newnode, list, p;
X
X  if (ishead(n)) {
X    if (n->p.root == n) {         /* Tree is empty */
X      mk_new_ext(newnode, key, val);
X      insert(newnode, n);
X      n->p.root = newnode;
X      newnode->p.parent = n;
X      setroot(newnode);
X      return newnode;
X    } else {
X      mk_new_ext(newright, key, val);
X      insert(newright, n);
X      newleft = newright->c.list.blink;
X      setnormal(newleft);
X      mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft));
X      p = rprev(newright);
X      if (!ishead(p)) p->k.lext = newright;
X      return newright;
X    }
X  } else {
X    mk_new_ext(newleft, key, val);
X    insert(newleft, n);
X    setnormal(n);
X    mk_new_int(newleft, n, n->p.parent, isleft(n));
X    p = lprev(newleft);
X    if (!ishead(p)) p->v.rext = newleft;
X    return newleft;
X  }
X}
X
Xrecolor(n)
XRb_node n;
X{
X  Rb_node p, gp, s;
X  int done = 0;
X
X  while(!done) {
X    if (isroot(n)) {
X      setblack(n);
X      return;
X    }
X
X    p = n->p.parent;
X
X    if (isblack(p)) return;
X
X    if (isroot(p)) {
X      setblack(p);
X      return;
X    }
X
X    gp = p->p.parent;
X    s = sibling(p);
X    if (isred(s)) {
X      setblack(p);
X      setred(gp);
X      setblack(s);
X      n = gp;
X    } else {
X      done = 1;
X    }
X  }
X  /* p's sibling is black, p is red, gp is black */
X
X  if ((isleft(n) == 0) == (isleft(p) == 0)) {
X    single_rotate(gp, isleft(n));
X    setblack(p);
X    setred(gp);
X  } else {
X    single_rotate(p, isleft(n));
X    single_rotate(gp, isleft(n));
X    setblack(n);
X    setred(gp);
X  }
X}
X
Xsingle_rotate(y, l)
XRb_node y;
Xint l;
X{
X  int rl, ir;
X  Rb_node x, yp;
X  char *tmp;
X
X  ir = isroot(y);
X  yp = y->p.parent;
X  if (!ir) {
X    rl = isleft(y);
X  }
X
X  if (l) {
X    x = y->c.child.left;
X    y->c.child.left = x->c.child.right;
X    setleft(y->c.child.left);
X    y->c.child.left->p.parent = y;
X    x->c.child.right = y;
X    setright(y);
X  } else {
X    x = y->c.child.right;
X    y->c.child.right = x->c.child.left;
X    setright(y->c.child.right);
X    y->c.child.right->p.parent = y;
X    x->c.child.left = y;
X    setleft(y);
X  }
X
X  x->p.parent = yp;
X  y->p.parent = x;
X  if (ir) {
X    yp->p.root = x;
X    setnormal(y);
X    setroot(x);
X  } else {
X    if (rl) {
X      yp->c.child.left = x;
X      setleft(x);
X    } else {
X      yp->c.child.right = x;
X      setright(x);
X    }
X  }
X}
X
Xrb_delete_node(n)
XRb_node n;
X{
X  Rb_node s, p, gp;
X  char ir;
X
X  if (isint(n)) {
X    fprintf(stderr, "Cannot delete an internal node: 0x%x\n", n);
X    exit(1);
X  }
X  if (ishead(n)) {
X    fprintf(stderr, "Cannot delete the head of an rb_tree: 0x%x\n", n);
X    exit(1);
X  }
X  delete_item(n); /* Delete it from the list */
X  p = n->p.parent;  /* The only node */
X  if (isroot(n)) {
X    p->p.root = p;
X    free(n);
X    return;
X  }
X  s = sibling(n);    /* The only node after deletion */
X  if (isroot(p)) {
X    s->p.parent = p->p.parent;
X    s->p.parent->p.root = s;
X    setroot(s);
X    free(p);
X    free(n);
X    return;
X  }
X  gp = p->p.parent;  /* Set parent to sibling */
X  s->p.parent = gp;
X  if (isleft(p)) {
X    gp->c.child.left = s;
X    setleft(s);
X  } else {
X    gp->c.child.right = s;
X    setright(s);
X  }
X  ir = isred(p);
X  free(p);
X  free(n);
X
X  if (isext(s)) {      /* Update proper rext and lext values */
X    p = lprev(s);
X    if (!ishead(p)) p->v.rext = s;
X    p = rprev(s);
X    if (!ishead(p)) p->k.lext = s;
X  } else if (isblack(s)) {
X    fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
X    exit(1);
X  } else {
X    p = lprev(s);
X    if (!ishead(p)) p->v.rext = s->c.child.left;
X    p = rprev(s);
X    if (!ishead(p)) p->k.lext = s->c.child.right;
X    setblack(s);
X    return;
X  }
X
X  if (ir) return;
X
X  /* Recolor */
X
X  n = s;
X  p = n->p.parent;
X  s = sibling(n);
X  while(isblack(p) && isblack(s) && isint(s) &&
X        isblack(s->c.child.left) && isblack(s->c.child.right)) {
X    setred(s);
X    n = p;
X    if (isroot(n)) return;
X    p = n->p.parent;
X    s = sibling(n);
X  }
X
X  if (isblack(p) && isred(s)) {  /* Rotation 2.3b */
X    single_rotate(p, isright(n));
X    setred(p);
X    setblack(s);
X    s = sibling(n);
X  }
X
X  { Rb_node x, z; char il;
X
X    if (isext(s)) {
X      fprintf(stderr, "DELETION ERROR: sibling not internal\n");
X      exit(1);
X    }
X
X    il = isleft(n);
X    x = il ? s->c.child.left : s->c.child.right ;
X    z = sibling(x);
X
X    if (isred(z)) {  /* Rotation 2.3f */
X      single_rotate(p, !il);
X      setblack(z);
X      if (isred(p)) setred(s); else setblack(s);
X      setblack(p);
X    } else if (isblack(x)) {   /* Recoloring only (2.3c) */
X      if (isred(s) || isblack(p)) {
X        fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
X        exit(1);
X      }
X      setblack(p);
X      setred(s);
X      return;
X    } else if (isred(p)) { /* 2.3d */
X      single_rotate(s, il);
X      single_rotate(p, !il);
X      setblack(x);
X      setred(s);
X      return;
X    } else {  /* 2.3e */
X      single_rotate(s, il);
X      single_rotate(p, !il);
X      setblack(x);
X      return;
X    }
X  }
X}
X
X
Xrb_print_tree(t, level)
XRb_node t;
Xint level;
X{
X  int i;
X  if (ishead(t) && t->p.parent == t) {
X    printf("tree 0x%x is empty\n", t);
X  } else if (ishead(t)) {
X    printf("Head: 0x%x.  Root = 0x%x\n", t, t->p.root);
X    rb_print_tree(t->p.root, 0);
X  } else {
X    if (isext(t)) {
X      for (i = 0; i < level; i++) putchar(' ');
X      printf("Ext node 0x%x: %c,%c: p=0x%x, k=%s\n",
X              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key);
X    } else {
X      rb_print_tree(t->c.child.left, level+2);
X      rb_print_tree(t->c.child.right, level+2);
X      for (i = 0; i < level; i++) putchar(' ');
X      printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n",
X              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left,
X              t->c.child.right,
X              t->p.parent, t->k.lext->k.key, t->v.rext->k.key);
X    }
X  }
X}
X
Xrb_iprint_tree(t, level)
XRb_node t;
Xint level;
X{
X  int i;
X  if (ishead(t) && t->p.parent == t) {
X    printf("tree 0x%x is empty\n", t);
X  } else if (ishead(t)) {
X    printf("Head: 0x%x.  Root = 0x%x, < = 0x%x, > = 0x%x\n",
X            t, t->p.root, t->c.list.blink, t->c.list.flink);
X    rb_iprint_tree(t->p.root, 0);
X  } else {
X    if (isext(t)) {
X      for (i = 0; i < level; i++) putchar(' ');
X      printf("Ext node 0x%x: %c,%c: p=0x%x, <=0x%x, >=0x%x k=%d\n",
X              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent,
X              t->c.list.blink, t->c.list.flink, t->k.ikey);
X    } else {
X      rb_iprint_tree(t->c.child.left, level+2);
X      rb_iprint_tree(t->c.child.right, level+2);
X      for (i = 0; i < level; i++) putchar(' ');
X      printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%d,%d)\n",
X              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left,
X              t->c.child.right,
X              t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
X    }
X  }
X}
X
Xrb_nblack(n)
XRb_node(n);
X{
X  int nb;
X  if (ishead(n) || isint(n)) {
X    fprintf(stderr, "ERROR: rb_nblack called on a non-external node 0x%x\n",
X            n);
X    exit(1);
X  }
X  nb = 0;
X  while(!ishead(n)) {
X    if (isblack(n)) nb++;
X    n = n->p.parent;
X  }
X  return nb;
X}
X
Xrb_plength(n)
XRb_node(n);
X{
X  int pl;
X  if (ishead(n) || isint(n)) {
X    fprintf(stderr, "ERROR: rb_plength called on a non-external node 0x%x\n",
X            n);
X    exit(1);
X  }
X  pl = 0;
X  while(!ishead(n)) {
X    pl++;
X    n = n->p.parent;
X  }
X  return pl;
X}
X
Xrb_free_tree(n)
XRb_node(n);
X{
X  if (!ishead(n)) {
X    fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
X    exit(1);
X  }
X
X  while(rb_first(n) != nil(n)) {
X    rb_delete_node(rb_first(n));
X  }
X  free(n);
X}
X
Xchar *rb_val(n)
XRb_node(n);
X{
X  return n->v.val;
X}
END_OF_FILE
  if test 11987 -ne `wc -c <'rb.c'`; then
    echo shar: \"'rb.c'\" unpacked with wrong size!
  fi
  # end of 'rb.c'
fi
if test -f 'rb.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'rb.h'\"
else
  echo shar: Extracting \"'rb.h'\" \(1839 characters\)
  sed "s/^X//" >'rb.h' <<'END_OF_FILE'
Xtypedef struct {
X  unsigned red : 1 ;
X  unsigned internal : 1 ;
X  unsigned left : 1 ;
X  unsigned root : 1 ;
X  unsigned head : 1 ;
X} status;
X
Xtypedef struct rb_node {
X  union {
X    struct {
X      struct rb_node *flink;
X      struct rb_node *blink;
X    } list;
X    struct {
X      struct rb_node *left;
X      struct rb_node *right;
X    } child;
X  } c;
X  union {
X    struct rb_node *parent;
X    struct rb_node *root;
X  } p;
X  status s;
X  union {
X    int ikey;
X    char *key;
X    struct rb_node *lext;
X  } k;
X  union {
X    char *val;
X    struct rb_node *rext;
X  } v;
X} *Rb_node;
X
Xextern Rb_node make_rb();
Xextern Rb_node rb_insert_b(/* node, char *key, char *value */);
X
Xextern Rb_node rb_find_key(/* tree, char *key */);
Xextern Rb_node rb_find_ikey(/* tree, int ikey */);
Xextern Rb_node rb_find_gkey(/* tree, char *key, cmpfxn */);
X
Xextern Rb_node rb_find_key_n(/* tree, char *key, int *found */);
Xextern Rb_node rb_find_ikey_n(/* tree, int ikey, int *found */);
Xextern Rb_node rb_find_gkey_n(/* tree, char *key, cmpfxn, int *found */);
Xextern rb_delete_node(/* node */);
Xextern rb_free_tree(/* node */);  /* Deletes and frees an entire tree */
Xextern char *rb_val(/* node */);  /* Returns node->v.val (this is to shut
X                     lint up */
X
X#define rb_insert_a(n, k, v) rb_insert_b(n->c.list.flink, k, v)
X#define rb_insert(t, k, v) rb_insert_b(rb_find_key(t, k), k, v)
X#define rb_inserti(t, k, v) rb_insert_b(rb_find_ikey(t, k), (char *) k, v)
X#define rb_insertg(t, k, v, f) rb_insert_b(rb_find_gkey(t, k, f), k, v)
X#define rb_first(n) (n->c.list.flink)
X#define rb_last(n) (n->c.list.blink)
X#define rb_next(n) (n->c.list.flink)
X#define rb_prev(n) (n->c.list.blink)
X#define rb_empty(t) (t->c.list.flink == t)
X#ifndef nil
X#define nil(t) (t)
X#endif
X
X#define rb_traverse(ptr, lst) \
X  for(ptr = rb_first(lst); ptr != nil(lst); ptr = rb_next(ptr))
X
END_OF_FILE
  if test 1839 -ne `wc -c <'rb.h'`; then
    echo shar: \"'rb.h'\" unpacked with wrong size!
  fi
  # end of 'rb.h'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have the archive.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...