NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/alt/sources/3075

Text File | 1993-01-23 | 26.7 KB | 1,129 lines

Newsgroups: alt.sources
Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!yale!gumby!destroyer!lambda.msfc.nasa.gov!decwrl!pa.dec.com!vix.com!vixie
From: [e-mail] (Paul A Vixie)
Message-ID: <[e-mail]>
Subject: new AVL library
Date: Fri, 22 Jan 93 21:55:08 -0800
X-Received: by usenet.pa.dec.com; id AA27287; Fri, 22 Jan 93 21:55:17 -0800
X-Received: by inet-gw-2.pa.dec.com; id AA25762; Fri, 22 Jan 93 21:55:10 -0800
X-Received: by gw.home.vix.com; id AA23768; Fri, 22 Jan 93 21:55:09 -0800
X-Btw: vix.com is also gw.home.vix.com and vixie.sf.ca.us
X-To: [e-mail]
X-Mts: smtp
Lines: 1114

before i put this into the comp.sources.unix queue, i'd like to
give people a chance to hack on the updated version.  the original
had a bug in delete; this one shouldn't, but i've lost my test case
so i really don't know.

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of shell archive."
# Contents:  README Makefile t_trtest.c tree.c tree.h tree.man3 vixie.h
# Wrapped by [e-mail] on Fri Jan 22 14:03:34 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(2468 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
AVL Trees V2.0
X22-Janulary-1993
Paul Vixie
X
There was a small bug in tree_delete() that manifested itself by corrupting
trees occasionally.  It didn't show up in 1987 because I was using a micro-
computer whose malloc() wasn't all that picky; on newer UNIX systems, malloc()
and free() are extremely picky and if you misuse them, they will abuse you.
X
I've taken the opportunity to convert the code to ANSI and POSIX.  If you
don't have <stdlib.h> you will have some small porting work to do; most newer
systems have this (BSDI, SYSV, Ultrix, OSF/1, OpenVMS, and so on) so you will
X(statistically speaking) not have too much of a problem with the changes.  I
conditionalized the ANSI'isms (function prototypes), so if you don't have a
fully ANSI compiler you should still be able to get this code to compile.
The one interface change I made was to change the external definition of the
tree from "int *" to "void *"; had "void *" existed in 1987 I would have used
it then.  I changed the delete_uar from "pointer to function returning int"
to "pointer to function returning void"; I don't know why I used "int" back
in 1987, those functions have never returned anything.
X
X--------
X
AVL Trees V1.0
X24-July-1987
Paul Vixie
X
This library and test program are useful for creating and using balanced
binary trees (AVL trees).  The tree is held in memory, using malloc(3) to
allocate storage.  A better version would allow file-based trees in
addition; once memory mapped files hit the UNIX(tm) community, this will
be much easier to do.  In the meanwhile, these routines have been very
useful to me for symbol tables and the like.  (Yes, I'm sure hashing is
better in some way, but I've used this for symbol tables, just the same.)
X
I cannot take credit for the algorithms.  See "Algorithms & Data Structures,"
Niklaus Wirth, Prentice-Hall 1986, ISBN 0-13-022005-1.  This is an update of
Wirth's previous book, titled "Algorythms + Data Structures = Programs,"
which used Pascal as the language for examples.  This later book uses the
newer Modula-2 for it's examples; this tree code was created using the
Modula-2 examples as guidelines.  At the time I typed this stuff in (about
a year ago, in July 1987), I understood how it all worked.  Today, well...
X
This code is hereby placed in the public domain, unless restrictions apply
from Prentice-Hall on the algorithms themselves.  If you use or redistribute
this code, please leave my name (and Wirth's) in the comments.
END_OF_FILE
if test 2468 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(593 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X# makefile for tree stuff
X# vix 24jul87 [stripped down from as makefile]
X# vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
X#
X# $Id:$
X
X#(choose a c compiler)
CC        =    gcc -Wall -Wtraditional -Wshadow -Wpointer-arith \
X            -Wcast-align -Wwrite-strings -pedantic
X#CC        =    cc
X
CDEBUG        =    -g
CFLAGS        =    $(CDEBUG) $(CCFLAGS)
LDFLAGS        =    $(CDEBUG)
X
TRTEST_OBJ    =    t_trtest.o tree.o
X
all        :    t_trtest
X
t_trtest    :    $(TRTEST_OBJ)
X            $(CC) -o t_trtest $(TRTEST_OBJ)
X
clean        :    FRC
X            rm -f core a.out t_trtest $(TRTEST_OBJ)
X
XFRC        :
X
tree.o        :    tree.c tree.h vixie.h
t_trtest.o    :    t_trtest.c tree.h vixie.h
END_OF_FILE
if test 593 -ne `wc -c <'Makefile'`; then
    echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 't_trtest.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'t_trtest.c'\"
else
echo shar: Extracting \"'t_trtest.c'\" \(2322 characters\)
sed "s/^X//" >'t_trtest.c' <<'END_OF_FILE'
X/* t_trtest - test the tree functions
X * vix 24jul87 [documented, added savestr for net distribution]
X * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
X */
X
X#ifndef LINT
static char RCSid[] = "$Id:";
X#endif
X
X#define MAIN
X
X#include <stdio.h>
X#include <strings.h>
X#include <stdlib.h>
X#include "vixie.h"
X#include "tree.h"
X
X
X#ifdef __STDC__
X#define __P(x) x
X#else
X#define    __P(x) ()
X#endif
X
static void    trtest        __P( (tree **, char *, int) );
static void    tree_trav1    __P( (tree *, int) );
static int    compar        __P( (char *, char *) );
static void    duar        __P( (char *) );
static char    *savestr    __P( (char *) );
X
X#undef __P
X
X
int
main()
X{
X    tree    *t;
X    char    line[100];
X
X    tree_init(&t);
X    while (printf("key (or .):  "), gets(line), line[0] != '.')
X    {
X        if (strncmp(line, "~r ", 3)) {
X            trtest(&t, line, 1);
X        }
X        else {
X            FILE *f;
X
X            if (!(f = fopen(&line[3], "r")))
X                perror(&line[3]);
X            else {
X                while (fgets(line, 100, f)) {
X                    line[strlen(line)-1] = '\0';
X                    printf("(%s)\n", line);
X                    trtest(&t, line, 0);
X                }
X                fclose(f);
X            }
X        }
X    }
X    return 0;
X}
X
static void
trtest(tt, line, inter)
X    tree    **tt;
X    char    *line;
X    int    inter;
X{
X    char    opts[100], *pc, *n;
X    int    opt, status;
X
X    pc = tree_srch(tt, compar, line);
X    printf("tree_srch=%x\n", (unsigned)pc);
X    if (pc)
X    {
X        printf("     <%s>\n", pc);
X
X        if (inter) {
X            printf("delete? "); gets(opts); opt = (opts[0]=='y');
X        }
X        else
X            opt = 1;
X
X        if (opt) {
X            status = tree_delete(tt, compar, line, duar);
X            printf("delete=%d\n", status);
X        }
X    }
X    else
X    {
X        if (inter) {
X            printf("add? "); gets(opts); opt = (opts[0]=='y');
X        }
X        else
X            opt = 1;
X
X        if (opt) {
X            char    *savestr();
X
X            n = savestr(line);
X            tree_add(tt, compar, n, duar);
X        }
X    }
X    tree_trav1(*tt, 0);
X}
X
static void
tree_trav1(t, l)
X    tree    *t;
X    int    l;
X{
X    int    i;
X
X    if (!t) return;
X    tree_trav1(t->tree_l, l+1);
X    for (i=0;  i<l;  i++) printf("  ");
X    printf("%08lx (%s)\n", (unsigned)t->tree_p, (char*)t->tree_p);
X    tree_trav1(t->tree_r, l+1);
X}
X
static void
duar(pc)
X    char *pc;
X{
X    printf("duar called, pc=%08X: <%s>\n", (unsigned)pc, pc?pc:"");
X    free(pc);
X}
X
static int
compar(l, r)
X    char *l, *r;
X{
X    printf("compar(%s,%s)=%d\n", l, r, strcmp(l, r));
X    return strcmp(l, r);
X}
X
static char *
savestr(str)
X    char    *str;
X{
X    char    *save;
X
X    save = malloc(strlen(str) + 1);
X    strcpy(save, str);
X    return save;
X}
END_OF_FILE
if test 2322 -ne `wc -c <'t_trtest.c'`; then
    echo shar: \"'t_trtest.c'\" unpacked with wrong size!
fi
# end of 't_trtest.c'
fi
if test -f 'tree.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'tree.c'\"
else
echo shar: Extracting \"'tree.c'\" \(10780 characters\)
sed "s/^X//" >'tree.c' <<'END_OF_FILE'
X/* as_tree - tree library for as
X * vix 14dec85 [written]
X * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
X * vix 06feb86 [added tree_mung()]
X * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
X * vix 23jun86 [added delete uar to add for replaced nodes]
X * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
X */
X
X
X/* This program text was created by Paul Vixie using examples from the book:
X * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
X * 0-13-022005-1.  This code and associated documentation is hereby placed
X * in the public domain.
X */
X
X
X#ifndef LINT
static char RCSid[] = "$Id:";
X#endif
X
X
X/*#define        DEBUG    "tree"*/
X
X
X#include <stdio.h>
X#include <stdlib.h>
X#include "vixie.h"
X#include "tree.h"
X
X
X#ifdef DEBUG
X#define        MSG(msg)    printf("DEBUG: '%s'\n", msg);
X#else
X#define        MSG(msg)
X#endif
X
X
X#ifdef __STDC__
X#define __P(x) x
X#else
X#define    __P(x) ()
X#endif
X
static void    sprout    __P( (tree **, tree_t, int *, int (*)(), void (*)()) );
static int    delete    __P( (tree **, int (*)(), tree_t, void (*)(),
X                  int *, int *) );
static void    del    __P( (tree **, int *, tree **, void (*)(), int *) );
static void    bal_L    __P( (tree **, int *) );
static void    bal_R    __P( (tree **, int *) );
X
X#undef __P
X
X
void
tree_init(ppr_tree)
X    tree    **ppr_tree;
X{
X    ENTER("tree_init")
X    *ppr_tree = NULL;
X    EXITV
X}
X
X
tree_t
tree_srch(ppr_tree, pfi_compare, p_user)
X    tree    **ppr_tree;
X    int    (*pfi_compare)();
X    tree_t    p_user;
X{
X    register int    i_comp;
X
X    ENTER("tree_srch")
X
X    if (*ppr_tree)
X    {
X        i_comp = (*pfi_compare)(p_user, (**ppr_tree).tree_p);
X        if (i_comp > 0)
X            EXIT(tree_srch(
X                &(**ppr_tree).tree_r,
X                pfi_compare,
X                p_user
X            ))
X        if (i_comp < 0)
X            EXIT(tree_srch(
X                &(**ppr_tree).tree_l,
X                pfi_compare,
X                p_user
X            ))
X
X        /* not higher, not lower... this must be the one.
X         */
X        EXIT((**ppr_tree).tree_p)
X    }
X
X    /* grounded. NOT found.
X     */
X    EXIT(NULL)
X}
X
X
void
tree_add(ppr_tree, pfi_compare, p_user, pfv_uar)
X    tree    **ppr_tree;
X    int    (*pfi_compare)();
X    tree_t    p_user;
X    void    (*pfv_uar)();
X{
X    int    i_balance = FALSE;
X
X    ENTER("tree_add")
X    sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar);
X    EXITV
X}
X
X
int
tree_delete(ppr_p, pfi_compare, p_user, pfv_uar)
X    tree    **ppr_p;
X    int    (*pfi_compare)();
X    tree_t    p_user;
X    void    (*pfv_uar)();
X{
X    int    i_balance = FALSE,
X        i_uar_called = FALSE;
X
X    ENTER("tree_delete");
X    EXIT(delete(ppr_p, pfi_compare, p_user, pfv_uar,
X            &i_balance, &i_uar_called))
X}
X
X
int
tree_trav(ppr_tree, pfi_uar)
X    tree    **ppr_tree;
X    int    (*pfi_uar)();
X{
X    ENTER("tree_trav")
X
X    if (!*ppr_tree)
X        EXIT(TRUE)
X
X    if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
X        EXIT(FALSE)
X    if (!(*pfi_uar)((**ppr_tree).tree_p))
X        EXIT(FALSE)
X    if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
X        EXIT(FALSE)
X    EXIT(TRUE)
X}
X
X
void
tree_mung(ppr_tree, pfv_uar)
X    tree    **ppr_tree;
X    void    (*pfv_uar)();
X{
X    ENTER("tree_mung")
X    if (*ppr_tree)
X    {
X        tree_mung(&(**ppr_tree).tree_l, pfv_uar);
X        tree_mung(&(**ppr_tree).tree_r, pfv_uar);
X        if (pfv_uar)
X            (*pfv_uar)((**ppr_tree).tree_p);
X        free(*ppr_tree);
X        *ppr_tree = NULL;
X    }
X    EXITV
X}
X
X
static void
sprout(ppr, p_data, pi_balance, pfi_compare, pfv_delete)
X    tree    **ppr;
X    tree_t    p_data;
X    int    *pi_balance;
X    int    (*pfi_compare)();
X    void    (*pfv_delete)();
X{
X    tree    *p1, *p2;
X    int    cmp;
X
X    ENTER("sprout")
X
X    /* are we grounded?  if so, add the node "here" and set the rebalance
X     * flag, then exit.
X     */
X    if (!*ppr) {
X        MSG("grounded. adding new node, setting h=true")
X        *ppr = (tree *) malloc(sizeof(tree));
X        (*ppr)->tree_l = NULL;
X        (*ppr)->tree_r = NULL;
X        (*ppr)->tree_b = 0;
X        (*ppr)->tree_p = p_data;
X        *pi_balance = TRUE;
X        EXITV
X    }
X
X    /* compare the data using routine passed by caller.
X     */
X    cmp = (*pfi_compare)(p_data, (*ppr)->tree_p);
X
X    /* if LESS, prepare to move to the left.
X     */
X    if (cmp < 0) {
X        MSG("LESS. sprouting left.")
X        sprout(&(*ppr)->tree_l, p_data, pi_balance,
X            pfi_compare, pfv_delete);
X        if (*pi_balance) {    /* left branch has grown longer */
X            MSG("LESS: left branch has grown")
X            switch ((*ppr)->tree_b)
X            {
X            case 1:    /* right branch WAS longer; balance is ok now */
X                MSG("LESS: case 1.. balnce restored implicitly")
X                (*ppr)->tree_b = 0;
X                *pi_balance = FALSE;
X                break;
X            case 0:    /* balance WAS okay; now left branch longer */
X                MSG("LESS: case 0.. balnce bad but still ok")
X                (*ppr)->tree_b = -1;
X                break;
X            case -1:
X                /* left branch was already too long. rebalnce */
X                MSG("LESS: case -1: rebalancing")
X                p1 = (*ppr)->tree_l;
X                if (p1->tree_b == -1) {    /* LL */
X                    MSG("LESS: single LL")
X                    (*ppr)->tree_l = p1->tree_r;
X                    p1->tree_r = *ppr;
X                    (*ppr)->tree_b = 0;
X                    *ppr = p1;
X                }
X                else {            /* double LR */
X                    MSG("LESS: double LR")
X
X                    p2 = p1->tree_r;
X                    p1->tree_r = p2->tree_l;
X                    p2->tree_l = p1;
X
X                    (*ppr)->tree_l = p2->tree_r;
X                    p2->tree_r = *ppr;
X
X                    if (p2->tree_b == -1)
X                        (*ppr)->tree_b = 1;
X                    else
X                        (*ppr)->tree_b = 0;
X
X                    if (p2->tree_b == 1)
X                        p1->tree_b = -1;
X                    else
X                        p1->tree_b = 0;
X                    *ppr = p2;
X                } /*else*/
X                (*ppr)->tree_b = 0;
X                *pi_balance = FALSE;
X            } /*switch*/
X        } /*if*/
X        EXITV
X    } /*if*/
X
X    /* if MORE, prepare to move to the right.
X     */
X    if (cmp > 0) {
X        MSG("MORE: sprouting to the right")
X        sprout(&(*ppr)->tree_r, p_data, pi_balance,
X            pfi_compare, pfv_delete);
X        if (*pi_balance) {    /* right branch has grown longer */
X            MSG("MORE: right branch has grown")
X
X            switch ((*ppr)->tree_b)
X            {
X            case -1:MSG("MORE: balance was off, fixed implicitly")
X                (*ppr)->tree_b = 0;
X                *pi_balance = FALSE;
X                break;
X            case 0:    MSG("MORE: balance was okay, now off but ok")
X                (*ppr)->tree_b = 1;
X                break;
X            case 1:    MSG("MORE: balance was off, need to rebalance")
X                p1 = (*ppr)->tree_r;
X                if (p1->tree_b == 1) {    /* RR */
X                    MSG("MORE: single RR")
X                    (*ppr)->tree_r = p1->tree_l;
X                    p1->tree_l = *ppr;
X                    (*ppr)->tree_b = 0;
X                    *ppr = p1;
X                }
X                else {            /* double RL */
X                    MSG("MORE: double RL")
X
X                    p2 = p1->tree_l;
X                    p1->tree_l = p2->tree_r;
X                    p2->tree_r = p1;
X
X                    (*ppr)->tree_r = p2->tree_l;
X                    p2->tree_l = *ppr;
X
X                    if (p2->tree_b == 1)
X                        (*ppr)->tree_b = -1;
X                    else
X                        (*ppr)->tree_b = 0;
X
X                    if (p2->tree_b == -1)
X                        p1->tree_b = 1;
X                    else
X                        p1->tree_b = 0;
X
X                    *ppr = p2;
X                } /*else*/
X                (*ppr)->tree_b = 0;
X                *pi_balance = FALSE;
X            } /*switch*/
X        } /*if*/
X        EXITV
X    } /*if*/
X
X    /* not less, not more: this is the same key!  replace...
X     */
X    MSG("I found it!  Replacing data value")
X    *pi_balance = FALSE;
X    if (pfv_delete)
X        (*pfv_delete)((*ppr)->tree_p);
X    (*ppr)->tree_p = p_data;
X    EXITV
X}
X
X
static int
delete(ppr_p, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called)
X    tree    **ppr_p;
X    int    (*pfi_compare)();
X    tree_t    p_user;
X    void    (*pfv_uar)();
X    int    *pi_balance;
X    int    *pi_uar_called;
X{
X    tree    *pr_q;
X    int    i_comp, i_ret;
X
X    ENTER("delete")
X
X    if (*ppr_p == NULL) {
X        MSG("key not in tree")
X        EXIT(FALSE)
X    }
X
X    i_comp = (*pfi_compare)((*ppr_p)->tree_p, p_user);
X    if (i_comp > 0) {
X        MSG("too high - scan left")
X        i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, p_user, pfv_uar,
X                        pi_balance, pi_uar_called);
X        if (*pi_balance)
X            bal_L(ppr_p, pi_balance);
X    }
X    else if (i_comp < 0) {
X        MSG("too low - scan right")
X        i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, p_user, pfv_uar,
X                        pi_balance, pi_uar_called);
X        if (*pi_balance)
X            bal_R(ppr_p, pi_balance);
X    }
X    else {
X        MSG("equal")
X        pr_q = *ppr_p;
X        if (pr_q->tree_r == NULL) {
X            MSG("right subtree null")
X            *ppr_p = pr_q->tree_l;
X            *pi_balance = TRUE;
X        }
X        else if (pr_q->tree_l == NULL) {
X            MSG("right subtree non-null, left subtree null")
X            *ppr_p = pr_q->tree_r;
X            *pi_balance = TRUE;
X        }
X        else {
X            MSG("neither subtree null")
X            del(&pr_q->tree_l, pi_balance, &pr_q, pfv_uar,
X                                pi_uar_called);
X            if (*pi_balance)
X                bal_L(ppr_p, pi_balance);
X        }
X        if (!*pi_uar_called && *pfv_uar)
X            (*pfv_uar)(pr_q->tree_p);
X        free(pr_q);    /* thanks to [e-mail] */
X        i_ret = TRUE;
X    }
X    EXIT(i_ret)
X}
X
X
static void
del(ppr_r, pi_balance, ppr_q, pfv_uar, pi_uar_called)
X    tree    **ppr_r;
X    int    *pi_balance;
X    tree    **ppr_q;
X    void    (*pfv_uar)();
X    int    *pi_uar_called;
X{
X    ENTER("del")
X
X    if ((*ppr_r)->tree_r != NULL) {
X        del(&(*ppr_r)->tree_r, pi_balance, ppr_q,
X            pfv_uar, pi_uar_called);
X        if (*pi_balance)
X            bal_R(ppr_r, pi_balance);
X    } else {
X        if (pfv_uar)
X            (*pfv_uar)((*ppr_q)->tree_p);
X        *pi_uar_called = TRUE;
X        (*ppr_q)->tree_p = (*ppr_r)->tree_p;
X        *ppr_q = *ppr_r;
X        *ppr_r = (*ppr_r)->tree_l;
X        *pi_balance = TRUE;
X    }
X
X    EXITV
X}
X
X
static void
bal_L(ppr_p, pi_balance)
X    tree    **ppr_p;
X    int    *pi_balance;
X{
X    tree    *p1, *p2;
X    int    b1, b2;
X
X    ENTER("bal_L")
X    MSG("left branch has shrunk")
X
X    switch ((*ppr_p)->tree_b)
X    {
X    case -1: MSG("was imbalanced, fixed implicitly")
X        (*ppr_p)->tree_b = 0;
X        break;
X    case 0:    MSG("was okay, is now one off")
X        (*ppr_p)->tree_b = 1;
X        *pi_balance = FALSE;
X        break;
X    case 1:    MSG("was already off, this is too much")
X        p1 = (*ppr_p)->tree_r;
X        b1 = p1->tree_b;
X        if (b1 >= 0) {
X            MSG("single RR")
X            (*ppr_p)->tree_r = p1->tree_l;
X            p1->tree_l = *ppr_p;
X            if (b1 == 0) {
X                MSG("b1 == 0")
X                (*ppr_p)->tree_b = 1;
X                p1->tree_b = -1;
X                *pi_balance = FALSE;
X            } else {
X                MSG("b1 != 0")
X                (*ppr_p)->tree_b = 0;
X                p1->tree_b = 0;
X            }
X            *ppr_p = p1;
X        } else {
X            MSG("double RL")
X            p2 = p1->tree_l;
X            b2 = p2->tree_b;
X            p1->tree_l = p2->tree_r;
X            p2->tree_r = p1;
X            (*ppr_p)->tree_r = p2->tree_l;
X            p2->tree_l = *ppr_p;
X            if (b2 == 1)
X                (*ppr_p)->tree_b = -1;
X            else
X                (*ppr_p)->tree_b = 0;
X            if (b2 == -1)
X                p1->tree_b = 1;
X            else
X                p1->tree_b = 0;
X            *ppr_p = p2;
X            p2->tree_b = 0;
X        }
X    }
X    EXITV
X}
X
X
static void
bal_R(ppr_p, pi_balance)
X    tree    **ppr_p;
X    int    *pi_balance;
X{
X    tree    *p1, *p2;
X    int    b1, b2;
X
X    ENTER("bal_R")
X    MSG("right branch has shrunk")
X    switch ((*ppr_p)->tree_b)
X    {
X    case 1:    MSG("was imbalanced, fixed implicitly")
X        (*ppr_p)->tree_b = 0;
X        break;
X    case 0:    MSG("was okay, is now one off")
X        (*ppr_p)->tree_b = -1;
X        *pi_balance = FALSE;
X        break;
X    case -1: MSG("was already off, this is too much")
X        p1 = (*ppr_p)->tree_l;
X        b1 = p1->tree_b;
X        if (b1 <= 0) {
X            MSG("single LL")
X            (*ppr_p)->tree_l = p1->tree_r;
X            p1->tree_r = *ppr_p;
X            if (b1 == 0) {
X                MSG("b1 == 0")
X                (*ppr_p)->tree_b = -1;
X                p1->tree_b = 1;
X                *pi_balance = FALSE;
X            } else {
X                MSG("b1 != 0")
X                (*ppr_p)->tree_b = 0;
X                p1->tree_b = 0;
X            }
X            *ppr_p = p1;
X        } else {
X            MSG("double LR")
X            p2 = p1->tree_r;
X            b2 = p2->tree_b;
X            p1->tree_r = p2->tree_l;
X            p2->tree_l = p1;
X            (*ppr_p)->tree_l = p2->tree_r;
X            p2->tree_r = *ppr_p;
X            if (b2 == -1)
X                (*ppr_p)->tree_b = 1;
X            else
X                (*ppr_p)->tree_b = 0;
X            if (b2 == 1)
X                p1->tree_b = -1;
X            else
X                p1->tree_b = 0;
X            *ppr_p = p2;
X            p2->tree_b = 0;
X        }
X    }
X    EXITV
X}
END_OF_FILE
if test 10780 -ne `wc -c <'tree.c'`; then
    echo shar: \"'tree.c'\" unpacked with wrong size!
fi
# end of 'tree.c'
fi
if test -f 'tree.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'tree.h'\"
else
echo shar: Extracting \"'tree.h'\" \(767 characters\)
sed "s/^X//" >'tree.h' <<'END_OF_FILE'
X/* tree.h - declare structures used by tree.c
X * vix 27jun86 [broken out of tree.c]
X * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
X *
X * $Id:$
X */
X
X
X#ifndef    _TREE_FLAG
X#define    _TREE_FLAG
X
X
X#ifdef __STDC__
typedef    void *    tree_t;
X#define __P(x) x
X#else
typedef    char *    tree_t;
X#define    __P(x) ()
X#endif
X
X
typedef    struct    tree_s
X    {
X        struct    tree_s    *tree_l, *tree_r;
X        short        tree_b;
X        tree_t        tree_p;
X    }
X    tree;
X
X
void    tree_init    __P( (tree **) );
tree_t    tree_srch    __P( (tree **, int (*)(), tree_t) );
void    tree_add    __P( (tree **, int (*)(), tree_t, void (*)()) );
int    tree_delete    __P( (tree **, int (*)(), tree_t, void (*)()) );
int    tree_trav    __P( (tree **, int (*)()) );
void    tree_mung    __P( (tree **, void (*)()) );
X
X
X#undef __P
X
X
X#endif    /* _TREE_FLAG */
END_OF_FILE
if test 767 -ne `wc -c <'tree.h'`; then
    echo shar: \"'tree.h'\" unpacked with wrong size!
fi
# end of 'tree.h'
fi
if test -f 'tree.man3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'tree.man3'\"
else
echo shar: Extracting \"'tree.man3'\" \(4082 characters\)
sed "s/^X//" >'tree.man3' <<'END_OF_FILE'
X.TH TREE 3 "22 Jan 1993"
X.\" from .TH TREE 2 "23 June 1986"
X.UC 4
X.SH NAME
tree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav
X\- balanced binary tree routines
X.SH SYNOPSIS
X.nf
X.B void
X.B tree_init(tree)
X.B void **tree;
X.PP
X.B int *
X.B tree_srch(tree, compare, data)
X.B void **tree;
X.B int (*compare)();
X.B void *data;
X.PP
X.B void
X.B tree_add(tree, compare, data, del_uar)
X.B void **tree;
X.B int (*compare)();
X.B void *data;
X.B void (*del_uar)();
X.PP
X.B int
X.B tree_delete(tree, compare, data, del_uar)
X.B void **tree;
X.B int (*compare)();
X.B void *data;
X.B void (*del_uar)();
X.PP
X.B int
X.B tree_trav(tree, trav_uar)
X.B void **tree;
X.B int (*trav_uar)();
X.PP
X.B void
X.B tree_mung(tree, del_uar)
X.B void **tree;
X.B void (*del_uar)();
X.fi
X.SH DESCRIPTION
These functions create and manipulate a balanced binary (AVL) tree.  Each node
of the tree contains the expected left & right subtree pointers, a short-int
balance indicator, and a pointer to the user-data.  On a 32-bit system, this
means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise
alignment-constrained system with implied padding, 4+4+4+4 bytes per node).
There is no key data type enforced by this package; a caller-supplied
compare routine is used to compare user-data blocks.
X.PP
Balanced binary trees are very fast on searches and replacements, but have a
moderately high cost for additions and deletions.  If your application does a
lot more searches and replacements than it does additions and deletions, the
balanced (AVL) binary tree is a good choice for a data structure.
X.PP
X.I Tree_init
creates an empty tree and binds it to
X.I tree
X(which for this and all other routines in this package should be declared as
a pointer to void or int, and passed by reference), which can then be used by
other routines in this package.  Note that more than one
X.I tree
variable can exist at once; thus multiple trees can be manipulated
simultaneously.
X.PP
X.I Tree_srch
searches a tree for a specific node and returns either
X.I NULL
if no node was found, or the value of the user-data pointer if the node
was found.
X.I compare
is the address of a function to compare two user-data blocks.  This routine
should work much the way
X.IR strcmp 2
does; in fact,
X.I strcmp
could be used if the user-data was a null-terminated string.
X.I data
is the address of a user-data block to be used by
X.I compare
as the search criteria.  The tree is searched for a node where
X.I compare
returns 0.
X.PP
X.I Tree_add
inserts or replaces a node in the specified tree.  The tree specified by
X.I tree
is searched as in
X.I tree_srch,
and if a node is found to match
X.I data,
then the
X.I del_uar
function is called with the address of the user-data block for the node
X(this routine should deallocate any dynamic memory which is referenced
exclusively by the node); the user-data pointer for the node is then
replaced by the value of
X.I data.
If no node is found to match, a new node is added (which may or may not
cause a transparent rebalance operation), with a user-data pointer equal to
X.I data.
A rebalance may or may not occur, depending on where the node is added
and what the rest of the tree looks like.
X.PP
X.I Tree_delete
deletes a node from
X.I tree.
A rebalance may or may not occur, depending on where the node is removed from
and what the rest of the tree looks like.
X.I Tree_delete
returns TRUE if a node was deleted, FALSE otherwise.
X.PP
X.I Tree_trav
traverses all of
X.I tree,
calling
X.I trav_uar
with the address of each user-data block.  If
X.I trav_uar
returns FALSE at any time,
X.I tree_trav
will immediately return FALSE to its caller.  Otherwise all nodes will be
reached and
X.I tree_trav
will return TRUE.
X.PP
X.I Tree_mung
deletes every node in
X.I tree,
calling
X.I del_uar
with the user-data address from each node (see
X.I tree_add
and
X.I tree_delete
above).  The tree is left in the same state that
X.I tree_init
leaves it in \- i.e., empty.
X.SH AUTHOR
Paul Vixie, converted and augumented from Modula-2 examples in
X.I Algorithms & Data Structures,
Niklaus Wirth, Prentice-Hall, ISBN 0-13-022005-1.
END_OF_FILE
if test 4082 -ne `wc -c <'tree.man3'`; then
    echo shar: \"'tree.man3'\" unpacked with wrong size!
fi
# end of 'tree.man3'
fi
if test -f 'vixie.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'vixie.h'\"
else
echo shar: Extracting \"'vixie.h'\" \(1555 characters\)
sed "s/^X//" >'vixie.h' <<'END_OF_FILE'
X/* vixie.h - include file to define general vixie-type things
X * v1.0 vix 21jun86 [broken out of as.h]
X */
X
X#ifdef    DOCUMENTATION
X
There are two macros you can define before including this file which can
change the things defined by this file.
X
DEBUG:    if defined, will cause enter/exit messages to be printed by the
X    ENTER/EXIT/EXITV macros.  If not defined, causes ENTER to do nothing,
X    and EXIT/EXITV to generate 'return' without any messages.
X
X    If defined, should be set to the name of the including module.
X
MAIN:    Should be defined for a program containing a main() function which
X    is linked with other modules which include this file.
X
X    Value is not important, only existence/nonexistence matters.
X
X#endif    /* DOCUMENTATION */
X
X
X#ifndef    _VIXIE_FLAG
X#define    _VIXIE_FLAG
X
X
X                        /*--- debugging stuff ---*/
X#define    MAXPROC    256
X
X#ifdef DEBUG
X#define    ENTER(proc) { \
X            APC_PROCS[I_PROC] = proc; \
X            printf("ENTER(%d:%s.%s)\n", \
X                I_PROC, DEBUG, APC_PROCS[I_PROC]); \
X            I_PROC++; \
X        }
X#define    EXIT(value) { \
X            I_PROC--; \
X            printf("EXIT(%d:%s.%s)\n", \
X                I_PROC, DEBUG, \
X                APC_PROCS[I_PROC]); \
X            return value; \
X        }
X#define    EXITV { \
X            I_PROC--; \
X            printf("EXITV(%d:%s.%s)\n", \
X                I_PROC, DEBUG, \
X                APC_PROCS[I_PROC]); \
X            return; \
X        }
X#else
X#define    ENTER(proc)
X#define    EXIT(value)    {return value;}
X#define    EXITV        return;
X#endif
X
X#ifdef MAIN
int    I_PROC = 0;
char    *APC_PROCS[MAXPROC];
X#else
extern    int    I_PROC;
extern    char    *APC_PROCS[MAXPROC];
X#endif
X
X
X#ifndef TRUE
X#define    TRUE        1
X#define    FALSE        0
X#endif
X
X
X#endif    /* _VIXIE_FLAG */
END_OF_FILE
if test 1555 -ne `wc -c <'vixie.h'`; then
    echo shar: \"'vixie.h'\" unpacked with wrong size!
fi
# end of 'vixie.h'
fi
echo shar: End of shell archive.
exit 0