1/* $NetBSD: avl.c,v 1.2 2021/08/14 16:14:55 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 1998-2020 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18/* Portions Copyright (c) 1993 Regents of the University of Michigan. 19 * All rights reserved. 20 * 21 * Redistribution and use in source and binary forms are permitted 22 * provided that this notice is preserved and that due credit is given 23 * to the University of Michigan at Ann Arbor. The name of the University 24 * may not be used to endorse or promote products derived from this 25 * software without specific prior written permission. This software 26 * is provided ``as is'' without express or implied warranty. 27 */ 28/* ACKNOWLEDGEMENTS: 29 * This work was originally developed by the University of Michigan 30 * (as part of U-MICH LDAP). Additional significant contributors 31 * include: 32 * Howard Y. Chu 33 * Hallvard B. Furuseth 34 * Kurt D. Zeilenga 35 */ 36 37#include <sys/cdefs.h> 38__RCSID("$NetBSD: avl.c,v 1.2 2021/08/14 16:14:55 christos Exp $"); 39 40#include "portable.h" 41 42#include <limits.h> 43#include <stdio.h> 44#include <ac/stdlib.h> 45 46#ifdef CSRIMALLOC 47#define ber_memalloc malloc 48#define ber_memrealloc realloc 49#define ber_memfree free 50#else 51#include "lber.h" 52#endif 53 54#define AVL_INTERNAL 55#include "ldap_avl.h" 56 57/* Maximum tree depth this host's address space could support */ 58#define MAX_TREE_DEPTH (sizeof(void *) * CHAR_BIT) 59 60static const int avl_bfs[] = {LH, RH}; 61 62/* 63 * ldap_avl_insert -- insert a node containing data data into the avl tree 64 * with root root. fcmp is a function to call to compare the data portion 65 * of two nodes. it should take two arguments and return <, >, or == 0, 66 * depending on whether its first argument is <, >, or == its second 67 * argument (like strcmp, e.g.). fdup is a function to call when a duplicate 68 * node is inserted. it should return 0, or -1 and its return value 69 * will be the return value from ldap_avl_insert in the case of a duplicate node. 70 * the function will be called with the original node's data as its first 71 * argument and with the incoming duplicate node's data as its second 72 * argument. this could be used, for example, to keep a count with each 73 * node. 74 * 75 * NOTE: this routine may malloc memory 76 */ 77int 78ldap_avl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup ) 79{ 80 Avlnode *t, *p, *s, *q, *r; 81 int a, cmp, ncmp; 82 83 if ( *root == NULL ) { 84 if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) { 85 return( -1 ); 86 } 87 r->avl_link[0] = r->avl_link[1] = NULL; 88 r->avl_data = data; 89 r->avl_bits[0] = r->avl_bits[1] = AVL_CHILD; 90 r->avl_bf = EH; 91 *root = r; 92 93 return( 0 ); 94 } 95 96 t = NULL; 97 s = p = *root; 98 99 /* find insertion point */ 100 while (1) { 101 cmp = fcmp( data, p->avl_data ); 102 if ( cmp == 0 ) 103 return (*fdup)( p->avl_data, data ); 104 105 cmp = (cmp > 0); 106 q = p->avl_link[cmp]; 107 if (q == NULL) { 108 /* insert */ 109 if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) { 110 return( -1 ); 111 } 112 q->avl_link[0] = q->avl_link[1] = NULL; 113 q->avl_data = data; 114 q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD; 115 q->avl_bf = EH; 116 117 p->avl_link[cmp] = q; 118 break; 119 } else if ( q->avl_bf ) { 120 t = p; 121 s = q; 122 } 123 p = q; 124 } 125 126 /* adjust balance factors */ 127 cmp = fcmp( data, s->avl_data ) > 0; 128 r = p = s->avl_link[cmp]; 129 a = avl_bfs[cmp]; 130 131 while ( p != q ) { 132 cmp = fcmp( data, p->avl_data ) > 0; 133 p->avl_bf = avl_bfs[cmp]; 134 p = p->avl_link[cmp]; 135 } 136 137 /* checks and balances */ 138 139 if ( s->avl_bf == EH ) { 140 s->avl_bf = a; 141 return 0; 142 } else if ( s->avl_bf == -a ) { 143 s->avl_bf = EH; 144 return 0; 145 } else if ( s->avl_bf == a ) { 146 cmp = (a > 0); 147 ncmp = !cmp; 148 if ( r->avl_bf == a ) { 149 /* single rotation */ 150 p = r; 151 s->avl_link[cmp] = r->avl_link[ncmp]; 152 r->avl_link[ncmp] = s; 153 s->avl_bf = 0; 154 r->avl_bf = 0; 155 } else if ( r->avl_bf == -a ) { 156 /* double rotation */ 157 p = r->avl_link[ncmp]; 158 r->avl_link[ncmp] = p->avl_link[cmp]; 159 p->avl_link[cmp] = r; 160 s->avl_link[cmp] = p->avl_link[ncmp]; 161 p->avl_link[ncmp] = s; 162 163 if ( p->avl_bf == a ) { 164 s->avl_bf = -a; 165 r->avl_bf = 0; 166 } else if ( p->avl_bf == -a ) { 167 s->avl_bf = 0; 168 r->avl_bf = a; 169 } else { 170 s->avl_bf = 0; 171 r->avl_bf = 0; 172 } 173 p->avl_bf = 0; 174 } 175 /* Update parent */ 176 if ( t == NULL ) 177 *root = p; 178 else if ( s == t->avl_right ) 179 t->avl_right = p; 180 else 181 t->avl_left = p; 182 } 183 184 return 0; 185} 186 187void* 188ldap_avl_delete( Avlnode **root, void* data, AVL_CMP fcmp ) 189{ 190 Avlnode *p, *q, *r, *top; 191 int side, side_bf, shorter, nside; 192 193 /* parent stack */ 194 Avlnode *pptr[MAX_TREE_DEPTH]; 195 unsigned char pdir[MAX_TREE_DEPTH]; 196 int depth = 0; 197 198 if ( *root == NULL ) 199 return NULL; 200 201 p = *root; 202 203 while (1) { 204 side = fcmp( data, p->avl_data ); 205 if ( !side ) 206 break; 207 side = ( side > 0 ); 208 pdir[depth] = side; 209 pptr[depth++] = p; 210 211 p = p->avl_link[side]; 212 if ( p == NULL ) 213 return p; 214 } 215 data = p->avl_data; 216 217 /* If this node has two children, swap so we are deleting a node with 218 * at most one child. 219 */ 220 if ( p->avl_link[0] && p->avl_link[1] ) { 221 222 /* find the immediate predecessor <q> */ 223 q = p->avl_link[0]; 224 side = depth; 225 pdir[depth++] = 0; 226 while (q->avl_link[1]) { 227 pdir[depth] = 1; 228 pptr[depth++] = q; 229 q = q->avl_link[1]; 230 } 231 /* swap links */ 232 r = p->avl_link[0]; 233 p->avl_link[0] = q->avl_link[0]; 234 q->avl_link[0] = r; 235 236 q->avl_link[1] = p->avl_link[1]; 237 p->avl_link[1] = NULL; 238 239 q->avl_bf = p->avl_bf; 240 241 /* fix stack positions: old parent of p points to q */ 242 pptr[side] = q; 243 if ( side ) { 244 r = pptr[side-1]; 245 r->avl_link[pdir[side-1]] = q; 246 } else { 247 *root = q; 248 } 249 /* new parent of p points to p */ 250 if ( depth-side > 1 ) { 251 r = pptr[depth-1]; 252 r->avl_link[1] = p; 253 } else { 254 q->avl_link[0] = p; 255 } 256 } 257 258 /* now <p> has at most one child, get it */ 259 q = p->avl_link[0] ? p->avl_link[0] : p->avl_link[1]; 260 261 ber_memfree( p ); 262 263 if ( !depth ) { 264 *root = q; 265 return data; 266 } 267 268 /* set the child into p's parent */ 269 depth--; 270 p = pptr[depth]; 271 side = pdir[depth]; 272 p->avl_link[side] = q; 273 274 top = NULL; 275 shorter = 1; 276 277 while ( shorter ) { 278 p = pptr[depth]; 279 side = pdir[depth]; 280 nside = !side; 281 side_bf = avl_bfs[side]; 282 283 /* case 1: height unchanged */ 284 if ( p->avl_bf == EH ) { 285 /* Tree is now heavier on opposite side */ 286 p->avl_bf = avl_bfs[nside]; 287 shorter = 0; 288 289 } else if ( p->avl_bf == side_bf ) { 290 /* case 2: taller subtree shortened, height reduced */ 291 p->avl_bf = EH; 292 } else { 293 /* case 3: shorter subtree shortened */ 294 if ( depth ) 295 top = pptr[depth-1]; /* p->parent; */ 296 else 297 top = NULL; 298 /* set <q> to the taller of the two subtrees of <p> */ 299 q = p->avl_link[nside]; 300 if ( q->avl_bf == EH ) { 301 /* case 3a: height unchanged, single rotate */ 302 p->avl_link[nside] = q->avl_link[side]; 303 q->avl_link[side] = p; 304 shorter = 0; 305 q->avl_bf = side_bf; 306 p->avl_bf = (- side_bf); 307 308 } else if ( q->avl_bf == p->avl_bf ) { 309 /* case 3b: height reduced, single rotate */ 310 p->avl_link[nside] = q->avl_link[side]; 311 q->avl_link[side] = p; 312 shorter = 1; 313 q->avl_bf = EH; 314 p->avl_bf = EH; 315 316 } else { 317 /* case 3c: height reduced, balance factors opposite */ 318 r = q->avl_link[side]; 319 q->avl_link[side] = r->avl_link[nside]; 320 r->avl_link[nside] = q; 321 322 p->avl_link[nside] = r->avl_link[side]; 323 r->avl_link[side] = p; 324 325 if ( r->avl_bf == side_bf ) { 326 q->avl_bf = (- side_bf); 327 p->avl_bf = EH; 328 } else if ( r->avl_bf == (- side_bf)) { 329 q->avl_bf = EH; 330 p->avl_bf = side_bf; 331 } else { 332 q->avl_bf = EH; 333 p->avl_bf = EH; 334 } 335 r->avl_bf = EH; 336 q = r; 337 } 338 /* a rotation has caused <q> (or <r> in case 3c) to become 339 * the root. let <p>'s former parent know this. 340 */ 341 if ( top == NULL ) { 342 *root = q; 343 } else if (top->avl_link[0] == p) { 344 top->avl_link[0] = q; 345 } else { 346 top->avl_link[1] = q; 347 } 348 /* end case 3 */ 349 p = q; 350 } 351 if ( !depth ) 352 break; 353 depth--; 354 } /* end while(shorter) */ 355 356 return data; 357} 358 359static int 360avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag ) 361{ 362 if ( root == 0 ) 363 return( AVL_NOMORE ); 364 365 if ( root->avl_left != 0 ) 366 if ( avl_inapply( root->avl_left, fn, arg, stopflag ) 367 == stopflag ) 368 return( stopflag ); 369 370 if ( (*fn)( root->avl_data, arg ) == stopflag ) 371 return( stopflag ); 372 373 if ( root->avl_right == 0 ) 374 return( AVL_NOMORE ); 375 else 376 return( avl_inapply( root->avl_right, fn, arg, stopflag ) ); 377} 378 379static int 380avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag ) 381{ 382 if ( root == 0 ) 383 return( AVL_NOMORE ); 384 385 if ( root->avl_left != 0 ) 386 if ( avl_postapply( root->avl_left, fn, arg, stopflag ) 387 == stopflag ) 388 return( stopflag ); 389 390 if ( root->avl_right != 0 ) 391 if ( avl_postapply( root->avl_right, fn, arg, stopflag ) 392 == stopflag ) 393 return( stopflag ); 394 395 return( (*fn)( root->avl_data, arg ) ); 396} 397 398static int 399avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag ) 400{ 401 if ( root == 0 ) 402 return( AVL_NOMORE ); 403 404 if ( (*fn)( root->avl_data, arg ) == stopflag ) 405 return( stopflag ); 406 407 if ( root->avl_left != 0 ) 408 if ( avl_preapply( root->avl_left, fn, arg, stopflag ) 409 == stopflag ) 410 return( stopflag ); 411 412 if ( root->avl_right == 0 ) 413 return( AVL_NOMORE ); 414 else 415 return( avl_preapply( root->avl_right, fn, arg, stopflag ) ); 416} 417 418/* 419 * ldap_avl_apply -- avl tree root is traversed, function fn is called with 420 * arguments arg and the data portion of each node. if fn returns stopflag, 421 * the traversal is cut short, otherwise it continues. Do not use -6 as 422 * a stopflag, as this is what is used to indicate the traversal ran out 423 * of nodes. 424 */ 425 426int 427ldap_avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type ) 428{ 429 switch ( type ) { 430 case AVL_INORDER: 431 return( avl_inapply( root, fn, arg, stopflag ) ); 432 case AVL_PREORDER: 433 return( avl_preapply( root, fn, arg, stopflag ) ); 434 case AVL_POSTORDER: 435 return( avl_postapply( root, fn, arg, stopflag ) ); 436 default: 437 fprintf( stderr, "Invalid traversal type %d\n", type ); 438 return( -1 ); 439 } 440 441 /* NOTREACHED */ 442} 443 444/* 445 * ldap_avl_prefixapply - traverse avl tree root, applying function fprefix 446 * to any nodes that match. fcmp is called with data as its first arg 447 * and the current node's data as its second arg. it should return 448 * 0 if they match, < 0 if data is less, and > 0 if data is greater. 449 * the idea is to efficiently find all nodes that are prefixes of 450 * some key... Like ldap_avl_apply, this routine also takes a stopflag 451 * and will return prematurely if fmatch returns this value. Otherwise, 452 * AVL_NOMORE is returned. 453 */ 454 455int 456ldap_avl_prefixapply( 457 Avlnode *root, 458 void* data, 459 AVL_CMP fmatch, 460 void* marg, 461 AVL_CMP fcmp, 462 void* carg, 463 int stopflag 464) 465{ 466 int cmp; 467 468 if ( root == 0 ) 469 return( AVL_NOMORE ); 470 471 cmp = (*fcmp)( data, root->avl_data /* , carg */); 472 if ( cmp == 0 ) { 473 if ( (*fmatch)( root->avl_data, marg ) == stopflag ) 474 return( stopflag ); 475 476 if ( root->avl_left != 0 ) 477 if ( ldap_avl_prefixapply( root->avl_left, data, fmatch, 478 marg, fcmp, carg, stopflag ) == stopflag ) 479 return( stopflag ); 480 481 if ( root->avl_right != 0 ) 482 return( ldap_avl_prefixapply( root->avl_right, data, fmatch, 483 marg, fcmp, carg, stopflag ) ); 484 else 485 return( AVL_NOMORE ); 486 487 } else if ( cmp < 0 ) { 488 if ( root->avl_left != 0 ) 489 return( ldap_avl_prefixapply( root->avl_left, data, fmatch, 490 marg, fcmp, carg, stopflag ) ); 491 } else { 492 if ( root->avl_right != 0 ) 493 return( ldap_avl_prefixapply( root->avl_right, data, fmatch, 494 marg, fcmp, carg, stopflag ) ); 495 } 496 497 return( AVL_NOMORE ); 498} 499 500/* 501 * ldap_avl_free -- traverse avltree root, freeing the memory it is using. 502 * the dfree() is called to free the data portion of each node. The 503 * number of items actually freed is returned. 504 */ 505 506int 507ldap_avl_free( Avlnode *root, AVL_FREE dfree ) 508{ 509 int nleft, nright; 510 511 if ( root == 0 ) 512 return( 0 ); 513 514 nleft = nright = 0; 515 if ( root->avl_left != 0 ) 516 nleft = ldap_avl_free( root->avl_left, dfree ); 517 518 if ( root->avl_right != 0 ) 519 nright = ldap_avl_free( root->avl_right, dfree ); 520 521 if ( dfree ) 522 (*dfree)( root->avl_data ); 523 ber_memfree( root ); 524 525 return( nleft + nright + 1 ); 526} 527 528/* 529 * ldap_avl_find -- search avltree root for a node with data data. the function 530 * cmp is used to compare things. it is called with data as its first arg 531 * and the current node data as its second. it should return 0 if they match, 532 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2. 533 */ 534 535Avlnode * 536ldap_avl_find2( Avlnode *root, const void *data, AVL_CMP fcmp ) 537{ 538 int cmp; 539 540 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) { 541 cmp = cmp > 0; 542 root = root->avl_link[cmp]; 543 } 544 return root; 545} 546 547void* 548ldap_avl_find( Avlnode *root, const void* data, AVL_CMP fcmp ) 549{ 550 int cmp; 551 552 while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) { 553 cmp = cmp > 0; 554 root = root->avl_link[cmp]; 555 } 556 557 return( root ? root->avl_data : 0 ); 558} 559 560/* 561 * ldap_avl_find_lin -- search avltree root linearly for a node with data data. 562 * the function cmp is used to compare things. it is called with data as its 563 * first arg and the current node data as its second. it should return 0 if 564 * they match, non-zero otherwise. 565 */ 566 567void* 568ldap_avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp ) 569{ 570 void* res; 571 572 if ( root == 0 ) 573 return( NULL ); 574 575 if ( (*fcmp)( data, root->avl_data ) == 0 ) 576 return( root->avl_data ); 577 578 if ( root->avl_left != 0 ) 579 if ( (res = ldap_avl_find_lin( root->avl_left, data, fcmp )) 580 != NULL ) 581 return( res ); 582 583 if ( root->avl_right == 0 ) 584 return( NULL ); 585 else 586 return( ldap_avl_find_lin( root->avl_right, data, fcmp ) ); 587} 588 589/* NON-REENTRANT INTERFACE */ 590 591static void* *avl_list; 592static int avl_maxlist; 593static int ldap_avl_nextlist; 594 595#define AVL_GRABSIZE 100 596 597/* ARGSUSED */ 598static int 599avl_buildlist( void* data, void* arg ) 600{ 601 static int slots; 602 603 if ( avl_list == (void* *) 0 ) { 604 avl_list = (void* *) ber_memalloc(AVL_GRABSIZE * sizeof(void*)); 605 slots = AVL_GRABSIZE; 606 avl_maxlist = 0; 607 } else if ( avl_maxlist == slots ) { 608 slots += AVL_GRABSIZE; 609 avl_list = (void* *) ber_memrealloc( (char *) avl_list, 610 (unsigned) slots * sizeof(void*)); 611 } 612 613 avl_list[ avl_maxlist++ ] = data; 614 615 return( 0 ); 616} 617 618/* 619 * ldap_avl_getfirst() and ldap_avl_getnext() are provided as alternate tree 620 * traversal methods, to be used when a single function cannot be 621 * provided to be called with every node in the tree. ldap_avl_getfirst() 622 * traverses the tree and builds a linear list of all the nodes, 623 * returning the first node. ldap_avl_getnext() returns the next thing 624 * on the list built by ldap_avl_getfirst(). This means that ldap_avl_getfirst() 625 * can take a while, and that the tree should not be messed with while 626 * being traversed in this way, and that multiple traversals (even of 627 * different trees) cannot be active at once. 628 */ 629 630void* 631ldap_avl_getfirst( Avlnode *root ) 632{ 633 if ( avl_list ) { 634 ber_memfree( (char *) avl_list); 635 avl_list = (void* *) 0; 636 } 637 avl_maxlist = 0; 638 ldap_avl_nextlist = 0; 639 640 if ( root == 0 ) 641 return( 0 ); 642 643 (void) ldap_avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER ); 644 645 return( avl_list[ ldap_avl_nextlist++ ] ); 646} 647 648void* 649ldap_avl_getnext( void ) 650{ 651 if ( avl_list == 0 ) 652 return( 0 ); 653 654 if ( ldap_avl_nextlist == avl_maxlist ) { 655 ber_memfree( (void*) avl_list); 656 avl_list = (void* *) 0; 657 return( 0 ); 658 } 659 660 return( avl_list[ ldap_avl_nextlist++ ] ); 661} 662 663/* end non-reentrant code */ 664 665 666int 667ldap_avl_dup_error( void* left, void* right ) 668{ 669 return( -1 ); 670} 671 672int 673ldap_avl_dup_ok( void* left, void* right ) 674{ 675 return( 0 ); 676} 677