turbo_avl.c

来自「ftam等标准协议服务器和客户端的源代码。」· C语言 代码 · 共 710 行 · 第 1/2 页

	cmp = (*fcmp)( data, (*root)->avl_data );

	/* found it! */
	if ( cmp == 0 ) {
		savenode = *root;
		savedata = savenode->avl_data;

		/* simple cases: no left child */
		if ( (*root)->avl_left == 0 ) {
			*root = (*root)->avl_right;
			*shorter = 1;
			free( (char *) savenode );
			return( savedata );
		/* no right child */
		} else if ( (*root)->avl_right == 0 ) {
			*root = (*root)->avl_left;
			*shorter = 1;
			free( (char *) savenode );
			return( savedata );
		}

		/* 
		 * avl_getmin will return to us the smallest node greater
		 * than the one we are trying to delete.  deleting this node
		 * from the right subtree is guaranteed to end in one of the
		 * simple cases above.
		 */

		minnode = (*root)->avl_right;
		while ( minnode->avl_left != NULLAVL )
			minnode = minnode->avl_left;

		/* swap the data */
		(*root)->avl_data = minnode->avl_data;
		minnode->avl_data = savedata;

		savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
		    &shortersubtree );

		if ( shortersubtree )
			*shorter = right_balance( root );
		else
			*shorter = 0;
	/* go left */
	} else if ( cmp < 0 ) {
		if ( (savedata = ravl_delete( &(*root)->avl_left, data, fcmp,
		    &shortersubtree )) == 0 ) {
			*shorter = 0;
			return( 0 );
		}

		/* left subtree shorter? */
		if ( shortersubtree )
			*shorter = left_balance( root );
		else
			*shorter = 0;
	/* go right */
	} else {
		if ( (savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
		    &shortersubtree )) == 0 ) {
			*shorter = 0;
			return( 0 );
		}

		if ( shortersubtree ) 
			*shorter = right_balance( root );
		else
			*shorter = 0;
	}

	return( savedata );
}

caddr_t avl_delete( root, data, fcmp )
Avlnode	**root;
caddr_t	data;
IFP	fcmp;
{
	int	shorter;

	return( ravl_delete( root, data, fcmp, &shorter ) );
}

avl_inapply( root, fn, arg, stopflag )
Avlnode	*root;
IFP	fn;
caddr_t	arg;
int	stopflag;
{
	if ( root == 0 )
		return( AVL_NOMORE );

	if ( root->avl_left != 0 )
		if ( avl_inapply( root->avl_left, fn, arg, stopflag ) 
		    == stopflag )
			return( stopflag );

	if ( (*fn)( root->avl_data, arg ) == stopflag )
		return( stopflag );

	if ( root->avl_right == 0 )
		return( AVL_NOMORE );
	else
		return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
}

avl_postapply( root, fn, arg, stopflag )
Avlnode	*root;
IFP	fn;
caddr_t	arg;
int	stopflag;
{
	if ( root == 0 )
		return( AVL_NOMORE );

	if ( root->avl_left != 0 )
		if ( avl_postapply( root->avl_left, fn, arg, stopflag ) 
		    == stopflag )
			return( stopflag );

	if ( root->avl_right != 0 )
		if ( avl_postapply( root->avl_right, fn, arg, stopflag ) 
		    == stopflag )
			return( stopflag );

	return( (*fn)( root->avl_data, arg ) );
}

avl_preapply( root, fn, arg, stopflag )
Avlnode	*root;
IFP	fn;
caddr_t	arg;
int	stopflag;
{
	if ( root == 0 )
		return( AVL_NOMORE );

	if ( (*fn)( root->avl_data, arg ) == stopflag )
		return( stopflag );

	if ( root->avl_left != 0 )
		if ( avl_preapply( root->avl_left, fn, arg, stopflag ) 
		    == stopflag )
			return( stopflag );

	if ( root->avl_right == 0 )
		return( AVL_NOMORE );
	else
		return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
}

/*
 * avl_apply -- avl tree root is traversed, function fn is called with
 * arguments arg and the data portion of each node.  if fn returns stopflag,
 * the traversal is cut short, otherwise it continues.  Do not use -6 as
 * a stopflag.
 */

avl_apply( root, fn, arg, stopflag, type )
Avlnode	*root;
IFP	fn;
caddr_t	arg;
int	stopflag;
int	type;
{
	switch ( type ) {
	case AVL_INORDER:
		return( avl_inapply( root, fn, arg, stopflag ) );
	case AVL_PREORDER:
		return( avl_preapply( root, fn, arg, stopflag ) );
	case AVL_POSTORDER:
		return( avl_postapply( root, fn, arg, stopflag ) );
	default:
		DLOG( log_dsap, LLOG_EXCEPTIONS, ("Invalid traversal type %d",
		    type) );
		return( NOTOK );
	}

	/* NOTREACHED */
}

/*
 * avl_prefixapply - traverse avl tree root, applying function fprefix
 * to any nodes that match.  fcmp is called with data as its first arg
 * and the current node's data as its second arg.  it should return
 * 0 if they match, < 0 if data is less, and > 0 if data is greater.
 * the idea is to efficiently find all nodes that are prefixes of
 * some key...  Like avl_apply, this routine also takes a stopflag
 * and will return prematurely if fmatch returns this value.  Otherwise,
 * AVL_NOMORE is returned.
 */

avl_prefixapply( root, data, fmatch, marg, fcmp, carg, stopflag )
Avlnode	*root;
caddr_t	data;
IFP	fmatch;
caddr_t	marg;
IFP	fcmp;
caddr_t	carg;
int	stopflag;
{
	int	cmp;

	if ( root == 0 )
		return( AVL_NOMORE );

	cmp = (*fcmp)( data, root->avl_data, carg );
	if ( cmp == 0 ) {
		if ( (*fmatch)( root->avl_data, marg ) == stopflag )
			return( stopflag );

		if ( root->avl_left != 0 )
			if ( avl_prefixapply( root->avl_left, data, fmatch,
			    marg, fcmp, carg, stopflag ) == stopflag )
				return( stopflag );

		if ( root->avl_right != 0 )
			return( avl_prefixapply( root->avl_right, data, fmatch,
			    marg, fcmp, carg, stopflag ) );
		else
			return( AVL_NOMORE );

	} else if ( cmp < 0 ) {
		if ( root->avl_left != 0 )
			return( avl_prefixapply( root->avl_left, data, fmatch,
			    marg, fcmp, carg, stopflag ) );
	} else {
		if ( root->avl_right != 0 )
			return( avl_prefixapply( root->avl_right, data, fmatch,
			    marg, fcmp, carg, stopflag ) );
	}

	return( AVL_NOMORE );
}

/*
 * avl_free -- traverse avltree root, freeing the memory it is using.
 * the dfree() is called to free the data portion of each node.  The
 * number of items actually freed is returned.
 */

avl_free( root, dfree )
Avlnode	*root;
IFP	dfree;
{
	int	nleft, nright;

	if ( root == 0 )
		return( 0 );

	nleft = nright = 0;
	if ( root->avl_left != 0 )
		nleft = avl_free( root->avl_left, dfree );

	if ( root->avl_right != 0 )
		nright = avl_free( root->avl_right, dfree );

	if ( dfree )
		(*dfree)( root->avl_data );

	free( (char *) root );

	return( nleft + nright + 1 );
}

/*
 * avl_find -- search avltree root for a node with data data.  the function
 * cmp is used to compare things.  it is called with data as its first arg 
 * and the current node data as its second.  it should return 0 if they match,
 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
 */

caddr_t avl_find( root, data, fcmp )
Avlnode	*root;
caddr_t	data;
IFP	fcmp;
{
	int	cmp;

	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
		if ( cmp < 0 )
			root = root->avl_left;
		else
			root = root->avl_right;
	}

	return( root ? root->avl_data : 0 );
}

static caddr_t	*avl_list;
static int	avl_maxlist;
static int	avl_nextlist;

#define AVL_GRABSIZE	100

/* ARGSUSED 1 */
static avl_buildlist( data, arg )
caddr_t	data;
int	arg;
{
	static int	slots;

	if ( avl_list == (caddr_t *) 0 ) {
		avl_list = (caddr_t *) malloc(AVL_GRABSIZE * sizeof(caddr_t));
		slots = AVL_GRABSIZE;
		avl_maxlist = 0;
	} else if ( avl_maxlist == slots ) {
		slots += AVL_GRABSIZE;
		avl_list = (caddr_t *) realloc( (char *) avl_list,
		    (unsigned) slots * sizeof(caddr_t));
	}

	avl_list[ avl_maxlist++ ] = data;

	return( 0 );
}

caddr_t avl_getfirst( root )
Avlnode	*root;
{
	if ( avl_list ) {
		free( (char *) avl_list);
		avl_list = (caddr_t *) 0;
	}
	avl_maxlist = 0;
	avl_nextlist = 0;

	if ( root == 0 )
		return( 0 );

	(void) avl_apply( root, avl_buildlist, (caddr_t) 0, -1, AVL_INORDER );

	return( avl_list[ avl_nextlist++ ] );
}

caddr_t avl_getnext()
{
	if ( avl_list == 0 )
		return( 0 );

	if ( avl_nextlist == avl_maxlist ) {
		free( (caddr_t) avl_list);
		avl_list = (caddr_t *) 0;
		return( 0 );
	}

	return( avl_list[ avl_nextlist++ ] );
}


avl_dup_error()
{
	return( NOTOK );
}