turbo_avl.c

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

/* turbo_avl.c */

#ifndef	lint
static char *rcsid = "$Header: /xtel/isode/isode/dsap/common/RCS/turbo_avl.c,v 9.0 1992/06/16 12:12:39 isode Rel $";
#endif

/* 
 * $Header: /xtel/isode/isode/dsap/common/RCS/turbo_avl.c,v 9.0 1992/06/16 12:12:39 isode Rel $
 *
 *
 * $Log: turbo_avl.c,v $
 * Revision 9.0  1992/06/16  12:12:39  isode
 * Release 8.0
 *
 */

/*
 *				  NOTICE
 *
 *    Acquisition, use, and distribution of this module and related
 *    materials are subject to the restrictions of a license agreement.
 *    Consult the Preface in the User's Manual for the full terms of
 *    this agreement.
 *
 */


#include <sys/types.h>

#include "manifest.h"
#include "quipu/util.h"
#include "quipu/attr.h"
#include "quipu/entry.h"
#include "quipu/turbo.h"

extern LLog * log_dsap;


#define ROTATERIGHT(x)	{ \
	Avlnode *tmp;\
	if ( *x == NULL || (*x)->avl_left == NULL ) {\
		(void) printf("RR error\n"); exit(1); \
	}\
	tmp = (*x)->avl_left;\
	(*x)->avl_left = tmp->avl_right;\
	tmp->avl_right = *x;\
	*x = tmp;\
}
#define ROTATELEFT(x)	{ \
	Avlnode *tmp;\
	if ( *x == NULL || (*x)->avl_right == NULL ) {\
		(void) printf("RL error\n"); exit(1); \
	}\
	tmp = (*x)->avl_right;\
	(*x)->avl_right = tmp->avl_left;\
	tmp->avl_left = *x;\
	*x = tmp;\
}


static ravl_insert( iroot, data, taller, fcmp, fdup, depth )
Avlnode 	**iroot;
caddr_t		data;
int		*taller;
IFP		fcmp;		/* comparison function */
IFP		fdup;		/* function to call for duplicates */
int		depth;
{
	int	rc, cmp, tallersub;
	Avlnode	*l, *r;

	if ( *iroot == 0 ) {
		*iroot = ( Avlnode * ) malloc( sizeof( Avlnode ) );
		(*iroot)->avl_left = 0;
		(*iroot)->avl_right = 0;
		(*iroot)->avl_bf = 0;
		(*iroot)->avl_data = data;
		*taller = 1;
		return( OK );
	}

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

	/* equal - duplicate name */
	if ( cmp == 0 ) {
		*taller = 0;
		return( (*fdup)( (*iroot)->avl_data, data ) );
	}

	/* go right */
	else if ( cmp > 0 ) {
		rc = ravl_insert( &((*iroot)->avl_right), data, &tallersub,
		   fcmp, fdup, depth );
		if ( tallersub )
			switch ( (*iroot)->avl_bf ) {
			case LH	: /* left high - balance is restored */
				(*iroot)->avl_bf = EH;
				*taller = 0;
				break;
			case EH	: /* equal height - now right heavy */
				(*iroot)->avl_bf = RH;
				*taller = 1;
				break;
			case RH	: /* right heavy to start - right balance */
				r = (*iroot)->avl_right;
				switch ( r->avl_bf ) {
				case LH	: /* double rotation left */
					l = r->avl_left;
					switch ( l->avl_bf ) {
					case LH	: (*iroot)->avl_bf = EH;
						  r->avl_bf = RH;
						  break;
					case EH	: (*iroot)->avl_bf = EH;
						  r->avl_bf = EH;
						  break;
					case RH	: (*iroot)->avl_bf = LH;
						  r->avl_bf = EH;
						  break;
					}
					l->avl_bf = EH;
					ROTATERIGHT( (&r) )
					(*iroot)->avl_right = r;
					ROTATELEFT( iroot )
					*taller = 0;
					break;
				case EH	: /* This should never happen */
					break;
				case RH	: /* single rotation left */
					(*iroot)->avl_bf = EH;
					r->avl_bf = EH;
					ROTATELEFT( iroot )
					*taller = 0;
					break;
				}
				break;
			}
		else
			*taller = 0;
	}

	/* go left */
	else {
		rc = ravl_insert( &((*iroot)->avl_left), data, &tallersub,
		   fcmp, fdup, depth );
		if ( tallersub )
			switch ( (*iroot)->avl_bf ) {
			case LH	: /* left high to start - left balance */
				l = (*iroot)->avl_left;
				switch ( l->avl_bf ) {
				case LH	: /* single rotation right */
					(*iroot)->avl_bf = EH;
					l->avl_bf = EH;
					ROTATERIGHT( iroot )
					*taller = 0;
					break;
				case EH	: /* this should never happen */
					break;
				case RH	: /* double rotation right */
					r = l->avl_right;
					switch ( r->avl_bf ) {
					case LH	: (*iroot)->avl_bf = RH;
						  l->avl_bf = EH;
						  break;
					case EH	: (*iroot)->avl_bf = EH;
						  l->avl_bf = EH;
						  break;
					case RH	: (*iroot)->avl_bf = EH;
						  l->avl_bf = LH;
						  break;
					}
					r->avl_bf = EH;
					ROTATELEFT( (&l) )
					(*iroot)->avl_left = l;
					ROTATERIGHT( iroot )
					*taller = 0;
					break;
				}
				break;
			case EH	: /* equal height - now left heavy */
				(*iroot)->avl_bf = LH;
				*taller = 1;
				break;
			case RH	: /* right high - balance is restored */
				(*iroot)->avl_bf = EH;
				*taller = 0;
				break;
			}
		else
			*taller = 0;
	}

	return( rc );
}

/*
 * avl_insert -- insert a node containing data data into the avl tree
 * with root root.  fcmp is a function to call to compare the data portion
 * of two nodes.  it should take two arguments and return <, >, or == 0,
 * depending on whether its first argument is <, >, or == its second
 * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
 * node is inserted.  it should return OK, or NOTOK and its return value
 * will be the return value from avl_insert in the case of a duplicate node.
 * the function will be called with the original node's data as its first
 * argument and with the incoming duplicate node's data as its second
 * argument.  this could be used, for example, to keep a count with each
 * node.
 *
 * NOTE: this routine may malloc memory
 */

avl_insert( root, data, fcmp, fdup )
Avlnode	**root;
caddr_t	data;
IFP	fcmp;
IFP	fdup;
{
	int	taller;

	return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
}

/* called from delete when root's right subtree has been shortened */
static right_balance( root )
Avlnode	**root;
{
	int	shorter;
	Avlnode	*r, *l;

	switch( (*root)->avl_bf ) {
	case RH:	/* was right high - equal now */
		(*root)->avl_bf = EH;
		shorter = 1;
		break;
	case EH:	/* was equal - left high now */
		(*root)->avl_bf = LH;
		shorter = 0;
		break;
	case LH:	/* was right high - balance */
		l = (*root)->avl_left;
		switch ( l->avl_bf ) {
		case RH	: /* double rotation left */
			r = l->avl_right;
			switch ( r->avl_bf ) {
			case RH	:
				(*root)->avl_bf = EH;
				l->avl_bf = LH;
				break;
			case EH	:
				(*root)->avl_bf = EH;
				l->avl_bf = EH;
				break;
			case LH	:
				(*root)->avl_bf = RH;
				l->avl_bf = EH;
				break;
			}
			r->avl_bf = EH;
			ROTATELEFT( (&l) )
			(*root)->avl_left = l;
			ROTATERIGHT( root )
			shorter = 1;
			break;
		case EH	: /* right rotation */
			(*root)->avl_bf = LH;
			l->avl_bf = RH;
			ROTATERIGHT( root );
			shorter = 0;
			break;
		case LH	: /* single rotation right */
			(*root)->avl_bf = EH;
			l->avl_bf = EH;
			ROTATERIGHT( root )
			shorter = 1;
			break;
		}
		break;
	}

	return( shorter );
}

/* called from delete when root's left subtree has gotten shorter */
static left_balance( root )
Avlnode	**root;
{
	int	shorter;
	Avlnode	*r, *l;

	switch( (*root)->avl_bf ) {
	case LH:	/* was left high - equal now */
		(*root)->avl_bf = EH;
		shorter = 1;
		break;
	case EH:	/* was equal - right high now */
		(*root)->avl_bf = RH;
		shorter = 0;
		break;
	case RH:	/* was right high - balance */
		r = (*root)->avl_right;
		switch ( r->avl_bf ) {
		case LH	: /* double rotation left */
			l = r->avl_left;
			switch ( l->avl_bf ) {
			case LH	:
				(*root)->avl_bf = EH;
				r->avl_bf = RH;
				break;
			case EH	:
				(*root)->avl_bf = EH;
				r->avl_bf = EH;
				break;
			case RH	:
				(*root)->avl_bf = LH;
				r->avl_bf = EH;
				break;
			}
			l->avl_bf = EH;
			ROTATERIGHT( (&r) )
			(*root)->avl_right = r;
			ROTATELEFT( root )
			shorter = 1;
			break;
		case EH	: /* single rotation left */
			(*root)->avl_bf = RH;
			r->avl_bf = LH;
			ROTATELEFT( root );
			shorter = 0;
			break;
		case RH	: /* single rotation left */
			(*root)->avl_bf = EH;
			r->avl_bf = EH;
			ROTATELEFT( root )
			shorter = 1;
			break;
		}
		break;
	}

	return( shorter );
}

static caddr_t ravl_delete( root, data, fcmp, shorter )
Avlnode	**root;
caddr_t	data;
IFP	fcmp;
int	*shorter;
{
	int	shortersubtree = 0;
	int	cmp;
	caddr_t	savedata;
	Avlnode	*minnode, *savenode;

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