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