1 /* avl.c - routines to implement an avl tree */
3 * Copyright 1998-1999 The OpenLDAP Foundation, All Rights Reserved.
4 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
7 * Copyright (c) 1993 Regents of the University of Michigan.
10 * Redistribution and use in source and binary forms are permitted
11 * provided that this notice is preserved and that due credit is given
12 * to the University of Michigan at Ann Arbor. The name of the University
13 * may not be used to endorse or promote products derived from this
14 * software without specific prior written permission. This software
15 * is provided ``as is'' without express or implied warranty.
21 static char copyright[] = "@(#) Copyright (c) 1993 Regents of the University of Michigan.\nAll rights reserved.\n";
22 static char avl_version[] = "AVL library version 1.0\n";
26 #include <ac/stdlib.h>
31 #define ROTATERIGHT(x) { \
33 if ( *(x) == NULL || (*(x))->avl_left == NULL ) {\
34 (void) fputs("RR error\n", stderr); exit( EXIT_FAILURE ); \
36 tmp = (*(x))->avl_left;\
37 (*(x))->avl_left = tmp->avl_right;\
38 tmp->avl_right = *(x);\
41 #define ROTATELEFT(x) { \
43 if ( *(x) == NULL || (*(x))->avl_right == NULL ) {\
44 (void) fputs("RL error\n", stderr); exit( EXIT_FAILURE ); \
46 tmp = (*(x))->avl_right;\
47 (*(x))->avl_right = tmp->avl_left;\
48 tmp->avl_left = *(x);\
53 * ravl_insert - called from avl_insert() to do a recursive insert into
54 * and balance of an avl tree.
62 AVL_CMP fcmp, /* comparison function */
63 AVL_DUP fdup, /* function to call for duplicates */
67 int rc, cmp, tallersub;
71 if ( (*iroot = (Avlnode *) malloc( sizeof( Avlnode ) ))
75 (*iroot)->avl_left = 0;
76 (*iroot)->avl_right = 0;
78 (*iroot)->avl_data = data;
83 cmp = (*fcmp)( data, (*iroot)->avl_data );
85 /* equal - duplicate name */
88 return( (*fdup)( (*iroot)->avl_data, data ) );
93 rc = ravl_insert( &((*iroot)->avl_right), data, &tallersub,
96 switch ( (*iroot)->avl_bf ) {
97 case LH : /* left high - balance is restored */
98 (*iroot)->avl_bf = EH;
101 case EH : /* equal height - now right heavy */
102 (*iroot)->avl_bf = RH;
105 case RH : /* right heavy to start - right balance */
106 r = (*iroot)->avl_right;
107 switch ( r->avl_bf ) {
108 case LH : /* double rotation left */
110 switch ( l->avl_bf ) {
111 case LH : (*iroot)->avl_bf = EH;
114 case EH : (*iroot)->avl_bf = EH;
117 case RH : (*iroot)->avl_bf = LH;
123 (*iroot)->avl_right = r;
127 case EH : /* This should never happen */
129 case RH : /* single rotation left */
130 (*iroot)->avl_bf = EH;
144 rc = ravl_insert( &((*iroot)->avl_left), data, &tallersub,
147 switch ( (*iroot)->avl_bf ) {
148 case LH : /* left high to start - left balance */
149 l = (*iroot)->avl_left;
150 switch ( l->avl_bf ) {
151 case LH : /* single rotation right */
152 (*iroot)->avl_bf = EH;
157 case EH : /* this should never happen */
159 case RH : /* double rotation right */
161 switch ( r->avl_bf ) {
162 case LH : (*iroot)->avl_bf = RH;
165 case EH : (*iroot)->avl_bf = EH;
168 case RH : (*iroot)->avl_bf = EH;
174 (*iroot)->avl_left = l;
180 case EH : /* equal height - now left heavy */
181 (*iroot)->avl_bf = LH;
184 case RH : /* right high - balance is restored */
185 (*iroot)->avl_bf = EH;
197 * avl_insert -- insert a node containing data data into the avl tree
198 * with root root. fcmp is a function to call to compare the data portion
199 * of two nodes. it should take two arguments and return <, >, or == 0,
200 * depending on whether its first argument is <, >, or == its second
201 * argument (like strcmp, e.g.). fdup is a function to call when a duplicate
202 * node is inserted. it should return 0, or -1 and its return value
203 * will be the return value from avl_insert in the case of a duplicate node.
204 * the function will be called with the original node's data as its first
205 * argument and with the incoming duplicate node's data as its second
206 * argument. this could be used, for example, to keep a count with each
209 * NOTE: this routine may malloc memory
213 avl_insert( Avlnode **root, void* data, AVL_CMP fcmp, AVL_DUP fdup )
217 return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
221 * right_balance() - called from delete when root's right subtree has
222 * been shortened because of a deletion.
226 right_balance( Avlnode **root )
231 switch( (*root)->avl_bf ) {
232 case RH: /* was right high - equal now */
233 (*root)->avl_bf = EH;
236 case EH: /* was equal - left high now */
237 (*root)->avl_bf = LH;
240 case LH: /* was right high - balance */
241 l = (*root)->avl_left;
242 switch ( l->avl_bf ) {
243 case RH : /* double rotation left */
245 switch ( r->avl_bf ) {
247 (*root)->avl_bf = EH;
251 (*root)->avl_bf = EH;
255 (*root)->avl_bf = RH;
261 (*root)->avl_left = l;
265 case EH : /* right rotation */
266 (*root)->avl_bf = LH;
271 case LH : /* single rotation right */
272 (*root)->avl_bf = EH;
285 * left_balance() - called from delete when root's left subtree has
286 * been shortened because of a deletion.
290 left_balance( Avlnode **root )
295 switch( (*root)->avl_bf ) {
296 case LH: /* was left high - equal now */
297 (*root)->avl_bf = EH;
300 case EH: /* was equal - right high now */
301 (*root)->avl_bf = RH;
304 case RH: /* was right high - balance */
305 r = (*root)->avl_right;
306 switch ( r->avl_bf ) {
307 case LH : /* double rotation left */
309 switch ( l->avl_bf ) {
311 (*root)->avl_bf = EH;
315 (*root)->avl_bf = EH;
319 (*root)->avl_bf = LH;
325 (*root)->avl_right = r;
329 case EH : /* single rotation left */
330 (*root)->avl_bf = RH;
335 case RH : /* single rotation left */
336 (*root)->avl_bf = EH;
349 * ravl_delete() - called from avl_delete to do recursive deletion of a
350 * node from an avl tree. It finds the node recursively, deletes it,
351 * and returns shorter if the tree is shorter after the deletion and
356 ravl_delete( Avlnode **root, void* data, AVL_CMP fcmp, int *shorter )
358 int shortersubtree = 0;
361 Avlnode *minnode, *savenode;
363 if ( *root == NULLAVL )
366 cmp = (*fcmp)( data, (*root)->avl_data );
371 savedata = savenode->avl_data;
373 /* simple cases: no left child */
374 if ( (*root)->avl_left == 0 ) {
375 *root = (*root)->avl_right;
377 free( (char *) savenode );
380 } else if ( (*root)->avl_right == 0 ) {
381 *root = (*root)->avl_left;
383 free( (char *) savenode );
388 * avl_getmin will return to us the smallest node greater
389 * than the one we are trying to delete. deleting this node
390 * from the right subtree is guaranteed to end in one of the
391 * simple cases above.
394 minnode = (*root)->avl_right;
395 while ( minnode->avl_left != NULLAVL )
396 minnode = minnode->avl_left;
399 (*root)->avl_data = minnode->avl_data;
400 minnode->avl_data = savedata;
402 savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
405 if ( shortersubtree )
406 *shorter = right_balance( root );
410 } else if ( cmp < 0 ) {
411 if ( (savedata = ravl_delete( &(*root)->avl_left, data, fcmp,
412 &shortersubtree )) == 0 ) {
417 /* left subtree shorter? */
418 if ( shortersubtree )
419 *shorter = left_balance( root );
424 if ( (savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
425 &shortersubtree )) == 0 ) {
430 if ( shortersubtree )
431 *shorter = right_balance( root );
440 * avl_delete() - deletes the node containing data (according to fcmp) from
441 * the avl tree rooted at root.
445 avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
449 return( ravl_delete( root, data, fcmp, &shorter ) );
453 avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
456 return( AVL_NOMORE );
458 if ( root->avl_left != 0 )
459 if ( avl_inapply( root->avl_left, fn, arg, stopflag )
463 if ( (*fn)( root->avl_data, arg ) == stopflag )
466 if ( root->avl_right == 0 )
467 return( AVL_NOMORE );
469 return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
473 avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
476 return( AVL_NOMORE );
478 if ( root->avl_left != 0 )
479 if ( avl_postapply( root->avl_left, fn, arg, stopflag )
483 if ( root->avl_right != 0 )
484 if ( avl_postapply( root->avl_right, fn, arg, stopflag )
488 return( (*fn)( root->avl_data, arg ) );
492 avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
495 return( AVL_NOMORE );
497 if ( (*fn)( root->avl_data, arg ) == stopflag )
500 if ( root->avl_left != 0 )
501 if ( avl_preapply( root->avl_left, fn, arg, stopflag )
505 if ( root->avl_right == 0 )
506 return( AVL_NOMORE );
508 return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
512 * avl_apply -- avl tree root is traversed, function fn is called with
513 * arguments arg and the data portion of each node. if fn returns stopflag,
514 * the traversal is cut short, otherwise it continues. Do not use -6 as
515 * a stopflag, as this is what is used to indicate the traversal ran out
520 avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type )
524 return( avl_inapply( root, fn, arg, stopflag ) );
526 return( avl_preapply( root, fn, arg, stopflag ) );
528 return( avl_postapply( root, fn, arg, stopflag ) );
530 fprintf( stderr, "Invalid traversal type %d\n", type );
538 * avl_prefixapply - traverse avl tree root, applying function fprefix
539 * to any nodes that match. fcmp is called with data as its first arg
540 * and the current node's data as its second arg. it should return
541 * 0 if they match, < 0 if data is less, and > 0 if data is greater.
542 * the idea is to efficiently find all nodes that are prefixes of
543 * some key... Like avl_apply, this routine also takes a stopflag
544 * and will return prematurely if fmatch returns this value. Otherwise,
545 * AVL_NOMORE is returned.
562 return( AVL_NOMORE );
564 cmp = (*fcmp)( data, root->avl_data /* , carg */);
566 if ( (*fmatch)( root->avl_data, marg ) == stopflag )
569 if ( root->avl_left != 0 )
570 if ( avl_prefixapply( root->avl_left, data, fmatch,
571 marg, fcmp, carg, stopflag ) == stopflag )
574 if ( root->avl_right != 0 )
575 return( avl_prefixapply( root->avl_right, data, fmatch,
576 marg, fcmp, carg, stopflag ) );
578 return( AVL_NOMORE );
580 } else if ( cmp < 0 ) {
581 if ( root->avl_left != 0 )
582 return( avl_prefixapply( root->avl_left, data, fmatch,
583 marg, fcmp, carg, stopflag ) );
585 if ( root->avl_right != 0 )
586 return( avl_prefixapply( root->avl_right, data, fmatch,
587 marg, fcmp, carg, stopflag ) );
590 return( AVL_NOMORE );
594 * avl_free -- traverse avltree root, freeing the memory it is using.
595 * the dfree() is called to free the data portion of each node. The
596 * number of items actually freed is returned.
600 avl_free( Avlnode *root, AVL_FREE dfree )
608 if ( root->avl_left != 0 )
609 nleft = avl_free( root->avl_left, dfree );
611 if ( root->avl_right != 0 )
612 nright = avl_free( root->avl_right, dfree );
615 (*dfree)( root->avl_data );
618 return( nleft + nright + 1 );
622 * avl_find -- search avltree root for a node with data data. the function
623 * cmp is used to compare things. it is called with data as its first arg
624 * and the current node data as its second. it should return 0 if they match,
625 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
629 avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
633 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
635 root = root->avl_left;
637 root = root->avl_right;
640 return( root ? root->avl_data : 0 );
644 * avl_find_lin -- search avltree root linearly for a node with data data.
645 * the function cmp is used to compare things. it is called with data as its
646 * first arg and the current node data as its second. it should return 0 if
647 * they match, non-zero otherwise.
651 avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp )
658 if ( (*fcmp)( data, root->avl_data ) == 0 )
659 return( root->avl_data );
661 if ( root->avl_left != 0 )
662 if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
666 if ( root->avl_right == 0 )
669 return( avl_find_lin( root->avl_right, data, fcmp ) );
672 /* NON-REENTRANT INTERFACE */
674 static void* *avl_list;
675 static int avl_maxlist;
676 static int avl_nextlist;
678 #define AVL_GRABSIZE 100
682 avl_buildlist( void* data, void* arg )
686 if ( avl_list == (void* *) 0 ) {
687 avl_list = (void* *) malloc(AVL_GRABSIZE * sizeof(void*));
688 slots = AVL_GRABSIZE;
690 } else if ( avl_maxlist == slots ) {
691 slots += AVL_GRABSIZE;
692 avl_list = (void* *) realloc( (char *) avl_list,
693 (unsigned) slots * sizeof(void*));
696 avl_list[ avl_maxlist++ ] = data;
702 * avl_getfirst() and avl_getnext() are provided as alternate tree
703 * traversal methods, to be used when a single function cannot be
704 * provided to be called with every node in the tree. avl_getfirst()
705 * traverses the tree and builds a linear list of all the nodes,
706 * returning the first node. avl_getnext() returns the next thing
707 * on the list built by avl_getfirst(). This means that avl_getfirst()
708 * can take a while, and that the tree should not be messed with while
709 * being traversed in this way, and that multiple traversals (even of
710 * different trees) cannot be active at once.
714 avl_getfirst( Avlnode *root )
717 free( (char *) avl_list);
718 avl_list = (void* *) 0;
726 (void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );
728 return( avl_list[ avl_nextlist++ ] );
737 if ( avl_nextlist == avl_maxlist ) {
738 free( (void*) avl_list);
739 avl_list = (void* *) 0;
743 return( avl_list[ avl_nextlist++ ] );
746 /* end non-reentrant code */
750 avl_dup_error( void* left, void* right )
756 avl_dup_ok( void* left, void* right )