1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 /* 6 * Copyright (C) 2008 Apple Inc. All rights reserved. 7 * 8 * Based on Abstract AVL Tree Template v1.5 by Walt Karas 9 * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 21 * its contributors may be used to endorse or promote products derived 22 * from this software without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 25 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 27 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 28 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 31 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 33 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 #ifndef CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_ 37 #define CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_ 38 39 #include "base/logging.h" 40 #include "content/browser/indexed_db/leveldb/fixed_array.h" 41 42 namespace content { 43 44 // Here is the reference class for BSet. 45 // 46 // class BSet 47 // { 48 // public: 49 // 50 // class ANY_bitref 51 // { 52 // public: 53 // operator bool (); 54 // void operator = (bool b); 55 // }; 56 // 57 // // Does not have to initialize bits. 58 // BSet(); 59 // 60 // // Must return a valid value for index when 0 <= index < maxDepth 61 // ANY_bitref operator [] (unsigned index); 62 // 63 // // Set all bits to 1. 64 // void Set(); 65 // 66 // // Set all bits to 0. 67 // void Reset(); 68 // }; 69 70 template <unsigned maxDepth> 71 class AVLTreeDefaultBSet { 72 public: 73 bool& operator[](unsigned i) { 74 #if defined(ADDRESS_SANITIZER) 75 CHECK(i < maxDepth); 76 #endif 77 return data_[i]; 78 } 79 void Set() { 80 for (unsigned i = 0; i < maxDepth; ++i) 81 data_[i] = true; 82 } 83 void Reset() { 84 for (unsigned i = 0; i < maxDepth; ++i) 85 data_[i] = false; 86 } 87 88 private: 89 FixedArray<bool, maxDepth> data_; 90 }; 91 92 // How to determine maxDepth: 93 // d Minimum number of nodes 94 // 2 2 95 // 3 4 96 // 4 7 97 // 5 12 98 // 6 20 99 // 7 33 100 // 8 54 101 // 9 88 102 // 10 143 103 // 11 232 104 // 12 376 105 // 13 609 106 // 14 986 107 // 15 1,596 108 // 16 2,583 109 // 17 4,180 110 // 18 6,764 111 // 19 10,945 112 // 20 17,710 113 // 21 28,656 114 // 22 46,367 115 // 23 75,024 116 // 24 121,392 117 // 25 196,417 118 // 26 317,810 119 // 27 514,228 120 // 28 832,039 121 // 29 1,346,268 122 // 30 2,178,308 123 // 31 3,524,577 124 // 32 5,702,886 125 // 33 9,227,464 126 // 34 14,930,351 127 // 35 24,157,816 128 // 36 39,088,168 129 // 37 63,245,985 130 // 38 102,334,154 131 // 39 165,580,140 132 // 40 267,914,295 133 // 41 433,494,436 134 // 42 701,408,732 135 // 43 1,134,903,169 136 // 44 1,836,311,902 137 // 45 2,971,215,072 138 // 139 // E.g., if, in a particular instantiation, the maximum number of nodes in a 140 // tree instance is 1,000,000, the maximum depth should be 28. 141 // You pick 28 because MN(28) is 832,039, which is less than or equal to 142 // 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000. 143 144 template <class Abstractor, 145 unsigned maxDepth = 32, 146 class BSet = AVLTreeDefaultBSet<maxDepth> > 147 class AVLTree { 148 public: 149 typedef typename Abstractor::key key; 150 typedef typename Abstractor::handle handle; 151 typedef typename Abstractor::size size; 152 153 enum SearchType { 154 EQUAL = 1, 155 LESS = 2, 156 GREATER = 4, 157 LESS_EQUAL = EQUAL | LESS, 158 GREATER_EQUAL = EQUAL | GREATER 159 }; 160 161 Abstractor& abstractor() { return abs_; } 162 163 inline handle Insert(handle h); 164 165 inline handle Search(key k, SearchType st = EQUAL); 166 inline handle SearchLeast(); 167 inline handle SearchGreatest(); 168 169 inline handle Remove(key k); 170 171 inline handle Subst(handle new_node); 172 173 void Purge() { abs_.root = Null(); } 174 175 bool IsEmpty() { return abs_.root == Null(); } 176 177 AVLTree() { abs_.root = Null(); } 178 179 class Iterator { 180 public: 181 // Initialize depth to invalid value, to indicate iterator is 182 // invalid. (Depth is zero-base.) 183 Iterator() { depth_ = ~0U; } 184 185 void StartIter(AVLTree* tree, key k, SearchType st = EQUAL) { 186 // Mask of high bit in an int. 187 const int kMaskHighBit = static_cast<int>(~((~(unsigned)0) >> 1)); 188 189 // Save the tree that we're going to iterate through in a 190 // member variable. 191 tree_ = tree; 192 193 int cmp, target_cmp; 194 handle h = tree_->abs_.root; 195 unsigned d = 0; 196 197 depth_ = ~0U; 198 199 if (h == Null()) { 200 // Tree is empty. 201 return; 202 } 203 204 if (st & LESS) { 205 // Key can be greater than key of starting node. 206 target_cmp = 1; 207 } else if (st & GREATER) { 208 // Key can be less than key of starting node. 209 target_cmp = -1; 210 } else { 211 // Key must be same as key of starting node. 212 target_cmp = 0; 213 } 214 215 for (;;) { 216 cmp = CmpKN(k, h); 217 if (cmp == 0) { 218 if (st & EQUAL) { 219 // Equal node was sought and found as starting node. 220 depth_ = d; 221 break; 222 } 223 cmp = -target_cmp; 224 } else if (target_cmp != 0) { 225 if (!((cmp ^ target_cmp) & kMaskHighBit)) { 226 // cmp and target_cmp are both negative or both positive. 227 depth_ = d; 228 } 229 } 230 h = cmp < 0 ? GetLT(h) : GetGT(h); 231 if (h == Null()) 232 break; 233 branch_[d] = cmp > 0; 234 path_h_[d++] = h; 235 } 236 } 237 238 void StartIterLeast(AVLTree* tree) { 239 tree_ = tree; 240 241 handle h = tree_->abs_.root; 242 243 depth_ = ~0U; 244 245 branch_.Reset(); 246 247 while (h != Null()) { 248 if (depth_ != ~0U) 249 path_h_[depth_] = h; 250 depth_++; 251 h = GetLT(h); 252 } 253 } 254 255 void StartIterGreatest(AVLTree* tree) { 256 tree_ = tree; 257 258 handle h = tree_->abs_.root; 259 260 depth_ = ~0U; 261 262 branch_.Set(); 263 264 while (h != Null()) { 265 if (depth_ != ~0U) 266 path_h_[depth_] = h; 267 depth_++; 268 h = GetGT(h); 269 } 270 } 271 272 handle operator*() { 273 if (depth_ == ~0U) 274 return Null(); 275 276 return depth_ == 0 ? tree_->abs_.root : path_h_[depth_ - 1]; 277 } 278 279 void operator++() { 280 if (depth_ != ~0U) { 281 handle h = GetGT(**this); 282 if (h == Null()) { 283 do { 284 if (depth_ == 0) { 285 depth_ = ~0U; 286 break; 287 } 288 depth_--; 289 } while (branch_[depth_]); 290 } else { 291 branch_[depth_] = true; 292 path_h_[depth_++] = h; 293 for (;;) { 294 h = GetLT(h); 295 if (h == Null()) 296 break; 297 branch_[depth_] = false; 298 path_h_[depth_++] = h; 299 } 300 } 301 } 302 } 303 304 void operator--() { 305 if (depth_ != ~0U) { 306 handle h = GetLT(**this); 307 if (h == Null()) { 308 do { 309 if (depth_ == 0) { 310 depth_ = ~0U; 311 break; 312 } 313 depth_--; 314 } while (!branch_[depth_]); 315 } else { 316 branch_[depth_] = false; 317 path_h_[depth_++] = h; 318 for (;;) { 319 h = GetGT(h); 320 if (h == Null()) 321 break; 322 branch_[depth_] = true; 323 path_h_[depth_++] = h; 324 } 325 } 326 } 327 } 328 329 void operator++(int /*ignored*/) { ++(*this); } 330 void operator--(int /*ignored*/) { --(*this); } 331 332 protected: 333 // Tree being iterated over. 334 AVLTree* tree_; 335 336 // Records a path into the tree. If branch_[n] is true, indicates 337 // take greater branch from the nth node in the path, otherwise 338 // take the less branch. branch_[0] gives branch from root, and 339 // so on. 340 BSet branch_; 341 342 // Zero-based depth of path into tree. 343 unsigned depth_; 344 345 // Handles of nodes in path from root to current node (returned by *). 346 static const size_t kPathSize = maxDepth - 1; 347 handle path_h_[kPathSize]; 348 349 int CmpKN(key k, handle h) { return tree_->abs_.CompareKeyNode(k, h); } 350 int CmpNN(handle h1, handle h2) { 351 return tree_->abs_.CompareNodeNode(h1, h2); 352 } 353 handle GetLT(handle h) { return tree_->abs_.GetLess(h); } 354 handle GetGT(handle h) { return tree_->abs_.GetGreater(h); } 355 handle Null() { return tree_->abs_.Null(); } 356 }; 357 358 template <typename fwd_iter> 359 bool Build(fwd_iter p, size num_nodes) { 360 if (num_nodes == 0) { 361 abs_.root = Null(); 362 return true; 363 } 364 365 // Gives path to subtree being built. If branch[N] is false, branch 366 // less from the node at depth N, if true branch greater. 367 BSet branch; 368 369 // If rem[N] is true, then for the current subtree at depth N, it's 370 // greater subtree has one more node than it's less subtree. 371 BSet rem; 372 373 // Depth of root node of current subtree. 374 unsigned depth = 0; 375 376 // Number of nodes in current subtree. 377 size num_sub = num_nodes; 378 379 // The algorithm relies on a stack of nodes whose less subtree has 380 // been built, but whose right subtree has not yet been built. The 381 // stack is implemented as linked list. The nodes are linked 382 // together by having the "greater" handle of a node set to the 383 // next node in the list. "less_parent" is the handle of the first 384 // node in the list. 385 handle less_parent = Null(); 386 387 // h is root of current subtree, child is one of its children. 388 handle h, child; 389 390 for (;;) { 391 while (num_sub > 2) { 392 // Subtract one for root of subtree. 393 num_sub--; 394 rem[depth] = !!(num_sub & 1); 395 branch[depth++] = false; 396 num_sub >>= 1; 397 } 398 399 if (num_sub == 2) { 400 // Build a subtree with two nodes, slanting to greater. 401 // I arbitrarily chose to always have the extra node in the 402 // greater subtree when there is an odd number of nodes to 403 // split between the two subtrees. 404 405 h = *p; 406 p++; 407 child = *p; 408 p++; 409 SetLT(child, Null()); 410 SetGT(child, Null()); 411 SetBF(child, 0); 412 SetGT(h, child); 413 SetLT(h, Null()); 414 SetBF(h, 1); 415 } else { // num_sub == 1 416 // Build a subtree with one node. 417 418 h = *p; 419 p++; 420 SetLT(h, Null()); 421 SetGT(h, Null()); 422 SetBF(h, 0); 423 } 424 425 while (depth) { 426 depth--; 427 if (!branch[depth]) { 428 // We've completed a less subtree. 429 break; 430 } 431 432 // We've completed a greater subtree, so attach it to 433 // its parent (that is less than it). We pop the parent 434 // off the stack of less parents. 435 child = h; 436 h = less_parent; 437 less_parent = GetGT(h); 438 SetGT(h, child); 439 // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 440 num_sub <<= 1; 441 num_sub += 1 - rem[depth]; 442 if (num_sub & (num_sub - 1)) { 443 // num_sub is not a power of 2 444 SetBF(h, 0); 445 } else { 446 // num_sub is a power of 2 447 SetBF(h, 1); 448 } 449 } 450 451 if (num_sub == num_nodes) { 452 // We've completed the full tree. 453 break; 454 } 455 456 // The subtree we've completed is the less subtree of the 457 // next node in the sequence. 458 459 child = h; 460 h = *p; 461 p++; 462 SetLT(h, child); 463 464 // Put h into stack of less parents. 465 SetGT(h, less_parent); 466 less_parent = h; 467 468 // Proceed to creating greater than subtree of h. 469 branch[depth] = true; 470 num_sub += rem[depth++]; 471 } // end for (;;) 472 473 abs_.root = h; 474 475 return true; 476 } 477 478 protected: 479 friend class Iterator; 480 481 // Create a class whose sole purpose is to take advantage of 482 // the "empty member" optimization. 483 struct abs_plus_root : public Abstractor { 484 // The handle of the root element in the AVL tree. 485 handle root; 486 }; 487 488 abs_plus_root abs_; 489 490 handle GetLT(handle h) { return abs_.GetLess(h); } 491 void SetLT(handle h, handle lh) { abs_.SetLess(h, lh); } 492 493 handle GetGT(handle h) { return abs_.GetGreater(h); } 494 void SetGT(handle h, handle gh) { abs_.SetGreater(h, gh); } 495 496 int GetBF(handle h) { return abs_.GetBalanceFactor(h); } 497 void SetBF(handle h, int bf) { abs_.SetBalanceFactor(h, bf); } 498 499 int CmpKN(key k, handle h) { return abs_.CompareKeyNode(k, h); } 500 int CmpNN(handle h1, handle h2) { return abs_.CompareNodeNode(h1, h2); } 501 502 handle Null() { return abs_.Null(); } 503 504 private: 505 // Balances subtree, returns handle of root node of subtree 506 // after balancing. 507 handle Balance(handle bal_h) { 508 handle deep_h; 509 510 // Either the "greater than" or the "less than" subtree of 511 // this node has to be 2 levels deeper (or else it wouldn't 512 // need balancing). 513 514 if (GetBF(bal_h) > 0) { 515 // "Greater than" subtree is deeper. 516 517 deep_h = GetGT(bal_h); 518 519 if (GetBF(deep_h) < 0) { 520 handle old_h = bal_h; 521 bal_h = GetLT(deep_h); 522 523 SetGT(old_h, GetLT(bal_h)); 524 SetLT(deep_h, GetGT(bal_h)); 525 SetLT(bal_h, old_h); 526 SetGT(bal_h, deep_h); 527 528 int bf = GetBF(bal_h); 529 if (bf != 0) { 530 if (bf > 0) { 531 SetBF(old_h, -1); 532 SetBF(deep_h, 0); 533 } else { 534 SetBF(deep_h, 1); 535 SetBF(old_h, 0); 536 } 537 SetBF(bal_h, 0); 538 } else { 539 SetBF(old_h, 0); 540 SetBF(deep_h, 0); 541 } 542 } else { 543 SetGT(bal_h, GetLT(deep_h)); 544 SetLT(deep_h, bal_h); 545 if (GetBF(deep_h) == 0) { 546 SetBF(deep_h, -1); 547 SetBF(bal_h, 1); 548 } else { 549 SetBF(deep_h, 0); 550 SetBF(bal_h, 0); 551 } 552 bal_h = deep_h; 553 } 554 } else { 555 // "Less than" subtree is deeper. 556 557 deep_h = GetLT(bal_h); 558 559 if (GetBF(deep_h) > 0) { 560 handle old_h = bal_h; 561 bal_h = GetGT(deep_h); 562 SetLT(old_h, GetGT(bal_h)); 563 SetGT(deep_h, GetLT(bal_h)); 564 SetGT(bal_h, old_h); 565 SetLT(bal_h, deep_h); 566 567 int bf = GetBF(bal_h); 568 if (bf != 0) { 569 if (bf < 0) { 570 SetBF(old_h, 1); 571 SetBF(deep_h, 0); 572 } else { 573 SetBF(deep_h, -1); 574 SetBF(old_h, 0); 575 } 576 SetBF(bal_h, 0); 577 } else { 578 SetBF(old_h, 0); 579 SetBF(deep_h, 0); 580 } 581 } else { 582 SetLT(bal_h, GetGT(deep_h)); 583 SetGT(deep_h, bal_h); 584 if (GetBF(deep_h) == 0) { 585 SetBF(deep_h, 1); 586 SetBF(bal_h, -1); 587 } else { 588 SetBF(deep_h, 0); 589 SetBF(bal_h, 0); 590 } 591 bal_h = deep_h; 592 } 593 } 594 595 return bal_h; 596 } 597 }; 598 599 template <class Abstractor, unsigned maxDepth, class BSet> 600 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 601 AVLTree<Abstractor, maxDepth, BSet>::Insert(handle h) { 602 SetLT(h, Null()); 603 SetGT(h, Null()); 604 SetBF(h, 0); 605 606 if (abs_.root == Null()) { 607 abs_.root = h; 608 } else { 609 // Last unbalanced node encountered in search for insertion point. 610 handle unbal = Null(); 611 // Parent of last unbalanced node. 612 handle parent_unbal = Null(); 613 // Balance factor of last unbalanced node. 614 int unbal_bf; 615 616 // Zero-based depth in tree. 617 unsigned depth = 0, unbal_depth = 0; 618 619 // Records a path into the tree. If branch[n] is true, indicates 620 // take greater branch from the nth node in the path, otherwise 621 // take the less branch. branch[0] gives branch from root, and 622 // so on. 623 BSet branch; 624 625 handle hh = abs_.root; 626 handle parent = Null(); 627 int cmp; 628 629 do { 630 if (GetBF(hh) != 0) { 631 unbal = hh; 632 parent_unbal = parent; 633 unbal_depth = depth; 634 } 635 cmp = CmpNN(h, hh); 636 if (cmp == 0) { 637 // Duplicate key. 638 return hh; 639 } 640 parent = hh; 641 hh = cmp < 0 ? GetLT(hh) : GetGT(hh); 642 branch[depth++] = cmp > 0; 643 } while (hh != Null()); 644 645 // Add node to insert as leaf of tree. 646 if (cmp < 0) 647 SetLT(parent, h); 648 else 649 SetGT(parent, h); 650 651 depth = unbal_depth; 652 653 if (unbal == Null()) { 654 hh = abs_.root; 655 } else { 656 cmp = branch[depth++] ? 1 : -1; 657 unbal_bf = GetBF(unbal); 658 if (cmp < 0) 659 unbal_bf--; 660 else // cmp > 0 661 unbal_bf++; 662 hh = cmp < 0 ? GetLT(unbal) : GetGT(unbal); 663 if ((unbal_bf != -2) && (unbal_bf != 2)) { 664 // No rebalancing of tree is necessary. 665 SetBF(unbal, unbal_bf); 666 unbal = Null(); 667 } 668 } 669 670 if (hh != Null()) { 671 while (h != hh) { 672 cmp = branch[depth++] ? 1 : -1; 673 if (cmp < 0) { 674 SetBF(hh, -1); 675 hh = GetLT(hh); 676 } else { // cmp > 0 677 SetBF(hh, 1); 678 hh = GetGT(hh); 679 } 680 } 681 } 682 683 if (unbal != Null()) { 684 unbal = Balance(unbal); 685 if (parent_unbal == Null()) { 686 abs_.root = unbal; 687 } else { 688 depth = unbal_depth - 1; 689 cmp = branch[depth] ? 1 : -1; 690 if (cmp < 0) 691 SetLT(parent_unbal, unbal); 692 else // cmp > 0 693 SetGT(parent_unbal, unbal); 694 } 695 } 696 } 697 698 return h; 699 } 700 701 template <class Abstractor, unsigned maxDepth, class BSet> 702 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 703 AVLTree<Abstractor, maxDepth, BSet>::Search( 704 key k, 705 typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st) { 706 const int kMaskHighBit = static_cast<int>(~((~(unsigned)0) >> 1)); 707 708 int cmp, target_cmp; 709 handle match_h = Null(); 710 handle h = abs_.root; 711 712 if (st & LESS) 713 target_cmp = 1; 714 else if (st & GREATER) 715 target_cmp = -1; 716 else 717 target_cmp = 0; 718 719 while (h != Null()) { 720 cmp = CmpKN(k, h); 721 if (cmp == 0) { 722 if (st & EQUAL) { 723 match_h = h; 724 break; 725 } 726 cmp = -target_cmp; 727 } else if (target_cmp != 0) { 728 if (!((cmp ^ target_cmp) & kMaskHighBit)) { 729 // cmp and target_cmp are both positive or both negative. 730 match_h = h; 731 } 732 } 733 h = cmp < 0 ? GetLT(h) : GetGT(h); 734 } 735 736 return match_h; 737 } 738 739 template <class Abstractor, unsigned maxDepth, class BSet> 740 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 741 AVLTree<Abstractor, maxDepth, BSet>::SearchLeast() { 742 handle h = abs_.root, parent = Null(); 743 744 while (h != Null()) { 745 parent = h; 746 h = GetLT(h); 747 } 748 749 return parent; 750 } 751 752 template <class Abstractor, unsigned maxDepth, class BSet> 753 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 754 AVLTree<Abstractor, maxDepth, BSet>::SearchGreatest() { 755 handle h = abs_.root, parent = Null(); 756 757 while (h != Null()) { 758 parent = h; 759 h = GetGT(h); 760 } 761 762 return parent; 763 } 764 765 template <class Abstractor, unsigned maxDepth, class BSet> 766 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 767 AVLTree<Abstractor, maxDepth, BSet>::Remove(key k) { 768 // Zero-based depth in tree. 769 unsigned depth = 0, rm_depth; 770 771 // Records a path into the tree. If branch[n] is true, indicates 772 // take greater branch from the nth node in the path, otherwise 773 // take the less branch. branch[0] gives branch from root, and 774 // so on. 775 BSet branch; 776 777 handle h = abs_.root; 778 handle parent = Null(), child; 779 int cmp, cmp_shortened_sub_with_path = 0; 780 781 for (;;) { 782 if (h == Null()) { 783 // No node in tree with given key. 784 return Null(); 785 } 786 cmp = CmpKN(k, h); 787 if (cmp == 0) { 788 // Found node to remove. 789 break; 790 } 791 parent = h; 792 h = cmp < 0 ? GetLT(h) : GetGT(h); 793 branch[depth++] = cmp > 0; 794 cmp_shortened_sub_with_path = cmp; 795 } 796 handle rm = h; 797 handle parent_rm = parent; 798 rm_depth = depth; 799 800 // If the node to remove is not a leaf node, we need to get a 801 // leaf node, or a node with a single leaf as its child, to put 802 // in the place of the node to remove. We will get the greatest 803 // node in the less subtree (of the node to remove), or the least 804 // node in the greater subtree. We take the leaf node from the 805 // deeper subtree, if there is one. 806 807 if (GetBF(h) < 0) { 808 child = GetLT(h); 809 branch[depth] = false; 810 cmp = -1; 811 } else { 812 child = GetGT(h); 813 branch[depth] = true; 814 cmp = 1; 815 } 816 depth++; 817 818 if (child != Null()) { 819 cmp = -cmp; 820 do { 821 parent = h; 822 h = child; 823 if (cmp < 0) { 824 child = GetLT(h); 825 branch[depth] = false; 826 } else { 827 child = GetGT(h); 828 branch[depth] = true; 829 } 830 depth++; 831 } while (child != Null()); 832 833 if (parent == rm) { 834 // Only went through do loop once. Deleted node will be replaced 835 // in the tree structure by one of its immediate children. 836 cmp_shortened_sub_with_path = -cmp; 837 } else { 838 cmp_shortened_sub_with_path = cmp; 839 } 840 841 // Get the handle of the opposite child, which may not be null. 842 child = cmp > 0 ? GetLT(h) : GetGT(h); 843 } 844 845 if (parent == Null()) { 846 // There were only 1 or 2 nodes in this tree. 847 abs_.root = child; 848 } else if (cmp_shortened_sub_with_path < 0) { 849 SetLT(parent, child); 850 } else { 851 SetGT(parent, child); 852 } 853 854 // "path" is the parent of the subtree being eliminated or reduced 855 // from a depth of 2 to 1. If "path" is the node to be removed, we 856 // set path to the node we're about to poke into the position of the 857 // node to be removed. 858 handle path = parent == rm ? h : parent; 859 860 if (h != rm) { 861 // Poke in the replacement for the node to be removed. 862 SetLT(h, GetLT(rm)); 863 SetGT(h, GetGT(rm)); 864 SetBF(h, GetBF(rm)); 865 if (parent_rm == Null()) { 866 abs_.root = h; 867 } else { 868 depth = rm_depth - 1; 869 if (branch[depth]) 870 SetGT(parent_rm, h); 871 else 872 SetLT(parent_rm, h); 873 } 874 } 875 876 if (path != Null()) { 877 // Create a temporary linked list from the parent of the path node 878 // to the root node. 879 h = abs_.root; 880 parent = Null(); 881 depth = 0; 882 while (h != path) { 883 if (branch[depth++]) { 884 child = GetGT(h); 885 SetGT(h, parent); 886 } else { 887 child = GetLT(h); 888 SetLT(h, parent); 889 } 890 parent = h; 891 h = child; 892 } 893 894 // Climb from the path node to the root node using the linked 895 // list, restoring the tree structure and rebalancing as necessary. 896 bool reduced_depth = true; 897 int bf; 898 cmp = cmp_shortened_sub_with_path; 899 for (;;) { 900 if (reduced_depth) { 901 bf = GetBF(h); 902 if (cmp < 0) 903 bf++; 904 else // cmp > 0 905 bf--; 906 if ((bf == -2) || (bf == 2)) { 907 h = Balance(h); 908 bf = GetBF(h); 909 } else { 910 SetBF(h, bf); 911 } 912 reduced_depth = (bf == 0); 913 } 914 if (parent == Null()) 915 break; 916 child = h; 917 h = parent; 918 cmp = branch[--depth] ? 1 : -1; 919 if (cmp < 0) { 920 parent = GetLT(h); 921 SetLT(h, child); 922 } else { 923 parent = GetGT(h); 924 SetGT(h, child); 925 } 926 } 927 abs_.root = h; 928 } 929 930 return rm; 931 } 932 933 template <class Abstractor, unsigned maxDepth, class BSet> 934 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle 935 AVLTree<Abstractor, maxDepth, BSet>::Subst(handle new_node) { 936 handle h = abs_.root; 937 handle parent = Null(); 938 int cmp, last_cmp; 939 940 // Search for node already in tree with same key. 941 for (;;) { 942 if (h == Null()) { 943 // No node in tree with same key as new node. 944 return Null(); 945 } 946 cmp = CmpNN(new_node, h); 947 if (cmp == 0) { 948 // Found the node to substitute new one for. 949 break; 950 } 951 last_cmp = cmp; 952 parent = h; 953 h = cmp < 0 ? GetLT(h) : GetGT(h); 954 } 955 956 // Copy tree housekeeping fields from node in tree to new node. 957 SetLT(new_node, GetLT(h)); 958 SetGT(new_node, GetGT(h)); 959 SetBF(new_node, GetBF(h)); 960 961 if (parent == Null()) { 962 // New node is also new root. 963 abs_.root = new_node; 964 } else { 965 // Make parent point to new node. 966 if (last_cmp < 0) 967 SetLT(parent, new_node); 968 else 969 SetGT(parent, new_node); 970 } 971 972 return h; 973 } 974 975 } // namespace content 976 977 #endif // CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_ 978