AVL tree library (part 2 of 2)
Brad Appleton
brad at SSD.CSD.HARRIS.COM
Fri Mar 29 06:40:27 AEST 1991
In article <2821 at travis.csd.harris.com> brad at SSD.CSD.HARRIS.COM (Brad Appleton) writes:
This is a Beta release of part 2 of an AVL tree library that I have been
using on and off for a few years. Please report any bugs ASAP to me at
brad at ssd.csd.harris.com
#! /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 archive 2 (of 2)."
# Contents: LICENSE avl.3 avl.c testvals.old
# Wrapped by brad at hcx2 on Thu Mar 28 15:32:56 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'LICENSE' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'LICENSE'\"
else
echo shar: Extracting \"'LICENSE'\" \(3563 characters\)
sed "s/^X//" >'LICENSE' <<'END_OF_FILE'
X_______________________________________________________________________________
X
X LICENSE
X =======
X
XThis software is not subject to any license of the American Telephone and
XTelegraph Company or of the Regents of the University of California.
X
XPermission is granted to anyone to use this software for any purpose on any
Xcomputer system, and to alter it and redistribute it freely, subject to the
Xfollowing restrictions:
X
X 1. Neither the authors of the software nor their employers
X (including any of the employers' subsidiaries and subdivisions)
X are responsible for maintaining & supporting this software or
X for any consequences resulting from the use of this software, no
X matter how awful, even if they arise from flaws in the software
X (see LIABILITY).
X
X 2. The origin of this software must not be misrepresented, either
X by explicit claim or by omission. Since few users ever read
X sources, credits must appear in the documentation.
X
X 3. Altered versions must be plainly marked as such, and must not be
X misrepresented as being the original software. Since few users
X ever read sources, credits must appear in the documentation.
X
X 4. This notice may not be removed or altered.
X_______________________________________________________________________________
X
X NO WARRANTY
X ===========
X
XBecause this software is licensed free of charge, we (the authors and/or
Xdistributors of this software) provide absolutely no warranty, to the extent
Xpermitted by applicable state law. Except when otherwise stated in writing,
Xthe authors and distributors of this software and/or other parties provide
Xthis program "as is" without warranty of any kind, either expressed or
Ximplied, including, but not limited to, the implied warranties of
Xmerchantability and fitness for a particular purpose. The entire risk as to
Xthe quality and performance of this software lies with the recipients and/or
Xusers of this software and not with any of the authors and/or distributors of
Xthis software, nor with any of their employers, including any of the
Xemployers' subsidiaries and subdivisions. Should the program prove defective,
Xthe recipients/users of this software assume the cost of all necessary
Xservicing, repair, or correction.
X_______________________________________________________________________________
X
X LIABILITY
X =========
X
XIn no event unless required by applicable law will the authors and/or
Xdistributors of this software, their employers, and any subsidiaries and/or
Xsubdivisions of their employers, and/or any other party who may redistribute
Xthis software as permitted in the LICENSE section of this notice, be liable to
Xthe recipients/users of this software for damages including any lost profits,
Xlost monies, or other special, incidental, or consequential damages arising
Xout of the use or inabilty to use (including but not limited to loss of data
Xor data being rendered inaccurate or lossed sustained by third parties or a
Xfailure of the software to operate with any other software or hardware) this
Xsoftware, even if you have been advised of the possibility of such damages, or
Xfor any claim by any other party.
X_______________________________________________________________________________
X
END_OF_FILE
if test 3563 -ne `wc -c <'LICENSE'`; then
echo shar: \"'LICENSE'\" unpacked with wrong size!
fi
# end of 'LICENSE'
fi
if test -f 'avl.3' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'avl.3'\"
else
echo shar: Extracting \"'avl.3'\" \(4005 characters\)
sed "s/^X//" >'avl.3' <<'END_OF_FILE'
X.TH AVL 3 "28 March 1991"
X.SH NAME
Xavl \- library for creating and manipulating AVL trees.
X.SH SYNOPSIS
X.nf
X#include <avl.h>
X
XAVL_TREE avlinit( int(*icmp)(), unsigned(*isize)() );
Xvoid avldispose( AVL_TREE *tree, void(*ifree)(), SIBLING_ORDER sib_ord );
Xvoid avlfree( AVL_TREE tree )
Xvoid avlwalk( AVL_TREE tree, void(*action)(), SIBLING_ORDER sib_ord );
Xint avlcount( AVL_TREE tree );
Xvoid *avlins( void *item, AVL_TREE tree );
Xvoid *avldel( void *item, AVL_TREE tree );
Xvoid *avlfind( void *item, AVL_TREE tree );
Xvoid *avldelmin( AVL_TREE tree );
Xvoid *avlfindmin( AVL_TREE tree );
Xvoid *avldelmax( AVL_TREE tree );
Xvoid *avlfindmax( AVL_TREE tree );
X.fi
X
X.SH DESCRIPTION
XThe functions above provide a library package for creating and manipulating
Xgeneric avl-trees.
X.PP
X.I Avlinit
Xtakes an item compare function (which returns a \fIstrcmp\fP-type result),
Xand a size function (which returns the size of an item), and returns the
Xroot of an empty AVL tree for the corresponding item-type.
X.PP
X.I Avldispose
Xwill walk through a tree, applying the function \fIifree\fP (which should be
Xsome type of item-deallocation function) to the item in each node, and then
Xdeallocates space for the given node. The parameter \fIorder\fP should be
Xone of \fILEFT_TO_RIGHT\fP or \fIRIGHT_TO_LEFT\fP.
Xof each node
X.PP
X.I Avlfree
Xis a macro which expands to
X"\f4avldispose( &tree, free, LEFT_TO_RIGHT )\fP".
X.PP
X.I Avlwalk
Xwill traverse each item in the tree in the specified sibling order and apply
Xthe function \fIaction\fP each time it encounters a node. Each non-empty
Xnode will be encountered three times (corresponding to the three different
Xtypes of tree traversal: preorder, inorder, and postorder). The declaration
Xfor \fIaction\fP should be the following:
X
X.RS
X.nf
X.ft 4
Xvoid action( void *dataptr, VISIT order, NODE node, int level, short bal );
X.ft R
X.fi
X
X.I Dataptr
Xis the pointer to the data item contained in the current node.
X.sp 8p
X.I Order
Xwill be one of
X.I PREORDER,
X.I INORDER,
Xor
X.I POSTORDER
Xdepending upon whether this is the first, second, or third time
X(respectively) that the current node has been visited by \fIavlwalk\fP.
X.sp 8p
X.I Node
Xwill be one of
X.I IS_TREE,
X.I IS_LBRANCH,
X.I IS_RBRANCH,
X.I IS_LEAF,
Xor
X.I IS_NULL
Xdepending upon whether the current node has two non-null children,
Xone non-null child in the left-subtree, one non-null child in the
Xright-subtree, two null children, or a null node (respectively).
X.sp 8p
X.I Level
Xwill be the current depth of the tree (with the root being level zero)
Xthat the current node corresponds to.
X.sp 8p
X.I Bal
Xwill be the balance factor for the current node (which should range
Xfrom -1 .. 1).
X.RE
X
X.PP
X.I Avlcount
Xwill return the number of items currently contained in the given AVL tree.
X.PP
X.I Avldel
Xwill remove the node containing the given item from the given AVL tree and
Xwill return a pointer to the data-item of the deleted node (or NULL if the
Xitem was not found in the tree).
X.PP
X.I Avlins
Xwill insert a node containing the given data item into the given AVL tree
Xand will return NULL (unless the item is already in the tree, in which case
Xthe address of the located data item is returned).
X.PP
X.I Avlfind
Xwill search for the node containing in the given tree which conatins the given
Xdata item. If found the address of the data item is returned, otherwise NULL
Xis returned.
X.PP
X.I Avldelmin
Xwill remove the "smallest" item (according the the compare function passed
Xto \fIavlinit\fP) from the given tree and return the address of the item
Xthat was removed.
X.PP
X.I Avlfindmin
Xwill return the address of the "smallest" data item in the tree.
X.PP
X.I Avldelmax
Xwill remove the "largest" item (according the the compare function passed
Xto \fIavlinit\fP) from the given tree and return the address of the item
Xthat was removed.
X.PP
X.I Avlfindmax
Xwill return the address of the "largest" data item in the tree.
X
X.SH AUTHOR
X.nf
XBrad Appleton <brad at ssd.csd.Harris.COM>
XHarris Computer Systems, Fort Lauderdale, FL USA
X.fi
END_OF_FILE
if test 4005 -ne `wc -c <'avl.3'`; then
echo shar: \"'avl.3'\" unpacked with wrong size!
fi
# end of 'avl.3'
fi
if test -f 'avl.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'avl.c'\"
else
echo shar: Extracting \"'avl.c'\" \(24464 characters\)
sed "s/^X//" >'avl.c' <<'END_OF_FILE'
X/**
X*
X* avl.c -- C source file for avl trees. Contains the auxillary routines
X* and defines for the avl tree functions and user interface and
X* includes all the necessary public and private routines
X*
X* Created 03/01/89 by Brad Appleton
X*
X* ^{Mods:* }
X*
X* Fri Jul 14 13:53:42 1989, Rev 1.0, brad(0165)
X*
X**/
X
X /* some common #defines used throughout most of my files */
X#define PUBLIC /* default */
X#define PRIVATE static
X#define FALSE 0
X#define TRUE !FALSE
X
X /* some defines for debugging purposes */
X#ifdef NDEBUG
X#define DBG(x) /* x */
X#else
X#define DBG(x) x
X#endif
X
X#define NEXTERN /* dont include "extern" declarations from header files */
X
X#include <stdio.h>
X#include "avl.h" /* public types for avl trees */
X#include "avl_typs.h" /* private types for avl trees */
X
X
X
X/************************************************************************
X* Auxillary functions
X*
X* routines to allocate/de-allocate an AVL node,
X* and determine the type of an AVL node.
X************************************************************************/
X
X/* ckalloc( size ) -- allocate space; check for success */
XPRIVATE char *ckalloc( size )
Xint size;
X{
X char *malloc(), *ptr;
X
X if ( (ptr = malloc( (unsigned) size)) == NULL ) {
X fprintf( stderr, "Unable to allocate storage." );
X exit( 1 );
X }/* if */
X
X return ptr;
X}/* ckalloc */
X
X
X/*
X* new_node() -- get space for a new node and its data;
X* return the address of the new node
X*/
XPRIVATE AVLtree new_node( data, size )
Xvoid *data;
Xunsigned size;
X{
X AVLtree root;
X
X root = (AVLtree) ckalloc( sizeof (AVLnode) );
X root -> data = (void *) ckalloc( size );
X memcpy( root -> data, data, size );
X root -> bal = BALANCED;
X root -> subtree[ LEFT ] = root -> subtree[ RIGHT ] = NULL_TREE;
X
X return root;
X}/* new_node */
X
X
X/*
X* free_node() -- free space for a node and its data!
X* reset the node pointer to NULL
X*/
XPRIVATE void free_node( rootp )
XAVLtree *rootp;
X{
X free( (void *) *rootp );
X *rootp = NULL_TREE;
X}/* free_node */
X
X
X/*
X* node_type() -- determine the number of null pointers for a given
X* node in an AVL tree, Returns a value of type NODE
X* which is an enumeration type with the following values:
X*
X* IS_TREE -- both subtrees are non-empty
X* IS_LBRANCH -- left subtree is non-empty; right is empty
X* IS_RBRANCH -- right subtree is non-empty; left is empty
X* IS_LEAF -- both subtrees are empty
X* IS_NULL -- given tree is empty
X*/
XPRIVATE NODE node_type( tree )
XAVLtree tree;
X{
X if ( tree == NULL_TREE )
X return IS_NULL;
X
X else if ( (tree -> subtree[ LEFT ] != NULL_TREE) && (tree -> subtree[ RIGHT ] != NULL_TREE) )
X return IS_TREE;
X
X else if ( tree -> subtree[ LEFT ] != NULL_TREE )
X return IS_LBRANCH;
X
X else if ( tree -> subtree[ RIGHT ] != NULL_TREE )
X return IS_RBRANCH;
X
X else
X return IS_LEAF;
X}/* node_type */
X
X
X
X/************************************************************************
X* PRIVATE functions for manipulating AVL trees
X*
X* This following defines a set of routines for creating, maintaining, and
X* manipulating AVL Trees as an Abtract Data Type. The routines in this
X* file that are accessible (through the avl tree user-interface) to other
X* files to allow other programmers to:
X*
X* Insert, Delete, and Find a given data item from a Tree.
X*
X* Delete and Find the minimal and Maximal items in a Tree.
X*
X* Walk through every node in a tree performing a giving operation.
X*
X* Walk through and free up space for every node in a tree while performing
X* a given operation on the data items as they are encountered.
X************************************************************************/
X
X
X
X/************************************************************************
X* routines used to find the minimal and maximal elements
X* (nodes) of an AVL tree.
X************************************************************************/
X
X/*
X* avl_min() -- compare function used to find the minimal element in a tree
X*/
XPRIVATE int avl_min( elt1, elt2, nd_typ )
Xvoid *elt1, *elt2;
XNODE nd_typ;
X{
X if ( nd_typ == IS_RBRANCH || nd_typ == IS_LEAF )
X return 0; /* left subtree is empty -- this is the minimum */
X
X else return -1; /* keep going left */
X}/* avl_min */
X
X
X/*
X* avl_max() -- compare function used to find the maximal element in a tree
X*/
XPRIVATE int avl_max( elt1, elt2, nd_typ )
Xvoid *elt1, *elt2;
XNODE nd_typ;
X{
X if ( nd_typ == IS_RBRANCH || nd_typ == IS_LEAF )
X return 0; /* right subtree is empty -- this is the maximum */
X
X else return 1; /* keep going right */
X}/* avl_max */
X
X
X
X/************************************************************************
X* Routines to perform rotations on AVL trees
X************************************************************************/
X
X/*
X* rotate_once() -- rotate a given node in the given direction
X* to restore the balance of a tree
X*/
XPRIVATE short rotate_once( rootp, dir )
XAVLtree *rootp;
XDIRECTION dir;
X{
X DIRECTION other_dir = OPPOSITE( dir ); /* opposite direction to "dir" */
X AVLtree old_root = *rootp; /* copy of original root of tree */
X short ht_unchanged; /* true if height unchanged */
X
X ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE;
X
X /* assign new root */
X *rootp = old_root -> subtree[ other_dir ];
X
X /* new-root exchanges it's "dir" subtree for it's parent */
X old_root -> subtree[ other_dir ] = (*rootp) -> subtree[ dir ];
X (*rootp) -> subtree[ dir ] = old_root;
X
X /* update balances */
X old_root -> bal = -( dir == LEFT ? --( (*rootp) -> bal ) : ++( (*rootp) -> bal ) );
X
X return ht_unchanged;
X}/* rotate_once */
X
X
X/*
X* rotate_twice() -- rotate a given node in the given direction
X* and then in the opposite direction
X* to restore the balance of a tree
X*/
XPRIVATE void rotate_twice( rootp, dir )
XAVLtree *rootp;
XDIRECTION dir;
X{
X DIRECTION other_dir = OPPOSITE( dir );
X AVLtree old_root = *rootp,
X old_other_dir_subtree = (*rootp) -> subtree[ other_dir ];
X
X /* assign new root */
X *rootp = old_root -> subtree[ other_dir ] -> subtree[ dir ];
X
X /* new-root exchanges it's "dir" subtree for it's grandparent */
X old_root -> subtree[ other_dir ] = (*rootp) -> subtree[ dir ];
X (*rootp) -> subtree[ dir ] = old_root;
X
X /* new-root exchanges it's "other-dir" subtree for it's parent */
X old_other_dir_subtree -> subtree[ dir ] = (*rootp) -> subtree[ other_dir ];
X (*rootp) -> subtree[ other_dir ] = old_other_dir_subtree;
X
X /* update balances */
X (*rootp) -> subtree[ LEFT ] -> bal = -MAX( (*rootp) -> bal, 0 );
X (*rootp) -> subtree[ RIGHT ] -> bal = -MIN( (*rootp) -> bal, 0 );
X (*rootp) -> bal = 0;
X
X}/* rotate_twice */
X
X
X/************************************************************************
X* Rebalance an AVL tree
X************************************************************************/
X
X/*
X* balance() -- determines and performs the sequence of rotations needed
X* (if any) to restore the balance of a given tree.
X*
X* Returns 1 if tree height changed due to rotation; 0 otherwise
X*/
XPRIVATE short balance( rootp )
XAVLtree *rootp;
X{
X short special_case = FALSE;
X
X if ( LEFT_IMBALANCE( *rootp ) ) { /* need a right rotation */
X if ( (*rootp) -> subtree[ LEFT ] -> bal == RIGHT_HEAVY )
X rotate_twice( rootp, RIGHT ); /* double RL rotation needed */
X
X else /* single RR rotation needed */
X special_case = rotate_once( rootp, RIGHT );
X }/* if */
X
X else if ( RIGHT_IMBALANCE( *rootp ) ) { /* need a left rotation */
X if ( (*rootp) -> subtree[ RIGHT ] -> bal == LEFT_HEAVY )
X rotate_twice( rootp, LEFT ); /* double LR rotation needed */
X
X else /* single LL rotation needed */
X special_case = rotate_once( rootp, LEFT );
X }/* elif */
X
X else return HEIGHT_UNCHANGED; /* no rotation occurred */
X
X return ( special_case ) ? HEIGHT_UNCHANGED : HEIGHT_CHANGED;
X}/* balance */
X
X
X/************************************************************************
X* Routines to: Find an item in an AVL tree
X* Insert an item into an AVL tree
X* Delete an item from an AVL tree
X************************************************************************/
X
X/*
X* avl_find() -- find an item in the given tree
X*
X* PARAMETERS:
X* data -- a pointer to the key to find
X* rootp -- a pointer to an AVL tree
X* compar -- name of a function to compare 2 data items
X*/
XPRIVATE void *avl_find( data, tree, compar )
Xvoid *data;
XAVLtree tree;
Xint (*compar)();
X{
X NODE nd_typ = node_type( tree );
X int cmp;
X
X while ( (cmp = (*compar)( data, tree -> data, nd_typ )) &&
X (tree != NULL_TREE) )
X tree = tree -> subtree[ (cmp < 0) ? LEFT : RIGHT ];
X
X return ( tree == NULL_TREE ) ? NULL : tree -> data;
X}/* avl_find */
X
X
X/*
X* avl_insert() -- insert an item into the given tree
X*
X* PARAMETERS:
X* data -- a pointer to a pointer to the data to add;
X* On exit, *data is NULL if insertion succeeded,
X* otherwise address of the duplicate key
X* rootp -- a pointer to an AVL tree
X* compar -- name of the function to compare 2 data items
X*/
XPRIVATE short avl_insert( data, size, rootp, compar )
Xvoid **data;
Xunsigned size;
XAVLtree *rootp;
Xint (*compar)();
X{
X short increase;
X int cmp;
X
X if ( *rootp == NULL_TREE ) { /* insert new node here */
X *rootp = new_node( *data, size );
X *data = NULL; /* set return value in data */
X return HEIGHT_CHANGED;
X }/* if */
X
X cmp = (*compar)( *data, (*rootp) -> data ); /* compare data items */
X
X if ( cmp < 0 ) { /* insert into the left subtree */
X increase = -avl_insert( data, size, &( (*rootp) -> subtree[ LEFT ] ), compar );
X if ( *data != NULL ) return HEIGHT_UNCHANGED;
X }/* elif */
X
X else if ( cmp > 0 ) { /* insert into the right subtree */
X increase = avl_insert( data, size, &( (*rootp) -> subtree[ RIGHT ] ), compar );
X if ( *data != NULL ) return HEIGHT_UNCHANGED;
X }/* elif */
X
X else { /* data already exists */
X *data = (*rootp) -> data; /* set return value in data */
X return HEIGHT_UNCHANGED;
X } /* else */
X
X (*rootp) -> bal += increase; /* update balance factor */
X
X /************************************************************************
X * re-balance if needed -- height of current tree increases only if its
X * subtree height increases and the current tree needs no rotation.
X ************************************************************************/
X if ( increase && (*rootp) -> bal )
X return ( 1 - balance( rootp ) );
X else
X return HEIGHT_UNCHANGED;
X}/* avl_insert */
X
X
X/*
X* avl_delete() -- delete an item from the given tree
X*
X* PARAMETERS:
X* data -- a pointer to a pointer to the key to delete
X* On exit, *data points to the deleted data item
X* (or NULL if deletion failed).
X* rootp -- a pointer to an AVL tree
X* compar -- name of function to compare 2 data items
X*/
XPRIVATE short avl_delete( data, rootp, compar )
Xvoid **data;
XAVLtree *rootp;
Xint (*compar)();
X{
X short decrease;
X int cmp;
X AVLtree old_root = *rootp;
X NODE nd_typ = node_type( *rootp );
X DIRECTION dir = (nd_typ == IS_LBRANCH) ? LEFT : RIGHT;
X
X if ( *rootp == NULL_TREE ) { /* data not found */
X *data = NULL; /* set return value in data */
X return HEIGHT_UNCHANGED;
X }/* if */
X
X cmp = compar( *data, (*rootp) -> data, nd_typ ); /* compare data items */
X
X if ( cmp < 0 ) { /* delete from left subtree */
X decrease = -avl_delete( data, &( (*rootp) -> subtree[ LEFT ] ), compar );
X if ( *data == NULL ) return HEIGHT_UNCHANGED;
X }/* elif */
X
X else if ( cmp > 0 ) { /* delete from right subtree */
X decrease = avl_delete( data, &( (*rootp) -> subtree[ RIGHT ] ), compar );
X if ( *data == NULL ) return HEIGHT_UNCHANGED;
X }/* elif */
X
X /************************************************************************
X * At this point we know that if "cmp" is zero then "*rootp" points to
X * the node that we need to delete. There are three cases:
X *
X * 1) The node is a leaf. Remove it and return.
X *
X * 2) The node is a branch (has only 1 child). Make "*rootp"
X * (the pointer to this node) point to the child.
X *
X * 3) The node has two children. We swap data with the successor of
X * "*rootp" (the smallest item in its right subtree) and delete
X * the successor from the right subtree of "*rootp". The
X * identifier "decrease" should be reset if the subtree height
X * decreased due to the deletion of the sucessor of "rootp".
X ************************************************************************/
X
X else { /* cmp == 0 */
X *data = (*rootp) -> data; /* set return value in data */
X
X switch ( nd_typ ) { /* what kind of node are we removing? */
X case IS_LEAF :
X free_node( rootp ); /* free the leaf, its height */
X return HEIGHT_CHANGED; /* changes from 1 to 0, return 1 */
X
X case IS_RBRANCH : /* only child becomes new root */
X case IS_LBRANCH :
X *rootp = (*rootp) -> subtree[ dir ];
X free_node( &old_root ); /* free the deleted node */
X return HEIGHT_CHANGED; /* we just shortened the "dir" subtree */
X
X case IS_TREE :
X decrease = avl_delete( &( (*rootp) -> data ),
X &( (*rootp) -> subtree[ RIGHT ] ),
X avl_min );
X } /* switch */
X } /* else */
X
X (*rootp) -> bal -= decrease; /* update balance factor */
X
X /**********************************************************************
X * Rebalance if necessary -- the height of current tree changes if one
X * of two things happens: (1) a rotation was performed which changed
X * the height of the subtree (2) the subtree height decreased and now
X * matches the height of its other subtree (so the current tree now
X * has a zero balance when it previously did not).
X **********************************************************************/
X if ( decrease && (*rootp) -> bal ) /* return 1 if height */
X return balance( rootp ); /* changed due to rotation */
X
X else if ( decrease && !(*rootp) -> bal ) /* or if balance is 0 from */
X return HEIGHT_CHANGED; /* height decrease of subtree */
X
X else
X return HEIGHT_UNCHANGED;
X
X}/* avl_delete */
X
X
X
X/**
X* Routines which Recursively Traverse an AVL TREE
X*
X* These routines may perform a particular action function upon each node
X* encountered. In these cases, "action" has the following definition:
X*
X* void action( data, order, node, level, bal )
X* void *data
X* VISIT order;
X* NODE node;
X* short bal;
X* int level;
X*
X* "data" is a pointer to the data field of an AVL node
X* "order" corresponds to whether this is the 1st, 2nd or 3rd time
X* that this node has been visited.
X* "node" indicates which children (if any) of the current node
X* are null.
X* "level" is the current level (or depth) in the tree of the
X* curent node.
X* "bal" is the balance factor of the current node.
X**/
X
X
X/************************************************************************
X* Walk an AVL tree, performing a given function at each node
X************************************************************************/
X
X
X/*
X* avl_walk -- traverse the given tree performing "action"
X* upon each data item encountered.
X*
X*/
XPRIVATE void avl_walk( tree, action, sibling_order, level )
XAVLtree tree;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
Xint level;
X{
X DIRECTION dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
X dir2 = OPPOSITE( dir1 );
X NODE node = node_type( tree );
X
X if ( (tree != NULL_TREE) && (action != NULL_ACTION) ) {
X (*action)( tree -> data, PREORDER, node, level, tree -> bal );
X
X if ( tree -> subtree[ dir1 ] != NULL_TREE )
X avl_walk( tree -> subtree[ dir1 ], action, sibling_order, level+1 );
X
X (*action)( tree -> data, INORDER, node, level, tree -> bal );
X
X if ( tree -> subtree[ dir2 ] != NULL_TREE )
X avl_walk( tree -> subtree[ dir2 ], action, sibling_order, level+1 );
X
X (*action)( tree -> data, POSTORDER, node, level, tree -> bal );
X }/* if non-empty tree */
X
X}/* avl_walk */
X
X
X
X/************************************************************************
X* Walk an AVL tree, de-allocating space for each node
X* and performing a given function at each node
X* (such as de-allocating the user-defined data item).
X************************************************************************/
X
X
X/*
X* avl_free() -- free up space for all nodes in a given tree
X* performing "action" upon each data item encountered.
X*
X* (only perform "action" if it is a non-null function)
X*/
X
XPRIVATE void avl_free( rootp, action, sibling_order, level )
XAVLtree *rootp;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
Xint level;
X{
X DIRECTION dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
X dir2 = OPPOSITE( dir1 );
X NODE node = node_type( *rootp );
X
X if ( *rootp != NULL_TREE ) {
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, PREORDER, node, level );
X
X if ( (*rootp) -> subtree[ dir1 ] != NULL_TREE )
X avl_free( &( (*rootp) -> subtree[ dir1 ] ),
X action, sibling_order, level+1 );
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, INORDER, node, level );
X
X if ( (*rootp) -> subtree[ dir2 ] != NULL_TREE )
X avl_free( &( (*rootp) -> subtree[ dir2 ] ),
X action, sibling_order, level+1 );
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, POSTORDER, node, level );
X
X free( *rootp );
X }/* if non-empty tree */
X
X}/* avl_free */
X
X
X
X
X/**********************************************************************
X*
X* C-interface (public functions) for avl trees
X*
X* These are the functions that are visible to the user of the
X* AVL Tree Library. Mostly they just return or modify a
X* particular attribute, or Call a private functions with the
X* given parameters.
X*
X* Note that public routine names begin with "avl" whereas
X* private routine names that are called by public routines
X* begin with "avl_" (the underscore character is added).
X*
X* Each public routine must convert (cast) any argument of the
X* public type "AVL_TREE" to a pointer to on object of the
X* private type "AVLdescriptor" before passing the actual
X* AVL tree to any of the private routines. In this way, the
X* type "AVL_TREE" is implemented as an opaque type.
X*
X* An "AVLdescriptor" is merely a container for AVL-tree
X* objects which contains the pointer to the root of the
X* tree and the various attributes of the tree.
X*
X* The function types prototypes for the routines which follow
X* are declared in the include file "avl.h"
X*
X***********************************************************************/
X
X
X
X/*
X* avlinit() -- get space for an AVL descriptor for the given tree
X* structure and initialize its fields.
X*/
XPUBLIC AVL_TREE avlinit( compar, isize )
Xint (*compar) ();
Xunsigned (*isize) ();
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) ckalloc( sizeof (AVLdescriptor) );
X avl_desc -> root = NULL_TREE;
X avl_desc -> compar = compar;
X avl_desc -> isize = isize;
X avl_desc -> count = 0;
X
X return (AVL_TREE) avl_desc;
X}/* avlinit */
X
X
X
X/*
X* avldispose() -- free up all space associated with the given tree structure.
X*/
XPUBLIC void avldispose( treeptr, action, sibling_order )
XAVL_TREE *treeptr;
Xvoid (*action) ();
XSIBLING_ORDER sibling_order;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) *treeptr;
X avl_free( &(avl_desc -> root), action, sibling_order, 1 );
X *treeptr = (AVL_TREE) NULL;
X}/* avldispose */
X
X
X
X/*
X* avlwalk() -- traverse the given tree structure and perform the
X* given action on each data item in the tree.
X*/
XPUBLIC void avlwalk( tree, action, sibling_order )
XAVL_TREE tree;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_walk( avl_desc -> root, action, sibling_order, 1 );
X}/* avlwalk */
X
X
X
X/*
X* avlcount () -- return the number of nodes in the given tree
X*/
XPUBLIC int avlcount( tree )
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_desc -> count;
X}/* avlcount */
X
X
X
X/*
X* avlins() -- insert the given item into the tree structure
X*/
XPUBLIC void *avlins( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_insert( &data, (*(avl_desc -> isize))( data ), &(avl_desc -> root), avl_desc -> compar );
X if ( data == NULL ) ++(avl_desc -> count);
X
X return data;
X}/* avlins */
X
X
X
X/*
X* avldel() -- delete the given item from the given tree structure
X*/
XPUBLIC void *avldel( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_desc -> compar );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldel */
X
X
X
X/*
X* avlfind() -- find the given item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfind( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( data, &(avl_desc -> root), avl_desc -> compar );
X}/* avlfind */
X
X
X
X/*
X* avldelmin() -- delete the minimal item from the given tree structure
X*/
XPUBLIC void *avldelmin( tree )
XAVL_TREE tree;
X{
X void *data;
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_min );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldelmin */
X
X
X
X/*
X* avlfindmin() -- find the minimal item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfindmin( tree )
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( NULL, &(avl_desc -> root), avl_min );
X}/* avlfindmin */
X
X
X
X/*
X* avldelmax() -- delete the maximal item from the given tree structure
X*/
XPUBLIC void *avldelmax( tree )
XAVL_TREE tree;
X{
X void *data;
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_max );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldelmax */
X
X
X
X/*
X* avlfindmax() -- find the maximal item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfindmax (tree)
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( NULL, &(avl_desc -> root), avl_max );
X}/* avlfindmax */
END_OF_FILE
if test 24464 -ne `wc -c <'avl.c'`; then
echo shar: \"'avl.c'\" unpacked with wrong size!
fi
# end of 'avl.c'
fi
if test -f 'testvals.old' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'testvals.old'\"
else
echo shar: Extracting \"'testvals.old'\" \(9970 characters\)
sed "s/^X//" >'testvals.old' <<'END_OF_FILE'
X/**
X*
X* testvals.old -- old test values for avl trees.
X*
X* Created 03/01/89 by Brad Appleton
X*
X* ^{Mods:* }
X*
X**/
X
Xint TestVals[] = {
X 16838,
X 5758,
X 10113,
X 17515,
X 31051,
X 5627,
X 23010,
X 7419,
X 16212,
X 4086,
X 2749,
X 12767,
X 9084,
X 12060,
X 32225,
X 17543,
X 25089,
X 21183,
X 25137,
X 25566,
X 26966,
X 4978,
X 20495,
X 10311,
X 11367,
X 30054,
X 17031,
X 13145,
X 19882,
X 25736,
X 30524,
X 28505,
X 28394,
X 22102,
X 24851,
X 19067,
X 12754,
X 11653,
X 6561,
X 27096,
X 13628,
X 15188,
X 32085,
X 4143,
X 6967,
X 31406,
X 24165,
X 13403,
X 25562,
X 24834,
X 31353,
X 920,
X 10444,
X 24803,
X 7962,
X 19318,
X 1422,
X 31327,
X 10457,
X 1945,
X 14479,
X 29983,
X 18751,
X 3894,
X 18670,
X 8259,
X 16248,
X 7757,
X 15629,
X 13306,
X 28606,
X 13990,
X 11738,
X 12516,
X 1414,
X 5262,
X 17116,
X 22825,
X 3181,
X 13134,
X 25343,
X 8022,
X 11233,
X 7536,
X 9760,
X 9979,
X 29071,
X 1201,
X 21336,
X 13061,
X 22160,
X 24005,
X 30729,
X 7644,
X 27475,
X 31693,
X 25514,
X 14139,
X 22088,
X 26521,
X 5202,
X 9171,
X 4434,
X 28317,
X 24582,
X 6815,
X 4586,
X 9653,
X 26306,
X 7174,
X 18451,
X 23448,
X 6473,
X 32434,
X 8193,
X 14110,
X 24748,
X 28210,
X 29320,
X 32049,
X 12956,
X 14162,
X 4166,
X 14997,
X 7793,
X 32310,
X 21391,
X 19799,
X 7926,
X 14905,
X 25885,
X 2582,
X 15610,
X 5000,
X 8052,
X 30965,
X 20120,
X 32380,
X 15639,
X 26204,
X 24385,
X 12475,
X 15725,
X 17265,
X 3214,
X 19471,
X 11376,
X 4697,
X 25543,
X 23297,
X 14619,
X 23087,
X 3123,
X 31549,
X 18065,
X 24256,
X 18973,
X 20901,
X 25613,
X 6157,
X 9899,
X 9267,
X 22413,
X 9598,
X 18526,
X 13711,
X 10046,
X 14566,
X 18536,
X 15988,
X 19878,
X 13626,
X 4273,
X 8387,
X 1171,
X 32017,
X 3752,
X 12388,
X 21191,
X 11483,
X 18122,
X 11744,
X 18528,
X 15585,
X 5363,
X 20159,
X 5641,
X 18176,
X 9575,
X 28578,
X 27363,
X 27685,
X 29344,
X 19489,
X 17713,
X 5511,
X 21461,
X 22626,
X 8645,
X 3496,
X 26703,
X 6270,
X 13870,
X 11529,
X 27499,
X 4500,
X 8607,
X 5808,
X 15725,
X 12457,
X 16542,
X 16474,
X 11531,
X 17222,
X 3952,
X 17024,
X 19894,
X 24015,
X 18247,
X 11276,
X 26278,
X 19365,
X 8746,
X 21976,
X 18092,
X 25851,
X 29088,
X 29163,
X 2231,
X 26233,
X 29732,
X 21106,
X 5411,
X 9874,
X 5448,
X 9344,
X 27589,
X 17574,
X 1191,
X 6789,
X 695,
X 11735,
X 20364,
X 17040,
X 17892,
X 5035,
X 26979,
X 1092,
X 850,
X 12390,
X 20195,
X 668,
X 20531,
X 29989,
X 12281,
X 23902,
X 12970,
X 32186,
X 19571,
X 3680,
X 7261,
X 26187,
X 28529,
X 24190,
X 446,
X 24233,
X 13708,
X 11863,
X 6681,
X 6001,
X 2499,
X 3786,
X 5214,
X 25829,
X 1322,
X 25907,
X 19628,
X 13192,
X 7505,
X 5990,
X 20129,
X 10875,
X 19829,
X 31591,
X 12388,
X 6042,
X 9833,
X 1775,
X 4719,
X 342,
X 28994,
X 31392,
X 20509,
X 31313,
X 20677,
X 1282,
X 11511,
X 4795,
X 3474,
X 6469,
X 2750,
X 879,
X 30989,
X 30134,
X 29752,
X 28364,
X 4880,
X 5629,
X 2235,
X 21332,
X 24145,
X 3356,
X 5243,
X 3079,
X 3988,
X 807,
X 24979,
X 31357,
X 914,
X 21187,
X 3540,
X 14022,
X 10149,
X 609,
X 29009,
X 24833,
X 16696,
X 5432,
X 24999,
X 28863,
X 16369,
X 28676,
X 24077,
X 7701,
X 1691,
X 19840,
X 28703,
X 16515,
X 22229,
X 32420,
X 19817,
X 16264,
X 19324,
X 29343,
X 1462,
X 28929,
X 3546,
X 17043,
X 18967,
X 325,
X 12683,
X 15634,
X 6322,
X 16642,
X 25395,
X 11612,
X 22864,
X 29910,
X 21985,
X 23126,
X 13988,
X 685,
X 6978,
X 31050,
X 16476,
X 6365,
X 21126,
X 4193,
X 8681,
X 11011,
X 23058,
X 1249,
X 31247,
X 24731,
X 28650,
X 20774,
X 7980,
X 20833,
X 27868,
X 7778,
X 23624,
X 11115,
X 1645,
X 15892,
X 29408,
X 7939,
X 17285,
X 16202,
X 28018,
X 11334,
X 4058,
X 7062,
X 3784,
X 11901,
X 6684,
X 14289,
X 27141,
X 16702,
X 26853,
X 13458,
X 28528,
X 23363,
X 21087,
X 19052,
X 31235,
X 15109,
X 17075,
X 11755,
X 10675,
X 288,
X 32053,
X 14157,
X 5758,
X 5222,
X 17488,
X 18945,
X 10294,
X 11200,
X 5171,
X 14305,
X 7951,
X 6601,
X 23608,
X 7214,
X 6377,
X 13865,
X 25369,
X 27215,
X 8030,
X 177,
X 16849,
X 11337,
X 2699,
X 23099,
X 8531,
X 11517,
X 17567,
X 28479,
X 9966,
X 2597,
X 14885,
X 12341,
X 15227,
X 27149,
X 785,
X 29615,
X 6476,
X 20753,
X 4236,
X 7730,
X 19668,
X 21210,
X 27519,
X 27608,
X 5142,
X 6999,
X 20449,
X 14246,
X 18638,
X 2941,
X 12481,
X 23726,
X 16738,
X 26047,
X 28947,
X 3300,
X 21639,
X 17996,
X 23866,
X 14785,
X 27571,
X 25356,
X 12633,
X 27289,
X 20551,
X 20312,
X 14426,
X 7357,
X 8056,
X 16252,
X 20410,
X 2384,
X 4353,
X 2029,
X 23579,
X 27882,
X 31882,
X 21577,
X 31368,
X 11502,
X 18902,
X 21012,
X 31365,
X 30379,
X 14256,
X 19244,
X 27870,
X 13365,
X 9619,
X 27665
X }; /* TestVals */
X
X#define NUM_VALS ( sizeof( TestVals ) / sizeof( int ) )
X
X
Xint DelVals[] = {
X 16838,
X 5758,
X 10113,
X 17515,
X 31051,
X 5627,
X 23010,
X 7419,
X 16212,
X 4086,
X 2749,
X 12767,
X 9084,
X 12060,
X 32225,
X 17543,
X 25089,
X 21183,
X 25137,
X 25566,
X 26966,
X 4978,
X 20495,
X 10311,
X 11367,
X 30054,
X 17031,
X 13145,
X 19882,
X 25736,
X 30524,
X 28505,
X 28394,
X 22102,
X 24851,
X 19067,
X 12754,
X 11653,
X 6561,
X 27096,
X 13628,
X 15188,
X 32085,
X 4143,
X 6967,
X 31406,
X 24165,
X 13403,
X 25562,
X 24834,
X 31353,
X 920,
X 10444,
X 24803,
X 7962,
X 19318,
X 1422,
X 31327,
X 10457,
X 1945,
X 14479,
X 29983,
X 18751,
X 3894,
X 18670,
X 8259,
X 16248,
X 7757,
X 15629,
X 13306,
X 28606,
X 13990,
X 11738,
X 12516,
X 1414,
X 5262,
X 17116,
X 22825,
X 3181,
X 13134,
X 25343,
X 8022,
X 11233,
X 7536,
X 9760,
X 9979,
X 29071,
X 1201,
X 21336,
X 13061,
X 22160,
X 24005,
X 30729,
X 7644,
X 27475,
X 31693,
X 25514,
X 14139,
X 22088,
X 26521,
X 5202,
X 9171,
X 4434,
X 28317,
X 24582,
X 6815,
X 4586,
X 9653,
X 26306,
X 7174,
X 18451,
X 23448,
X 6473,
X 32434,
X 8193,
X 14110,
X 24748,
X 28210,
X 29320,
X 32049,
X 12956,
X 14162,
X 4166,
X 14997,
X 7793,
X 32310,
X 21391,
X 19799,
X 7926,
X 14905,
X 25885,
X 2582,
X 15610,
X 5000,
X 8052,
X 30965,
X 20120,
X 32380,
X 15639,
X 26204,
X 24385,
X 12475,
X 15725,
X 17265,
X 3214,
X 19471,
X 11376,
X 4697,
X 25543,
X 23297,
X 14619,
X 23087,
X 3123,
X 31549,
X 18065,
X 24256,
X 18973,
X 20901,
X 25613,
X 6157,
X 9899,
X 9267,
X 22413,
X 9598,
X 18526,
X 13711,
X 10046,
X 14566,
X 18536,
X 15988,
X 19878,
X 13626,
X 4273,
X 8387,
X 1171,
X 32017,
X 3752,
X 12388,
X 21191,
X 11483,
X 18122,
X 11744,
X 18528,
X 15585,
X 5363,
X 20159,
X 5641,
X 18176,
X 9575,
X 28578,
X 27363,
X 27685,
X 29344,
X 19489,
X 17713,
X 5511,
X 21461,
X 22626,
X 8645,
X 3496,
X 26703,
X 6270,
X 13870,
X 11529,
X 27499,
X 4500,
X 8607,
X 5808,
X 15725,
X 12457,
X 16542,
X 16474,
X 11531,
X 17222,
X 3952,
X 17024,
X 19894,
X 24015,
X 18247,
X 11276,
X 26278,
X 19365,
X 8746,
X 21976,
X 18092,
X 25851,
X 29088,
X 29163,
X 2231,
X 26233,
X 29732,
X 21106,
X 5411,
X 9874,
X 5448,
X 9344,
X 27589,
X 17574,
X 1191,
X 6789,
X 695,
X 11735,
X 20364,
X 17040,
X 17892,
X 5035,
X 26979,
X 1092,
X 850,
X 12390,
X 20195,
X 668,
X 20531,
X 29989,
X 12281,
X 23902,
X 12970,
X 32186,
X 19571,
X 3680,
X 7261,
X 26187,
X 28529,
X 24190,
X 446,
X 24233,
X 13708,
X 11863,
X 6681,
X 6001,
X 2499,
X 3786,
X 5214,
X 25829,
X 1322,
X 25907,
X 19628,
X 13192,
X 7505,
X 5990,
X 20129,
X 10875,
X 19829,
X 31591,
X 12388,
X 6042,
X 9833,
X 1775,
X 4719,
X 342,
X 28994,
X 31392,
X 20509,
X 31313,
X 20677,
X 1282,
X 11511,
X 4795,
X 3474,
X 6469,
X 2750,
X 879,
X 30989,
X 30134,
X 29752,
X 28364,
X 4880,
X 5629,
X 2235,
X 21332,
X 24145,
X 3356,
X 5243,
X 3079,
X 3988,
X 807,
X 24979,
X 31357,
X 914,
X 21187,
X 3540,
X 14022,
X 10149,
X 609,
X 29009,
X 24833,
X 16696,
X 5432,
X 24999,
X 28863,
X 16369,
X 28676,
X 24077,
X 7701,
X 1691,
X 19840,
X 28703,
X 16515,
X 22229,
X 32420,
X 19817,
X 16264,
X 19324,
X 29343,
X 1462,
X 28929,
X 3546,
X 17043,
X 18967,
X 325,
X 12683,
X 15634,
X 6322,
X 16642,
X 25395,
X 11612,
X 22864,
X 29910,
X 21985,
X 23126,
X 13988,
X 685,
X 6978,
X 31050,
X 16476,
X 6365,
X 21126,
X 4193,
X 8681,
X 11011,
X 23058,
X 1249,
X 31247,
X 24731,
X 28650,
X 20774,
X 7980,
X 20833,
X 27868,
X 7778,
X 23624,
X 11115,
X 1645,
X 15892,
X 29408,
X 7939,
X 17285,
X 16202,
X 28018,
X 11334,
X 4058,
X 7062,
X 3784,
X 11901,
X 6684,
X 14289,
X 27141,
X 16702,
X 26853,
X 13458,
X 28528,
X 23363,
X 21087,
X 19052,
X 31235,
X 15109,
X 17075,
X 11755,
X 10675,
X 288,
X 32053,
X 14157,
X 5758,
X 5222,
X 17488,
X 18945,
X 10294,
X 11200,
X 5171,
X 14305,
X 7951,
X 6601,
X 23608,
X 7214,
X 6377,
X 13865,
X 25369,
X 27215,
X 8030,
X 177,
X 16849,
X 11337,
X 2699,
X 23099,
X 8531,
X 11517,
X 17567,
X 28479,
X 9966,
X 2597,
X 14885,
X 12341,
X 15227,
X 27149,
X 785,
X 29615,
X 6476,
X 20753,
X 4236,
X 7730,
X 19668,
X 21210,
X 27519,
X 27608,
X 5142,
X 6999,
X 20449,
X 14246,
X 18638,
X 2941,
X 12481,
X 23726,
X 16738,
X 26047,
X 28947,
X 3300
X/*,
X 21639,
X 17996,
X 23866,
X 14785,
X 27571,
X 25356,
X 12633,
X 27289,
X 20551,
X 20312,
X 14426,
X 7357,
X 8056,
X 16252,
X 20410,
X 2384,
X 4353,
X 2029,
X 23579,
X 27882,
X 31882,
X 21577,
X 31368,
X 11502,
X 18902,
X 21012,
X 31365,
X 30379,
X 14256,
X 19244,
X 27870,
X 13365,
X 9619,
X 27665
X*/
X }; /*DelVals */
X
X#define NUM_DELS ( sizeof( DelVals ) / sizeof( int ) )
END_OF_FILE
if test 9970 -ne `wc -c <'testvals.old'`; then
echo shar: \"'testvals.old'\" unpacked with wrong size!
fi
# end of 'testvals.old'
fi
echo shar: End of archive 2 \(of 2\).
cp /dev/null ark2isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
______________________ "And miles to go before I sleep." ______________________
Brad Appleton brad at ssd.csd.harris.com Harris Computer Systems
uunet!hcx1!brad Fort Lauderdale, FL USA
~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~
More information about the Alt.sources
mailing list