-#define ROTATERIGHT(x) { \
- Avlnode *tmp;\
- if ( *(x) == NULL || (*(x))->avl_left == NULL ) {\
- (void) fputs("RR error\n", stderr); exit( EXIT_FAILURE ); \
- }\
- 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) fputs("RL error\n", stderr); exit( EXIT_FAILURE ); \
- }\
- tmp = (*(x))->avl_right;\
- (*(x))->avl_right = tmp->avl_left;\
- tmp->avl_left = *(x);\
- *(x) = tmp;\
-}
-
-/*
- * ravl_insert - called from avl_insert() to do a recursive insert into
- * and balance of an avl tree.
- */
-
-static int
-ravl_insert(
- Avlnode **iroot,
- void* data,
- int *taller,
- AVL_CMP fcmp, /* comparison function */
- AVL_DUP fdup, /* function to call for duplicates */
- int depth
-)
-{
- int rc, cmp, tallersub;
- Avlnode *l, *r;
-
- if ( *iroot == 0 ) {
- if ( (*iroot = (Avlnode *) ber_memalloc( sizeof( Avlnode ) ))
- == NULL ) {
- return( -1 );
- }
- (*iroot)->avl_left = 0;
- (*iroot)->avl_right = 0;
- (*iroot)->avl_bf = 0;
- (*iroot)->avl_data = data;
- *taller = 1;
- return( 0 );
- }
-
- 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 );
-}