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 182 L_SC void L_(init)(L_(avl) *l_tree) 183 { 184 l_tree->root = AVL_NULL; 185 } 186 187 #endif 188 189 #if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) 190 191 L_SC int L_(is_empty)(L_(avl) *l_tree) 192 { 193 return(l_tree->root == AVL_NULL); 194 } 195 196 #endif 197 198 /* Put the private balance function in the same compilation module as 199 ** the insert function. */ 200 #if (L_IMPL_MASK & AVL_IMPL_INSERT) 201 202 /* Balances subtree, returns handle of root node of subtree after balancing. 203 */ 204 L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) 205 { 206 AVL_HANDLE deep_h; 207 208 /* Either the "greater than" or the "less than" subtree of 209 ** this node has to be 2 levels deeper (or else it wouldn't 210 ** need balancing). 211 */ 212 if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) 213 { 214 /* "Greater than" subtree is deeper. */ 215 216 deep_h = AVL_GET_GREATER(bal_h, 1); 217 218 L_CHECK_READ_ERROR(AVL_NULL) 219 220 if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) 221 { 222 int bf; 223 224 AVL_HANDLE old_h = bal_h; 225 bal_h = AVL_GET_LESS(deep_h, 1); 226 L_CHECK_READ_ERROR(AVL_NULL) 227 AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) 228 AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) 229 AVL_SET_LESS(bal_h, old_h) 230 AVL_SET_GREATER(bal_h, deep_h) 231 232 bf = AVL_GET_BALANCE_FACTOR(bal_h); 233 234 if (bf != 0) 235 { 236 if (bf > 0) 237 { 238 AVL_SET_BALANCE_FACTOR(old_h, -1) 239 AVL_SET_BALANCE_FACTOR(deep_h, 0) 240 } 241 else 242 { 243 AVL_SET_BALANCE_FACTOR(deep_h, 1) 244 AVL_SET_BALANCE_FACTOR(old_h, 0) 245 } 246 247 AVL_SET_BALANCE_FACTOR(bal_h, 0) 248 } 249 else 250 { 251 AVL_SET_BALANCE_FACTOR(old_h, 0) 252 AVL_SET_BALANCE_FACTOR(deep_h, 0) 253 } 254 } 255 else 256 { 257 AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) 258 AVL_SET_LESS(deep_h, bal_h) 259 260 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) 261 { 262 AVL_SET_BALANCE_FACTOR(deep_h, -1) 263 AVL_SET_BALANCE_FACTOR(bal_h, 1) 264 } 265 else 266 { 267 AVL_SET_BALANCE_FACTOR(deep_h, 0) 268 AVL_SET_BALANCE_FACTOR(bal_h, 0) 269 } 270 271 bal_h = deep_h; 272 } 273 } 274 else 275 { 276 /* "Less than" subtree is deeper. */ 277 278 deep_h = AVL_GET_LESS(bal_h, 1); 279 L_CHECK_READ_ERROR(AVL_NULL) 280 281 if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) 282 { 283 int bf; 284 AVL_HANDLE old_h = bal_h; 285 bal_h = AVL_GET_GREATER(deep_h, 1); 286 L_CHECK_READ_ERROR(AVL_NULL) 287 AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) 288 AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) 289 AVL_SET_GREATER(bal_h, old_h) 290 AVL_SET_LESS(bal_h, deep_h) 291 292 bf = AVL_GET_BALANCE_FACTOR(bal_h); 293 294 if (bf != 0) 295 { 296 if (bf < 0) 297 { 298 AVL_SET_BALANCE_FACTOR(old_h, 1) 299 AVL_SET_BALANCE_FACTOR(deep_h, 0) 300 } 301 else 302 { 303 AVL_SET_BALANCE_FACTOR(deep_h, -1) 304 AVL_SET_BALANCE_FACTOR(old_h, 0) 305 } 306 307 AVL_SET_BALANCE_FACTOR(bal_h, 0) 308 } 309 else 310 { 311 AVL_SET_BALANCE_FACTOR(old_h, 0) 312 AVL_SET_BALANCE_FACTOR(deep_h, 0) 313 } 314 } 315 else 316 { 317 AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) 318 AVL_SET_GREATER(deep_h, bal_h) 319 320 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) 321 { 322 AVL_SET_BALANCE_FACTOR(deep_h, 1) 323 AVL_SET_BALANCE_FACTOR(bal_h, -1) 324 } 325 else 326 { 327 AVL_SET_BALANCE_FACTOR(deep_h, 0) 328 AVL_SET_BALANCE_FACTOR(bal_h, 0) 329 } 330 331 bal_h = deep_h; 332 } 333 } 334 335 return(bal_h); 336 } 337 338 L_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) 339 { 340 AVL_SET_LESS(h, AVL_NULL) 341 AVL_SET_GREATER(h, AVL_NULL) 342 AVL_SET_BALANCE_FACTOR(h, 0) 343 344 if (l_tree->root == AVL_NULL) 345 l_tree->root = h; 346 else 347 { 348 /* Last unbalanced node encountered in search for insertion point. */ 349 AVL_HANDLE unbal = AVL_NULL; 350 /* Parent of last unbalanced node. */ 351 AVL_HANDLE parent_unbal = AVL_NULL; 352 /* Balance factor of last unbalanced node. */ 353 int unbal_bf; 354 355 /* Zero-based depth in tree. */ 356 unsigned depth = 0, unbal_depth = 0; 357 358 /* Records a path into the tree. If bit n is true, indicates 359 ** take greater branch from the nth node in the path, otherwise 360 ** take the less branch. bit 0 gives branch from root, and 361 ** so on. */ 362 L_BIT_ARR_DEFN(branch) 363 364 AVL_HANDLE hh = l_tree->root; 365 AVL_HANDLE parent = AVL_NULL; 366 int cmp; 367 368 do 369 { 370 if (AVL_GET_BALANCE_FACTOR(hh) != 0) 371 { 372 unbal = hh; 373 parent_unbal = parent; 374 unbal_depth = depth; 375 } 376 377 cmp = AVL_COMPARE_NODE_NODE(h, hh); 378 379 if (cmp == 0) 380 /* Duplicate key. */ 381 return(hh); 382 383 parent = hh; 384 385 if (cmp > 0) 386 { 387 hh = AVL_GET_GREATER(hh, 1); 388 L_BIT_ARR_1(branch, depth) 389 } 390 else 391 { 392 hh = AVL_GET_LESS(hh, 1); 393 L_BIT_ARR_0(branch, depth) 394 } 395 396 L_CHECK_READ_ERROR(AVL_NULL) 397 depth++; 398 } 399 while (hh != AVL_NULL); 400 401 /* Add node to insert as leaf of tree. */ 402 if (cmp < 0) 403 AVL_SET_LESS(parent, h) 404 else 405 AVL_SET_GREATER(parent, h) 406 407 depth = unbal_depth; 408 409 if (unbal == AVL_NULL) 410 hh = l_tree->root; 411 else 412 { 413 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 414 depth++; 415 unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); 416 417 if (cmp < 0) 418 unbal_bf--; 419 else /* cmp > 0 */ 420 unbal_bf++; 421 422 hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); 423 L_CHECK_READ_ERROR(AVL_NULL) 424 425 if ((unbal_bf != -2) && (unbal_bf != 2)) 426 { 427 /* No rebalancing of tree is necessary. */ 428 AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) 429 unbal = AVL_NULL; 430 } 431 } 432 433 if (hh != AVL_NULL) 434 while (h != hh) 435 { 436 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 437 depth++; 438 439 if (cmp < 0) 440 { 441 AVL_SET_BALANCE_FACTOR(hh, -1) 442 hh = AVL_GET_LESS(hh, 1); 443 } 444 else /* cmp > 0 */ 445 { 446 AVL_SET_BALANCE_FACTOR(hh, 1) 447 hh = AVL_GET_GREATER(hh, 1); 448 } 449 450 L_CHECK_READ_ERROR(AVL_NULL) 451 } 452 453 if (unbal != AVL_NULL) 454 { 455 unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); 456 L_CHECK_READ_ERROR(AVL_NULL) 457 458 if (parent_unbal == AVL_NULL) 459 l_tree->root = unbal; 460 else 461 { 462 depth = unbal_depth - 1; 463 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 464 465 if (cmp < 0) 466 AVL_SET_LESS(parent_unbal, unbal) 467 else /* cmp > 0 */ 468 AVL_SET_GREATER(parent_unbal, unbal) 469 } 470 } 471 472 } 473 474 return(h); 475 } 476 477 #endif 478 479 #if (L_IMPL_MASK & AVL_IMPL_SEARCH) 480 481 L_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) 482 { 483 int cmp, target_cmp; 484 AVL_HANDLE match_h = AVL_NULL; 485 AVL_HANDLE h = l_tree->root; 486 487 if (st & AVL_LESS) 488 target_cmp = 1; 489 else if (st & AVL_GREATER) 490 target_cmp = -1; 491 else 492 target_cmp = 0; 493 494 while (h != AVL_NULL) 495 { 496 cmp = AVL_COMPARE_KEY_NODE(k, h); 497 498 if (cmp == 0) 499 { 500 if (st & AVL_EQUAL) 501 { 502 match_h = h; 503 break; 504 } 505 506 cmp = -target_cmp; 507 } 508 else if (target_cmp != 0) 509 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 510 /* cmp and target_cmp are both positive or both negative. */ 511 match_h = h; 512 513 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 514 L_CHECK_READ_ERROR(AVL_NULL) 515 } 516 517 return(match_h); 518 } 519 520 #endif 521 522 #if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) 523 524 L_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) 525 { 526 AVL_HANDLE h = l_tree->root; 527 AVL_HANDLE parent = AVL_NULL; 528 529 while (h != AVL_NULL) 530 { 531 parent = h; 532 h = AVL_GET_LESS(h, 1); 533 L_CHECK_READ_ERROR(AVL_NULL) 534 } 535 536 return(parent); 537 } 538 539 #endif 540 541 #if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) 542 543 L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) 544 { 545 AVL_HANDLE h = l_tree->root; 546 AVL_HANDLE parent = AVL_NULL; 547 548 while (h != AVL_NULL) 549 { 550 parent = h; 551 h = AVL_GET_GREATER(h, 1); 552 L_CHECK_READ_ERROR(AVL_NULL) 553 } 554 555 return(parent); 556 } 557 558 #endif 559 560 #if (L_IMPL_MASK & AVL_IMPL_REMOVE) 561 562 /* Prototype of balance function (called by remove) in case not in 563 ** same compilation unit. 564 */ 565 L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); 566 567 L_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) 568 { 569 /* Zero-based depth in tree. */ 570 unsigned depth = 0, rm_depth; 571 572 /* Records a path into the tree. If bit n is true, indicates 573 ** take greater branch from the nth node in the path, otherwise 574 ** take the less branch. bit 0 gives branch from root, and 575 ** so on. */ 576 L_BIT_ARR_DEFN(branch) 577 578 AVL_HANDLE h = l_tree->root; 579 AVL_HANDLE parent = AVL_NULL; 580 AVL_HANDLE child; 581 AVL_HANDLE path; 582 int cmp, cmp_shortened_sub_with_path; 583 int reduced_depth; 584 int bf; 585 AVL_HANDLE rm; 586 AVL_HANDLE parent_rm; 587 588 for (; ;) 589 { 590 if (h == AVL_NULL) 591 /* No node in tree with given key. */ 592 return(AVL_NULL); 593 594 cmp = AVL_COMPARE_KEY_NODE(k, h); 595 596 if (cmp == 0) 597 /* Found node to remove. */ 598 break; 599 600 parent = h; 601 602 if (cmp > 0) 603 { 604 h = AVL_GET_GREATER(h, 1); 605 L_BIT_ARR_1(branch, depth) 606 } 607 else 608 { 609 h = AVL_GET_LESS(h, 1); 610 L_BIT_ARR_0(branch, depth) 611 } 612 613 L_CHECK_READ_ERROR(AVL_NULL) 614 depth++; 615 cmp_shortened_sub_with_path = cmp; 616 } 617 618 rm = h; 619 parent_rm = parent; 620 rm_depth = depth; 621 622 /* If the node to remove is not a leaf node, we need to get a 623 ** leaf node, or a node with a single leaf as its child, to put 624 ** in the place of the node to remove. We will get the greatest 625 ** node in the less subtree (of the node to remove), or the least 626 ** node in the greater subtree. We take the leaf node from the 627 ** deeper subtree, if there is one. */ 628 629 if (AVL_GET_BALANCE_FACTOR(h) < 0) 630 { 631 child = AVL_GET_LESS(h, 1); 632 L_BIT_ARR_0(branch, depth) 633 cmp = -1; 634 } 635 else 636 { 637 child = AVL_GET_GREATER(h, 1); 638 L_BIT_ARR_1(branch, depth) 639 cmp = 1; 640 } 641 642 L_CHECK_READ_ERROR(AVL_NULL) 643 depth++; 644 645 if (child != AVL_NULL) 646 { 647 cmp = -cmp; 648 649 do 650 { 651 parent = h; 652 h = child; 653 654 if (cmp < 0) 655 { 656 child = AVL_GET_LESS(h, 1); 657 L_BIT_ARR_0(branch, depth) 658 } 659 else 660 { 661 child = AVL_GET_GREATER(h, 1); 662 L_BIT_ARR_1(branch, depth) 663 } 664 665 L_CHECK_READ_ERROR(AVL_NULL) 666 depth++; 667 } 668 while (child != AVL_NULL); 669 670 if (parent == rm) 671 /* Only went through do loop once. Deleted node will be replaced 672 ** in the tree structure by one of its immediate children. */ 673 cmp_shortened_sub_with_path = -cmp; 674 else 675 cmp_shortened_sub_with_path = cmp; 676 677 /* Get the handle of the opposite child, which may not be null. */ 678 child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); 679 } 680 681 if (parent == AVL_NULL) 682 /* There were only 1 or 2 nodes in this tree. */ 683 l_tree->root = child; 684 else if (cmp_shortened_sub_with_path < 0) 685 AVL_SET_LESS(parent, child) 686 else 687 AVL_SET_GREATER(parent, child) 688 689 /* "path" is the parent of the subtree being eliminated or reduced 690 ** from a depth of 2 to 1. If "path" is the node to be removed, we 691 ** set path to the node we're about to poke into the position of the 692 ** node to be removed. */ 693 path = parent == rm ? h : parent; 694 695 if (h != rm) 696 { 697 /* Poke in the replacement for the node to be removed. */ 698 AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) 699 AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) 700 AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) 701 702 if (parent_rm == AVL_NULL) 703 l_tree->root = h; 704 else 705 { 706 depth = rm_depth - 1; 707 708 if (L_BIT_ARR_VAL(branch, depth)) 709 AVL_SET_GREATER(parent_rm, h) 710 else 711 AVL_SET_LESS(parent_rm, h) 712 } 713 } 714 715 if (path != AVL_NULL) 716 { 717 /* Create a temporary linked list from the parent of the path node 718 ** to the root node. */ 719 h = l_tree->root; 720 parent = AVL_NULL; 721 depth = 0; 722 723 while (h != path) 724 { 725 if (L_BIT_ARR_VAL(branch, depth)) 726 { 727 child = AVL_GET_GREATER(h, 1); 728 AVL_SET_GREATER(h, parent) 729 } 730 else 731 { 732 child = AVL_GET_LESS(h, 1); 733 AVL_SET_LESS(h, parent) 734 } 735 736 L_CHECK_READ_ERROR(AVL_NULL) 737 depth++; 738 parent = h; 739 h = child; 740 } 741 742 /* Climb from the path node to the root node using the linked 743 ** list, restoring the tree structure and rebalancing as necessary. 744 */ 745 reduced_depth = 1; 746 cmp = cmp_shortened_sub_with_path; 747 748 for (; ;) 749 { 750 if (reduced_depth) 751 { 752 bf = AVL_GET_BALANCE_FACTOR(h); 753 754 if (cmp < 0) 755 bf++; 756 else /* cmp > 0 */ 757 bf--; 758 759 if ((bf == -2) || (bf == 2)) 760 { 761 h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); 762 L_CHECK_READ_ERROR(AVL_NULL) 763 bf = AVL_GET_BALANCE_FACTOR(h); 764 } 765 else 766 AVL_SET_BALANCE_FACTOR(h, bf) 767 reduced_depth = (bf == 0); 768 } 769 770 if (parent == AVL_NULL) 771 break; 772 773 child = h; 774 h = parent; 775 depth--; 776 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 777 778 if (cmp < 0) 779 { 780 parent = AVL_GET_LESS(h, 1); 781 AVL_SET_LESS(h, child) 782 } 783 else 784 { 785 parent = AVL_GET_GREATER(h, 1); 786 AVL_SET_GREATER(h, child) 787 } 788 789 L_CHECK_READ_ERROR(AVL_NULL) 790 } 791 792 l_tree->root = h; 793 } 794 795 return(rm); 796 } 797 798 #endif 799 800 #if (L_IMPL_MASK & AVL_IMPL_SUBST) 801 802 L_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) 803 { 804 AVL_HANDLE h = l_tree->root; 805 AVL_HANDLE parent = AVL_NULL; 806 int cmp, last_cmp; 807 808 /* Search for node already in tree with same key. */ 809 for (; ;) 810 { 811 if (h == AVL_NULL) 812 /* No node in tree with same key as new node. */ 813 return(AVL_NULL); 814 815 cmp = AVL_COMPARE_NODE_NODE(new_node, h); 816 817 if (cmp == 0) 818 /* Found the node to substitute new one for. */ 819 break; 820 821 last_cmp = cmp; 822 parent = h; 823 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 824 L_CHECK_READ_ERROR(AVL_NULL) 825 } 826 827 /* Copy tree housekeeping fields from node in tree to new node. */ 828 AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) 829 AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) 830 AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) 831 832 if (parent == AVL_NULL) 833 /* New node is also new root. */ 834 l_tree->root = new_node; 835 else 836 { 837 /* Make parent point to new node. */ 838 if (last_cmp < 0) 839 AVL_SET_LESS(parent, new_node) 840 else 841 AVL_SET_GREATER(parent, new_node) 842 } 843 844 return(h); 845 } 846 847 #endif 848 849 #ifdef AVL_BUILD_ITER_TYPE 850 851 #if (L_IMPL_MASK & AVL_IMPL_BUILD) 852 853 L_SC int L_(build)( 854 L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) 855 { 856 /* Gives path to subtree being built. If bit n is false, branch 857 ** less from the node at depth n, if true branch greater. */ 858 L_BIT_ARR_DEFN(branch) 859 860 /* If bit n is true, then for the current subtree at depth n, its 861 ** greater subtree has one more node than its less subtree. */ 862 L_BIT_ARR_DEFN(rem) 863 864 /* Depth of root node of current subtree. */ 865 unsigned depth = 0; 866 867 /* Number of nodes in current subtree. */ 868 L_SIZE num_sub = num_nodes; 869 870 /* The algorithm relies on a stack of nodes whose less subtree has 871 ** been built, but whose greater subtree has not yet been built. 872 ** The stack is implemented as linked list. The nodes are linked 873 ** together by having the "greater" handle of a node set to the 874 ** next node in the list. "less_parent" is the handle of the first 875 ** node in the list. */ 876 AVL_HANDLE less_parent = AVL_NULL; 877 878 /* h is root of current subtree, child is one of its children. */ 879 AVL_HANDLE h; 880 AVL_HANDLE child; 881 882 if (num_nodes == 0) 883 { 884 l_tree->root = AVL_NULL; 885 return(1); 886 } 887 888 for (; ;) 889 { 890 while (num_sub > 2) 891 { 892 /* Subtract one for root of subtree. */ 893 num_sub--; 894 895 if (num_sub & 1) 896 L_BIT_ARR_1(rem, depth) 897 else 898 L_BIT_ARR_0(rem, depth) 899 L_BIT_ARR_0(branch, depth) 900 depth++; 901 902 num_sub >>= 1; 903 } 904 905 if (num_sub == 2) 906 { 907 /* Build a subtree with two nodes, slanting to greater. 908 ** I arbitrarily chose to always have the extra node in the 909 ** greater subtree when there is an odd number of nodes to 910 ** split between the two subtrees. */ 911 912 h = AVL_BUILD_ITER_VAL(p); 913 L_CHECK_READ_ERROR(0) 914 AVL_BUILD_ITER_INCR(p) 915 child = AVL_BUILD_ITER_VAL(p); 916 L_CHECK_READ_ERROR(0) 917 AVL_BUILD_ITER_INCR(p) 918 AVL_SET_LESS(child, AVL_NULL) 919 AVL_SET_GREATER(child, AVL_NULL) 920 AVL_SET_BALANCE_FACTOR(child, 0) 921 AVL_SET_GREATER(h, child) 922 AVL_SET_LESS(h, AVL_NULL) 923 AVL_SET_BALANCE_FACTOR(h, 1) 924 } 925 else /* num_sub == 1 */ 926 { 927 /* Build a subtree with one node. */ 928 929 h = AVL_BUILD_ITER_VAL(p); 930 L_CHECK_READ_ERROR(0) 931 AVL_BUILD_ITER_INCR(p) 932 AVL_SET_LESS(h, AVL_NULL) 933 AVL_SET_GREATER(h, AVL_NULL) 934 AVL_SET_BALANCE_FACTOR(h, 0) 935 } 936 937 while (depth) 938 { 939 depth--; 940 941 if (!L_BIT_ARR_VAL(branch, depth)) 942 /* We've completed a less subtree. */ 943 break; 944 945 /* We've completed a greater subtree, so attach it to 946 ** its parent (that is less than it). We pop the parent 947 ** off the stack of less parents. */ 948 child = h; 949 h = less_parent; 950 less_parent = AVL_GET_GREATER(h, 1); 951 L_CHECK_READ_ERROR(0) 952 AVL_SET_GREATER(h, child) 953 /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ 954 num_sub <<= 1; 955 num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; 956 957 if (num_sub & (num_sub - 1)) 958 /* num_sub is not a power of 2. */ 959 AVL_SET_BALANCE_FACTOR(h, 0) 960 else 961 /* num_sub is a power of 2. */ 962 AVL_SET_BALANCE_FACTOR(h, 1) 963 } 964 965 if (num_sub == num_nodes) 966 /* We've completed the full tree. */ 967 break; 968 969 /* The subtree we've completed is the less subtree of the 970 ** next node in the sequence. */ 971 972 child = h; 973 h = AVL_BUILD_ITER_VAL(p); 974 L_CHECK_READ_ERROR(0) 975 AVL_BUILD_ITER_INCR(p) 976 AVL_SET_LESS(h, child) 977 978 /* Put h into stack of less parents. */ 979 AVL_SET_GREATER(h, less_parent) 980 less_parent = h; 981 982 /* Proceed to creating greater than subtree of h. */ 983 L_BIT_ARR_1(branch, depth) 984 num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; 985 depth++; 986 987 } /* end for ( ; ; ) */ 988 989 l_tree->root = h; 990 991 return(1); 992 } 993 994 #endif 995 996 #endif 997 998 #if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) 999 1000 /* Initialize depth to invalid value, to indicate iterator is 1001 ** invalid. (Depth is zero-base.) It's not necessary to initialize 1002 ** iterators prior to passing them to the "start" function. 1003 */ 1004 L_SC void L_(init_iter)(L_(iter) *iter) 1005 { 1006 iter->depth = ~0; 1007 } 1008 1009 #endif 1010 1011 #ifdef AVL_READ_ERRORS_HAPPEN 1012 1013 #define L_CHECK_READ_ERROR_INV_DEPTH \ 1014 { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } 1015 1016 #else 1017 1018 #define L_CHECK_READ_ERROR_INV_DEPTH 1019 1020 #endif 1021 1022 #if (L_IMPL_MASK & AVL_IMPL_START_ITER) 1023 1024 L_SC void L_(start_iter)( 1025 L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) 1026 { 1027 AVL_HANDLE h = l_tree->root; 1028 unsigned d = 0; 1029 int cmp, target_cmp; 1030 1031 /* Save the tree that we're going to iterate through in a 1032 ** member variable. */ 1033 iter->tree_ = l_tree; 1034 1035 iter->depth = ~0; 1036 1037 if (h == AVL_NULL) 1038 /* Tree is empty. */ 1039 return; 1040 1041 if (st & AVL_LESS) 1042 /* Key can be greater than key of starting node. */ 1043 target_cmp = 1; 1044 else if (st & AVL_GREATER) 1045 /* Key can be less than key of starting node. */ 1046 target_cmp = -1; 1047 else 1048 /* Key must be same as key of starting node. */ 1049 target_cmp = 0; 1050 1051 for (; ;) 1052 { 1053 cmp = AVL_COMPARE_KEY_NODE(k, h); 1054 1055 if (cmp == 0) 1056 { 1057 if (st & AVL_EQUAL) 1058 { 1059 /* Equal node was sought and found as starting node. */ 1060 iter->depth = d; 1061 break; 1062 } 1063 1064 cmp = -target_cmp; 1065 } 1066 else if (target_cmp != 0) 1067 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 1068 /* cmp and target_cmp are both negative or both positive. */ 1069 iter->depth = d; 1070 1071 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 1072 L_CHECK_READ_ERROR_INV_DEPTH 1073 1074 if (h == AVL_NULL) 1075 break; 1076 1077 if (cmp > 0) 1078 L_BIT_ARR_1(iter->branch, d) 1079 else 1080 L_BIT_ARR_0(iter->branch, d) 1081 iter->path_h[d++] = h; 1082 } 1083 } 1084 1085 #endif 1086 1087 #if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) 1088 1089 L_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) 1090 { 1091 AVL_HANDLE h = l_tree->root; 1092 1093 iter->tree_ = l_tree; 1094 1095 iter->depth = ~0; 1096 1097 L_BIT_ARR_ALL(iter->branch, 0) 1098 1099 while (h != AVL_NULL) 1100 { 1101 if (iter->depth != ~0) 1102 iter->path_h[iter->depth] = h; 1103 1104 iter->depth++; 1105 h = AVL_GET_LESS(h, 1); 1106 L_CHECK_READ_ERROR_INV_DEPTH 1107 } 1108 } 1109 1110 #endif 1111 1112 #if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) 1113 1114 L_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) 1115 { 1116 AVL_HANDLE h = l_tree->root; 1117 1118 iter->tree_ = l_tree; 1119 1120 iter->depth = ~0; 1121 1122 L_BIT_ARR_ALL(iter->branch, 1) 1123 1124 while (h != AVL_NULL) 1125 { 1126 if (iter->depth != ~0) 1127 iter->path_h[iter->depth] = h; 1128 1129 iter->depth++; 1130 h = AVL_GET_GREATER(h, 1); 1131 L_CHECK_READ_ERROR_INV_DEPTH 1132 } 1133 } 1134 1135 #endif 1136 1137 #if (L_IMPL_MASK & AVL_IMPL_GET_ITER) 1138 1139 L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) 1140 { 1141 if (iter->depth == ~0) 1142 return(AVL_NULL); 1143 1144 return(iter->depth == 0 ? 1145 iter->tree_->root : iter->path_h[iter->depth - 1]); 1146 } 1147 1148 #endif 1149 1150 #if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) 1151 1152 L_SC void L_(incr_iter)(L_(iter) *iter) 1153 { 1154 #define l_tree (iter->tree_) 1155 1156 if (iter->depth != ~0) 1157 { 1158 AVL_HANDLE h = 1159 AVL_GET_GREATER((iter->depth == 0 ? 1160 iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1161 L_CHECK_READ_ERROR_INV_DEPTH 1162 1163 if (h == AVL_NULL) 1164 do 1165 { 1166 if (iter->depth == 0) 1167 { 1168 iter->depth = ~0; 1169 break; 1170 } 1171 1172 iter->depth--; 1173 } 1174 while (L_BIT_ARR_VAL(iter->branch, iter->depth)); 1175 else 1176 { 1177 L_BIT_ARR_1(iter->branch, iter->depth) 1178 iter->path_h[iter->depth++] = h; 1179 1180 for (; ;) 1181 { 1182 h = AVL_GET_LESS(h, 1); 1183 L_CHECK_READ_ERROR_INV_DEPTH 1184 1185 if (h == AVL_NULL) 1186 break; 1187 1188 L_BIT_ARR_0(iter->branch, iter->depth) 1189 iter->path_h[iter->depth++] = h; 1190 } 1191 } 1192 } 1193 1194 #undef l_tree 1195 } 1196 1197 #endif 1198 1199 #if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) 1200 1201 L_SC void L_(decr_iter)(L_(iter) *iter) 1202 { 1203 #define l_tree (iter->tree_) 1204 1205 if (iter->depth != ~0) 1206 { 1207 AVL_HANDLE h = 1208 AVL_GET_LESS((iter->depth == 0 ? 1209 iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1210 L_CHECK_READ_ERROR_INV_DEPTH 1211 1212 if (h == AVL_NULL) 1213 do 1214 { 1215 if (iter->depth == 0) 1216 { 1217 iter->depth = ~0; 1218 break; 1219 } 1220 1221 iter->depth--; 1222 } 1223 while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); 1224 else 1225 { 1226 L_BIT_ARR_0(iter->branch, iter->depth) 1227 iter->path_h[iter->depth++] = h; 1228 1229 for (; ;) 1230 { 1231 h = AVL_GET_GREATER(h, 1); 1232 L_CHECK_READ_ERROR_INV_DEPTH 1233 1234 if (h == AVL_NULL) 1235 break; 1236 1237 L_BIT_ARR_1(iter->branch, iter->depth) 1238 iter->path_h[iter->depth++] = h; 1239 } 1240 } 1241 } 1242 1243 #undef l_tree 1244 } 1245 1246 #endif 1247 1248 /* Tidy up the preprocessor symbol name space. */ 1249 #undef L_ 1250 #undef L_EST_LONG_BIT 1251 #undef L_SIZE 1252 #undef L_MASK_HIGH_BIT 1253 #undef L_LONG_BIT 1254 #undef L_BIT_ARR_DEFN 1255 #undef L_BIT_ARR_VAL 1256 #undef L_BIT_ARR_0 1257 #undef L_BIT_ARR_1 1258 #undef L_BIT_ARR_ALL 1259 #undef L_CHECK_READ_ERROR 1260 #undef L_CHECK_READ_ERROR_INV_DEPTH 1261 #undef L_BIT_ARR_LONGS 1262 #undef L_IMPL_MASK 1263 #undef L_CHECK_READ_ERROR 1264 #undef L_CHECK_READ_ERROR_INV_DEPTH 1265 #undef L_SC 1266 #undef L_BALANCE_PARAM_CALL_PREFIX 1267 #undef L_BALANCE_PARAM_DECL_PREFIX 1268
