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