src/third_party/WebKit/Source/platform/PODRedBlackTree.h

   1 /*
   2  * Copyright (C) 2010 Google 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  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 // A red-black tree, which is a form of a balanced binary tree. It
  27 // supports efficient insertion, deletion and queries of comparable
  28 // elements. The same element may be inserted multiple times. The
  29 // algorithmic complexity of common operations is:
  30 //
  31 //   Insertion: O(lg(n))
  32 //   Deletion:  O(lg(n))
  33 //   Querying:  O(lg(n))
  34 //
  35 // The data type T that is stored in this red-black tree must be only
  36 // Plain Old Data (POD), or bottom out into POD. It must _not_ rely on
  37 // having its destructor called. This implementation internally
  38 // allocates storage in large chunks and does not call the destructor
  39 // on each object.
  40 //
  41 // Type T must supply a default constructor, a copy constructor, and
  42 // the "<" and "==" operators.
  43 //
  44 // In debug mode, printing of the data contained in the tree is
  45 // enabled. This requires the template specialization to be available:
  46 //
  47 //   template<> struct WebCore::ValueToString<T> {
  48 //       static String string(const T& t);
  49 //   };
  50 //
  51 // Note that when complex types are stored in this red/black tree, it
  52 // is possible that single invocations of the "<" and "==" operators
  53 // will be insufficient to describe the ordering of elements in the
  54 // tree during queries. As a concrete example, consider the case where
  55 // intervals are stored in the tree sorted by low endpoint. The "<"
  56 // operator on the Interval class only compares the low endpoint, but
  57 // the "==" operator takes into account the high endpoint as well.
  58 // This makes the necessary logic for querying and deletion somewhat
  59 // more complex. In order to properly handle such situations, the
  60 // property "needsFullOrderingComparisons" must be set to true on
  61 // the tree.
  62 //
  63 // This red-black tree is designed to be _augmented_; subclasses can
  64 // add additional and summary information to each node to efficiently
  65 // store and index more complex data structures. A concrete example is
  66 // the IntervalTree, which extends each node with a summary statistic
  67 // to efficiently store one-dimensional intervals.
  68 //
  69 // The design of this red-black tree comes from Cormen, Leiserson,
  70 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
  71
  72 #ifndef PODRedBlackTree_h
  73 #define PODRedBlackTree_h
  74
  75 #include "platform/PODFreeListArena.h"
  76 #include "wtf/Assertions.h"
  77 #include "wtf/Noncopyable.h"
  78 #include "wtf/RefPtr.h"
  79 #ifndef NDEBUG
  80 #include "wtf/text/CString.h"
  81 #include "wtf/text/StringBuilder.h"
  82 #include "wtf/text/WTFString.h"
  83 #endif
  84
  85 namespace WebCore {
  86
  87 #ifndef NDEBUG
  88 template<class T>
  89 struct ValueToString;
  90 #endif
  91
  92 enum UninitializedTreeEnum {
  93     UninitializedTree
  94 };
  95
  96 template<class T>
  97 class PODRedBlackTree {
  98 public:
  99     class Node;
 100
 101     // Visitor interface for walking all of the tree's elements.
 102     class Visitor {
 103     public:
 104         virtual void visit(const T& data) = 0;
 105     protected:
 106         virtual ~Visitor() { }
 107     };
 108
 109     // Constructs a new red-black tree without allocating an arena.
 110     // isInitialized will return false in this case. initIfNeeded can be used
 111     // to init the structure. This constructor is usefull for creating
 112     // lazy initialized tree.
 113     explicit PODRedBlackTree(UninitializedTreeEnum)
 114         : m_root(0)
 115         , m_needsFullOrderingComparisons(false)
 116 #ifndef NDEBUG
 117         , m_verboseDebugging(false)
 118 #endif
 119     {
 120     }
 121
 122     // Constructs a new red-black tree, allocating temporary objects
 123     // from a newly constructed PODFreeListArena.
 124     PODRedBlackTree()
 125         : m_arena(PODFreeListArena<Node>::create())
 126         , m_root(0)
 127         , m_needsFullOrderingComparisons(false)
 128 #ifndef NDEBUG
 129         , m_verboseDebugging(false)
 130 #endif
 131     {
 132     }
 133
 134     // Constructs a new red-black tree, allocating temporary objects
 135     // from the given PODArena.
 136     explicit PODRedBlackTree(PassRefPtr<PODFreeListArena<Node> > arena)
 137         : m_arena(arena)
 138         , m_root(0)
 139         , m_needsFullOrderingComparisons(false)
 140 #ifndef NDEBUG
 141         , m_verboseDebugging(false)
 142 #endif
 143     {
 144     }
 145
 146     virtual ~PODRedBlackTree() { }
 147
 148     // Clearing will delete the contents of the tree. After this call
 149     // isInitialized will return false.
 150     void clear()
 151     {
 152         markFree(m_root);
 153         m_arena = 0;
 154         m_root = 0;
 155     }
 156
 157     bool isInitialized() const
 158     {
 159         return m_arena;
 160     }
 161
 162     void initIfNeeded()
 163     {
 164         if (!m_arena)
 165             m_arena = PODFreeListArena<Node>::create();
 166     }
 167
 168     void initIfNeeded(PODFreeListArena<Node>* arena)
 169     {
 170         if (!m_arena)
 171             m_arena = arena;
 172     }
 173
 174     void add(const T& data)
 175     {
 176         ASSERT(isInitialized());
 177         Node* node = m_arena->template allocateObject<T>(data);
 178         insertNode(node);
 179     }
 180
 181     // Returns true if the datum was found in the tree.
 182     bool remove(const T& data)
 183     {
 184         ASSERT(isInitialized());
 185         Node* node = treeSearch(data);
 186         if (node) {
 187             deleteNode(node);
 188             return true;
 189         }
 190         return false;
 191     }
 192
 193     bool contains(const T& data) const
 194     {
 195         ASSERT(isInitialized());
 196         return treeSearch(data);
 197     }
 198
 199     void visitInorder(Visitor* visitor) const
 200     {
 201         ASSERT(isInitialized());
 202         if (!m_root)
 203             return;
 204         visitInorderImpl(m_root, visitor);
 205     }
 206
 207     int size() const
 208     {
 209         ASSERT(isInitialized());
 210         Counter counter;
 211         visitInorder(&counter);
 212         return counter.count();
 213     }
 214
 215     // See the class documentation for an explanation of this property.
 216     void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
 217     {
 218         m_needsFullOrderingComparisons = needsFullOrderingComparisons;
 219     }
 220
 221     virtual bool checkInvariants() const
 222     {
 223         ASSERT(isInitialized());
 224         int blackCount;
 225         return checkInvariantsFromNode(m_root, &blackCount);
 226     }
 227
 228 #ifndef NDEBUG
 229     // Dumps the tree's contents to the logging info stream for
 230     // debugging purposes.
 231     void dump() const
 232     {
 233         if (m_arena)
 234             dumpFromNode(m_root, 0);
 235     }
 236
 237     // Turns on or off verbose debugging of the tree, causing many
 238     // messages to be logged during insertion and other operations in
 239     // debug mode.
 240     void setVerboseDebugging(bool verboseDebugging)
 241     {
 242         m_verboseDebugging = verboseDebugging;
 243     }
 244 #endif
 245
 246     enum Color {
 247         Red = 1,
 248         Black
 249     };
 250
 251     // The base Node class which is stored in the tree. Nodes are only
 252     // an internal concept; users of the tree deal only with the data
 253     // they store in it.
 254     class Node {
 255         WTF_MAKE_NONCOPYABLE(Node);
 256     public:
 257         // Constructor. Newly-created nodes are colored red.
 258         explicit Node(const T& data)
 259             : m_left(0)
 260             , m_right(0)
 261             , m_parent(0)
 262             , m_color(Red)
 263             , m_data(data)
 264         {
 265         }
 266
 267         virtual ~Node() { }
 268
 269         Color color() const { return m_color; }
 270         void setColor(Color color) { m_color = color; }
 271
 272         // Fetches the user data.
 273         T& data() { return m_data; }
 274
 275         // Copies all user-level fields from the source node, but not
 276         // internal fields. For example, the base implementation of this
 277         // method copies the "m_data" field, but not the child or parent
 278         // fields. Any augmentation information also does not need to be
 279         // copied, as it will be recomputed. Subclasses must call the
 280         // superclass implementation.
 281         virtual void copyFrom(Node* src) { m_data = src->data(); }
 282
 283         Node* left() const { return m_left; }
 284         void setLeft(Node* node) { m_left = node; }
 285
 286         Node* right() const { return m_right; }
 287         void setRight(Node* node) { m_right = node; }
 288
 289         Node* parent() const { return m_parent; }
 290         void setParent(Node* node) { m_parent = node; }
 291
 292     private:
 293         Node* m_left;
 294         Node* m_right;
 295         Node* m_parent;
 296         Color m_color;
 297         T m_data;
 298     };
 299
 300 protected:
 301     // Returns the root of the tree, which is needed by some subclasses.
 302     Node* root() const { return m_root; }
 303
 304 private:
 305     // This virtual method is the hook that subclasses should use when
 306     // augmenting the red-black tree with additional per-node summary
 307     // information. For example, in the case of an interval tree, this
 308     // is used to compute the maximum endpoint of the subtree below the
 309     // given node based on the values in the left and right children. It
 310     // is guaranteed that this will be called in the correct order to
 311     // properly update such summary information based only on the values
 312     // in the left and right children. This method should return true if
 313     // the node's summary information changed.
 314     virtual bool updateNode(Node*) { return false; }
 315
 316     //----------------------------------------------------------------------
 317     // Generic binary search tree operations
 318     //
 319
 320     // Searches the tree for the given datum.
 321     Node* treeSearch(const T& data) const
 322     {
 323         if (m_needsFullOrderingComparisons)
 324             return treeSearchFullComparisons(m_root, data);
 325
 326         return treeSearchNormal(m_root, data);
 327     }
 328
 329     // Searches the tree using the normal comparison operations,
 330     // suitable for simple data types such as numbers.
 331     Node* treeSearchNormal(Node* current, const T& data) const
 332     {
 333         while (current) {
 334             if (current->data() == data)
 335                 return current;
 336             if (data < current->data())
 337                 current = current->left();
 338             else
 339                 current = current->right();
 340         }
 341         return 0;
 342     }
 343
 344     // Searches the tree using multiple comparison operations, required
 345     // for data types with more complex behavior such as intervals.
 346     Node* treeSearchFullComparisons(Node* current, const T& data) const
 347     {
 348         if (!current)
 349             return 0;
 350         if (data < current->data())
 351             return treeSearchFullComparisons(current->left(), data);
 352         if (current->data() < data)
 353             return treeSearchFullComparisons(current->right(), data);
 354         if (data == current->data())
 355             return current;
 356
 357         // We may need to traverse both the left and right subtrees.
 358         Node* result = treeSearchFullComparisons(current->left(), data);
 359         if (!result)
 360             result = treeSearchFullComparisons(current->right(), data);
 361         return result;
 362     }
 363
 364     void treeInsert(Node* z)
 365     {
 366         Node* y = 0;
 367         Node* x = m_root;
 368         while (x) {
 369             y = x;
 370             if (z->data() < x->data())
 371                 x = x->left();
 372             else
 373                 x = x->right();
 374         }
 375         z->setParent(y);
 376         if (!y) {
 377             m_root = z;
 378         } else {
 379             if (z->data() < y->data())
 380                 y->setLeft(z);
 381             else
 382                 y->setRight(z);
 383         }
 384     }
 385
 386     // Finds the node following the given one in sequential ordering of
 387     // their data, or null if none exists.
 388     Node* treeSuccessor(Node* x)
 389     {
 390         if (x->right())
 391             return treeMinimum(x->right());
 392         Node* y = x->parent();
 393         while (y && x == y->right()) {
 394             x = y;
 395             y = y->parent();
 396         }
 397         return y;
 398     }
 399
 400     // Finds the minimum element in the sub-tree rooted at the given
 401     // node.
 402     Node* treeMinimum(Node* x)
 403     {
 404         while (x->left())
 405             x = x->left();
 406         return x;
 407     }
 408
 409     // Helper for maintaining the augmented red-black tree.
 410     void propagateUpdates(Node* start)
 411     {
 412         bool shouldContinue = true;
 413         while (start && shouldContinue) {
 414             shouldContinue = updateNode(start);
 415             start = start->parent();
 416         }
 417     }
 418
 419     //----------------------------------------------------------------------
 420     // Red-Black tree operations
 421     //
 422
 423     // Left-rotates the subtree rooted at x.
 424     // Returns the new root of the subtree (x's right child).
 425     Node* leftRotate(Node* x)
 426     {
 427         // Set y.
 428         Node* y = x->right();
 429
 430         // Turn y's left subtree into x's right subtree.
 431         x->setRight(y->left());
 432         if (y->left())
 433             y->left()->setParent(x);
 434
 435         // Link x's parent to y.
 436         y->setParent(x->parent());
 437         if (!x->parent()) {
 438             m_root = y;
 439         } else {
 440             if (x == x->parent()->left())
 441                 x->parent()->setLeft(y);
 442             else
 443                 x->parent()->setRight(y);
 444         }
 445
 446         // Put x on y's left.
 447         y->setLeft(x);
 448         x->setParent(y);
 449
 450         // Update nodes lowest to highest.
 451         updateNode(x);
 452         updateNode(y);
 453         return y;
 454     }
 455
 456     // Right-rotates the subtree rooted at y.
 457     // Returns the new root of the subtree (y's left child).
 458     Node* rightRotate(Node* y)
 459     {
 460         // Set x.
 461         Node* x = y->left();
 462
 463         // Turn x's right subtree into y's left subtree.
 464         y->setLeft(x->right());
 465         if (x->right())
 466             x->right()->setParent(y);
 467
 468         // Link y's parent to x.
 469         x->setParent(y->parent());
 470         if (!y->parent()) {
 471             m_root = x;
 472         } else {
 473             if (y == y->parent()->left())
 474                 y->parent()->setLeft(x);
 475             else
 476                 y->parent()->setRight(x);
 477         }
 478
 479         // Put y on x's right.
 480         x->setRight(y);
 481         y->setParent(x);
 482
 483         // Update nodes lowest to highest.
 484         updateNode(y);
 485         updateNode(x);
 486         return x;
 487     }
 488
 489     // Inserts the given node into the tree.
 490     void insertNode(Node* x)
 491     {
 492         treeInsert(x);
 493         x->setColor(Red);
 494         updateNode(x);
 495
 496         logIfVerbose("  PODRedBlackTree::InsertNode");
 497
 498         // The node from which to start propagating updates upwards.
 499         Node* updateStart = x->parent();
 500
 501         while (x != m_root && x->parent()->color() == Red) {
 502             if (x->parent() == x->parent()->parent()->left()) {
 503                 Node* y = x->parent()->parent()->right();
 504                 if (y && y->color() == Red) {
 505                     // Case 1
 506                     logIfVerbose("  Case 1/1");
 507                     x->parent()->setColor(Black);
 508                     y->setColor(Black);
 509                     x->parent()->parent()->setColor(Red);
 510                     updateNode(x->parent());
 511                     x = x->parent()->parent();
 512                     updateNode(x);
 513                     updateStart = x->parent();
 514                 } else {
 515                     if (x == x->parent()->right()) {
 516                         logIfVerbose("  Case 1/2");
 517                         // Case 2
 518                         x = x->parent();
 519                         leftRotate(x);
 520                     }
 521                     // Case 3
 522                     logIfVerbose("  Case 1/3");
 523                     x->parent()->setColor(Black);
 524                     x->parent()->parent()->setColor(Red);
 525                     Node* newSubTreeRoot = rightRotate(x->parent()->parent());
 526                     updateStart = newSubTreeRoot->parent();
 527                 }
 528             } else {
 529                 // Same as "then" clause with "right" and "left" exchanged.
 530                 Node* y = x->parent()->parent()->left();
 531                 if (y && y->color() == Red) {
 532                     // Case 1
 533                     logIfVerbose("  Case 2/1");
 534                     x->parent()->setColor(Black);
 535                     y->setColor(Black);
 536                     x->parent()->parent()->setColor(Red);
 537                     updateNode(x->parent());
 538                     x = x->parent()->parent();
 539                     updateNode(x);
 540                     updateStart = x->parent();
 541                 } else {
 542                     if (x == x->parent()->left()) {
 543                         // Case 2
 544                         logIfVerbose("  Case 2/2");
 545                         x = x->parent();
 546                         rightRotate(x);
 547                     }
 548                     // Case 3
 549                     logIfVerbose("  Case 2/3");
 550                     x->parent()->setColor(Black);
 551                     x->parent()->parent()->setColor(Red);
 552                     Node* newSubTreeRoot = leftRotate(x->parent()->parent());
 553                     updateStart = newSubTreeRoot->parent();
 554                 }
 555             }
 556         }
 557
 558         propagateUpdates(updateStart);
 559
 560         m_root->setColor(Black);
 561     }
 562
 563     // Restores the red-black property to the tree after splicing out
 564     // a node. Note that x may be null, which is why xParent must be
 565     // supplied.
 566     void deleteFixup(Node* x, Node* xParent)
 567     {
 568         while (x != m_root && (!x || x->color() == Black)) {
 569             if (x == xParent->left()) {
 570                 // Note: the text points out that w can not be null.
 571                 // The reason is not obvious from simply looking at
 572                 // the code; it comes about from the properties of the
 573                 // red-black tree.
 574                 Node* w = xParent->right();
 575                 ASSERT(w); // x's sibling should not be null.
 576                 if (w->color() == Red) {
 577                     // Case 1
 578                     w->setColor(Black);
 579                     xParent->setColor(Red);
 580                     leftRotate(xParent);
 581                     w = xParent->right();
 582                 }
 583                 if ((!w->left() || w->left()->color() == Black)
 584                     && (!w->right() || w->right()->color() == Black)) {
 585                     // Case 2
 586                     w->setColor(Red);
 587                     x = xParent;
 588                     xParent = x->parent();
 589                 } else {
 590                     if (!w->right() || w->right()->color() == Black) {
 591                         // Case 3
 592                         w->left()->setColor(Black);
 593                         w->setColor(Red);
 594                         rightRotate(w);
 595                         w = xParent->right();
 596                     }
 597                     // Case 4
 598                     w->setColor(xParent->color());
 599                     xParent->setColor(Black);
 600                     if (w->right())
 601                         w->right()->setColor(Black);
 602                     leftRotate(xParent);
 603                     x = m_root;
 604                     xParent = x->parent();
 605                 }
 606             } else {
 607                 // Same as "then" clause with "right" and "left"
 608                 // exchanged.
 609
 610                 // Note: the text points out that w can not be null.
 611                 // The reason is not obvious from simply looking at
 612                 // the code; it comes about from the properties of the
 613                 // red-black tree.
 614                 Node* w = xParent->left();
 615                 ASSERT(w); // x's sibling should not be null.
 616                 if (w->color() == Red) {
 617                     // Case 1
 618                     w->setColor(Black);
 619                     xParent->setColor(Red);
 620                     rightRotate(xParent);
 621                     w = xParent->left();
 622                 }
 623                 if ((!w->right() || w->right()->color() == Black)
 624                     && (!w->left() || w->left()->color() == Black)) {
 625                     // Case 2
 626                     w->setColor(Red);
 627                     x = xParent;
 628                     xParent = x->parent();
 629                 } else {
 630                     if (!w->left() || w->left()->color() == Black) {
 631                         // Case 3
 632                         w->right()->setColor(Black);
 633                         w->setColor(Red);
 634                         leftRotate(w);
 635                         w = xParent->left();
 636                     }
 637                     // Case 4
 638                     w->setColor(xParent->color());
 639                     xParent->setColor(Black);
 640                     if (w->left())
 641                         w->left()->setColor(Black);
 642                     rightRotate(xParent);
 643                     x = m_root;
 644                     xParent = x->parent();
 645                 }
 646             }
 647         }
 648         if (x)
 649             x->setColor(Black);
 650     }
 651
 652     // Deletes the given node from the tree. Note that this
 653     // particular node may not actually be removed from the tree;
 654     // instead, another node might be removed and its contents
 655     // copied into z.
 656     void deleteNode(Node* z)
 657     {
 658         // Y is the node to be unlinked from the tree.
 659         Node* y;
 660         if (!z->left() || !z->right())
 661             y = z;
 662         else
 663             y = treeSuccessor(z);
 664
 665         // Y is guaranteed to be non-null at this point.
 666         Node* x;
 667         if (y->left())
 668             x = y->left();
 669         else
 670             x = y->right();
 671
 672         // X is the child of y which might potentially replace y in
 673         // the tree. X might be null at this point.
 674         Node* xParent;
 675         if (x) {
 676             x->setParent(y->parent());
 677             xParent = x->parent();
 678         } else {
 679             xParent = y->parent();
 680         }
 681         if (!y->parent()) {
 682             m_root = x;
 683         } else {
 684             if (y == y->parent()->left())
 685                 y->parent()->setLeft(x);
 686             else
 687                 y->parent()->setRight(x);
 688         }
 689         if (y != z) {
 690             z->copyFrom(y);
 691             // This node has changed location in the tree and must be updated.
 692             updateNode(z);
 693             // The parent and its parents may now be out of date.
 694             propagateUpdates(z->parent());
 695         }
 696
 697         // If we haven't already updated starting from xParent, do so now.
 698         if (xParent && xParent != y && xParent != z)
 699             propagateUpdates(xParent);
 700         if (y->color() == Black)
 701             deleteFixup(x, xParent);
 702
 703         m_arena->freeObject(y);
 704     }
 705
 706     // Visits the subtree rooted at the given node in order.
 707     void visitInorderImpl(Node* node, Visitor* visitor) const
 708     {
 709         if (node->left())
 710             visitInorderImpl(node->left(), visitor);
 711         visitor->visit(node->data());
 712         if (node->right())
 713             visitInorderImpl(node->right(), visitor);
 714     }
 715
 716     void markFree(Node *node)
 717     {
 718         if (!node)
 719             return;
 720
 721         if (node->left())
 722             markFree(node->left());
 723         if (node->right())
 724             markFree(node->right());
 725         m_arena->freeObject(node);
 726     }
 727
 728     //----------------------------------------------------------------------
 729     // Helper class for size()
 730
 731     // A Visitor which simply counts the number of visited elements.
 732     class Counter : public Visitor {
 733         WTF_MAKE_NONCOPYABLE(Counter);
 734     public:
 735         Counter()
 736             : m_count(0) { }
 737
 738         virtual void visit(const T&) { ++m_count; }
 739         int count() const { return m_count; }
 740
 741     private:
 742         int m_count;
 743     };
 744
 745     //----------------------------------------------------------------------
 746     // Verification and debugging routines
 747     //
 748
 749     // Returns in the "blackCount" parameter the number of black
 750     // children along all paths to all leaves of the given node.
 751     bool checkInvariantsFromNode(Node* node, int* blackCount) const
 752     {
 753         // Base case is a leaf node.
 754         if (!node) {
 755             *blackCount = 1;
 756             return true;
 757         }
 758
 759         // Each node is either red or black.
 760         if (!(node->color() == Red || node->color() == Black))
 761             return false;
 762
 763         // Every leaf (or null) is black.
 764
 765         if (node->color() == Red) {
 766             // Both of its children are black.
 767             if (!((!node->left() || node->left()->color() == Black)))
 768                 return false;
 769             if (!((!node->right() || node->right()->color() == Black)))
 770                 return false;
 771         }
 772
 773         // Every simple path to a leaf node contains the same number of
 774         // black nodes.
 775         int leftCount = 0, rightCount = 0;
 776         bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
 777         bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
 778         if (!leftValid || !rightValid)
 779             return false;
 780         *blackCount = leftCount + (node->color() == Black ? 1 : 0);
 781         return leftCount == rightCount;
 782     }
 783
 784 #ifdef NDEBUG
 785     void logIfVerbose(const char*) const { }
 786 #else
 787     void logIfVerbose(const char* output) const
 788     {
 789         if (m_verboseDebugging)
 790             LOG_ERROR("%s", output);
 791     }
 792 #endif
 793
 794 #ifndef NDEBUG
 795     // Dumps the subtree rooted at the given node.
 796     void dumpFromNode(Node* node, int indentation) const
 797     {
 798         StringBuilder builder;
 799         for (int i = 0; i < indentation; i++)
 800             builder.append(" ");
 801         builder.append("-");
 802         if (node) {
 803             builder.append(" ");
 804             builder.append(ValueToString<T>::string(node->data()));
 805             builder.append((node->color() == Black) ? " (black)" : " (red)");
 806         }
 807         LOG_ERROR("%s", builder.toString().ascii().data());
 808         if (node) {
 809             dumpFromNode(node->left(), indentation + 2);
 810             dumpFromNode(node->right(), indentation + 2);
 811         }
 812     }
 813 #endif
 814
 815     //----------------------------------------------------------------------
 816     // Data members
 817
 818     RefPtr<PODFreeListArena<Node> > m_arena;
 819     Node* m_root;
 820     bool m_needsFullOrderingComparisons;
 821 #ifndef NDEBUG
 822     bool m_verboseDebugging;
 823 #endif
 824 };
 825
 826 } // namespace WebCore
 827
 828 #endif // PODRedBlackTree_h