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