Home | History | Annotate | Download | only in platform
      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 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 blink {
     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 = nullptr;
    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             WTF_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         WTF_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 blink
    827 
    828 #endif // PODRedBlackTree_h
    829