rs@uunet.UU.NET (Rich Salz) (08/28/87)
Submitted-by: vixie!paul@uunet.UU.NET (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 rsalz@bbn.com Moderator, comp.sources.unix sources@uunet.uu.net