1 /* avl.c - routines to implement an avl tree */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 1998-2022 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
16 /* Portions Copyright (c) 1993 Regents of the University of Michigan.
17 * All rights reserved.
19 * Redistribution and use in source and binary forms are permitted
20 * provided that this notice is preserved and that due credit is given
21 * to the University of Michigan at Ann Arbor. The name of the University
22 * may not be used to endorse or promote products derived from this
23 * software without specific prior written permission. This software
24 * is provided ``as is'' without express or implied warranty.
27 * This work was originally developed by the University of Michigan
28 * (as part of U-MICH LDAP). Additional significant contributors
31 * Hallvard B. Furuseth
39 #include <ac/stdlib.h>
42 #define ber_memalloc malloc
43 #define ber_memrealloc realloc
44 #define ber_memfree free
52 /* Maximum tree depth this host's address space could support */
53 #define MAX_TREE_DEPTH (sizeof(void *) * CHAR_BIT)
55 static const int avl_bfs
[] = {LH
, RH
};
58 * ldap_avl_insert -- insert a node containing data data into the avl tree
59 * with root root. fcmp is a function to call to compare the data portion
60 * of two nodes. it should take two arguments and return <, >, or == 0,
61 * depending on whether its first argument is <, >, or == its second
62 * argument (like strcmp, e.g.). fdup is a function to call when a duplicate
63 * node is inserted. it should return 0, or -1 and its return value
64 * will be the return value from ldap_avl_insert in the case of a duplicate node.
65 * the function will be called with the original node's data as its first
66 * argument and with the incoming duplicate node's data as its second
67 * argument. this could be used, for example, to keep a count with each
70 * NOTE: this routine may malloc memory
73 ldap_avl_insert( Avlnode
** root
, void *data
, AVL_CMP fcmp
, AVL_DUP fdup
)
75 Avlnode
*t
, *p
, *s
, *q
, *r
;
78 if ( *root
== NULL
) {
79 if (( r
= (Avlnode
*) ber_memalloc( sizeof( Avlnode
))) == NULL
) {
82 r
->avl_link
[0] = r
->avl_link
[1] = NULL
;
84 r
->avl_bits
[0] = r
->avl_bits
[1] = AVL_CHILD
;
94 /* find insertion point */
96 cmp
= fcmp( data
, p
->avl_data
);
98 return (*fdup
)( p
->avl_data
, data
);
101 q
= p
->avl_link
[cmp
];
104 if (( q
= (Avlnode
*) ber_memalloc( sizeof( Avlnode
))) == NULL
) {
107 q
->avl_link
[0] = q
->avl_link
[1] = NULL
;
109 q
->avl_bits
[0] = q
->avl_bits
[1] = AVL_CHILD
;
112 p
->avl_link
[cmp
] = q
;
114 } else if ( q
->avl_bf
) {
121 /* adjust balance factors */
122 cmp
= fcmp( data
, s
->avl_data
) > 0;
123 r
= p
= s
->avl_link
[cmp
];
127 cmp
= fcmp( data
, p
->avl_data
) > 0;
128 p
->avl_bf
= avl_bfs
[cmp
];
129 p
= p
->avl_link
[cmp
];
132 /* checks and balances */
134 if ( s
->avl_bf
== EH
) {
137 } else if ( s
->avl_bf
== -a
) {
140 } else if ( s
->avl_bf
== a
) {
143 if ( r
->avl_bf
== a
) {
144 /* single rotation */
146 s
->avl_link
[cmp
] = r
->avl_link
[ncmp
];
147 r
->avl_link
[ncmp
] = s
;
150 } else if ( r
->avl_bf
== -a
) {
151 /* double rotation */
152 p
= r
->avl_link
[ncmp
];
153 r
->avl_link
[ncmp
] = p
->avl_link
[cmp
];
154 p
->avl_link
[cmp
] = r
;
155 s
->avl_link
[cmp
] = p
->avl_link
[ncmp
];
156 p
->avl_link
[ncmp
] = s
;
158 if ( p
->avl_bf
== a
) {
161 } else if ( p
->avl_bf
== -a
) {
173 else if ( s
== t
->avl_right
)
183 ldap_avl_delete( Avlnode
**root
, void* data
, AVL_CMP fcmp
)
185 Avlnode
*p
, *q
, *r
, *top
;
186 int side
, side_bf
, shorter
, nside
;
189 Avlnode
*pptr
[MAX_TREE_DEPTH
];
190 unsigned char pdir
[MAX_TREE_DEPTH
];
199 side
= fcmp( data
, p
->avl_data
);
206 p
= p
->avl_link
[side
];
212 /* If this node has two children, swap so we are deleting a node with
215 if ( p
->avl_link
[0] && p
->avl_link
[1] ) {
217 /* find the immediate predecessor <q> */
221 while (q
->avl_link
[1]) {
228 p
->avl_link
[0] = q
->avl_link
[0];
231 q
->avl_link
[1] = p
->avl_link
[1];
232 p
->avl_link
[1] = NULL
;
234 q
->avl_bf
= p
->avl_bf
;
236 /* fix stack positions: old parent of p points to q */
240 r
->avl_link
[pdir
[side
-1]] = q
;
244 /* new parent of p points to p */
245 if ( depth
-side
> 1 ) {
253 /* now <p> has at most one child, get it */
254 q
= p
->avl_link
[0] ? p
->avl_link
[0] : p
->avl_link
[1];
263 /* set the child into p's parent */
267 p
->avl_link
[side
] = q
;
276 side_bf
= avl_bfs
[side
];
278 /* case 1: height unchanged */
279 if ( p
->avl_bf
== EH
) {
280 /* Tree is now heavier on opposite side */
281 p
->avl_bf
= avl_bfs
[nside
];
284 } else if ( p
->avl_bf
== side_bf
) {
285 /* case 2: taller subtree shortened, height reduced */
288 /* case 3: shorter subtree shortened */
290 top
= pptr
[depth
-1]; /* p->parent; */
293 /* set <q> to the taller of the two subtrees of <p> */
294 q
= p
->avl_link
[nside
];
295 if ( q
->avl_bf
== EH
) {
296 /* case 3a: height unchanged, single rotate */
297 p
->avl_link
[nside
] = q
->avl_link
[side
];
298 q
->avl_link
[side
] = p
;
301 p
->avl_bf
= (- side_bf
);
303 } else if ( q
->avl_bf
== p
->avl_bf
) {
304 /* case 3b: height reduced, single rotate */
305 p
->avl_link
[nside
] = q
->avl_link
[side
];
306 q
->avl_link
[side
] = p
;
312 /* case 3c: height reduced, balance factors opposite */
313 r
= q
->avl_link
[side
];
314 q
->avl_link
[side
] = r
->avl_link
[nside
];
315 r
->avl_link
[nside
] = q
;
317 p
->avl_link
[nside
] = r
->avl_link
[side
];
318 r
->avl_link
[side
] = p
;
320 if ( r
->avl_bf
== side_bf
) {
321 q
->avl_bf
= (- side_bf
);
323 } else if ( r
->avl_bf
== (- side_bf
)) {
333 /* a rotation has caused <q> (or <r> in case 3c) to become
334 * the root. let <p>'s former parent know this.
338 } else if (top
->avl_link
[0] == p
) {
339 top
->avl_link
[0] = q
;
341 top
->avl_link
[1] = q
;
349 } /* end while(shorter) */
355 avl_inapply( Avlnode
*root
, AVL_APPLY fn
, void* arg
, int stopflag
)
358 return( AVL_NOMORE
);
360 if ( root
->avl_left
!= 0 )
361 if ( avl_inapply( root
->avl_left
, fn
, arg
, stopflag
)
365 if ( (*fn
)( root
->avl_data
, arg
) == stopflag
)
368 if ( root
->avl_right
== 0 )
369 return( AVL_NOMORE
);
371 return( avl_inapply( root
->avl_right
, fn
, arg
, stopflag
) );
375 avl_postapply( Avlnode
*root
, AVL_APPLY fn
, void* arg
, int stopflag
)
378 return( AVL_NOMORE
);
380 if ( root
->avl_left
!= 0 )
381 if ( avl_postapply( root
->avl_left
, fn
, arg
, stopflag
)
385 if ( root
->avl_right
!= 0 )
386 if ( avl_postapply( root
->avl_right
, fn
, arg
, stopflag
)
390 return( (*fn
)( root
->avl_data
, arg
) );
394 avl_preapply( Avlnode
*root
, AVL_APPLY fn
, void* arg
, int stopflag
)
397 return( AVL_NOMORE
);
399 if ( (*fn
)( root
->avl_data
, arg
) == stopflag
)
402 if ( root
->avl_left
!= 0 )
403 if ( avl_preapply( root
->avl_left
, fn
, arg
, stopflag
)
407 if ( root
->avl_right
== 0 )
408 return( AVL_NOMORE
);
410 return( avl_preapply( root
->avl_right
, fn
, arg
, stopflag
) );
414 * ldap_avl_apply -- avl tree root is traversed, function fn is called with
415 * arguments arg and the data portion of each node. if fn returns stopflag,
416 * the traversal is cut short, otherwise it continues. Do not use -6 as
417 * a stopflag, as this is what is used to indicate the traversal ran out
422 ldap_avl_apply( Avlnode
*root
, AVL_APPLY fn
, void* arg
, int stopflag
, int type
)
426 return( avl_inapply( root
, fn
, arg
, stopflag
) );
428 return( avl_preapply( root
, fn
, arg
, stopflag
) );
430 return( avl_postapply( root
, fn
, arg
, stopflag
) );
432 fprintf( stderr
, "Invalid traversal type %d\n", type
);
440 * ldap_avl_prefixapply - traverse avl tree root, applying function fprefix
441 * to any nodes that match. fcmp is called with data as its first arg
442 * and the current node's data as its second arg. it should return
443 * 0 if they match, < 0 if data is less, and > 0 if data is greater.
444 * the idea is to efficiently find all nodes that are prefixes of
445 * some key... Like ldap_avl_apply, this routine also takes a stopflag
446 * and will return prematurely if fmatch returns this value. Otherwise,
447 * AVL_NOMORE is returned.
451 ldap_avl_prefixapply(
464 return( AVL_NOMORE
);
466 cmp
= (*fcmp
)( data
, root
->avl_data
/* , carg */);
468 if ( (*fmatch
)( root
->avl_data
, marg
) == stopflag
)
471 if ( root
->avl_left
!= 0 )
472 if ( ldap_avl_prefixapply( root
->avl_left
, data
, fmatch
,
473 marg
, fcmp
, carg
, stopflag
) == stopflag
)
476 if ( root
->avl_right
!= 0 )
477 return( ldap_avl_prefixapply( root
->avl_right
, data
, fmatch
,
478 marg
, fcmp
, carg
, stopflag
) );
480 return( AVL_NOMORE
);
482 } else if ( cmp
< 0 ) {
483 if ( root
->avl_left
!= 0 )
484 return( ldap_avl_prefixapply( root
->avl_left
, data
, fmatch
,
485 marg
, fcmp
, carg
, stopflag
) );
487 if ( root
->avl_right
!= 0 )
488 return( ldap_avl_prefixapply( root
->avl_right
, data
, fmatch
,
489 marg
, fcmp
, carg
, stopflag
) );
492 return( AVL_NOMORE
);
496 * ldap_avl_free -- traverse avltree root, freeing the memory it is using.
497 * the dfree() is called to free the data portion of each node. The
498 * number of items actually freed is returned.
502 ldap_avl_free( Avlnode
*root
, AVL_FREE dfree
)
510 if ( root
->avl_left
!= 0 )
511 nleft
= ldap_avl_free( root
->avl_left
, dfree
);
513 if ( root
->avl_right
!= 0 )
514 nright
= ldap_avl_free( root
->avl_right
, dfree
);
517 (*dfree
)( root
->avl_data
);
520 return( nleft
+ nright
+ 1 );
524 * ldap_avl_find -- search avltree root for a node with data data. the function
525 * cmp is used to compare things. it is called with data as its first arg
526 * and the current node data as its second. it should return 0 if they match,
527 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
531 ldap_avl_find2( Avlnode
*root
, const void *data
, AVL_CMP fcmp
)
535 while ( root
!= 0 && (cmp
= (*fcmp
)( data
, root
->avl_data
)) != 0 ) {
537 root
= root
->avl_link
[cmp
];
543 ldap_avl_find( Avlnode
*root
, const void* data
, AVL_CMP fcmp
)
547 while ( root
!= 0 && (cmp
= (*fcmp
)( data
, root
->avl_data
)) != 0 ) {
549 root
= root
->avl_link
[cmp
];
552 return( root
? root
->avl_data
: 0 );
556 * ldap_avl_find_lin -- search avltree root linearly for a node with data data.
557 * the function cmp is used to compare things. it is called with data as its
558 * first arg and the current node data as its second. it should return 0 if
559 * they match, non-zero otherwise.
563 ldap_avl_find_lin( Avlnode
*root
, const void* data
, AVL_CMP fcmp
)
570 if ( (*fcmp
)( data
, root
->avl_data
) == 0 )
571 return( root
->avl_data
);
573 if ( root
->avl_left
!= 0 )
574 if ( (res
= ldap_avl_find_lin( root
->avl_left
, data
, fcmp
))
578 if ( root
->avl_right
== 0 )
581 return( ldap_avl_find_lin( root
->avl_right
, data
, fcmp
) );
584 /* NON-REENTRANT INTERFACE */
586 static void* *avl_list
;
587 static int avl_maxlist
;
588 static int ldap_avl_nextlist
;
590 #define AVL_GRABSIZE 100
594 avl_buildlist( void* data
, void* arg
)
598 if ( avl_list
== (void* *) 0 ) {
599 avl_list
= (void* *) ber_memalloc(AVL_GRABSIZE
* sizeof(void*));
600 slots
= AVL_GRABSIZE
;
602 } else if ( avl_maxlist
== slots
) {
603 slots
+= AVL_GRABSIZE
;
604 avl_list
= (void* *) ber_memrealloc( (char *) avl_list
,
605 (unsigned) slots
* sizeof(void*));
608 avl_list
[ avl_maxlist
++ ] = data
;
614 * ldap_avl_getfirst() and ldap_avl_getnext() are provided as alternate tree
615 * traversal methods, to be used when a single function cannot be
616 * provided to be called with every node in the tree. ldap_avl_getfirst()
617 * traverses the tree and builds a linear list of all the nodes,
618 * returning the first node. ldap_avl_getnext() returns the next thing
619 * on the list built by ldap_avl_getfirst(). This means that ldap_avl_getfirst()
620 * can take a while, and that the tree should not be messed with while
621 * being traversed in this way, and that multiple traversals (even of
622 * different trees) cannot be active at once.
626 ldap_avl_getfirst( Avlnode
*root
)
629 ber_memfree( (char *) avl_list
);
630 avl_list
= (void* *) 0;
633 ldap_avl_nextlist
= 0;
638 (void) ldap_avl_apply( root
, avl_buildlist
, (void*) 0, -1, AVL_INORDER
);
640 return( avl_list
[ ldap_avl_nextlist
++ ] );
644 ldap_avl_getnext( void )
649 if ( ldap_avl_nextlist
== avl_maxlist
) {
650 ber_memfree( (void*) avl_list
);
651 avl_list
= (void* *) 0;
655 return( avl_list
[ ldap_avl_nextlist
++ ] );
658 /* end non-reentrant code */
662 ldap_avl_dup_error( void* left
, void* right
)
668 ldap_avl_dup_ok( void* left
, void* right
)