| OLD | NEW |
|---|
| (Empty) |
| 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_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 17462005:
IndexedDB: Replace transaction's AVLTree with std::map (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src