Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume11/avl-subs

Text File | 1987-08-27 | 23.5 KB | 1,012 lines

Path: uunet!rs
From: [e-mail] (Rich Salz)
Newsgroups: comp.sources.unix
Subject: v11i020:  AVL Tree subroutines
Message-ID: <[e-mail]>
Date: 28 Aug 87 13:00:46 GMT
Organization: UUNET Communications Services, Arlington, VA
Lines: 1001
Approved: [e-mail]

Submitted-by: vixie![e-mail] (Paul Vixie Esq)
Posting-number: Volume 11, Issue 20
Archive-name: avl-subs

Here's an AVL tree library, written in C.  Someone asked about it on
comp.sources.wanted; I'll send him a copy too, but I think it's of
general utility, so I'd like to see it in comp.sources.unix.  It's known
to run on my Symmetric, and on a Macintosh (!) with the DeSmet C Compiler.

I extracted it from a PD assembler I was writing a year or so back, so
it makes some references to "as" in some comments... Please ignore these...

#! /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".  If this archive is complete, you will
##  see the following message at the end:
#        "End of shell archive."
# Contents:  Makefile README t_trtest.c tree.c tree.h tree.man3 vixie.h
# Wrapped by paul@vixie on Fri Jul 24 10:35:46 1987
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f Makefile -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"Makefile\"
else
echo shar: Extracting \"Makefile\" \(331 characters\)
sed "s/^X//" >Makefile <<'END_OF_Makefile'
X# makefile for tree stuff
X# vix 24jul87 [stripped down from as makefile]
X
XCFLAGS        =    -O
X
XTRTEST_OBJ    =    t_trtest.o tree.o
X
Xall        :    t_trtest
X
Xt_trtest    :    $(TRTEST_OBJ)
X            cc -o t_trtest $(TRTEST_OBJ)
X
Xclean        :    FRC
X            rm -f core a.out t_trtest $(TRTEST_OBJ)
X
XFRC        :
X
Xtree.o        :    tree.c tree.h vixie.h
Xt_trtest.o    :    t_trtest.c tree.h vixie.h
END_OF_Makefile
if test 331 -ne `wc -c <Makefile`; then
    echo shar: \"Makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f README -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"README\"
else
echo shar: Extracting \"README\" \(1286 characters\)
sed "s/^X//" >README <<'END_OF_README'
XAVL Trees V1.0
X24-July-1987
XPaul Vixie
X
XThis library and test program are useful for creating and using balanced
Xbinary trees (AVL trees).  The tree is held in memory, using malloc(3) to
Xallocate storage.  A better version would allow file-based trees in
Xaddition; once memory mapped files hit the UNIX(tm) community, this will
Xbe much easier to do.  In the meanwhile, these routines have been very
Xuseful to be for symbol tables and the like.  (Yes, I'm sure hashing is
Xbetter in some way, but I've used this for symbol tables, just the same.)
X
XI cannot take credit for the algorithms.  See "Algorithms & Data Structures,"
XNiklaus Wirth, Prentice-Hall 1986, ISBN 0-13-022005-1.  This is an update of
XWirth's previous book, titled "Algorythms + Data Structures = Programs,"
Xwhich used Pascal as the language for examples.  This later book uses the
Xnewer Modula-2 for it's examples; this tree code was created using the
XModula-2 examples as guidelines.  At the time I typed this stuff in (about
Xa year ago, in July 1987), I understood how it all worked.  Today, well...
X
XThis code is hereby placed in the public domain, unless restrictions apply
Xfrom Prentice-Hall on the algorithms themselves.  If you use or redistribute
Xthis code, please leave my name (and Wirth's) in the comments.
END_OF_README
if test 1286 -ne `wc -c <README`; then
    echo shar: \"README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f t_trtest.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"t_trtest.c\"
else
echo shar: Extracting \"t_trtest.c\" \(1912 characters\)
sed "s/^X//" >t_trtest.c <<'END_OF_t_trtest.c'
X/* t_trtest - test the tree functions
X * vix 24jul87 [documented, added savestr for net distribution]
X */
X
X#define MAIN
X
X#include <stdio.h>
X#include "vixie.h"
X#include "tree.h"
X
Xmain()
X{
X    tree    *t;
X    char    line[100];
X
X    tree_init(&t);
X    while (printf("line (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}
X
Xtrtest(tt, line, inter)
Xtree    **tt;
Xchar    *line;
X{
X    char    opts[100], *tree_srch(), *pc, *n;
X    int    uar_print(), duar(), compar(), opt, status;
X
X    pc = tree_srch(tt, compar, line);
X    printf("tree_srch=%08lx\n", 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
Xduar(pc)
Xchar *pc;
X{
X    printf("duar called, pc=%08X: <%s>\n", pc, pc?pc:"");
X    free(pc);
X}
X
Xtree_trav1(t, l)
Xtree    *t;
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", t->tree_p, t->tree_p);
X    tree_trav1(t->tree_r, l+1);
X}
X
Xuar_print(pc)
Xchar    *pc;
X{
X    printf("uar_print(%08lx)", pc);
X    if (pc)
X        printf(" '%s'", pc);
X    putchar('\n');
X    return 1;
X}
X
Xcompar(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
Xchar *
Xsavestr(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_t_trtest.c
if test 1912 -ne `wc -c <t_trtest.c`; then
    echo shar: \"t_trtest.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f tree.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"tree.c\"
else
echo shar: Extracting \"tree.c\" \(10313 characters\)
sed "s/^X//" >tree.c <<'END_OF_tree.c'
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 */
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/*#define        DEBUG    "tree"*/
X
X
X#include <stdio.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
Xvoid tree_init(ppr_tree)
Xtree    **ppr_tree;
X{
X    ENTER("tree_init")
X    *ppr_tree = NULL;
X    EXITV
X}
X
X
Xchar *tree_srch(ppr_tree, pfi_compare, pc_user)
Xtree    **ppr_tree;
Xint    (*pfi_compare)();
Xchar    *pc_user;
X{
X    register int    i_comp;
X    register tree    *pr_new;
X
X    ENTER("tree_srch")
X
X    if (*ppr_tree)
X    {
X        i_comp = (*pfi_compare)(pc_user, (**ppr_tree).tree_p);
X        if (i_comp > 0)
X            EXIT(tree_srch(
X                &(**ppr_tree).tree_r,
X                pfi_compare,
X                pc_user
X            ))
X        if (i_comp < 0)
X            EXIT(tree_srch(
X                &(**ppr_tree).tree_l,
X                pfi_compare,
X                pc_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
Xvoid tree_add(ppr_tree, pfi_compare, pc_user, pfi_delete)
Xtree    **ppr_tree;
Xint    (*pfi_compare)();
Xchar    *pc_user;
Xint    (*pfi_delete)();
X{
X    void    sprout();
X    int    i_balance = FALSE;
X
X    ENTER("tree_add")
X    sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete);
X    EXITV
X}
X
X
Xstatic void sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete)
Xtree    **ppr;
Xchar    *pc_data;
Xint    *pi_balance;
Xint    (*pfi_compare)();
Xint    (*pfi_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 = pc_data;
X        *pi_balance = TRUE;
X        EXITV
X    }
X
X    /* compare the data using routine passed by caller.
X     */
X    cmp = (*pfi_compare)(pc_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, pc_data, pi_balance,
X            pfi_compare, pfi_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, pc_data, pi_balance,
X            pfi_compare, pfi_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 (pfi_delete)
X        (*pfi_delete)((*ppr)->tree_p);
X    (*ppr)->tree_p = pc_data;
X    EXITV
X}
X
X
Xint tree_delete(ppr_p, pfi_compare, pc_user, pfi_uar)
Xtree    **ppr_p;
Xint    (*pfi_compare)();
Xchar    *pc_user;
Xint    (*pfi_uar)();
X{
X    int    i_balance = FALSE, i_uar_called = FALSE;
X
X    ENTER("tree_delete");
X    EXIT(delete(ppr_p, pfi_compare, pc_user, pfi_uar,
X                &i_balance, &i_uar_called))
X}
X
X
Xstatic int delete(ppr_p, pfi_compare, pc_user, pfi_uar,
X                        pi_balance, pi_uar_called)
Xtree    **ppr_p;
Xint    (*pfi_compare)();
Xchar    *pc_user;
Xint    (*pfi_uar)();
Xint    *pi_balance;
Xint    *pi_uar_called;
X{
X    void    del(), balanceL(), balanceR();
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, pc_user);
X    if (i_comp > 0) {
X        MSG("too high - scan left")
X        i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar,
X                        pi_balance, pi_uar_called);
X        if (*pi_balance)
X            balanceL(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, pc_user, pfi_uar,
X                        pi_balance, pi_uar_called);
X        if (*pi_balance)
X            balanceR(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, pfi_uar,
X                                pi_uar_called);
X            if (*pi_balance)
X                balanceL(ppr_p, pi_balance);
X        }
X        free(pr_q);
X        if (!*pi_uar_called && *pfi_uar)
X            (*pfi_uar)(pr_q->tree_p);
X        i_ret = TRUE;
X    }
X    EXIT(i_ret)
X}
X
X
Xstatic void del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called)
Xtree    **ppr_r;
Xint    *pi_balance;
Xtree    **ppr_q;
Xint    (*pfi_uar)();
Xint    *pi_uar_called;
X{
X    void    balanceR();
X
X    ENTER("del")
X
X    if ((*ppr_r)->tree_r != NULL) {
X        del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar,
X                                pi_uar_called);
X        if (*pi_balance)
X            balanceR(ppr_r, pi_balance);
X    } else {
X        if (pfi_uar)
X            (*pfi_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
Xstatic void balanceL(ppr_p, pi_balance)
Xtree    **ppr_p;
Xint    *pi_balance;
X{
X    tree    *p1, *p2;
X    int    b1, b2;
X
X    ENTER("balanceL")
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
Xstatic void balanceR(ppr_p, pi_balance)
Xtree    **ppr_p;
Xint    *pi_balance;
X{
X    tree    *p1, *p2;
X    int    b1, b2;
X
X    ENTER("balanceR")
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}
X
X
Xint tree_trav(ppr_tree, pfi_uar)
Xtree    **ppr_tree;
Xint    (*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
Xvoid tree_mung(ppr_tree, pfi_uar)
Xtree    **ppr_tree;
Xint    (*pfi_uar)();
X{
X    ENTER("tree_mung")
X    if (*ppr_tree)
X    {
X        tree_mung(&(**ppr_tree).tree_l, pfi_uar);
X        tree_mung(&(**ppr_tree).tree_r, pfi_uar);
X        if (pfi_uar)
X            (*pfi_uar)((**ppr_tree).tree_p);
X        free(*ppr_tree);
X        *ppr_tree = NULL;
X    }
X    EXITV
X}
END_OF_tree.c
if test 10313 -ne `wc -c <tree.c`; then
    echo shar: \"tree.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f tree.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"tree.h\"
else
echo shar: Extracting \"tree.h\" \(253 characters\)
sed "s/^X//" >tree.h <<'END_OF_tree.h'
X/* tree.h - declare structures used by tree.c
X * vix 27jun86 [broken out of tree.c]
X */
X
X
X#ifndef    _TREE_FLAG
X#define    _TREE_FLAG
X
X
Xtypedef    struct    tree_s
X    {
X        struct    tree_s    *tree_l, *tree_r;
X        short        tree_b;
X        char        *tree_p;
X    }
X    tree;
X
X
X#endif    _TREE_FLAG
END_OF_tree.h
if test 253 -ne `wc -c <tree.h`; then
    echo shar: \"tree.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f tree.man3 -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"tree.man3\"
else
echo shar: Extracting \"tree.man3\" \(3448 characters\)
sed "s/^X//" >tree.man3 <<'END_OF_tree.man3'
X.TH TREE 2 "23 June 1986"
X.UC 4
X.SH NAME
Xtree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav \- balanced binary tree routines
X.SH SYNOPSIS
X.nf
X.B void
X.B tree_init(tree)
X.B int **tree;
X.PP
X.B int *
X.B tree_srch(tree, compare, data)
X.B int **tree, (*compare)(), *data;
X.PP
X.B void
X.B tree_add(tree, compare, data, del_uar)
X.B int **tree, (*compare)(), *data, (*del_uar)();
X.PP
X.B int
X.B tree_delete(tree, compare, data, del_uar)
X.B int **tree, (*compare)(), *data, (*del_uar)();
X.PP
X.B int
X.B tree_trav(tree, trav_uar)
X.B int **tree, (*trav_uar)();
X.PP
X.B void
X.B tree_mung(tree, del_uar)
X.B int **tree, (*del_uar)();
X.fi
X.SH DESCRIPTION
XThese functions create and manipulate a balanced binary (AVL) tree.  Each node
Xof the tree contains the expected left & right subtree pointers, a short-int
Xbalance indicator, and a pointer to the user-data.  On a 32-bit system, this
Xmeans an overhead of 4+4+2+4 bytes per node.  There is no key data type
Xenforced by this package; a caller-supplied compare routine is used to compare
Xuser-data blocks.
X.PP
X.I Tree_init
Xcreates 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
Xa pointer to integer and passed by reference), which can then be used by other
Xroutines in this package.  Note that more than one
X.I tree
Xvariable can exist at once; thus multiple trees can be manipulated
Xsimultaneously.
X.PP
X.I Tree_srch
Xsearches a tree for a specific node and returns either
X.I NULL
Xif no node was found, or the address of the user-data for that node if one was
Xfound.
X.I compare
Xis the address of a function to compare two user-data blocks.  This routine
Xshould work much the way
X.IR strcmp 2
Xdoes; in fact,
X.I strcmp
Xcould be used if the user-data was a null-terminated string.
X.I data
Xis the address of a user-data block to be used via
X.I compare
Xas the search criteria.  The tree is searched for a node where
X.I compare
Xreturns 0.
X.PP
X.I Tree_add
Xinserts or replaces a node in the specified tree.  The tree specified by
X.I tree
Xis searched as in
X.I tree_srch,
Xand if a node is found to match
X.I data,
Xthen the
X.I del_uar
Xfunction is called with the address of the user-data block for the node
X(this routine should deallocate any dynamic memory which is pointed to
Xexclusively by the node); the user-data pointer for the node is then
Xreplaced by the value of
X.I data.
XIf no node is found to match, a new node is added (which may or may not
Xcause a transparent rebalance operation), with a user-data pointer equal
Xto
X.I data.
X.PP
X.I Tree_delete
Xdeletes a node from
X.I tree.
XA rebalance may or may not occur, depending on where the node is removed from
Xand what the rest of the tree looks like.
X.I Tree_delete
Xreturns TRUE if a node was deleted, FALSE otherwise.
X.PP
X.I Tree_trav
Xtraverses all of
X.I tree,
Xcalling
X.I trav_uar
Xwith the address of each user-data block.  If
X.I trav_uar
Xreturns FALSE at any time,
X.I tree_trav
Xwill immediately return FALSE to its caller.  Otherwise all nodes will be
Xreached and
X.I tree_trav
Xwill return TRUE.
X.PP
X.I Tree_mung
Xdeletes every node in
X.I tree,
Xcalling
X.I del_uar
Xwith the user-data address from each node (see
X.I tree_add
Xand
X.I tree_delete
Xabove).  The tree is left in the same state that
X.I tree_init
Xleaves it in \- i.e., empty.
X.SH AUTHOR
XPaul Vixie, converted and augumented from Modula-2 examples in
X.I Algorithms & Data Structures,
XNiklaus Wirth, Prentice-Hall, ISBN 0-13-022005-1.
END_OF_tree.man3
if test 3448 -ne `wc -c <tree.man3`; then
    echo shar: \"tree.man3\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f vixie.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"vixie.h\"
else
echo shar: Extracting \"vixie.h\" \(1618 characters\)
sed "s/^X//" >vixie.h <<'END_OF_vixie.h'
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
XThere are two macros you can define before including this file which can
Xchange the things defined by this file.
X
XDEBUG:    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
XMAIN:    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 value; \
X        }
X#else
X#define    ENTER(proc)
X#define    EXIT(value)    {return value;}
X#define    EXITV        return;
X#endif
X
X#ifdef MAIN
Xint    I_PROC = 0;
Xchar    *APC_PROCS[MAXPROC];
X#else
Xextern    int    I_PROC;
Xextern    char    *APC_PROCS[MAXPROC];
X#endif
X
X
X            /*--- why didn't k&r put these into stdio.h? ---*/
X#define    TRUE        1
X#define    FALSE        0
Xextern    char        *malloc(), *calloc();
X
X
X#endif    _VIXIE_FLAG
END_OF_vixie.h
if test 1618 -ne `wc -c <vixie.h`; then
    echo shar: \"vixie.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0
--

Rich $alz
Cronus Project, BBN Labs            [e-mail]
Moderator, comp.sources.unix            [e-mail]