1 /* avl.c - routines to implement an avl tree */
3 * Copyright (c) 1993 Regents of the University of Michigan.
6 * Redistribution and use in source and binary forms are permitted
7 * provided that this notice is preserved and that due credit is given
8 * to the University of Michigan at Ann Arbor. The name of the University
9 * may not be used to endorse or promote products derived from this
10 * software without specific prior written permission. This software
11 * is provided ``as is'' without express or implied warranty.
15 static char copyright[] = "@(#) Copyright (c) 1993 Regents of the University of Michigan.\nAll rights reserved.\n";
16 static char avl_version[] = "AVL library version 1.0\n";
19 #include <sys/types.h>
23 #define ROTATERIGHT(x) { \
25 if ( *x == NULL || (*x)->avl_left == NULL ) {\
26 (void) printf("RR error\n"); exit(1); \
28 tmp = (*x)->avl_left;\
29 (*x)->avl_left = tmp->avl_right;\
33 #define ROTATELEFT(x) { \
35 if ( *x == NULL || (*x)->avl_right == NULL ) {\
36 (void) printf("RL error\n"); exit(1); \
38 tmp = (*x)->avl_right;\
39 (*x)->avl_right = tmp->avl_left;\
45 * ravl_insert - called from avl_insert() to do a recursive insert into
46 * and balance of an avl tree.
50 ravl_insert( iroot, data, taller, fcmp, fdup, depth )
54 IFP fcmp; /* comparison function */
55 IFP fdup; /* function to call for duplicates */
58 int rc, cmp, tallersub;
62 if ( (*iroot = (Avlnode *) malloc( sizeof( Avlnode ) ))
66 (*iroot)->avl_left = 0;
67 (*iroot)->avl_right = 0;
69 (*iroot)->avl_data = data;
74 cmp = (*fcmp)( data, (*iroot)->avl_data );
76 /* equal - duplicate name */
79 return( (*fdup)( (*iroot)->avl_data, data ) );
84 rc = ravl_insert( &((*iroot)->avl_right), data, &tallersub,
87 switch ( (*iroot)->avl_bf ) {
88 case LH : /* left high - balance is restored */
89 (*iroot)->avl_bf = EH;
92 case EH : /* equal height - now right heavy */
93 (*iroot)->avl_bf = RH;
96 case RH : /* right heavy to start - right balance */
97 r = (*iroot)->avl_right;
98 switch ( r->avl_bf ) {
99 case LH : /* double rotation left */
101 switch ( l->avl_bf ) {
102 case LH : (*iroot)->avl_bf = EH;
105 case EH : (*iroot)->avl_bf = EH;
108 case RH : (*iroot)->avl_bf = LH;
114 (*iroot)->avl_right = r;
118 case EH : /* This should never happen */
120 case RH : /* single rotation left */
121 (*iroot)->avl_bf = EH;
135 rc = ravl_insert( &((*iroot)->avl_left), data, &tallersub,
138 switch ( (*iroot)->avl_bf ) {
139 case LH : /* left high to start - left balance */
140 l = (*iroot)->avl_left;
141 switch ( l->avl_bf ) {
142 case LH : /* single rotation right */
143 (*iroot)->avl_bf = EH;
148 case EH : /* this should never happen */
150 case RH : /* double rotation right */
152 switch ( r->avl_bf ) {
153 case LH : (*iroot)->avl_bf = RH;
156 case EH : (*iroot)->avl_bf = EH;
159 case RH : (*iroot)->avl_bf = EH;
165 (*iroot)->avl_left = l;
171 case EH : /* equal height - now left heavy */
172 (*iroot)->avl_bf = LH;
175 case RH : /* right high - balance is restored */
176 (*iroot)->avl_bf = EH;
188 * avl_insert -- insert a node containing data data into the avl tree
189 * with root root. fcmp is a function to call to compare the data portion
190 * of two nodes. it should take two arguments and return <, >, or == 0,
191 * depending on whether its first argument is <, >, or == its second
192 * argument (like strcmp, e.g.). fdup is a function to call when a duplicate
193 * node is inserted. it should return 0, or -1 and its return value
194 * will be the return value from avl_insert in the case of a duplicate node.
195 * the function will be called with the original node's data as its first
196 * argument and with the incoming duplicate node's data as its second
197 * argument. this could be used, for example, to keep a count with each
200 * NOTE: this routine may malloc memory
203 avl_insert( root, data, fcmp, fdup )
211 return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
215 * right_balance() - called from delete when root's right subtree has
216 * been shortened because of a deletion.
220 right_balance( root )
226 switch( (*root)->avl_bf ) {
227 case RH: /* was right high - equal now */
228 (*root)->avl_bf = EH;
231 case EH: /* was equal - left high now */
232 (*root)->avl_bf = LH;
235 case LH: /* was right high - balance */
236 l = (*root)->avl_left;
237 switch ( l->avl_bf ) {
238 case RH : /* double rotation left */
240 switch ( r->avl_bf ) {
242 (*root)->avl_bf = EH;
246 (*root)->avl_bf = EH;
250 (*root)->avl_bf = RH;
256 (*root)->avl_left = l;
260 case EH : /* right rotation */
261 (*root)->avl_bf = LH;
266 case LH : /* single rotation right */
267 (*root)->avl_bf = EH;
280 * left_balance() - called from delete when root's left subtree has
281 * been shortened because of a deletion.
291 switch( (*root)->avl_bf ) {
292 case LH: /* was left high - equal now */
293 (*root)->avl_bf = EH;
296 case EH: /* was equal - right high now */
297 (*root)->avl_bf = RH;
300 case RH: /* was right high - balance */
301 r = (*root)->avl_right;
302 switch ( r->avl_bf ) {
303 case LH : /* double rotation left */
305 switch ( l->avl_bf ) {
307 (*root)->avl_bf = EH;
311 (*root)->avl_bf = EH;
315 (*root)->avl_bf = LH;
321 (*root)->avl_right = r;
325 case EH : /* single rotation left */
326 (*root)->avl_bf = RH;
331 case RH : /* single rotation left */
332 (*root)->avl_bf = EH;
345 * ravl_delete() - called from avl_delete to do recursive deletion of a
346 * node from an avl tree. It finds the node recursively, deletes it,
347 * and returns shorter if the tree is shorter after the deletion and
352 ravl_delete( root, data, fcmp, 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( root, data, fcmp )
452 return( ravl_delete( root, data, fcmp, &shorter ) );
456 avl_inapply( root, fn, arg, stopflag )
463 return( AVL_NOMORE );
465 if ( root->avl_left != 0 )
466 if ( avl_inapply( root->avl_left, fn, arg, stopflag )
470 if ( (*fn)( root->avl_data, arg ) == stopflag )
473 if ( root->avl_right == 0 )
474 return( AVL_NOMORE );
476 return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
480 avl_postapply( root, fn, arg, stopflag )
487 return( AVL_NOMORE );
489 if ( root->avl_left != 0 )
490 if ( avl_postapply( root->avl_left, fn, arg, stopflag )
494 if ( root->avl_right != 0 )
495 if ( avl_postapply( root->avl_right, fn, arg, stopflag )
499 return( (*fn)( root->avl_data, arg ) );
503 avl_preapply( root, fn, arg, stopflag )
510 return( AVL_NOMORE );
512 if ( (*fn)( root->avl_data, arg ) == stopflag )
515 if ( root->avl_left != 0 )
516 if ( avl_preapply( root->avl_left, fn, arg, stopflag )
520 if ( root->avl_right == 0 )
521 return( AVL_NOMORE );
523 return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
527 * avl_apply -- avl tree root is traversed, function fn is called with
528 * arguments arg and the data portion of each node. if fn returns stopflag,
529 * the traversal is cut short, otherwise it continues. Do not use -6 as
530 * a stopflag, as this is what is used to indicate the traversal ran out
534 avl_apply( root, fn, arg, stopflag, type )
543 return( avl_inapply( root, fn, arg, stopflag ) );
545 return( avl_preapply( root, fn, arg, stopflag ) );
547 return( avl_postapply( root, fn, arg, stopflag ) );
549 fprintf( stderr, "Invalid traversal type %d\n", type );
557 * avl_prefixapply - traverse avl tree root, applying function fprefix
558 * to any nodes that match. fcmp is called with data as its first arg
559 * and the current node's data as its second arg. it should return
560 * 0 if they match, < 0 if data is less, and > 0 if data is greater.
561 * the idea is to efficiently find all nodes that are prefixes of
562 * some key... Like avl_apply, this routine also takes a stopflag
563 * and will return prematurely if fmatch returns this value. Otherwise,
564 * AVL_NOMORE is returned.
567 avl_prefixapply( root, data, fmatch, marg, fcmp, carg, stopflag )
579 return( AVL_NOMORE );
581 cmp = (*fcmp)( data, root->avl_data, carg );
583 if ( (*fmatch)( root->avl_data, marg ) == stopflag )
586 if ( root->avl_left != 0 )
587 if ( avl_prefixapply( root->avl_left, data, fmatch,
588 marg, fcmp, carg, stopflag ) == stopflag )
591 if ( root->avl_right != 0 )
592 return( avl_prefixapply( root->avl_right, data, fmatch,
593 marg, fcmp, carg, stopflag ) );
595 return( AVL_NOMORE );
597 } else if ( cmp < 0 ) {
598 if ( root->avl_left != 0 )
599 return( avl_prefixapply( root->avl_left, data, fmatch,
600 marg, fcmp, carg, stopflag ) );
602 if ( root->avl_right != 0 )
603 return( avl_prefixapply( root->avl_right, data, fmatch,
604 marg, fcmp, carg, stopflag ) );
607 return( AVL_NOMORE );
611 * avl_free -- traverse avltree root, freeing the memory it is using.
612 * the dfree() is called to free the data portion of each node. The
613 * number of items actually freed is returned.
616 avl_free( root, dfree )
626 if ( root->avl_left != 0 )
627 nleft = avl_free( root->avl_left, dfree );
629 if ( root->avl_right != 0 )
630 nright = avl_free( root->avl_right, dfree );
633 (*dfree)( root->avl_data );
635 return( nleft + nright + 1 );
639 * avl_find -- search avltree root for a node with data data. the function
640 * cmp is used to compare things. it is called with data as its first arg
641 * and the current node data as its second. it should return 0 if they match,
642 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
646 avl_find( root, data, fcmp )
653 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
655 root = root->avl_left;
657 root = root->avl_right;
660 return( root ? root->avl_data : 0 );
664 * avl_find_lin -- search avltree root linearly for a node with data data.
665 * the function cmp is used to compare things. it is called with data as its
666 * first arg and the current node data as its second. it should return 0 if
667 * they match, non-zero otherwise.
671 avl_find_lin( root, data, fcmp )
681 if ( (*fcmp)( data, root->avl_data ) == 0 )
682 return( root->avl_data );
684 if ( root->avl_left != 0 )
685 if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
689 if ( root->avl_right == 0 )
692 return( avl_find_lin( root->avl_right, data, fcmp ) );
695 static caddr_t *avl_list;
696 static int avl_maxlist;
697 static int avl_nextlist;
699 #define AVL_GRABSIZE 100
703 avl_buildlist( data, arg )
709 if ( avl_list == (caddr_t *) 0 ) {
710 avl_list = (caddr_t *) malloc(AVL_GRABSIZE * sizeof(caddr_t));
711 slots = AVL_GRABSIZE;
713 } else if ( avl_maxlist == slots ) {
714 slots += AVL_GRABSIZE;
715 avl_list = (caddr_t *) realloc( (char *) avl_list,
716 (unsigned) slots * sizeof(caddr_t));
719 avl_list[ avl_maxlist++ ] = data;
725 * avl_getfirst() and avl_getnext() are provided as alternate tree
726 * traversal methods, to be used when a single function cannot be
727 * provided to be called with every node in the tree. avl_getfirst()
728 * traverses the tree and builds a linear list of all the nodes,
729 * returning the first node. avl_getnext() returns the next thing
730 * on the list built by avl_getfirst(). This means that avl_getfirst()
731 * can take a while, and that the tree should not be messed with while
732 * being traversed in this way, and that multiple traversals (even of
733 * different trees) cannot be active at once.
741 free( (char *) avl_list);
742 avl_list = (caddr_t *) 0;
750 (void) avl_apply( root, avl_buildlist, (caddr_t) 0, -1, AVL_INORDER );
752 return( avl_list[ avl_nextlist++ ] );
761 if ( avl_nextlist == avl_maxlist ) {
762 free( (caddr_t) avl_list);
763 avl_list = (caddr_t *) 0;
767 return( avl_list[ avl_nextlist++ ] );