code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/RedBlackTree.h

   1 /*
   2  * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  14  *     its contributors may be used to endorse or promote products derived
  15  *     from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #ifndef RedBlackTree_h
  30 #define RedBlackTree_h
  31
  32 #include <wtf/Assertions.h>
  33 #include <wtf/Noncopyable.h>
  34
  35 namespace WTF {
  36
  37 // This implements a red-black tree with the following properties:
  38 // - The allocation of nodes in the tree is entirely up to the user.
  39 // - If you are in possession of a pointer to a node, you can delete
  40 //   it from the tree. The tree will subsequently no longer have a
  41 //   reference to this node.
  42 // - The key type must implement operator< and ==.
  43
  44 template<typename KeyType, typename ValueType>
  45 class RedBlackTree {
  46     WTF_MAKE_NONCOPYABLE(RedBlackTree);
  47 private:
  48     enum Color {
  49         Red = 1,
  50         Black
  51     };
  52
  53 public:
  54     class Node {
  55         friend class RedBlackTree;
  56
  57     public:
  58         Node(KeyType key, ValueType value)
  59             : m_key(key)
  60             , m_value(value)
  61         {
  62         }
  63
  64         const Node* successor() const
  65         {
  66             const Node* x = this;
  67             if (x->right())
  68                 return treeMinimum(x->right());
  69             const Node* y = x->parent();
  70             while (y && x == y->right()) {
  71                 x = y;
  72                 y = y->parent();
  73             }
  74             return y;
  75         }
  76
  77         const Node* predecessor() const
  78         {
  79             const Node* x = this;
  80             if (x->left())
  81                 return treeMaximum(x->left());
  82             const Node* y = x->parent();
  83             while (y && x == y->left()) {
  84                 x = y;
  85                 y = y->parent();
  86             }
  87             return y;
  88         }
  89
  90         Node* successor()
  91         {
  92             return const_cast<Node*>(const_cast<const Node*>(this)->successor());
  93         }
  94
  95         Node* predecessor()
  96         {
  97             return const_cast<Node*>(const_cast<const Node*>(this)->predecessor());
  98         }
  99
 100         KeyType m_key;
 101         ValueType m_value;
 102
 103     private:
 104         void reset()
 105         {
 106             m_left = 0;
 107             m_right = 0;
 108             m_parentAndRed = 1; // initialize to red
 109         }
 110
 111         // NOTE: these methods should pack the parent and red into a single
 112         // word. But doing so appears to reveal a bug in the compiler.
 113         Node* parent() const
 114         {
 115             return reinterpret_cast<Node*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
 116         }
 117
 118         void setParent(Node* newParent)
 119         {
 120             m_parentAndRed = reinterpret_cast<uintptr_t>(newParent) | (m_parentAndRed & 1);
 121         }
 122
 123         Node* left() const
 124         {
 125             return m_left;
 126         }
 127
 128         void setLeft(Node* node)
 129         {
 130             m_left = node;
 131         }
 132
 133         Node* right() const
 134         {
 135             return m_right;
 136         }
 137
 138         void setRight(Node* node)
 139         {
 140             m_right = node;
 141         }
 142
 143         Color color() const
 144         {
 145             if (m_parentAndRed & 1)
 146                 return Red;
 147             return Black;
 148         }
 149
 150         void setColor(Color value)
 151         {
 152             if (value == Red)
 153                 m_parentAndRed |= 1;
 154             else
 155                 m_parentAndRed &= ~static_cast<uintptr_t>(1);
 156         }
 157
 158         Node* m_left;
 159         Node* m_right;
 160         uintptr_t m_parentAndRed;
 161     };
 162
 163     RedBlackTree()
 164         : m_root(0)
 165     {
 166     }
 167
 168     void insert(Node* x)
 169     {
 170         x->reset();
 171         treeInsert(x);
 172         x->setColor(Red);
 173
 174         while (x != m_root && x->parent()->color() == Red) {
 175             if (x->parent() == x->parent()->parent()->left()) {
 176                 Node* y = x->parent()->parent()->right();
 177                 if (y && y->color() == Red) {
 178                     // Case 1
 179                     x->parent()->setColor(Black);
 180                     y->setColor(Black);
 181                     x->parent()->parent()->setColor(Red);
 182                     x = x->parent()->parent();
 183                 } else {
 184                     if (x == x->parent()->right()) {
 185                         // Case 2
 186                         x = x->parent();
 187                         leftRotate(x);
 188                     }
 189                     // Case 3
 190                     x->parent()->setColor(Black);
 191                     x->parent()->parent()->setColor(Red);
 192                     rightRotate(x->parent()->parent());
 193                 }
 194             } else {
 195                 // Same as "then" clause with "right" and "left" exchanged.
 196                 Node* y = x->parent()->parent()->left();
 197                 if (y && y->color() == Red) {
 198                     // Case 1
 199                     x->parent()->setColor(Black);
 200                     y->setColor(Black);
 201                     x->parent()->parent()->setColor(Red);
 202                     x = x->parent()->parent();
 203                 } else {
 204                     if (x == x->parent()->left()) {
 205                         // Case 2
 206                         x = x->parent();
 207                         rightRotate(x);
 208                     }
 209                     // Case 3
 210                     x->parent()->setColor(Black);
 211                     x->parent()->parent()->setColor(Red);
 212                     leftRotate(x->parent()->parent());
 213                 }
 214             }
 215         }
 216
 217         m_root->setColor(Black);
 218     }
 219
 220     Node* remove(Node* z)
 221     {
 222         ASSERT(z);
 223         ASSERT(z->parent() || z == m_root);
 224
 225         // Y is the node to be unlinked from the tree.
 226         Node* y;
 227         if (!z->left() || !z->right())
 228             y = z;
 229         else
 230             y = z->successor();
 231
 232         // Y is guaranteed to be non-null at this point.
 233         Node* x;
 234         if (y->left())
 235             x = y->left();
 236         else
 237             x = y->right();
 238
 239         // X is the child of y which might potentially replace y in
 240         // the tree. X might be null at this point.
 241         Node* xParent;
 242         if (x) {
 243             x->setParent(y->parent());
 244             xParent = x->parent();
 245         } else
 246             xParent = y->parent();
 247         if (!y->parent())
 248             m_root = x;
 249         else {
 250             if (y == y->parent()->left())
 251                 y->parent()->setLeft(x);
 252             else
 253                 y->parent()->setRight(x);
 254         }
 255
 256         if (y != z) {
 257             if (y->color() == Black)
 258                 removeFixup(x, xParent);
 259
 260             y->setParent(z->parent());
 261             y->setColor(z->color());
 262             y->setLeft(z->left());
 263             y->setRight(z->right());
 264
 265             if (z->left())
 266                 z->left()->setParent(y);
 267             if (z->right())
 268                 z->right()->setParent(y);
 269             if (z->parent()) {
 270                 if (z->parent()->left() == z)
 271                     z->parent()->setLeft(y);
 272                 else
 273                     z->parent()->setRight(y);
 274             } else {
 275                 ASSERT(m_root == z);
 276                 m_root = y;
 277             }
 278         } else if (y->color() == Black)
 279             removeFixup(x, xParent);
 280
 281         return z;
 282     }
 283
 284     Node* remove(const KeyType& key)
 285     {
 286         Node* result = findExact(key);
 287         if (!result)
 288             return 0;
 289         return remove(result);
 290     }
 291
 292     Node* findExact(const KeyType& key) const
 293     {
 294         for (Node* current = m_root; current;) {
 295             if (current->m_key == key)
 296                 return current;
 297             if (key < current->m_key)
 298                 current = current->left();
 299             else
 300                 current = current->right();
 301         }
 302         return 0;
 303     }
 304
 305     Node* findLeastGreaterThanOrEqual(const KeyType& key) const
 306     {
 307         Node* best = 0;
 308         for (Node* current = m_root; current;) {
 309             if (current->m_key == key)
 310                 return current;
 311             if (current->m_key < key)
 312                 current = current->right();
 313             else {
 314                 best = current;
 315                 current = current->left();
 316             }
 317         }
 318         return best;
 319     }
 320
 321     Node* findGreatestLessThanOrEqual(const KeyType& key) const
 322     {
 323         Node* best = 0;
 324         for (Node* current = m_root; current;) {
 325             if (current->m_key == key)
 326                 return current;
 327             if (current->m_key > key)
 328                 current = current->left();
 329             else {
 330                 best = current;
 331                 current = current->right();
 332             }
 333         }
 334         return best;
 335     }
 336
 337     Node* first() const
 338     {
 339         if (!m_root)
 340             return 0;
 341         return treeMinimum(m_root);
 342     }
 343
 344     Node* last() const
 345     {
 346         if (!m_root)
 347             return 0;
 348         return treeMaximum(m_root);
 349     }
 350
 351     // This is an O(n) operation.
 352     size_t size()
 353     {
 354         size_t result = 0;
 355         for (Node* current = first(); current; current = current->successor())
 356             result++;
 357         return result;
 358     }
 359
 360     // This is an O(1) operation.
 361     bool isEmpty()
 362     {
 363         return !m_root;
 364     }
 365
 366 private:
 367     // Finds the minimum element in the sub-tree rooted at the given
 368     // node.
 369     static Node* treeMinimum(Node* x)
 370     {
 371         while (x->left())
 372             x = x->left();
 373         return x;
 374     }
 375
 376     static Node* treeMaximum(Node* x)
 377     {
 378         while (x->right())
 379             x = x->right();
 380         return x;
 381     }
 382
 383     static const Node* treeMinimum(const Node* x)
 384     {
 385         while (x->left())
 386             x = x->left();
 387         return x;
 388     }
 389
 390     static const Node* treeMaximum(const Node* x)
 391     {
 392         while (x->right())
 393             x = x->right();
 394         return x;
 395     }
 396
 397     void treeInsert(Node* z)
 398     {
 399         ASSERT(!z->left());
 400         ASSERT(!z->right());
 401         ASSERT(!z->parent());
 402         ASSERT(z->color() == Red);
 403
 404         Node* y = 0;
 405         Node* x = m_root;
 406         while (x) {
 407             y = x;
 408             if (z->m_key < x->m_key)
 409                 x = x->left();
 410             else
 411                 x = x->right();
 412         }
 413         z->setParent(y);
 414         if (!y)
 415             m_root = z;
 416         else {
 417             if (z->m_key < y->m_key)
 418                 y->setLeft(z);
 419             else
 420                 y->setRight(z);
 421         }
 422     }
 423
 424     //----------------------------------------------------------------------
 425     // Red-Black tree operations
 426     //
 427
 428     // Left-rotates the subtree rooted at x.
 429     // Returns the new root of the subtree (x's right child).
 430     Node* leftRotate(Node* x)
 431     {
 432         // Set y.
 433         Node* y = x->right();
 434
 435         // Turn y's left subtree into x's right subtree.
 436         x->setRight(y->left());
 437         if (y->left())
 438             y->left()->setParent(x);
 439
 440         // Link x's parent to y.
 441         y->setParent(x->parent());
 442         if (!x->parent())
 443             m_root = y;
 444         else {
 445             if (x == x->parent()->left())
 446                 x->parent()->setLeft(y);
 447             else
 448                 x->parent()->setRight(y);
 449         }
 450
 451         // Put x on y's left.
 452         y->setLeft(x);
 453         x->setParent(y);
 454
 455         return y;
 456     }
 457
 458     // Right-rotates the subtree rooted at y.
 459     // Returns the new root of the subtree (y's left child).
 460     Node* rightRotate(Node* y)
 461     {
 462         // Set x.
 463         Node* x = y->left();
 464
 465         // Turn x's right subtree into y's left subtree.
 466         y->setLeft(x->right());
 467         if (x->right())
 468             x->right()->setParent(y);
 469
 470         // Link y's parent to x.
 471         x->setParent(y->parent());
 472         if (!y->parent())
 473             m_root = x;
 474         else {
 475             if (y == y->parent()->left())
 476                 y->parent()->setLeft(x);
 477             else
 478                 y->parent()->setRight(x);
 479         }
 480
 481         // Put y on x's right.
 482         x->setRight(y);
 483         y->setParent(x);
 484
 485         return x;
 486     }
 487
 488     // Restores the red-black property to the tree after splicing out
 489     // a node. Note that x may be null, which is why xParent must be
 490     // supplied.
 491     void removeFixup(Node* x, Node* xParent)
 492     {
 493         while (x != m_root && (!x || x->color() == Black)) {
 494             if (x == xParent->left()) {
 495                 // Note: the text points out that w can not be null.
 496                 // The reason is not obvious from simply looking at
 497                 // the code; it comes about from the properties of the
 498                 // red-black tree.
 499                 Node* w = xParent->right();
 500                 ASSERT(w); // x's sibling should not be null.
 501                 if (w->color() == Red) {
 502                     // Case 1
 503                     w->setColor(Black);
 504                     xParent->setColor(Red);
 505                     leftRotate(xParent);
 506                     w = xParent->right();
 507                 }
 508                 if ((!w->left() || w->left()->color() == Black)
 509                     && (!w->right() || w->right()->color() == Black)) {
 510                     // Case 2
 511                     w->setColor(Red);
 512                     x = xParent;
 513                     xParent = x->parent();
 514                 } else {
 515                     if (!w->right() || w->right()->color() == Black) {
 516                         // Case 3
 517                         w->left()->setColor(Black);
 518                         w->setColor(Red);
 519                         rightRotate(w);
 520                         w = xParent->right();
 521                     }
 522                     // Case 4
 523                     w->setColor(xParent->color());
 524                     xParent->setColor(Black);
 525                     if (w->right())
 526                         w->right()->setColor(Black);
 527                     leftRotate(xParent);
 528                     x = m_root;
 529                     xParent = x->parent();
 530                 }
 531             } else {
 532                 // Same as "then" clause with "right" and "left"
 533                 // exchanged.
 534
 535                 // Note: the text points out that w can not be null.
 536                 // The reason is not obvious from simply looking at
 537                 // the code; it comes about from the properties of the
 538                 // red-black tree.
 539                 Node* w = xParent->left();
 540                 ASSERT(w); // x's sibling should not be null.
 541                 if (w->color() == Red) {
 542                     // Case 1
 543                     w->setColor(Black);
 544                     xParent->setColor(Red);
 545                     rightRotate(xParent);
 546                     w = xParent->left();
 547                 }
 548                 if ((!w->right() || w->right()->color() == Black)
 549                     && (!w->left() || w->left()->color() == Black)) {
 550                     // Case 2
 551                     w->setColor(Red);
 552                     x = xParent;
 553                     xParent = x->parent();
 554                 } else {
 555                     if (!w->left() || w->left()->color() == Black) {
 556                         // Case 3
 557                         w->right()->setColor(Black);
 558                         w->setColor(Red);
 559                         leftRotate(w);
 560                         w = xParent->left();
 561                     }
 562                     // Case 4
 563                     w->setColor(xParent->color());
 564                     xParent->setColor(Black);
 565                     if (w->left())
 566                         w->left()->setColor(Black);
 567                     rightRotate(xParent);
 568                     x = m_root;
 569                     xParent = x->parent();
 570                 }
 571             }
 572         }
 573         if (x)
 574             x->setColor(Black);
 575     }
 576
 577     Node* m_root;
 578 };
 579
 580 }
 581
 582 #endif
 583