1 /* avl.c - routines to implement an avl tree */
2 /* $OpenLDAP$ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2005-2020 The OpenLDAP Foundation.
6 * Portions Copyright (c) 2005 by Howard Chu, Symas Corp.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted only as authorized by the OpenLDAP
11 * Public License.
12 *
13 * A copy of this license is available in the file LICENSE in the
14 * top-level directory of the distribution or, alternatively, at
15 * <http://www.OpenLDAP.org/license.html>.
16 */
17 /* ACKNOWLEDGEMENTS:
18 * This work was initially developed by Howard Chu for inclusion
19 * in OpenLDAP software.
20 */
21
22 #include "portable.h"
23
24 #include <limits.h>
25 #include <stdio.h>
26 #include <ac/stdlib.h>
27
28 #ifdef CSRIMALLOC
29 #define ber_memalloc malloc
30 #define ber_memrealloc realloc
31 #define ber_memfree free
32 #else
33 #include "lber.h"
34 #endif
35
36 #define AVL_INTERNAL
37 #include "ldap_avl.h"
38
39 /* Maximum tree depth this host's address space could support */
40 #define MAX_TREE_DEPTH (sizeof(void *) * CHAR_BIT)
41
42 static const int avl_bfs[] = {LH, RH};
43
44 /*
45 * Threaded AVL trees - for fast in-order traversal of nodes.
46 */
47 /*
48 * ldap_tavl_insert -- insert a node containing data data into the avl tree
49 * with root root. fcmp is a function to call to compare the data portion
50 * of two nodes. it should take two arguments and return <, >, or == 0,
51 * depending on whether its first argument is <, >, or == its second
52 * argument (like strcmp, e.g.). fdup is a function to call when a duplicate
53 * node is inserted. it should return 0, or -1 and its return value
54 * will be the return value from ldap_avl_insert in the case of a duplicate node.
55 * the function will be called with the original node's data as its first
56 * argument and with the incoming duplicate node's data as its second
57 * argument. this could be used, for example, to keep a count with each
58 * node.
59 *
60 * NOTE: this routine may malloc memory
61 */
62 int
ldap_tavl_insert(TAvlnode ** root,void * data,AVL_CMP fcmp,AVL_DUP fdup)63 ldap_tavl_insert( TAvlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
64 {
65 TAvlnode *t, *p, *s, *q, *r;
66 int a, cmp, ncmp;
67
68 if ( *root == NULL ) {
69 if (( r = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
70 return( -1 );
71 }
72 r->avl_link[0] = r->avl_link[1] = NULL;
73 r->avl_data = data;
74 r->avl_bf = EH;
75 r->avl_bits[0] = r->avl_bits[1] = AVL_THREAD;
76 *root = r;
77
78 return( 0 );
79 }
80
81 t = NULL;
82 s = p = *root;
83
84 /* find insertion point */
85 while (1) {
86 cmp = fcmp( data, p->avl_data );
87 if ( cmp == 0 )
88 return (*fdup)( p->avl_data, data );
89
90 cmp = (cmp > 0);
91 q = ldap_avl_child( p, cmp );
92 if (q == NULL) {
93 /* insert */
94 if (( q = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
95 return( -1 );
96 }
97 q->avl_link[cmp] = p->avl_link[cmp];
98 q->avl_link[!cmp] = p;
99 q->avl_data = data;
100 q->avl_bf = EH;
101 q->avl_bits[0] = q->avl_bits[1] = AVL_THREAD;
102
103 p->avl_link[cmp] = q;
104 p->avl_bits[cmp] = AVL_CHILD;
105 break;
106 } else if ( q->avl_bf ) {
107 t = p;
108 s = q;
109 }
110 p = q;
111 }
112
113 /* adjust balance factors */
114 cmp = fcmp( data, s->avl_data ) > 0;
115 r = p = s->avl_link[cmp];
116 a = avl_bfs[cmp];
117
118 while ( p != q ) {
119 cmp = fcmp( data, p->avl_data ) > 0;
120 p->avl_bf = avl_bfs[cmp];
121 p = p->avl_link[cmp];
122 }
123
124 /* checks and balances */
125
126 if ( s->avl_bf == EH ) {
127 s->avl_bf = a;
128 return 0;
129 } else if ( s->avl_bf == -a ) {
130 s->avl_bf = EH;
131 return 0;
132 } else if ( s->avl_bf == a ) {
133 cmp = (a > 0);
134 ncmp = !cmp;
135 if ( r->avl_bf == a ) {
136 /* single rotation */
137 p = r;
138 if ( r->avl_bits[ncmp] == AVL_THREAD ) {
139 r->avl_bits[ncmp] = AVL_CHILD;
140 s->avl_bits[cmp] = AVL_THREAD;
141 } else {
142 s->avl_link[cmp] = r->avl_link[ncmp];
143 r->avl_link[ncmp] = s;
144 }
145 s->avl_bf = 0;
146 r->avl_bf = 0;
147 } else if ( r->avl_bf == -a ) {
148 /* double rotation */
149 p = r->avl_link[ncmp];
150 if ( p->avl_bits[cmp] == AVL_THREAD ) {
151 p->avl_bits[cmp] = AVL_CHILD;
152 r->avl_bits[ncmp] = AVL_THREAD;
153 } else {
154 r->avl_link[ncmp] = p->avl_link[cmp];
155 p->avl_link[cmp] = r;
156 }
157 if ( p->avl_bits[ncmp] == AVL_THREAD ) {
158 p->avl_bits[ncmp] = AVL_CHILD;
159 s->avl_link[cmp] = p;
160 s->avl_bits[cmp] = AVL_THREAD;
161 } else {
162 s->avl_link[cmp] = p->avl_link[ncmp];
163 p->avl_link[ncmp] = s;
164 }
165 if ( p->avl_bf == a ) {
166 s->avl_bf = -a;
167 r->avl_bf = 0;
168 } else if ( p->avl_bf == -a ) {
169 s->avl_bf = 0;
170 r->avl_bf = a;
171 } else {
172 s->avl_bf = 0;
173 r->avl_bf = 0;
174 }
175 p->avl_bf = 0;
176 }
177 /* Update parent */
178 if ( t == NULL )
179 *root = p;
180 else if ( s == t->avl_right )
181 t->avl_right = p;
182 else
183 t->avl_left = p;
184 }
185
186 return 0;
187 }
188
189 void*
ldap_tavl_delete(TAvlnode ** root,void * data,AVL_CMP fcmp)190 ldap_tavl_delete( TAvlnode **root, void* data, AVL_CMP fcmp )
191 {
192 TAvlnode *p, *q, *r, *top;
193 int side, side_bf, shorter, nside = -1;
194
195 /* parent stack */
196 TAvlnode *pptr[MAX_TREE_DEPTH];
197 unsigned char pdir[MAX_TREE_DEPTH];
198 int depth = 0;
199
200 if ( *root == NULL )
201 return NULL;
202
203 p = *root;
204
205 while (1) {
206 side = fcmp( data, p->avl_data );
207 if ( !side )
208 break;
209 side = ( side > 0 );
210 pdir[depth] = side;
211 pptr[depth++] = p;
212
213 if ( p->avl_bits[side] == AVL_THREAD )
214 return NULL;
215 p = p->avl_link[side];
216 }
217 data = p->avl_data;
218
219 /* If this node has two children, swap so we are deleting a node with
220 * at most one child.
221 */
222 if ( p->avl_bits[0] == AVL_CHILD && p->avl_bits[1] == AVL_CHILD &&
223 p->avl_link[0] && p->avl_link[1] ) {
224
225 /* find the immediate predecessor <q> */
226 q = p->avl_link[0];
227 side = depth;
228 pdir[depth++] = 0;
229 while (q->avl_bits[1] == AVL_CHILD && q->avl_link[1]) {
230 pdir[depth] = 1;
231 pptr[depth++] = q;
232 q = q->avl_link[1];
233 }
234 /* swap links */
235 r = p->avl_link[0];
236 p->avl_link[0] = q->avl_link[0];
237 q->avl_link[0] = r;
238
239 q->avl_link[1] = p->avl_link[1];
240 p->avl_link[1] = q;
241
242 p->avl_bits[0] = q->avl_bits[0];
243 p->avl_bits[1] = q->avl_bits[1];
244 q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD;
245
246 q->avl_bf = p->avl_bf;
247
248 /* fix stack positions: old parent of p points to q */
249 pptr[side] = q;
250 if ( side ) {
251 r = pptr[side-1];
252 r->avl_link[pdir[side-1]] = q;
253 } else {
254 *root = q;
255 }
256 /* new parent of p points to p */
257 if ( depth-side > 1 ) {
258 r = pptr[depth-1];
259 r->avl_link[1] = p;
260 } else {
261 q->avl_link[0] = p;
262 }
263
264 /* fix right subtree: successor of p points to q */
265 r = q->avl_link[1];
266 while ( r->avl_bits[0] == AVL_CHILD && r->avl_link[0] )
267 r = r->avl_link[0];
268 r->avl_link[0] = q;
269 }
270
271 /* now <p> has at most one child, get it */
272 if ( p->avl_link[0] && p->avl_bits[0] == AVL_CHILD ) {
273 q = p->avl_link[0];
274 /* Preserve thread continuity */
275 r = p->avl_link[1];
276 nside = 1;
277 } else if ( p->avl_link[1] && p->avl_bits[1] == AVL_CHILD ) {
278 q = p->avl_link[1];
279 r = p->avl_link[0];
280 nside = 0;
281 } else {
282 q = NULL;
283 if ( depth > 0 )
284 r = p->avl_link[pdir[depth-1]];
285 else
286 r = NULL;
287 }
288
289 ber_memfree( p );
290
291 /* Update child thread */
292 if ( q ) {
293 for ( ; q->avl_bits[nside] == AVL_CHILD && q->avl_link[nside];
294 q = q->avl_link[nside] ) ;
295 q->avl_link[nside] = r;
296 }
297
298 if ( !depth ) {
299 *root = q;
300 return data;
301 }
302
303 /* set the child into p's parent */
304 depth--;
305 p = pptr[depth];
306 side = pdir[depth];
307 p->avl_link[side] = q;
308
309 if ( !q ) {
310 p->avl_bits[side] = AVL_THREAD;
311 p->avl_link[side] = r;
312 }
313
314 top = NULL;
315 shorter = 1;
316
317 while ( shorter ) {
318 p = pptr[depth];
319 side = pdir[depth];
320 nside = !side;
321 side_bf = avl_bfs[side];
322
323 /* case 1: height unchanged */
324 if ( p->avl_bf == EH ) {
325 /* Tree is now heavier on opposite side */
326 p->avl_bf = avl_bfs[nside];
327 shorter = 0;
328
329 } else if ( p->avl_bf == side_bf ) {
330 /* case 2: taller subtree shortened, height reduced */
331 p->avl_bf = EH;
332 } else {
333 /* case 3: shorter subtree shortened */
334 if ( depth )
335 top = pptr[depth-1]; /* p->parent; */
336 else
337 top = NULL;
338 /* set <q> to the taller of the two subtrees of <p> */
339 q = p->avl_link[nside];
340 if ( q->avl_bf == EH ) {
341 /* case 3a: height unchanged, single rotate */
342 if ( q->avl_bits[side] == AVL_THREAD ) {
343 q->avl_bits[side] = AVL_CHILD;
344 p->avl_bits[nside] = AVL_THREAD;
345 } else {
346 p->avl_link[nside] = q->avl_link[side];
347 q->avl_link[side] = p;
348 }
349 shorter = 0;
350 q->avl_bf = side_bf;
351 p->avl_bf = (- side_bf);
352
353 } else if ( q->avl_bf == p->avl_bf ) {
354 /* case 3b: height reduced, single rotate */
355 if ( q->avl_bits[side] == AVL_THREAD ) {
356 q->avl_bits[side] = AVL_CHILD;
357 p->avl_bits[nside] = AVL_THREAD;
358 } else {
359 p->avl_link[nside] = q->avl_link[side];
360 q->avl_link[side] = p;
361 }
362 shorter = 1;
363 q->avl_bf = EH;
364 p->avl_bf = EH;
365
366 } else {
367 /* case 3c: height reduced, balance factors opposite */
368 r = q->avl_link[side];
369 if ( r->avl_bits[nside] == AVL_THREAD ) {
370 r->avl_bits[nside] = AVL_CHILD;
371 q->avl_bits[side] = AVL_THREAD;
372 } else {
373 q->avl_link[side] = r->avl_link[nside];
374 r->avl_link[nside] = q;
375 }
376
377 if ( r->avl_bits[side] == AVL_THREAD ) {
378 r->avl_bits[side] = AVL_CHILD;
379 p->avl_bits[nside] = AVL_THREAD;
380 p->avl_link[nside] = r;
381 } else {
382 p->avl_link[nside] = r->avl_link[side];
383 r->avl_link[side] = p;
384 }
385
386 if ( r->avl_bf == side_bf ) {
387 q->avl_bf = (- side_bf);
388 p->avl_bf = EH;
389 } else if ( r->avl_bf == (- side_bf)) {
390 q->avl_bf = EH;
391 p->avl_bf = side_bf;
392 } else {
393 q->avl_bf = EH;
394 p->avl_bf = EH;
395 }
396 r->avl_bf = EH;
397 q = r;
398 }
399 /* a rotation has caused <q> (or <r> in case 3c) to become
400 * the root. let <p>'s former parent know this.
401 */
402 if ( top == NULL ) {
403 *root = q;
404 } else if (top->avl_link[0] == p) {
405 top->avl_link[0] = q;
406 } else {
407 top->avl_link[1] = q;
408 }
409 /* end case 3 */
410 p = q;
411 }
412 if ( !depth )
413 break;
414 depth--;
415 } /* end while(shorter) */
416
417 return data;
418 }
419
420 /*
421 * ldap_tavl_free -- traverse avltree root, freeing the memory it is using.
422 * the dfree() is called to free the data portion of each node. The
423 * number of items actually freed is returned.
424 */
425
426 int
ldap_tavl_free(TAvlnode * root,AVL_FREE dfree)427 ldap_tavl_free( TAvlnode *root, AVL_FREE dfree )
428 {
429 int nleft, nright;
430
431 if ( root == 0 )
432 return( 0 );
433
434 nleft = ldap_tavl_free( ldap_avl_lchild( root ), dfree );
435
436 nright = ldap_tavl_free( ldap_avl_rchild( root ), dfree );
437
438 if ( dfree )
439 (*dfree)( root->avl_data );
440 ber_memfree( root );
441
442 return( nleft + nright + 1 );
443 }
444
445 /*
446 * ldap_tavl_find -- search avltree root for a node with data data. the function
447 * cmp is used to compare things. it is called with data as its first arg
448 * and the current node data as its second. it should return 0 if they match,
449 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
450 */
451
452 /*
453 * ldap_tavl_find2 - returns TAvlnode instead of data pointer.
454 * ldap_tavl_find3 - as above, but returns TAvlnode even if no match is found.
455 * also set *ret = last comparison result, or -1 if root == NULL.
456 */
457 TAvlnode *
ldap_tavl_find3(TAvlnode * root,const void * data,AVL_CMP fcmp,int * ret)458 ldap_tavl_find3( TAvlnode *root, const void *data, AVL_CMP fcmp, int *ret )
459 {
460 int cmp = -1, dir;
461 TAvlnode *prev = root;
462
463 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
464 prev = root;
465 dir = cmp > 0;
466 root = ldap_avl_child( root, dir );
467 }
468 *ret = cmp;
469 return root ? root : prev;
470 }
471
472 TAvlnode *
ldap_tavl_find2(TAvlnode * root,const void * data,AVL_CMP fcmp)473 ldap_tavl_find2( TAvlnode *root, const void *data, AVL_CMP fcmp )
474 {
475 int cmp;
476
477 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
478 cmp = cmp > 0;
479 root = ldap_avl_child( root, cmp );
480 }
481 return root;
482 }
483
484 void*
ldap_tavl_find(TAvlnode * root,const void * data,AVL_CMP fcmp)485 ldap_tavl_find( TAvlnode *root, const void* data, AVL_CMP fcmp )
486 {
487 int cmp;
488
489 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
490 cmp = cmp > 0;
491 root = ldap_avl_child( root, cmp );
492 }
493
494 return( root ? root->avl_data : 0 );
495 }
496
497 /* Return the leftmost or rightmost node in the tree */
498 TAvlnode *
ldap_tavl_end(TAvlnode * root,int dir)499 ldap_tavl_end( TAvlnode *root, int dir )
500 {
501 if ( root ) {
502 while ( root->avl_bits[dir] == AVL_CHILD )
503 root = root->avl_link[dir];
504 }
505 return root;
506 }
507
508 /* Return the next node in the given direction */
509 TAvlnode *
ldap_tavl_next(TAvlnode * root,int dir)510 ldap_tavl_next( TAvlnode *root, int dir )
511 {
512 if ( root ) {
513 int c = root->avl_bits[dir];
514
515 root = root->avl_link[dir];
516 if ( c == AVL_CHILD ) {
517 dir ^= 1;
518 while ( root->avl_bits[dir] == AVL_CHILD )
519 root = root->avl_link[dir];
520 }
521 }
522 return root;
523 }
524