cavl_impl.h revision ba164dffc5a6795bce97fae02b51ccf3330e15e4
1/* 2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 12/* Abstract AVL Tree Generic C Package. 13** Implementation generation header file. 14** 15** This code is in the public domain. See cavl_tree.html for interface 16** documentation. 17** 18** Version: 1.5 Author: Walt Karas 19*/ 20 21#undef L_ 22#undef L_EST_LONG_BIT 23#undef L_SIZE 24#undef l_tree 25#undef L_MASK_HIGH_BIT 26#undef L_LONG_BIT 27#undef L_BIT_ARR_DEFN 28#undef L_BIT_ARR_VAL 29#undef L_BIT_ARR_0 30#undef L_BIT_ARR_1 31#undef L_BIT_ARR_ALL 32#undef L_BIT_ARR_LONGS 33#undef L_IMPL_MASK 34#undef L_CHECK_READ_ERROR 35#undef L_CHECK_READ_ERROR_INV_DEPTH 36#undef L_SC 37#undef L_BALANCE_PARAM_PREFIX 38 39#ifdef AVL_UNIQUE 40 41#define L_ AVL_UNIQUE 42 43#else 44 45#define L_(X) X 46 47#endif 48 49/* Determine correct storage class for functions */ 50#ifdef AVL_PRIVATE 51 52#define L_SC static 53 54#else 55 56#define L_SC 57 58#endif 59 60#ifdef AVL_SIZE 61 62#define L_SIZE AVL_SIZE 63 64#else 65 66#define L_SIZE unsigned long 67 68#endif 69 70#define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1)) 71 72/* ANSI C/ISO C++ require that a long have at least 32 bits. Set 73** L_EST_LONG_BIT to be the greatest multiple of 8 in the range 74** 32 - 64 (inclusive) that is less than or equal to the number of 75** bits in a long. 76*/ 77 78#if (((LONG_MAX >> 31) >> 7) == 0) 79 80#define L_EST_LONG_BIT 32 81 82#elif (((LONG_MAX >> 31) >> 15) == 0) 83 84#define L_EST_LONG_BIT 40 85 86#elif (((LONG_MAX >> 31) >> 23) == 0) 87 88#define L_EST_LONG_BIT 48 89 90#elif (((LONG_MAX >> 31) >> 31) == 0) 91 92#define L_EST_LONG_BIT 56 93 94#else 95 96#define L_EST_LONG_BIT 64 97 98#endif 99 100#define L_LONG_BIT (sizeof(long) * CHAR_BIT) 101 102#if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) 103 104/* The maximum depth may be greater than the number of bits in a long, 105** so multiple longs are needed to hold a bit array indexed by node 106** depth. */ 107 108#define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT) 109 110#define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS]; 111 112#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \ 113 ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT))) 114 115#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \ 116 (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT)); 117 118#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \ 119 (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT); 120 121#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \ 122 { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); } 123 124#else /* The bit array can definitely fit in one long */ 125 126#define L_BIT_ARR_DEFN(NAME) unsigned long NAME; 127 128#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM))) 129 130#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM)); 131 132#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM); 133 134#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL); 135 136#endif 137 138#ifdef AVL_READ_ERRORS_HAPPEN 139 140#define L_CHECK_READ_ERROR(ERROR_RETURN) \ 141 { if (AVL_READ_ERROR) return(ERROR_RETURN); } 142 143#else 144 145#define L_CHECK_READ_ERROR(ERROR_RETURN) 146 147#endif 148 149/* The presumed reason that an instantiation places additional fields 150** inside the AVL tree structure is that the SET_ and GET_ macros 151** need these fields. The "balance" function does not explicitly use 152** any fields in the AVL tree structure, so only pass an AVL tree 153** structure pointer to "balance" if it has instantiation-specific 154** fields that are (presumably) needed by the SET_/GET_ calls within 155** "balance". 156*/ 157#ifdef AVL_INSIDE_STRUCT 158 159#define L_BALANCE_PARAM_CALL_PREFIX l_tree, 160#define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree, 161 162#else 163 164#define L_BALANCE_PARAM_CALL_PREFIX 165#define L_BALANCE_PARAM_DECL_PREFIX 166 167#endif 168 169#ifdef AVL_IMPL_MASK 170 171#define L_IMPL_MASK (AVL_IMPL_MASK) 172 173#else 174 175/* Define all functions. */ 176#define L_IMPL_MASK AVL_IMPL_ALL 177 178#endif 179 180#if (L_IMPL_MASK & AVL_IMPL_INIT) 181 182L_SC void L_(init)(L_(avl) *l_tree) { 183 l_tree->root = AVL_NULL; 184} 185 186#endif 187 188#if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) 189 190L_SC int L_(is_empty)(L_(avl) *l_tree) { 191 return(l_tree->root == AVL_NULL); 192} 193 194#endif 195 196/* Put the private balance function in the same compilation module as 197** the insert function. */ 198#if (L_IMPL_MASK & AVL_IMPL_INSERT) 199 200/* Balances subtree, returns handle of root node of subtree after balancing. 201*/ 202L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) { 203 AVL_HANDLE deep_h; 204 205 /* Either the "greater than" or the "less than" subtree of 206 ** this node has to be 2 levels deeper (or else it wouldn't 207 ** need balancing). 208 */ 209 if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) { 210 /* "Greater than" subtree is deeper. */ 211 212 deep_h = AVL_GET_GREATER(bal_h, 1); 213 214 L_CHECK_READ_ERROR(AVL_NULL) 215 216 if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) { 217 int bf; 218 219 AVL_HANDLE old_h = bal_h; 220 bal_h = AVL_GET_LESS(deep_h, 1); 221 L_CHECK_READ_ERROR(AVL_NULL) 222 AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) 223 AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) 224 AVL_SET_LESS(bal_h, old_h) 225 AVL_SET_GREATER(bal_h, deep_h) 226 227 bf = AVL_GET_BALANCE_FACTOR(bal_h); 228 229 if (bf != 0) { 230 if (bf > 0) { 231 AVL_SET_BALANCE_FACTOR(old_h, -1) 232 AVL_SET_BALANCE_FACTOR(deep_h, 0) 233 } else { 234 AVL_SET_BALANCE_FACTOR(deep_h, 1) 235 AVL_SET_BALANCE_FACTOR(old_h, 0) 236 } 237 238 AVL_SET_BALANCE_FACTOR(bal_h, 0) 239 } else { 240 AVL_SET_BALANCE_FACTOR(old_h, 0) 241 AVL_SET_BALANCE_FACTOR(deep_h, 0) 242 } 243 } else { 244 AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) 245 AVL_SET_LESS(deep_h, bal_h) 246 247 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 248 AVL_SET_BALANCE_FACTOR(deep_h, -1) 249 AVL_SET_BALANCE_FACTOR(bal_h, 1) 250 } else { 251 AVL_SET_BALANCE_FACTOR(deep_h, 0) 252 AVL_SET_BALANCE_FACTOR(bal_h, 0) 253 } 254 255 bal_h = deep_h; 256 } 257 } else { 258 /* "Less than" subtree is deeper. */ 259 260 deep_h = AVL_GET_LESS(bal_h, 1); 261 L_CHECK_READ_ERROR(AVL_NULL) 262 263 if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) { 264 int bf; 265 AVL_HANDLE old_h = bal_h; 266 bal_h = AVL_GET_GREATER(deep_h, 1); 267 L_CHECK_READ_ERROR(AVL_NULL) 268 AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) 269 AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) 270 AVL_SET_GREATER(bal_h, old_h) 271 AVL_SET_LESS(bal_h, deep_h) 272 273 bf = AVL_GET_BALANCE_FACTOR(bal_h); 274 275 if (bf != 0) { 276 if (bf < 0) { 277 AVL_SET_BALANCE_FACTOR(old_h, 1) 278 AVL_SET_BALANCE_FACTOR(deep_h, 0) 279 } else { 280 AVL_SET_BALANCE_FACTOR(deep_h, -1) 281 AVL_SET_BALANCE_FACTOR(old_h, 0) 282 } 283 284 AVL_SET_BALANCE_FACTOR(bal_h, 0) 285 } else { 286 AVL_SET_BALANCE_FACTOR(old_h, 0) 287 AVL_SET_BALANCE_FACTOR(deep_h, 0) 288 } 289 } else { 290 AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) 291 AVL_SET_GREATER(deep_h, bal_h) 292 293 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 294 AVL_SET_BALANCE_FACTOR(deep_h, 1) 295 AVL_SET_BALANCE_FACTOR(bal_h, -1) 296 } else { 297 AVL_SET_BALANCE_FACTOR(deep_h, 0) 298 AVL_SET_BALANCE_FACTOR(bal_h, 0) 299 } 300 301 bal_h = deep_h; 302 } 303 } 304 305 return(bal_h); 306} 307 308L_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) { 309 AVL_SET_LESS(h, AVL_NULL) 310 AVL_SET_GREATER(h, AVL_NULL) 311 AVL_SET_BALANCE_FACTOR(h, 0) 312 313 if (l_tree->root == AVL_NULL) 314 l_tree->root = h; 315 else { 316 /* Last unbalanced node encountered in search for insertion point. */ 317 AVL_HANDLE unbal = AVL_NULL; 318 /* Parent of last unbalanced node. */ 319 AVL_HANDLE parent_unbal = AVL_NULL; 320 /* Balance factor of last unbalanced node. */ 321 int unbal_bf; 322 323 /* Zero-based depth in tree. */ 324 unsigned depth = 0, unbal_depth = 0; 325 326 /* Records a path into the tree. If bit n is true, indicates 327 ** take greater branch from the nth node in the path, otherwise 328 ** take the less branch. bit 0 gives branch from root, and 329 ** so on. */ 330 L_BIT_ARR_DEFN(branch) 331 332 AVL_HANDLE hh = l_tree->root; 333 AVL_HANDLE parent = AVL_NULL; 334 int cmp; 335 336 do { 337 if (AVL_GET_BALANCE_FACTOR(hh) != 0) { 338 unbal = hh; 339 parent_unbal = parent; 340 unbal_depth = depth; 341 } 342 343 cmp = AVL_COMPARE_NODE_NODE(h, hh); 344 345 if (cmp == 0) 346 /* Duplicate key. */ 347 return(hh); 348 349 parent = hh; 350 351 if (cmp > 0) { 352 hh = AVL_GET_GREATER(hh, 1); 353 L_BIT_ARR_1(branch, depth) 354 } else { 355 hh = AVL_GET_LESS(hh, 1); 356 L_BIT_ARR_0(branch, depth) 357 } 358 359 L_CHECK_READ_ERROR(AVL_NULL) 360 depth++; 361 } while (hh != AVL_NULL); 362 363 /* Add node to insert as leaf of tree. */ 364 if (cmp < 0) 365 AVL_SET_LESS(parent, h) 366 else 367 AVL_SET_GREATER(parent, h) 368 369 depth = unbal_depth; 370 371 if (unbal == AVL_NULL) 372 hh = l_tree->root; 373 else { 374 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 375 depth++; 376 unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); 377 378 if (cmp < 0) 379 unbal_bf--; 380 else /* cmp > 0 */ 381 unbal_bf++; 382 383 hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); 384 L_CHECK_READ_ERROR(AVL_NULL) 385 386 if ((unbal_bf != -2) && (unbal_bf != 2)) { 387 /* No rebalancing of tree is necessary. */ 388 AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) 389 unbal = AVL_NULL; 390 } 391 } 392 393 if (hh != AVL_NULL) 394 while (h != hh) { 395 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 396 depth++; 397 398 if (cmp < 0) { 399 AVL_SET_BALANCE_FACTOR(hh, -1) 400 hh = AVL_GET_LESS(hh, 1); 401 } else { /* cmp > 0 */ 402 AVL_SET_BALANCE_FACTOR(hh, 1) 403 hh = AVL_GET_GREATER(hh, 1); 404 } 405 406 L_CHECK_READ_ERROR(AVL_NULL) 407 } 408 409 if (unbal != AVL_NULL) { 410 unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); 411 L_CHECK_READ_ERROR(AVL_NULL) 412 413 if (parent_unbal == AVL_NULL) 414 l_tree->root = unbal; 415 else { 416 depth = unbal_depth - 1; 417 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 418 419 if (cmp < 0) 420 AVL_SET_LESS(parent_unbal, unbal) 421 else /* cmp > 0 */ 422 AVL_SET_GREATER(parent_unbal, unbal) 423 } 424 } 425 426 } 427 428 return(h); 429} 430 431#endif 432 433#if (L_IMPL_MASK & AVL_IMPL_SEARCH) 434 435L_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) { 436 int cmp, target_cmp; 437 AVL_HANDLE match_h = AVL_NULL; 438 AVL_HANDLE h = l_tree->root; 439 440 if (st & AVL_LESS) 441 target_cmp = 1; 442 else if (st & AVL_GREATER) 443 target_cmp = -1; 444 else 445 target_cmp = 0; 446 447 while (h != AVL_NULL) { 448 cmp = AVL_COMPARE_KEY_NODE(k, h); 449 450 if (cmp == 0) { 451 if (st & AVL_EQUAL) { 452 match_h = h; 453 break; 454 } 455 456 cmp = -target_cmp; 457 } else if (target_cmp != 0) 458 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 459 /* cmp and target_cmp are both positive or both negative. */ 460 match_h = h; 461 462 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 463 L_CHECK_READ_ERROR(AVL_NULL) 464 } 465 466 return(match_h); 467} 468 469#endif 470 471#if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) 472 473L_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) { 474 AVL_HANDLE h = l_tree->root; 475 AVL_HANDLE parent = AVL_NULL; 476 477 while (h != AVL_NULL) { 478 parent = h; 479 h = AVL_GET_LESS(h, 1); 480 L_CHECK_READ_ERROR(AVL_NULL) 481 } 482 483 return(parent); 484} 485 486#endif 487 488#if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) 489 490L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) { 491 AVL_HANDLE h = l_tree->root; 492 AVL_HANDLE parent = AVL_NULL; 493 494 while (h != AVL_NULL) { 495 parent = h; 496 h = AVL_GET_GREATER(h, 1); 497 L_CHECK_READ_ERROR(AVL_NULL) 498 } 499 500 return(parent); 501} 502 503#endif 504 505#if (L_IMPL_MASK & AVL_IMPL_REMOVE) 506 507/* Prototype of balance function (called by remove) in case not in 508** same compilation unit. 509*/ 510L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); 511 512L_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) { 513 /* Zero-based depth in tree. */ 514 unsigned depth = 0, rm_depth; 515 516 /* Records a path into the tree. If bit n is true, indicates 517 ** take greater branch from the nth node in the path, otherwise 518 ** take the less branch. bit 0 gives branch from root, and 519 ** so on. */ 520 L_BIT_ARR_DEFN(branch) 521 522 AVL_HANDLE h = l_tree->root; 523 AVL_HANDLE parent = AVL_NULL; 524 AVL_HANDLE child; 525 AVL_HANDLE path; 526 int cmp, cmp_shortened_sub_with_path; 527 int reduced_depth; 528 int bf; 529 AVL_HANDLE rm; 530 AVL_HANDLE parent_rm; 531 532 for (;;) { 533 if (h == AVL_NULL) 534 /* No node in tree with given key. */ 535 return(AVL_NULL); 536 537 cmp = AVL_COMPARE_KEY_NODE(k, h); 538 539 if (cmp == 0) 540 /* Found node to remove. */ 541 break; 542 543 parent = h; 544 545 if (cmp > 0) { 546 h = AVL_GET_GREATER(h, 1); 547 L_BIT_ARR_1(branch, depth) 548 } else { 549 h = AVL_GET_LESS(h, 1); 550 L_BIT_ARR_0(branch, depth) 551 } 552 553 L_CHECK_READ_ERROR(AVL_NULL) 554 depth++; 555 cmp_shortened_sub_with_path = cmp; 556 } 557 558 rm = h; 559 parent_rm = parent; 560 rm_depth = depth; 561 562 /* If the node to remove is not a leaf node, we need to get a 563 ** leaf node, or a node with a single leaf as its child, to put 564 ** in the place of the node to remove. We will get the greatest 565 ** node in the less subtree (of the node to remove), or the least 566 ** node in the greater subtree. We take the leaf node from the 567 ** deeper subtree, if there is one. */ 568 569 if (AVL_GET_BALANCE_FACTOR(h) < 0) { 570 child = AVL_GET_LESS(h, 1); 571 L_BIT_ARR_0(branch, depth) 572 cmp = -1; 573 } else { 574 child = AVL_GET_GREATER(h, 1); 575 L_BIT_ARR_1(branch, depth) 576 cmp = 1; 577 } 578 579 L_CHECK_READ_ERROR(AVL_NULL) 580 depth++; 581 582 if (child != AVL_NULL) { 583 cmp = -cmp; 584 585 do { 586 parent = h; 587 h = child; 588 589 if (cmp < 0) { 590 child = AVL_GET_LESS(h, 1); 591 L_BIT_ARR_0(branch, depth) 592 } else { 593 child = AVL_GET_GREATER(h, 1); 594 L_BIT_ARR_1(branch, depth) 595 } 596 597 L_CHECK_READ_ERROR(AVL_NULL) 598 depth++; 599 } while (child != AVL_NULL); 600 601 if (parent == rm) 602 /* Only went through do loop once. Deleted node will be replaced 603 ** in the tree structure by one of its immediate children. */ 604 cmp_shortened_sub_with_path = -cmp; 605 else 606 cmp_shortened_sub_with_path = cmp; 607 608 /* Get the handle of the opposite child, which may not be null. */ 609 child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); 610 } 611 612 if (parent == AVL_NULL) 613 /* There were only 1 or 2 nodes in this tree. */ 614 l_tree->root = child; 615 else if (cmp_shortened_sub_with_path < 0) 616 AVL_SET_LESS(parent, child) 617 else 618 AVL_SET_GREATER(parent, child) 619 620 /* "path" is the parent of the subtree being eliminated or reduced 621 ** from a depth of 2 to 1. If "path" is the node to be removed, we 622 ** set path to the node we're about to poke into the position of the 623 ** node to be removed. */ 624 path = parent == rm ? h : parent; 625 626 if (h != rm) { 627 /* Poke in the replacement for the node to be removed. */ 628 AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) 629 AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) 630 AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) 631 632 if (parent_rm == AVL_NULL) 633 l_tree->root = h; 634 else { 635 depth = rm_depth - 1; 636 637 if (L_BIT_ARR_VAL(branch, depth)) 638 AVL_SET_GREATER(parent_rm, h) 639 else 640 AVL_SET_LESS(parent_rm, h) 641 } 642 } 643 644 if (path != AVL_NULL) { 645 /* Create a temporary linked list from the parent of the path node 646 ** to the root node. */ 647 h = l_tree->root; 648 parent = AVL_NULL; 649 depth = 0; 650 651 while (h != path) { 652 if (L_BIT_ARR_VAL(branch, depth)) { 653 child = AVL_GET_GREATER(h, 1); 654 AVL_SET_GREATER(h, parent) 655 } else { 656 child = AVL_GET_LESS(h, 1); 657 AVL_SET_LESS(h, parent) 658 } 659 660 L_CHECK_READ_ERROR(AVL_NULL) 661 depth++; 662 parent = h; 663 h = child; 664 } 665 666 /* Climb from the path node to the root node using the linked 667 ** list, restoring the tree structure and rebalancing as necessary. 668 */ 669 reduced_depth = 1; 670 cmp = cmp_shortened_sub_with_path; 671 672 for (;;) { 673 if (reduced_depth) { 674 bf = AVL_GET_BALANCE_FACTOR(h); 675 676 if (cmp < 0) 677 bf++; 678 else /* cmp > 0 */ 679 bf--; 680 681 if ((bf == -2) || (bf == 2)) { 682 h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); 683 L_CHECK_READ_ERROR(AVL_NULL) 684 bf = AVL_GET_BALANCE_FACTOR(h); 685 } else 686 AVL_SET_BALANCE_FACTOR(h, bf) 687 reduced_depth = (bf == 0); 688 } 689 690 if (parent == AVL_NULL) 691 break; 692 693 child = h; 694 h = parent; 695 depth--; 696 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 697 698 if (cmp < 0) { 699 parent = AVL_GET_LESS(h, 1); 700 AVL_SET_LESS(h, child) 701 } else { 702 parent = AVL_GET_GREATER(h, 1); 703 AVL_SET_GREATER(h, child) 704 } 705 706 L_CHECK_READ_ERROR(AVL_NULL) 707 } 708 709 l_tree->root = h; 710 } 711 712 return(rm); 713} 714 715#endif 716 717#if (L_IMPL_MASK & AVL_IMPL_SUBST) 718 719L_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) { 720 AVL_HANDLE h = l_tree->root; 721 AVL_HANDLE parent = AVL_NULL; 722 int cmp, last_cmp; 723 724 /* Search for node already in tree with same key. */ 725 for (;;) { 726 if (h == AVL_NULL) 727 /* No node in tree with same key as new node. */ 728 return(AVL_NULL); 729 730 cmp = AVL_COMPARE_NODE_NODE(new_node, h); 731 732 if (cmp == 0) 733 /* Found the node to substitute new one for. */ 734 break; 735 736 last_cmp = cmp; 737 parent = h; 738 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 739 L_CHECK_READ_ERROR(AVL_NULL) 740 } 741 742 /* Copy tree housekeeping fields from node in tree to new node. */ 743 AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) 744 AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) 745 AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) 746 747 if (parent == AVL_NULL) 748 /* New node is also new root. */ 749 l_tree->root = new_node; 750 else { 751 /* Make parent point to new node. */ 752 if (last_cmp < 0) 753 AVL_SET_LESS(parent, new_node) 754 else 755 AVL_SET_GREATER(parent, new_node) 756 } 757 758 return(h); 759} 760 761#endif 762 763#ifdef AVL_BUILD_ITER_TYPE 764 765#if (L_IMPL_MASK & AVL_IMPL_BUILD) 766 767L_SC int L_(build)( 768 L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) { 769 /* Gives path to subtree being built. If bit n is false, branch 770 ** less from the node at depth n, if true branch greater. */ 771 L_BIT_ARR_DEFN(branch) 772 773 /* If bit n is true, then for the current subtree at depth n, its 774 ** greater subtree has one more node than its less subtree. */ 775 L_BIT_ARR_DEFN(rem) 776 777 /* Depth of root node of current subtree. */ 778 unsigned depth = 0; 779 780 /* Number of nodes in current subtree. */ 781 L_SIZE num_sub = num_nodes; 782 783 /* The algorithm relies on a stack of nodes whose less subtree has 784 ** been built, but whose greater subtree has not yet been built. 785 ** The stack is implemented as linked list. The nodes are linked 786 ** together by having the "greater" handle of a node set to the 787 ** next node in the list. "less_parent" is the handle of the first 788 ** node in the list. */ 789 AVL_HANDLE less_parent = AVL_NULL; 790 791 /* h is root of current subtree, child is one of its children. */ 792 AVL_HANDLE h; 793 AVL_HANDLE child; 794 795 if (num_nodes == 0) { 796 l_tree->root = AVL_NULL; 797 return(1); 798 } 799 800 for (;;) { 801 while (num_sub > 2) { 802 /* Subtract one for root of subtree. */ 803 num_sub--; 804 805 if (num_sub & 1) 806 L_BIT_ARR_1(rem, depth) 807 else 808 L_BIT_ARR_0(rem, depth) 809 L_BIT_ARR_0(branch, depth) 810 depth++; 811 812 num_sub >>= 1; 813 } 814 815 if (num_sub == 2) { 816 /* Build a subtree with two nodes, slanting to greater. 817 ** I arbitrarily chose to always have the extra node in the 818 ** greater subtree when there is an odd number of nodes to 819 ** split between the two subtrees. */ 820 821 h = AVL_BUILD_ITER_VAL(p); 822 L_CHECK_READ_ERROR(0) 823 AVL_BUILD_ITER_INCR(p) 824 child = AVL_BUILD_ITER_VAL(p); 825 L_CHECK_READ_ERROR(0) 826 AVL_BUILD_ITER_INCR(p) 827 AVL_SET_LESS(child, AVL_NULL) 828 AVL_SET_GREATER(child, AVL_NULL) 829 AVL_SET_BALANCE_FACTOR(child, 0) 830 AVL_SET_GREATER(h, child) 831 AVL_SET_LESS(h, AVL_NULL) 832 AVL_SET_BALANCE_FACTOR(h, 1) 833 } else { /* num_sub == 1 */ 834 /* Build a subtree with one node. */ 835 836 h = AVL_BUILD_ITER_VAL(p); 837 L_CHECK_READ_ERROR(0) 838 AVL_BUILD_ITER_INCR(p) 839 AVL_SET_LESS(h, AVL_NULL) 840 AVL_SET_GREATER(h, AVL_NULL) 841 AVL_SET_BALANCE_FACTOR(h, 0) 842 } 843 844 while (depth) { 845 depth--; 846 847 if (!L_BIT_ARR_VAL(branch, depth)) 848 /* We've completed a less subtree. */ 849 break; 850 851 /* We've completed a greater subtree, so attach it to 852 ** its parent (that is less than it). We pop the parent 853 ** off the stack of less parents. */ 854 child = h; 855 h = less_parent; 856 less_parent = AVL_GET_GREATER(h, 1); 857 L_CHECK_READ_ERROR(0) 858 AVL_SET_GREATER(h, child) 859 /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ 860 num_sub <<= 1; 861 num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; 862 863 if (num_sub & (num_sub - 1)) 864 /* num_sub is not a power of 2. */ 865 AVL_SET_BALANCE_FACTOR(h, 0) 866 else 867 /* num_sub is a power of 2. */ 868 AVL_SET_BALANCE_FACTOR(h, 1) 869 } 870 871 if (num_sub == num_nodes) 872 /* We've completed the full tree. */ 873 break; 874 875 /* The subtree we've completed is the less subtree of the 876 ** next node in the sequence. */ 877 878 child = h; 879 h = AVL_BUILD_ITER_VAL(p); 880 L_CHECK_READ_ERROR(0) 881 AVL_BUILD_ITER_INCR(p) 882 AVL_SET_LESS(h, child) 883 884 /* Put h into stack of less parents. */ 885 AVL_SET_GREATER(h, less_parent) 886 less_parent = h; 887 888 /* Proceed to creating greater than subtree of h. */ 889 L_BIT_ARR_1(branch, depth) 890 num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; 891 depth++; 892 893 } /* end for (;; ) */ 894 895 l_tree->root = h; 896 897 return(1); 898} 899 900#endif 901 902#endif 903 904#if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) 905 906/* Initialize depth to invalid value, to indicate iterator is 907** invalid. (Depth is zero-base.) It's not necessary to initialize 908** iterators prior to passing them to the "start" function. 909*/ 910L_SC void L_(init_iter)(L_(iter) *iter) { 911 iter->depth = ~0; 912} 913 914#endif 915 916#ifdef AVL_READ_ERRORS_HAPPEN 917 918#define L_CHECK_READ_ERROR_INV_DEPTH \ 919 { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } 920 921#else 922 923#define L_CHECK_READ_ERROR_INV_DEPTH 924 925#endif 926 927#if (L_IMPL_MASK & AVL_IMPL_START_ITER) 928 929L_SC void L_(start_iter)( 930 L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) { 931 AVL_HANDLE h = l_tree->root; 932 unsigned d = 0; 933 int cmp, target_cmp; 934 935 /* Save the tree that we're going to iterate through in a 936 ** member variable. */ 937 iter->tree_ = l_tree; 938 939 iter->depth = ~0; 940 941 if (h == AVL_NULL) 942 /* Tree is empty. */ 943 return; 944 945 if (st & AVL_LESS) 946 /* Key can be greater than key of starting node. */ 947 target_cmp = 1; 948 else if (st & AVL_GREATER) 949 /* Key can be less than key of starting node. */ 950 target_cmp = -1; 951 else 952 /* Key must be same as key of starting node. */ 953 target_cmp = 0; 954 955 for (;;) { 956 cmp = AVL_COMPARE_KEY_NODE(k, h); 957 958 if (cmp == 0) { 959 if (st & AVL_EQUAL) { 960 /* Equal node was sought and found as starting node. */ 961 iter->depth = d; 962 break; 963 } 964 965 cmp = -target_cmp; 966 } else if (target_cmp != 0) 967 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 968 /* cmp and target_cmp are both negative or both positive. */ 969 iter->depth = d; 970 971 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 972 L_CHECK_READ_ERROR_INV_DEPTH 973 974 if (h == AVL_NULL) 975 break; 976 977 if (cmp > 0) 978 L_BIT_ARR_1(iter->branch, d) 979 else 980 L_BIT_ARR_0(iter->branch, d) 981 iter->path_h[d++] = h; 982 } 983} 984 985#endif 986 987#if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) 988 989L_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) { 990 AVL_HANDLE h = l_tree->root; 991 992 iter->tree_ = l_tree; 993 994 iter->depth = ~0; 995 996 L_BIT_ARR_ALL(iter->branch, 0) 997 998 while (h != AVL_NULL) { 999 if (iter->depth != ~0) 1000 iter->path_h[iter->depth] = h; 1001 1002 iter->depth++; 1003 h = AVL_GET_LESS(h, 1); 1004 L_CHECK_READ_ERROR_INV_DEPTH 1005 } 1006} 1007 1008#endif 1009 1010#if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) 1011 1012L_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) { 1013 AVL_HANDLE h = l_tree->root; 1014 1015 iter->tree_ = l_tree; 1016 1017 iter->depth = ~0; 1018 1019 L_BIT_ARR_ALL(iter->branch, 1) 1020 1021 while (h != AVL_NULL) { 1022 if (iter->depth != ~0) 1023 iter->path_h[iter->depth] = h; 1024 1025 iter->depth++; 1026 h = AVL_GET_GREATER(h, 1); 1027 L_CHECK_READ_ERROR_INV_DEPTH 1028 } 1029} 1030 1031#endif 1032 1033#if (L_IMPL_MASK & AVL_IMPL_GET_ITER) 1034 1035L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) { 1036 if (iter->depth == ~0) 1037 return(AVL_NULL); 1038 1039 return(iter->depth == 0 ? 1040 iter->tree_->root : iter->path_h[iter->depth - 1]); 1041} 1042 1043#endif 1044 1045#if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) 1046 1047L_SC void L_(incr_iter)(L_(iter) *iter) { 1048#define l_tree (iter->tree_) 1049 1050 if (iter->depth != ~0) { 1051 AVL_HANDLE h = 1052 AVL_GET_GREATER((iter->depth == 0 ? 1053 iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1054 L_CHECK_READ_ERROR_INV_DEPTH 1055 1056 if (h == AVL_NULL) 1057 do { 1058 if (iter->depth == 0) { 1059 iter->depth = ~0; 1060 break; 1061 } 1062 1063 iter->depth--; 1064 } while (L_BIT_ARR_VAL(iter->branch, iter->depth)); 1065 else { 1066 L_BIT_ARR_1(iter->branch, iter->depth) 1067 iter->path_h[iter->depth++] = h; 1068 1069 for (;;) { 1070 h = AVL_GET_LESS(h, 1); 1071 L_CHECK_READ_ERROR_INV_DEPTH 1072 1073 if (h == AVL_NULL) 1074 break; 1075 1076 L_BIT_ARR_0(iter->branch, iter->depth) 1077 iter->path_h[iter->depth++] = h; 1078 } 1079 } 1080 } 1081 1082#undef l_tree 1083} 1084 1085#endif 1086 1087#if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) 1088 1089L_SC void L_(decr_iter)(L_(iter) *iter) { 1090#define l_tree (iter->tree_) 1091 1092 if (iter->depth != ~0) { 1093 AVL_HANDLE h = 1094 AVL_GET_LESS((iter->depth == 0 ? 1095 iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1096 L_CHECK_READ_ERROR_INV_DEPTH 1097 1098 if (h == AVL_NULL) 1099 do { 1100 if (iter->depth == 0) { 1101 iter->depth = ~0; 1102 break; 1103 } 1104 1105 iter->depth--; 1106 } while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); 1107 else { 1108 L_BIT_ARR_0(iter->branch, iter->depth) 1109 iter->path_h[iter->depth++] = h; 1110 1111 for (;;) { 1112 h = AVL_GET_GREATER(h, 1); 1113 L_CHECK_READ_ERROR_INV_DEPTH 1114 1115 if (h == AVL_NULL) 1116 break; 1117 1118 L_BIT_ARR_1(iter->branch, iter->depth) 1119 iter->path_h[iter->depth++] = h; 1120 } 1121 } 1122 } 1123 1124#undef l_tree 1125} 1126 1127#endif 1128 1129/* Tidy up the preprocessor symbol name space. */ 1130#undef L_ 1131#undef L_EST_LONG_BIT 1132#undef L_SIZE 1133#undef L_MASK_HIGH_BIT 1134#undef L_LONG_BIT 1135#undef L_BIT_ARR_DEFN 1136#undef L_BIT_ARR_VAL 1137#undef L_BIT_ARR_0 1138#undef L_BIT_ARR_1 1139#undef L_BIT_ARR_ALL 1140#undef L_CHECK_READ_ERROR 1141#undef L_CHECK_READ_ERROR_INV_DEPTH 1142#undef L_BIT_ARR_LONGS 1143#undef L_IMPL_MASK 1144#undef L_CHECK_READ_ERROR 1145#undef L_CHECK_READ_ERROR_INV_DEPTH 1146#undef L_SC 1147#undef L_BALANCE_PARAM_CALL_PREFIX 1148#undef L_BALANCE_PARAM_DECL_PREFIX 1149