NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/programm/2512

Internet Message Format | 1992-08-27 | 21.6 KB

Path: sparky!uunet!uunet!not-for-mail
From: [e-mail] (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
Lines: 1012
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]>
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