Newsgroups: comp.sources.unix From: paul@vix.com (Paul Vixie) Subject: v27i034: REPOST AVL Tree subroutines (replaces v11i020 from 1987), Part01/01 Message-id: <1.747348668.4037@gw.home.vix.com> Sender: unix-sources-moderator@gw.home.vix.com Approved: vixie@gw.home.vix.com Submitted-By: paul@vix.com (Paul Vixie) Posting-Number: Volume 27, Issue 34 Archive-Name: avl-subs/part01 [ There was a minor error in the previous posting; I'm going to cancel that article and repost this one. --vix ] This is the second release of this library. The first release was in 1987, as v11i020. There is at least one important bug fix here, as well as ANSI and POSIX support, so users of the old version should get this one. Folks who havn't used the old version can take a look at this excerpt from the man page... 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 indica- tor, 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 com- pare routine is used to compare user-data blocks. Balanced binary trees are very fast on searches and replacements, but have a moderately high cost for addi- tions 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. paul@vix.com (Paul Vixie) #! /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 'README' <<'END_OF_FILE' XAVL Trees V2.0 X5-September-1993 XPaul Vixie X XThere was a small bug in tree_delete() that manifested itself by corrupting Xtrees occasionally. It didn't show up in 1987 because I was using a micro- Xcomputer whose malloc() wasn't all that picky; on newer UNIX systems, malloc() Xand free() are extremely picky and if you misuse them, they will abuse you. X XI've taken the opportunity to convert the code to ANSI and POSIX. If you Xdon't have you will have some small porting work to do; most newer Xsystems have this (BSD/386, SYSV, Ultrix, OSF/1, OpenVMS, and so on) so you Xwill (statistically speaking) probably not have too much of a problem with Xthe changes. I conditionalized the ANSI'isms (function prototypes), so if Xyou don't have a fully ANSI compiler you should still be able to get this Xcode to compile. The one interface change I made was to change the external Xdefinition of the tree from "int *" to "void *"; had "void *" existed in X1987 I would have used it then. I changed the delete_uar from "pointer to Xfunction returning int" to "pointer to function returning void"; I don't Xknow why I used "int" back in 1987, those functions have never returned Xanything. X X-------- X 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 me 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_FILE if test 2481 -ne `wc -c <'README'`; then echo shar: \"'README'\" unpacked with wrong size! fi # end of 'README' 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'\" \(4084 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 Xtree_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 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 (or, on a RISC or otherwise Xalignment-constrained system with implied padding, 4+4+4+4 bytes per node). XThere is no key data type enforced by this package; a caller-supplied Xcompare routine is used to compare user-data blocks. X.PP XBalanced binary trees are very fast on searches and replacements, but have a Xmoderately high cost for additions and deletions. If your application does a Xlot more searches and replacements than it does additions and deletions, the Xbalanced (AVL) binary tree is a good choice for a data structure. 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 void or int, and passed by reference), which can then be used by Xother routines 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 value of the user-data pointer if the node Xwas found. 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 by 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 referenced 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 to X.I data. XA rebalance may or may not occur, depending on where the node is added Xand what the rest of the tree looks like. 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_FILE if test 4084 -ne `wc -c <'tree.man3'`; then echo shar: \"'tree.man3'\" unpacked with wrong size! fi # end of 'tree.man3' fi if test -f 'Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Makefile'\" else echo shar: Extracting \"'Makefile'\" \(841 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: Makefile,v 1.2 1993/09/06 20:44:57 vixie Exp $ X X#(choose a c compiler) XCC = gcc -Wall -Wtraditional -Wshadow -Wpointer-arith \ X -Wcast-align -Wwrite-strings -pedantic X#CC = cc X XCDEBUG = -g XCFLAGS = $(CDEBUG) $(CCFLAGS) XLDFLAGS = $(CDEBUG) X XTRTEST_OBJ = t_trtest.o tree.o X Xall : t_trtest tree.cat3 X Xt_trtest : $(TRTEST_OBJ) X $(CC) -o t_trtest $(TRTEST_OBJ) X Xtree.cat3 : tree.man3 X tbl tree.man3 | nroff -man > tree.cat3 X Xclean : FRC X rm -f *.o *~ *.CKP *.BAK X rm -f core a.out t_trtest tree.cat3 kit X Xkit : FRC X cshar -o kit \ X README tree.man3 Makefile \ X tree.c t_trtest.c tree.h vixie.h X XFRC : X Xtree.o : tree.c tree.h vixie.h Xt_trtest.o : t_trtest.c tree.h vixie.h END_OF_FILE if test 841 -ne `wc -c <'Makefile'`; then echo shar: \"'Makefile'\" unpacked with wrong size! fi # end of 'Makefile' 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'\" \(10702 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 Xstatic char RCSid[] = "$Id:"; X#endif X X X/*#define DEBUG "tree"*/ X X X#include X#include 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 Xstatic void sprout __P( (tree **, tree_t, int *, int (*)(), void (*)()) ); Xstatic int delete __P( (tree **, int (*)(), tree_t, void (*)(), X int *, int *) ); Xstatic void del __P( (tree **, int *, tree **, void (*)(), int *) ); Xstatic void bal_L __P( (tree **, int *) ); Xstatic void bal_R __P( (tree **, int *) ); X X Xvoid Xtree_init(ppr_tree) X tree **ppr_tree; X{ X ENTER("tree_init") X *ppr_tree = NULL; X EXITV X} X X Xtree_t Xtree_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 Xvoid Xtree_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 Xint Xtree_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 Xint Xtree_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 Xvoid Xtree_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 Xstatic void Xsprout(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 Xstatic int Xdelete(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 wuth@castrov.cuc.ab.ca */ X i_ret = TRUE; X } X EXIT(i_ret) X} X X Xstatic void Xdel(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 Xstatic void Xbal_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 Xstatic void Xbal_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 10702 -ne `wc -c <'tree.c'`; then echo shar: \"'tree.c'\" unpacked with wrong size! fi # end of 'tree.c' 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'\" \(2245 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 Xstatic char RCSid[] = "$Id:"; X#endif X X#define MAIN X X#include X#include X#include X#include "vixie.h" X#include "tree.h" X X Xstatic void trtest __P( (tree **, char *, int) ); Xstatic void tree_trav1 __P( (tree *, int) ); Xstatic int compar __P( (char *, char *) ); Xstatic void duar __P( (char *) ); Xstatic char *savestr __P( (char *) ); X X Xint Xmain() 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 Xstatic void Xtrtest(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 Xstatic void Xtree_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; itree_p, (char*)t->tree_p); X tree_trav1(t->tree_r, l+1); X} X Xstatic void Xduar(pc) X char *pc; X{ X printf("duar called, pc=%08X: <%s>\n", (unsigned)pc, pc?pc:""); X free(pc); X} X Xstatic int 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 Xstatic char * 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_FILE if test 2245 -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.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'tree.h'\" else echo shar: Extracting \"'tree.h'\" \(825 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: tree.h,v 1.2 1993/09/06 20:44:57 vixie Exp $ X */ X X X#ifndef _TREE_FLAG X#define _TREE_FLAG X X X#if defined(__STDC__) || defined(__GNUC__) Xtypedef void * tree_t; X#define __P(x) x X#else Xtypedef char * tree_t; X#define __P(x) () X#endif X X Xtypedef 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 Xvoid tree_init __P( (tree **) ); Xtree_t tree_srch __P( (tree **, int (*)(), tree_t) ); Xvoid tree_add __P( (tree **, int (*)(), tree_t, void (*)()) ); Xint tree_delete __P( (tree **, int (*)(), tree_t, void (*)()) ); Xint tree_trav __P( (tree **, int (*)()) ); Xvoid tree_mung __P( (tree **, void (*)()) ); X X X#endif /* _TREE_FLAG */ END_OF_FILE if test 825 -ne `wc -c <'tree.h'`; then echo shar: \"'tree.h'\" unpacked with wrong size! fi # end of 'tree.h' 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 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; \ 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#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