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