From: avg@rodan.UU.NET (Vadim Antonov)
Newsgroups: comp.programming
Subject: Re: Why Are Red-Black Trees Obscure?
Date: 27 Aug 1992 16:45:49 -0400
Organization: Berkeley Software Design
NNTP-Posting-Host: rodan.uu.net

They aren't.

--vadim

# This is a shell archive.  Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file".  Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
#	rb-generic.c
#	rb-test.c
#
echo x - rb-generic.c
sed 's/^X//' >rb-generic.c << 'END-of-rb-generic.c'
X/*
X * Copyright 1991, Vadim Antonov
X * All rights reserved.
X *
X * This code is developed as a part of Grail project and can
X * be used and redistributed freely as long as this copyright
X * notice is retained.
X *
X * THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTIES.
X */
X
X/* Revision 1.0, 7-12-1991 */
X
X/*
X * Generic simple/interval red-black tree maintenance routines
X *
X *
X *	This file should be included into C source files after the
X *	following defines:
X *
X *	RB_INTERVALS		- interval trees
X *	RB_MAY_OVERLAP		- intervals may overlap
X *	RB_MINIMAL_KEY		- the minimal value of a key
X *	RB_NODE_REF_TYPE	- type of a pointer to a tree node
X *	RB_KEY_TYPE		- type of the key (or interval limits)
X *	RB_LESS(a, b) 		- true if a < b
X *	RB_EQ(a, b)		- true if a == b
X *	RB_ISRED(node)		- check if RED flag is set for node
X *	RB_SETRED(node)		- set the node red
X *	RB_SETBLACK(node)	- set the node black
X *	RB_NOINLINE		- do not do inlines
X *	RB_DEBUG		- add routines for validating and printing
X *				  out the tree
X *	RB_KEY_FMT		- format (like "%d") for printing the value of
X *				  a key
X *	RB_XPRINTF(x)		- if defined - a statement printing additional
X *				  information from the tree node x. Should not
X *				  print newline at the end.
X *
X * 	This file defines the following routines (xxx is for RB_PROC_PREFIX):
X *
X *	RB_SEARCH		node = search(tree, key)  or
X *				node = search(tree, b, e) for interval trees
X *	RB_OVERLAP		node = overlap(tree, b, e)
X *	RB_INSERT		insert(tree, node)
X *	RB_DELETE		delete(tree, node)
X *	RB_INITIALIZE		initialize(tree)
X *	RB_PRINT		print(tree)
X *	RB_SCAN1		scan1(tree)
X *	RB_SCAN2		scan2(tree)
X *	RB_SCAN3		scan3(tree)
X *
X * Routines scanning the tree can be created with the defines RB_SCANn
X * (the name for the scan routine) and RB_SCAN_PROCn(x) where n = 1,2 or 3 and
X * x is the pointer to the current node. RB_SCANn_ORDERED should be defined if
X * scanning nodes in increasing order is desired; but this mode does not allow
X * for destruction of nodes.
X *
X *	The structure *RB_NODE_REF_TYPE should contain the following fields
X *	(yyy is for RB_FIELD_PREFIX):
X *
X * RB_KEY_TYPE:
X *	RB_BEGIN	- the beginning of the interval (for interval trees)
X *			  or the key (for non-interval trees)
X *	RB_END		- the end of the interval (for interval trees)
X *	RB_MAX		- the last point of all intervals in the subtree 
X *			  (interval trees only)
X *
X * RB_NODE_REF_TYPE:
X *	RB_LEFT		- link to the left
X * 	RB_RIGHT	- link to the right
X *	RB_PARENT	- link to the parent
X *
X * The following definitions should contain some unique names for internal procedures:
X *	RB_MAX3_
X *	RB_ROTATE_LEFT_
X *	RB_ROTATE_RIGHT_
X *	RB_PRINT_
X */
X
X
X#ifdef RB_SCAN1
X/*
X * Scan the tree from lower nodes to upper (can be used to
X * destroy the whole tree if non-ordered)
X */
Xvoid RB_SCAN1(tt)
X	register RB_NODE_REF_TYPE tt;
X{
X	register RB_NODE_REF_TYPE x = tt->RB_LEFT;
X	register RB_NODE_REF_TYPE z;
X
X	for(;;) {
X		while( x->RB_LEFT != tt )
X			x = x->RB_LEFT;
X		for(;;) {
X#ifdef RB_SCAN1_ORDERED
X			RB_SCAN_PROC1(x);
X#endif
X			if( x->RB_RIGHT != tt ) {
X				x = x->RB_RIGHT;
X				break;
X			}
X		
X			for(;;) {
X				z = x->RB_PARENT;
X#ifndef RB_SCAN1_ORDERED
X				RB_SCAN_PROC1(x);
X#endif
X				if( x == z->RB_LEFT ) {
X					if( z == tt )
X						return;
X					x = z;
X					break;
X				}
X				x = z;
X			}
X		}
X	}
X}
X#endif /* RB_SCAN1 */
X
X/* 2nd replica */
X#ifdef RB_SCAN2
Xvoid RB_SCAN2(tt)
X	register RB_NODE_REF_TYPE tt;
X{
X	register RB_NODE_REF_TYPE x = tt->RB_LEFT;
X	register RB_NODE_REF_TYPE z;
X
X	for(;;) {
X		while( x->RB_LEFT != tt )
X			x = x->RB_LEFT;
X		for(;;) {
X#ifdef RB_SCAN2_ORDERED
X			RB_SCAN_PROC2(x);
X#endif
X			if( x->RB_RIGHT != tt ) {
X				x = x->RB_RIGHT;
X				break;
X			}
X		
X			for(;;) {
X				z = x->RB_PARENT;
X#ifndef RB_SCAN2_ORDERED
X				RB_SCAN_PROC2(x);
X#endif
X				if( x == z->RB_LEFT ) {
X					if( z == tt )
X						return;
X					x = z;
X					break;
X				}
X				x = z;
X			}
X		}
X	}
X}
X#endif /* RB_SCAN2 */
X
X/* 3rd replica */
X#ifdef RB_SCAN3
Xvoid RB_SCAN3(tt)
X	register RB_NODE_REF_TYPE tt;
X{
X	register RB_NODE_REF_TYPE x = tt->RB_LEFT;
X	register RB_NODE_REF_TYPE z;
X
X	for(;;) {
X		while( x->RB_LEFT != tt )
X			x = x->RB_LEFT;
X		for(;;) {
X#ifdef RB_SCAN3_ORDERED
X			RB_SCAN_PROC3(x);
X#endif
X			if( x->RB_RIGHT != tt ) {
X				x = x->RB_RIGHT;
X				break;
X			}
X		
X			for(;;) {
X				z = x->RB_PARENT;
X#ifndef RB_SCAN3_ORDERED
X				RB_SCAN_PROC3(x);
X#endif
X				if( x == z->RB_LEFT ) {
X					if( z == tt )
X						return;
X					x = z;
X					break;
X				}
X				x = z;
X			}
X		}
X	}
X}
X#endif /* RB_SCAN3 */
X
X#ifndef RB_INTERVALS
X
X#ifdef RB_SEARCH
X/*
X * Search for the key
X */
XRB_NODE_REF_TYPE RB_SEARCH(tt, key)
X	register RB_NODE_REF_TYPE tt;
X	register RB_KEY_TYPE      key;
X{
X	register RB_NODE_REF_TYPE t = tt->RB_LEFT;
X
X	while( t != tt ) {
X		if( RB_EQ(t->RB_BEGIN, key) )
X			return t;
X		t = (RB_LESS(key, t->RB_BEGIN)) ? t->RB_LEFT : t->RB_RIGHT;
X	}
X	return 0;
X}
X#endif /* RB_SEARCH */
X
X/* for any case... */
X#undef RB_MAY_OVERLAP
X#undef RB_OVERLAP
X
X#else	/* RB_INTERVALS */
X
X
X#ifdef RB_MAY_OVERLAP
X
X#ifdef RB_SEARCH
X/*
X * Search in the interval red-black tree for
X * exact matches (the tree can keep overlapping intervals)
X */
XRB_NODE_REF_TYPE RB_SEARCH(tt, b, e)
X	register RB_NODE_REF_TYPE tt;
X	register RB_KEY_TYPE b;
X	register RB_KEY_TYPE e;
X{
X	register RB_NODE_REF_TYPE t = tt->RB_LEFT;
X
X	while( t != tt ) {
X		if( RB_EQ(b, t->RB_BEGIN) ) {
X			if( RB_EQ(t->RB_END, e) )
X				return t;
X			t = (RB_LESS(e, t->RB_END)) ? t->RB_LEFT : t->RB_RIGHT;
X		} else
X			t = (RB_LESS(b, t->RB_BEGIN)) ? t->RB_LEFT : t->RB_RIGHT;
X	}
X	return 0;
X}
X#endif /* RB_SEARCH */
X
X
X#ifdef RB_OVERLAP
X/*
X * Search for an overlapping interval in red-black tree
X *	(tree can keep overlapping intervals)
X */
XRB_NODE_REF_TYPE RB_OVERLAP(tt, b, e)
X	register RB_NODE_REF_TYPE tt;
X	register RB_KEY_TYPE b;
X	register RB_KEY_TYPE e;
X{
X	register RB_NODE_REF_TYPE t = tt->RB_LEFT;
X	register RB_NODE_REF_TYPE x;
X
X	while( t != tt ) {
X		if( !(RB_LESS(t->RB_END, b)) && !(RB_LESS(e, t->RB_BEGIN)) )
X			return t;
X		x = t->RB_RIGHT;
X		t = t->RB_LEFT;
X		if( t == tt || (RB_LESS(t->RB_MAX, b)) ) 
X			t = x;
X	}
X	return 0;
X}
X#endif
X
X/*
X * Calculate maximum of 3 values
X */
X#ifndef RB_NOINLINE
Xinline
X#endif
Xstatic RB_KEY_TYPE RB_MAX3_(x)
X	register RB_NODE_REF_TYPE x;
X{
X	register RB_KEY_TYPE a = x->RB_LEFT->RB_MAX;
X
X	if( RB_LESS(a, x->RB_RIGHT->RB_MAX) )
X		a = x->RB_RIGHT->RB_MAX;
X	if( RB_LESS(a, x->RB_END) )
X		a = x->RB_END;
X	return a;
X}
X
X#else /* !RB_MAY_OVERLAP */
X
X#ifdef RB_SEARCH
X/*
X * Search in the interval red-black tree for
X * exact matches (tree does not keep overlapping intervals)
X */
XRB_NODE_REF_TYPE RB_SEARCH(tt, b, e)
X	register RB_NODE_REF_TYPE tt;
X	register RB_KEY_TYPE b;
X	register RB_KEY_TYPE e;
X{
X	register RB_NODE_REF_TYPE t = tt->RB_LEFT;
X
X	while( t != tt ) {
X		if( RB_EQ(b, t->RB_BEGIN) ) {
X			if( RB_EQ(t->RB_END, e) )
X				return t;
X			return 0;
X		}
X		t = (RB_LESS(b, t->RB_BEGIN)) ? t->RB_LEFT : t->RB_RIGHT;
X	}
X	return 0;
X}
X#endif /* RB_SEARCH */
X
X#ifdef RB_OVERLAP
X/*
X * Search for an overlapping interval in red-black tree
X *	(tree does not keep overlapping intervals)
X */
XRB_NODE_REF_TYPE RB_OVERLAP(tt, b, e)
X	register RB_NODE_REF_TYPE tt;
X	register RB_KEY_TYPE b;
X	register RB_KEY_TYPE e;
X{
X	register RB_NODE_REF_TYPE t = tt->RB_LEFT;
X
X	while( t != tt ) {
X		if( !(RB_LESS(t->RB_END, b)) && !(RB_LESS(e, t->RB_BEGIN)) )
X			return t;
X		t = (RB_LESS(b, t->RB_BEGIN)) ? t->RB_LEFT : t->RB_RIGHT;
X	}
X	return 0;
X}
X#endif
X
X#endif /* !RB_MAY_OVERLAP */
X
X#endif /* RB_INTERVALS */
X	
X
X/*
X * Rotating aroud the tree's node adjusting intervals
X */
X#ifndef RB_NOINLINE
Xinline
X#endif
Xstatic void RB_ROTATE_LEFT_(x)
X	register RB_NODE_REF_TYPE x;
X{
X	register RB_NODE_REF_TYPE y;
X
X	y = x->RB_RIGHT;
X	x->RB_RIGHT = y->RB_LEFT;
X	y->RB_LEFT->RB_PARENT = x;	/* can affect the sentinel */
X	y->RB_PARENT = x->RB_PARENT;
X	if( x == x->RB_PARENT->RB_LEFT )
X		x->RB_PARENT->RB_LEFT = y;
X	else
X		x->RB_PARENT->RB_RIGHT = y;
X	y->RB_LEFT = x;
X	x->RB_PARENT = y;
X#ifdef RB_MAY_OVERLAP
X	y->RB_MAX = x->RB_MAX;
X	x->RB_MAX = RB_MAX3_(x);
X#endif
X}
X
X#ifndef RB_NOINLINE
Xinline
X#endif
Xstatic void RB_ROTATE_RIGHT_(x)
X	register RB_NODE_REF_TYPE x;
X{
X	register RB_NODE_REF_TYPE y;
X
X	y = x->RB_LEFT;
X	x->RB_LEFT = y->RB_RIGHT;
X	y->RB_RIGHT->RB_PARENT = x;	/* can affect the sentinel */
X	y->RB_PARENT = x->RB_PARENT;
X	if( x == x->RB_PARENT->RB_RIGHT )
X		x->RB_PARENT->RB_RIGHT = y;
X	else
X		x->RB_PARENT->RB_LEFT = y;
X	y->RB_RIGHT = x;
X	x->RB_PARENT = y;
X#ifdef RB_MAY_OVERLAP
X	y->RB_MAX = x->RB_MAX;
X	x->RB_MAX = RB_MAX3_(x);
X#endif
X}
X		
X
X#ifdef RB_INSERT
X/*
X * Insert into the red-black tree
X */
Xvoid RB_INSERT(t, x)
X	RB_NODE_REF_TYPE          t;
X	register RB_NODE_REF_TYPE x;
X{
X	register RB_NODE_REF_TYPE y, z;
X
X	/*
X	 * Standard insertion into binary tree
X	 */
X	x->RB_RIGHT = x->RB_LEFT = t;	/* sentinels */
X#ifdef RB_INTERVALS
X	x->RB_MAX = x->RB_END;
X#endif
X	y = t->RB_LEFT;
X	if( y == t ) {
X		t->RB_LEFT = x;
X		x->RB_PARENT = t;
X		RB_SETBLACK(x);
X		return;
X	}
X	z = t;
X	do {
X		z = y;
X		/*
X		 * The following three lines are necessary only for
X		 * exact-match interval searches
X		 */
X#if defined(RB_INTERVALS) && defined(RB_SEARCH)
X		if( RB_EQ(x->RB_BEGIN, y->RB_BEGIN) )
X			y = (RB_LESS(x->RB_END, y->RB_END)) ? y->RB_LEFT : y->RB_RIGHT;
X		else
X#endif
X			y = (RB_LESS(x->RB_BEGIN, y->RB_BEGIN)) ? y->RB_LEFT : y->RB_RIGHT;
X	} while( y != t );
X	x->RB_PARENT = z;
X	if(
X#if defined(RB_INTERVALS) && defined(RB_SEARCH)
X	    ((RB_EQ(x->RB_BEGIN, z->RB_BEGIN)) &&
X	     (RB_LESS(x->RB_END, z->RB_END))) ||
X#endif
X	     (RB_LESS(x->RB_BEGIN, z->RB_BEGIN)) )
X		z->RB_LEFT = x;
X	else
X		z->RB_RIGHT = x;
X
X#ifdef RB_MAY_OVERLAP
X	/*
X	 * Adjust maximal values
X	 */
X	for( y = z ; y != t ; y = y->RB_PARENT ) {
X		if ( x->RB_END <= y->RB_MAX )
X			break;
X		y->RB_MAX = x->RB_END;
X	} 
X#endif /* RB_MAY_OVERLAP */
X
X	/*
X	 * Balancing the tree
X	 */
X	RB_SETRED(x);
X	while( RB_ISRED(z) ) {
X		y = z->RB_PARENT->RB_LEFT;
X		if( z == y ) {
X			y = z->RB_PARENT->RB_RIGHT;
X			if( RB_ISRED(y) ) {
X				RB_SETBLACK(z);
X				RB_SETBLACK(y);
X				RB_SETRED(z->RB_PARENT);
X				x = z->RB_PARENT;
X				z = x->RB_PARENT;
X			} else {
X				if( x == z->RB_RIGHT ) {
X					x = z;
X					RB_ROTATE_LEFT_(x);
X					z = x->RB_PARENT;
X				}
X				RB_SETBLACK(z);
X				RB_SETRED(z->RB_PARENT);
X				RB_ROTATE_RIGHT_(z->RB_PARENT);
X			}
X		} else {
X			if( RB_ISRED(y) ) {
X				RB_SETBLACK(z);
X				RB_SETBLACK(y);
X				RB_SETRED(z->RB_PARENT);
X				x = z->RB_PARENT;
X				z = x->RB_PARENT;
X			} else {
X				if( x == z->RB_LEFT ) {
X					x = z;
X					RB_ROTATE_RIGHT_(x);
X					z = x->RB_PARENT;
X				}
X				RB_SETBLACK(z);
X				RB_SETRED(z->RB_PARENT);
X				RB_ROTATE_LEFT_(z->RB_PARENT);
X			}
X		}
X	}
X	RB_SETBLACK(t->RB_LEFT);
X}
X#endif /* RB_INSERT */
X
X#ifdef RB_DELETE
X/*
X * Delete node from red-black tree
X */
Xvoid RB_DELETE(t, w)
X	RB_NODE_REF_TYPE t;
X	register RB_NODE_REF_TYPE w;
X{
X	register RB_NODE_REF_TYPE x;
X	register RB_NODE_REF_TYPE y;
X	register RB_NODE_REF_TYPE z;
X	RB_NODE_REF_TYPE xpar;
X	RB_KEY_TYPE mval;
X	int removed_red;
X
X	xpar = w->RB_PARENT;
X	removed_red = (RB_ISRED(w));
X	if( w->RB_LEFT == t )
X		x = y = w->RB_RIGHT;
X	else if( w->RB_RIGHT == t )
X		x = y = w->RB_LEFT;
X	else {
X		y = w->RB_RIGHT;
X		if( y->RB_LEFT == t ) {
X			x = y->RB_RIGHT;
X			xpar = y;
X		} else {
X			do {
X				y = y->RB_LEFT;
X			} while( y->RB_LEFT != t );
X			x = y->RB_RIGHT;
X			xpar = x->RB_PARENT = y->RB_PARENT;
X			y->RB_PARENT->RB_LEFT = x;
X			y->RB_RIGHT = w->RB_RIGHT;
X			w->RB_RIGHT->RB_PARENT = y;
X		}
X		y->RB_LEFT = w->RB_LEFT;
X		y->RB_LEFT->RB_PARENT = y;
X		removed_red = (RB_ISRED(y));
X		RB_SETBLACK(y);
X		if( RB_ISRED(w) )
X			RB_SETRED(y);
X#ifdef RB_MAY_OVERLAP
X		/* adjust y MAX value */
X		y->RB_MAX = RB_MAX3_(y);
X#endif
X	}
X	z = w->RB_PARENT;
X	y->RB_PARENT = z; 
X	if( z->RB_LEFT == w )
X		z->RB_LEFT = y;
X	else
X		z->RB_RIGHT = y;
X	if( t->RB_LEFT == t )
X		return;
X
X#ifdef RB_MAY_OVERLAP
X	/*
X	 * Adjust max values
X	 */
X	if( x != y ) {
X		/* this loop cannot reach the root (actually, it cannot reach y) */
X		for( y = xpar ; ; y = y->RB_PARENT ) {
X			mval = RB_MAX3_(y);
X			if( mval == y->RB_MAX )
X				break;
X			y->RB_MAX = mval;
X		}
X	}
X	while( z != t ) {
X		mval = RB_MAX3_(z);
X		if( mval == z->RB_MAX )
X			break;
X		z->RB_MAX = mval;
X		z = z->RB_PARENT;
X	}
X#endif /* RB_MAY_OVERLAP */
X
X	/*
X	 * Fix up red-black properties
X	 */
X	if( removed_red )
X		return;
X	z = xpar;
X	while( x != t->RB_LEFT && !(RB_ISRED(x)) ) {
X		if( x == z->RB_LEFT ) {
X			y = z->RB_RIGHT;
X			if( RB_ISRED(y) ) {
X				RB_SETBLACK(y);
X				RB_SETRED(z);
X				RB_ROTATE_LEFT_(z);
X				y = z->RB_RIGHT;
X			}
X			if( !(RB_ISRED(y->RB_LEFT)) && !(RB_ISRED(y->RB_RIGHT)) ) {
X				RB_SETRED(y);
X				x = z;
X				z = x->RB_PARENT;
X			} else {
X				if( !(RB_ISRED(y->RB_RIGHT)) ) {
X					/* y->RB_LEFT cannot be nil */
X					RB_SETBLACK(y->RB_LEFT);
X					RB_SETRED(y);
X					RB_ROTATE_RIGHT_(y);
X					y = z->RB_RIGHT;
X				}
X				RB_SETBLACK(y);
X				if( RB_ISRED(z) )
X					RB_SETRED(y);
X				RB_SETBLACK(z);
X				RB_SETBLACK(y->RB_RIGHT);
X				RB_ROTATE_LEFT_(z);
X				break;
X			}
X		} else {
X			y = z->RB_LEFT;
X			if( RB_ISRED(y) ) {
X				RB_SETBLACK(y);
X				RB_SETRED(z);
X				RB_ROTATE_RIGHT_(z);
X				y = z->RB_LEFT;
X			}
X			if( !(RB_ISRED(y->RB_LEFT)) && !(RB_ISRED(y->RB_RIGHT)) ) {
X				RB_SETRED(y);
X				x = z;
X				z = x->RB_PARENT;
X			} else {
X				if( !(RB_ISRED(y->RB_LEFT)) ) {
X					/* y->RB_RIGHT cannot be nil */
X					RB_SETBLACK(y->RB_RIGHT);
X					RB_SETRED(y);
X					RB_ROTATE_LEFT_(y);
X					y = z->RB_LEFT;
X				}
X				RB_SETBLACK(y);
X				if( RB_ISRED(z) )
X					RB_SETRED(y);
X				RB_SETBLACK(z);
X				RB_SETBLACK(y->RB_LEFT);
X				RB_ROTATE_RIGHT_(z);
X				break;
X			}
X		}
X	}
X	RB_SETBLACK(x);
X}
X#endif /* RB_DELETE */
X
X#ifdef RB_INITIALIZE
X/*
X * Initialize the tree header/nil sentinel
X */
Xvoid RB_INITIALIZE(t)
X	register RB_NODE_REF_TYPE t;
X{
X	t->RB_LEFT = t->RB_RIGHT = t->RB_PARENT = t;
X	t->RB_BEGIN = RB_MINIMAL_KEY;
X#ifdef RB_INTERVALS
X	t->RB_END = RB_MINIMAL_KEY;
X#ifdef RB_MAY_OVERLAP
X	t->RB_MAX = RB_MINIMAL_KEY;
X#endif
X#endif /* RB_INTERVALS */
X	RB_SETBLACK(t);
X}
X#endif /* RB_INITIALIZE */
X
X
X#if defined(RB_PRINT) && defined(RB_PRINT_)
X
X#ifndef RB_KEY_FMT
X#define RB_KEY_FMT "%x"
X#endif
X
X/*
X * Printing the tree nodes in increasing order
X */
Xstatic void RB_PRINT_(t, tt, l)
X	register RB_NODE_REF_TYPE t;
X	register RB_NODE_REF_TYPE tt;
X	int l;
X{
X	if( t->RB_LEFT != tt )
X		RB_PRINT_(t->RB_LEFT, tt, l+1);
X	printf("%*s%x [%c] ", l*4, "", t, (RB_ISRED(t))? 'R' : 'B');
X	printf(RB_KEY_FMT, t->RB_BEGIN);
X#ifdef RB_INTERVALS
X	printf("-");
X	printf(RB_KEY_FMT, t->RB_END);
X#ifdef RB_MAY_OVERLAP
X	printf(" max=");
X	printf(RB_KEY_FMT, t->RB_MAX);
X#endif
X#endif /* RB_INTERVALS */
X	printf(t->RB_LEFT   == tt? " l=NIL": " l=%x", t->RB_LEFT);
X	printf(t->RB_RIGHT  == tt? " r=NIL": " r=%x", t->RB_RIGHT);
X	printf(t->RB_PARENT == tt? " p=NIL": " p=%x", t->RB_PARENT);
X#ifdef RB_XPRINTF
X	RB_XPRINTF(t);
X#endif
X	printf("\n");
X	if( t->RB_RIGHT != tt )
X		RB_PRINT_(t->RB_RIGHT, tt, l+1);
X}
X
X/*
X * Print out the tree
X */
Xvoid RB_PRINT(t)
X	register RB_NODE_REF_TYPE t;
X{
X	if( t->RB_LEFT == t )
X		printf("EMPTY\n");
X	else
X		RB_PRINT_(t->RB_LEFT, t, 0);
X}
X#endif /* RB_PRINT */
X
X/*
X * Recursive verification step
X */
X
X	
X/*
X * Un-define the module parameters
X */
X#undef	RB_INTERVALS
X#undef	RB_MAY_OVERLAP
X#undef	RB_MINIMAL_KEY
X#undef	RB_NODE_REF_TYPE
X#undef	RB_KEY_TYPE
X#undef	RB_LESS(a, b) 
X#undef	RB_EQ(a, b)
X#undef	RB_ISRED(node)
X#undef	RB_SETRED(node)	
X#undef	RB_SETBLACK(node)
X#undef	RB_NO_INLINES
X#undef	RB_KEY_FMT
X#undef	RB_XPRINTF
X
X#undef	RB_SCAN1
X#undef	RB_SCAN2
X#undef	RB_SCAN3
X#undef	RB_SCAN_PROC1
X#undef	RB_SCAN_PROC2
X#undef	RB_SCAN_PROC3
X#undef	RB_SCAN1_ORDERED
X#undef	RB_SCAN2_ORDERED
X#undef	RB_SCAN3_ORDERED
X#undef	RB_SEARCH
X#undef	RB_OVERLAP
X#undef	RB_INSERT
X#undef	RB_DELETE
X#undef	RB_INITIALIZE
X#undef	RB_PRINT
X
X#undef	RB_MAX3_
X#undef	RB_ROTATE_RIGHT_
X#undef	RB_ROTATE_LEFT_
X#undef	RB_PRINT_
X
X#undef	RB_BEGIN
X#undef	RB_END
X#undef	RB_MAX
X#undef	RB_LEFT
X#undef	RB_RIGHT
X#undef	RB_PARENT
END-of-rb-generic.c
echo x - rb-test.c
sed 's/^X//' >rb-test.c << 'END-of-rb-test.c'
X
X/*
X * Copyright 1991, Vadim Antonov
X * All rights reserved.
X *
X * This code is developed as a part of Grail project and can
X * be used and redistributed freely as long as this copyright
X * notice is retained.
X *
X * THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTIES.
X */
X
X/* Revision 1.0, 7-12-1991 */
X
X#include <stdio.h>
X#include <assert.h>
X
X/*
X * Red-Black tree node
X */
X
Xtypedef struct RBNODE *rbnode;
X
Xstruct RBNODE {
X	int	rb_red;		/* node is red */
X	int	rb_begin;	/* beginning of the interval */
X	int	rb_end;		/* end of the interval */
X	int	rb_max;		/* highest value in the subtree */
X	rbnode	rb_left;	/* left link */
X	rbnode	rb_right;	/* right link */
X	rbnode	rb_parent;	/* parent link */
X};
X
X
X/*
X * Include generic routines
X */
X#define RB_INTERVALS
X#undef RB_MAY_OVERLAP
X#define RB_MINIMAL_KEY		(~0)
X#define RB_NODE_REF_TYPE	rbnode
X#define RB_KEY_TYPE		int
X#define RB_LESS(a,b)		a < b
X#define RB_EQ(a,b)		a == b
X#define RB_ISRED(x)		x->rb_red
X#define RB_SETRED(x)		x->rb_red = 1
X#define RB_SETBLACK(x)		x->rb_red = 0
X#define RB_DEBUG
X#define RB_KEY_FMT		"%d"
X#define RB_SCAN1		rbi_scan1
X#define RB_SCAN_PROC1(x)	printf("(%d-%d) ", x->rb_begin, x->rb_end)
X#define RB_SCAN2		rbi_scan2
X#define RB_SCAN_PROC2(x)	printf("(%d-%d) ", x->rb_begin, x->rb_end)
X#define RB_SCAN2_ORDERED
X#define RB_SEARCH		rbi_search
X#define RB_OVERLAP		rbi_overlap
X#define RB_INSERT		rbi_insert
X#define RB_DELETE		rbi_delete
X#define RB_INITIALIZE		rbi_initialize
X#define RB_PRINT		rbi_print
X
X#define RB_MAX3_		_rbi_max3
X#define RB_ROTATE_LEFT_		_rbi_rleft
X#define RB_ROTATE_RIGHT_	_rbi_rright
X#define RB_PRINT_		_rbi_print
X
X#define RB_BEGIN		rb_begin
X#define RB_END			rb_end
X#define RB_MAX			rb_max
X#define RB_LEFT			rb_left
X#define RB_RIGHT		rb_right
X#define RB_PARENT		rb_parent
X
X#include "rb-generic.c"
X
X#ifdef NOTYET
X#define MAXNODES 20000
Xint nnodes;
Xrbnode nodes[MAXNODES];
X#endif /*NOTYET*/
X
X/*
X * Debugging routines
X */
Xmain()
X{
X	char line[100];
X	char *p;
X	struct RBNODE tree;
X	rbnode x;
X	int i, j;
X	char *index();
X
X	rbi_initialize(&tree);
X	for(;;) {
X		printf("> ");
X		fflush(stdout);
X		fgets(line, 100, stdin);
X		if( (p = index(line, '\n')) != NULL )
X			*p = 0;
X		p = line;
X		while( *p && *p != ' ' ) p++;
X		while( *p == ' ' ) p++;
X		switch( line[0] ) {
X		default:
X			printf("valid commands: q, p, s key, a key, d key\n");
X			break;
X		case 0:
X			break;
X		case 'q':
X			exit(0);
X		case 'p':
X			rbi_print(&tree);
X			break;
X		case 'S':
X			i = atoi(p);
X			if( i == 1 )
X				rbi_scan1(&tree);
X			else if( i == 2 )
X				rbi_scan2(&tree);	
X			else
X				printf("Scan 1,2 only");
X			printf("\n");
X			break;
X		case 's':
X			i = atoi(p);
X			while( *p && *p != ' ' ) p++;
X			while( *p == ' ' ) p++;
X			j = atoi(p);
X			x = rbi_search(&tree, i, j);
X			if( x == 0 ) 
X				printf("%d-%d not found\n", i, j);
X			else
X				printf("%d-%d ==> %x\n", i,j, x);
X			break;
X		case 'o':
X			i = atoi(p);
X			while( *p && *p != ' ' ) p++;
X			while( *p == ' ' ) p++;
X			j = atoi(p);
X			x = rbi_overlap(&tree, i, j);
X			if( x == 0 ) 
X				printf("%d-%d not found\n", i, j);
X			else
X				printf("%d-%d overlaps with %d-%d (%x)\n", i,j, x->rb_begin, x->rb_end, x);
X			break;
X		case 'a':
X			i = atoi(p);
X			while( *p && *p != ' ' ) p++;
X			while( *p == ' ' ) p++;
X			j = atoi(p);
X			if( i > j ) {
X				printf("Inverted interval");
X				break;
X			}
X			x = (rbnode)malloc(sizeof(struct RBNODE));
X			x->rb_begin = i;
X			x->rb_end = j;
X			rbi_insert(&tree, x);
X			break;
X		case 'd':
X			i = atoi(p);
X			while( *p && *p != ' ' ) p++;
X			while( *p == ' ' ) p++;
X			j = atoi(p);
X			x = rbi_search(&tree, i, j);
X			if (x == 0)
X				printf("No such node\n");
X			else {
X				rbi_delete(&tree, x);
X				free(x);
X			}
X			break;
X/*
X		case 'v':
X			rbvrfy(&tree);
X			break;
X*/
X#ifdef NOTYET
X		case 'S':
X			i = atoi(p);
X			srand(i);
X			printf("SEED %d\n", i);
X			break;
X		case 'A':
X			i = atoi(p);
X			while( i-- > 0 ) {
X				if (nnodes >= MAXNODES)
X					break;
X				x = (rbnode)malloc(sizeof(struct RBNODE));
X				x->key = rand();
X				nodes[nnodes++] = x;
X				rbinsert(&tree, x);
X			}
X			printf("%d NODES\n", nnodes);
X			break;
X
X		case 'D':
X			i = atoi(p);
X			while( i-- > 0 ) {
X				if (nnodes <= 0)
X					break;
X				j = rand();
X				if( j < 0 )
X					j = -j;
X				j %= nnodes;
X				x = nodes[j];
X				nodes[j] = nodes[--nnodes];
X				rbdelete(&tree, x);
X				free(x);
X			}
X			printf("%d NODES\n", nnodes);
X			break;
X#endif /*NOTYET*/
X		}
X	}
X}
END-of-rb-test.c
exit