Source/WebCore/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 <wtf/Assertions.h>
  76 #include <wtf/Noncopyable.h>
  77 #include <wtf/text/ValueToString.h>
  78 #ifndef NDEBUG
  79 #include <wtf/text/StringBuilder.h>
  80 #include <wtf/text/WTFString.h>
  81 #endif
  82
  83 namespace WebCore {
  84
  85 template<class T>
  86 class PODRedBlackTree {
  87     WTF_MAKE_FAST_ALLOCATED;
  88 public:
  89     class Node;
  90
  91     // Visitor interface for walking all of the tree's elements.
  92     class Visitor {
  93     public:
  94         virtual void visit(const T& data) = 0;
  95     protected:
  96         virtual ~Visitor() { }
  97     };
  98
  99     PODRedBlackTree()
 100         : m_root(0)
 101         , m_needsFullOrderingComparisons(false)
 102 #ifndef NDEBUG
 103         , m_verboseDebugging(false)
 104 #endif
 105     {
 106     }
 107
 108     virtual ~PODRedBlackTree()
 109     {
 110         clear();
 111     }
 112
 113     // Clearing will delete the contents of the tree. After this call
 114     // isInitialized will return false.
 115     void clear()
 116     {
 117         markFree(m_root);
 118         m_root = 0;
 119     }
 120
 121     void add(const T& data)
 122     {
 123         Node* node = new Node(data);
 124         insertNode(node);
 125     }
 126
 127     // Returns true if the datum was found in the tree.
 128     bool remove(const T& data)
 129     {
 130         Node* node = treeSearch(data);
 131         if (node) {
 132             deleteNode(node);
 133             return true;
 134         }
 135         return false;
 136     }
 137
 138     bool contains(const T& data) const
 139     {
 140         return treeSearch(data);
 141     }
 142
 143     void visitInorder(Visitor* visitor) const
 144     {
 145         if (!m_root)
 146             return;
 147         visitInorderImpl(m_root, visitor);
 148     }
 149
 150     int size() const
 151     {
 152         Counter counter;
 153         visitInorder(&counter);
 154         return counter.count();
 155     }
 156
 157     // See the class documentation for an explanation of this property.
 158     void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
 159     {
 160         m_needsFullOrderingComparisons = needsFullOrderingComparisons;
 161     }
 162
 163     virtual bool checkInvariants() const
 164     {
 165         int blackCount;
 166         return checkInvariantsFromNode(m_root, &blackCount);
 167     }
 168
 169 #ifndef NDEBUG
 170     // Dumps the tree's contents to the logging info stream for
 171     // debugging purposes.
 172     void dump() const
 173     {
 174         dumpFromNode(m_root, 0);
 175     }
 176
 177     // Turns on or off verbose debugging of the tree, causing many
 178     // messages to be logged during insertion and other operations in
 179     // debug mode.
 180     void setVerboseDebugging(bool verboseDebugging)
 181     {
 182         m_verboseDebugging = verboseDebugging;
 183     }
 184 #endif
 185
 186     enum Color {
 187         Red = 1,
 188         Black
 189     };
 190
 191     // The base Node class which is stored in the tree. Nodes are only
 192     // an internal concept; users of the tree deal only with the data
 193     // they store in it.
 194     class Node {
 195         WTF_MAKE_FAST_ALLOCATED;
 196         WTF_MAKE_NONCOPYABLE(Node);
 197     public:
 198         // Constructor. Newly-created nodes are colored red.
 199         explicit Node(const T& data)
 200             : m_left(0)
 201             , m_right(0)
 202             , m_parent(0)
 203             , m_color(Red)
 204             , m_data(data)
 205         {
 206         }
 207
 208         virtual ~Node() { }
 209
 210         Color color() const { return m_color; }
 211         void setColor(Color color) { m_color = color; }
 212
 213         // Fetches the user data.
 214         T& data() { return m_data; }
 215
 216         // Copies all user-level fields from the source node, but not
 217         // internal fields. For example, the base implementation of this
 218         // method copies the "m_data" field, but not the child or parent
 219         // fields. Any augmentation information also does not need to be
 220         // copied, as it will be recomputed. Subclasses must call the
 221         // superclass implementation.
 222         virtual void copyFrom(Node* src) { m_data = src->data(); }
 223
 224         Node* left() const { return m_left; }
 225         void setLeft(Node* node) { m_left = node; }
 226
 227         Node* right() const { return m_right; }
 228         void setRight(Node* node) { m_right = node; }
 229
 230         Node* parent() const { return m_parent; }
 231         void setParent(Node* node) { m_parent = node; }
 232
 233     private:
 234         Node* m_left;
 235         Node* m_right;
 236         Node* m_parent;
 237         Color m_color;
 238         T m_data;
 239     };
 240
 241 protected:
 242     // Returns the root of the tree, which is needed by some subclasses.
 243     Node* root() const { return m_root; }
 244
 245 private:
 246     // This virtual method is the hook that subclasses should use when
 247     // augmenting the red-black tree with additional per-node summary
 248     // information. For example, in the case of an interval tree, this
 249     // is used to compute the maximum endpoint of the subtree below the
 250     // given node based on the values in the left and right children. It
 251     // is guaranteed that this will be called in the correct order to
 252     // properly update such summary information based only on the values
 253     // in the left and right children. This method should return true if
 254     // the node's summary information changed.
 255     virtual bool updateNode(Node*) { return false; }
 256
 257     //----------------------------------------------------------------------
 258     // Generic binary search tree operations
 259     //
 260
 261     // Searches the tree for the given datum.
 262     Node* treeSearch(const T& data) const
 263     {
 264         if (m_needsFullOrderingComparisons)
 265             return treeSearchFullComparisons(m_root, data);
 266
 267         return treeSearchNormal(m_root, data);
 268     }
 269
 270     // Searches the tree using the normal comparison operations,
 271     // suitable for simple data types such as numbers.
 272     Node* treeSearchNormal(Node* current, const T& data) const
 273     {
 274         while (current) {
 275             if (current->data() == data)
 276                 return current;
 277             if (data < current->data())
 278                 current = current->left();
 279             else
 280                 current = current->right();
 281         }
 282         return 0;
 283     }
 284
 285     // Searches the tree using multiple comparison operations, required
 286     // for data types with more complex behavior such as intervals.
 287     Node* treeSearchFullComparisons(Node* current, const T& data) const
 288     {
 289         if (!current)
 290             return 0;
 291         if (data < current->data())
 292             return treeSearchFullComparisons(current->left(), data);
 293         if (current->data() < data)
 294             return treeSearchFullComparisons(current->right(), data);
 295         if (data == current->data())
 296             return current;
 297
 298         // We may need to traverse both the left and right subtrees.
 299         Node* result = treeSearchFullComparisons(current->left(), data);
 300         if (!result)
 301             result = treeSearchFullComparisons(current->right(), data);
 302         return result;
 303     }
 304
 305     void treeInsert(Node* z)
 306     {
 307         Node* y = 0;
 308         Node* x = m_root;
 309         while (x) {
 310             y = x;
 311             if (z->data() < x->data())
 312                 x = x->left();
 313             else
 314                 x = x->right();
 315         }
 316         z->setParent(y);
 317         if (!y)
 318             m_root = z;
 319         else {
 320             if (z->data() < y->data())
 321                 y->setLeft(z);
 322             else
 323                 y->setRight(z);
 324         }
 325     }
 326
 327     // Finds the node following the given one in sequential ordering of
 328     // their data, or null if none exists.
 329     Node* treeSuccessor(Node* x)
 330     {
 331         if (x->right())
 332             return treeMinimum(x->right());
 333         Node* y = x->parent();
 334         while (y && x == y->right()) {
 335             x = y;
 336             y = y->parent();
 337         }
 338         return y;
 339     }
 340
 341     // Finds the minimum element in the sub-tree rooted at the given
 342     // node.
 343     Node* treeMinimum(Node* x)
 344     {
 345         while (x->left())
 346             x = x->left();
 347         return x;
 348     }
 349
 350     // Helper for maintaining the augmented red-black tree.
 351     void propagateUpdates(Node* start)
 352     {
 353         bool shouldContinue = true;
 354         while (start && shouldContinue) {
 355             shouldContinue = updateNode(start);
 356             start = start->parent();
 357         }
 358     }
 359
 360     //----------------------------------------------------------------------
 361     // Red-Black tree operations
 362     //
 363
 364     // Left-rotates the subtree rooted at x.
 365     // Returns the new root of the subtree (x's right child).
 366     Node* leftRotate(Node* x)
 367     {
 368         // Set y.
 369         Node* y = x->right();
 370
 371         // Turn y's left subtree into x's right subtree.
 372         x->setRight(y->left());
 373         if (y->left())
 374             y->left()->setParent(x);
 375
 376         // Link x's parent to y.
 377         y->setParent(x->parent());
 378         if (!x->parent())
 379             m_root = y;
 380         else {
 381             if (x == x->parent()->left())
 382                 x->parent()->setLeft(y);
 383             else
 384                 x->parent()->setRight(y);
 385         }
 386
 387         // Put x on y's left.
 388         y->setLeft(x);
 389         x->setParent(y);
 390
 391         // Update nodes lowest to highest.
 392         updateNode(x);
 393         updateNode(y);
 394         return y;
 395     }
 396
 397     // Right-rotates the subtree rooted at y.
 398     // Returns the new root of the subtree (y's left child).
 399     Node* rightRotate(Node* y)
 400     {
 401         // Set x.
 402         Node* x = y->left();
 403
 404         // Turn x's right subtree into y's left subtree.
 405         y->setLeft(x->right());
 406         if (x->right())
 407             x->right()->setParent(y);
 408
 409         // Link y's parent to x.
 410         x->setParent(y->parent());
 411         if (!y->parent())
 412             m_root = x;
 413         else {
 414             if (y == y->parent()->left())
 415                 y->parent()->setLeft(x);
 416             else
 417                 y->parent()->setRight(x);
 418         }
 419
 420         // Put y on x's right.
 421         x->setRight(y);
 422         y->setParent(x);
 423
 424         // Update nodes lowest to highest.
 425         updateNode(y);
 426         updateNode(x);
 427         return x;
 428     }
 429
 430     // Inserts the given node into the tree.
 431     void insertNode(Node* x)
 432     {
 433         treeInsert(x);
 434         x->setColor(Red);
 435         updateNode(x);
 436
 437         logIfVerbose("  PODRedBlackTree::InsertNode");
 438
 439         // The node from which to start propagating updates upwards.
 440         Node* updateStart = x->parent();
 441
 442         while (x != m_root && x->parent()->color() == Red) {
 443             if (x->parent() == x->parent()->parent()->left()) {
 444                 Node* y = x->parent()->parent()->right();
 445                 if (y && y->color() == Red) {
 446                     // Case 1
 447                     logIfVerbose("  Case 1/1");
 448                     x->parent()->setColor(Black);
 449                     y->setColor(Black);
 450                     x->parent()->parent()->setColor(Red);
 451                     updateNode(x->parent());
 452                     x = x->parent()->parent();
 453                     updateNode(x);
 454                     updateStart = x->parent();
 455                 } else {
 456                     if (x == x->parent()->right()) {
 457                         logIfVerbose("  Case 1/2");
 458                         // Case 2
 459                         x = x->parent();
 460                         leftRotate(x);
 461                     }
 462                     // Case 3
 463                     logIfVerbose("  Case 1/3");
 464                     x->parent()->setColor(Black);
 465                     x->parent()->parent()->setColor(Red);
 466                     Node* newSubTreeRoot = rightRotate(x->parent()->parent());
 467                     updateStart = newSubTreeRoot->parent();
 468                 }
 469             } else {
 470                 // Same as "then" clause with "right" and "left" exchanged.
 471                 Node* y = x->parent()->parent()->left();
 472                 if (y && y->color() == Red) {
 473                     // Case 1
 474                     logIfVerbose("  Case 2/1");
 475                     x->parent()->setColor(Black);
 476                     y->setColor(Black);
 477                     x->parent()->parent()->setColor(Red);
 478                     updateNode(x->parent());
 479                     x = x->parent()->parent();
 480                     updateNode(x);
 481                     updateStart = x->parent();
 482                 } else {
 483                     if (x == x->parent()->left()) {
 484                         // Case 2
 485                         logIfVerbose("  Case 2/2");
 486                         x = x->parent();
 487                         rightRotate(x);
 488                     }
 489                     // Case 3
 490                     logIfVerbose("  Case 2/3");
 491                     x->parent()->setColor(Black);
 492                     x->parent()->parent()->setColor(Red);
 493                     Node* newSubTreeRoot = leftRotate(x->parent()->parent());
 494                     updateStart = newSubTreeRoot->parent();
 495                 }
 496             }
 497         }
 498
 499         propagateUpdates(updateStart);
 500
 501         m_root->setColor(Black);
 502     }
 503
 504     // Restores the red-black property to the tree after splicing out
 505     // a node. Note that x may be null, which is why xParent must be
 506     // supplied.
 507     void deleteFixup(Node* x, Node* xParent)
 508     {
 509         while (x != m_root && (!x || x->color() == Black)) {
 510             if (x == xParent->left()) {
 511                 // Note: the text points out that w can not be null.
 512                 // The reason is not obvious from simply looking at
 513                 // the code; it comes about from the properties of the
 514                 // red-black tree.
 515                 Node* w = xParent->right();
 516                 ASSERT(w); // x's sibling should not be null.
 517                 if (w->color() == Red) {
 518                     // Case 1
 519                     w->setColor(Black);
 520                     xParent->setColor(Red);
 521                     leftRotate(xParent);
 522                     w = xParent->right();
 523                 }
 524                 if ((!w->left() || w->left()->color() == Black)
 525                     && (!w->right() || w->right()->color() == Black)) {
 526                     // Case 2
 527                     w->setColor(Red);
 528                     x = xParent;
 529                     xParent = x->parent();
 530                 } else {
 531                     if (!w->right() || w->right()->color() == Black) {
 532                         // Case 3
 533                         w->left()->setColor(Black);
 534                         w->setColor(Red);
 535                         rightRotate(w);
 536                         w = xParent->right();
 537                     }
 538                     // Case 4
 539                     w->setColor(xParent->color());
 540                     xParent->setColor(Black);
 541                     if (w->right())
 542                         w->right()->setColor(Black);
 543                     leftRotate(xParent);
 544                     x = m_root;
 545                     xParent = x->parent();
 546                 }
 547             } else {
 548                 // Same as "then" clause with "right" and "left"
 549                 // exchanged.
 550
 551                 // Note: the text points out that w can not be null.
 552                 // The reason is not obvious from simply looking at
 553                 // the code; it comes about from the properties of the
 554                 // red-black tree.
 555                 Node* w = xParent->left();
 556                 ASSERT(w); // x's sibling should not be null.
 557                 if (w->color() == Red) {
 558                     // Case 1
 559                     w->setColor(Black);
 560                     xParent->setColor(Red);
 561                     rightRotate(xParent);
 562                     w = xParent->left();
 563                 }
 564                 if ((!w->right() || w->right()->color() == Black)
 565                     && (!w->left() || w->left()->color() == Black)) {
 566                     // Case 2
 567                     w->setColor(Red);
 568                     x = xParent;
 569                     xParent = x->parent();
 570                 } else {
 571                     if (!w->left() || w->left()->color() == Black) {
 572                         // Case 3
 573                         w->right()->setColor(Black);
 574                         w->setColor(Red);
 575                         leftRotate(w);
 576                         w = xParent->left();
 577                     }
 578                     // Case 4
 579                     w->setColor(xParent->color());
 580                     xParent->setColor(Black);
 581                     if (w->left())
 582                         w->left()->setColor(Black);
 583                     rightRotate(xParent);
 584                     x = m_root;
 585                     xParent = x->parent();
 586                 }
 587             }
 588         }
 589         if (x)
 590             x->setColor(Black);
 591     }
 592
 593     // Deletes the given node from the tree. Note that this
 594     // particular node may not actually be removed from the tree;
 595     // instead, another node might be removed and its contents
 596     // copied into z.
 597     void deleteNode(Node* z)
 598     {
 599         // Y is the node to be unlinked from the tree.
 600         Node* y;
 601         if (!z->left() || !z->right())
 602             y = z;
 603         else
 604             y = treeSuccessor(z);
 605
 606         // Y is guaranteed to be non-null at this point.
 607         Node* x;
 608         if (y->left())
 609             x = y->left();
 610         else
 611             x = y->right();
 612
 613         // X is the child of y which might potentially replace y in
 614         // the tree. X might be null at this point.
 615         Node* xParent;
 616         if (x) {
 617             x->setParent(y->parent());
 618             xParent = x->parent();
 619         } else
 620             xParent = y->parent();
 621         if (!y->parent())
 622             m_root = x;
 623         else {
 624             if (y == y->parent()->left())
 625                 y->parent()->setLeft(x);
 626             else
 627                 y->parent()->setRight(x);
 628         }
 629         if (y != z) {
 630             z->copyFrom(y);
 631             // This node has changed location in the tree and must be updated.
 632             updateNode(z);
 633             // The parent and its parents may now be out of date.
 634             propagateUpdates(z->parent());
 635         }
 636
 637         // If we haven't already updated starting from xParent, do so now.
 638         if (xParent && xParent != y && xParent != z)
 639             propagateUpdates(xParent);
 640         if (y->color() == Black)
 641             deleteFixup(x, xParent);
 642
 643         delete y;
 644     }
 645
 646     // Visits the subtree rooted at the given node in order.
 647     void visitInorderImpl(Node* node, Visitor* visitor) const
 648     {
 649         if (node->left())
 650             visitInorderImpl(node->left(), visitor);
 651         visitor->visit(node->data());
 652         if (node->right())
 653             visitInorderImpl(node->right(), visitor);
 654     }
 655
 656     void markFree(Node *node)
 657     {
 658         if (!node)
 659             return;
 660
 661         if (node->left())
 662             markFree(node->left());
 663         if (node->right())
 664             markFree(node->right());
 665         delete node;
 666     }
 667
 668     //----------------------------------------------------------------------
 669     // Helper class for size()
 670
 671     // A Visitor which simply counts the number of visited elements.
 672     class Counter : public Visitor {
 673         WTF_MAKE_NONCOPYABLE(Counter);
 674     public:
 675         Counter()
 676             : m_count(0) { }
 677
 678         void visit(const T&) override { ++m_count; }
 679         int count() const { return m_count; }
 680
 681     private:
 682         int m_count;
 683     };
 684
 685     //----------------------------------------------------------------------
 686     // Verification and debugging routines
 687     //
 688
 689     // Returns in the "blackCount" parameter the number of black
 690     // children along all paths to all leaves of the given node.
 691     bool checkInvariantsFromNode(Node* node, int* blackCount) const
 692     {
 693         // Base case is a leaf node.
 694         if (!node) {
 695             *blackCount = 1;
 696             return true;
 697         }
 698
 699         // Each node is either red or black.
 700         if (!(node->color() == Red || node->color() == Black))
 701             return false;
 702
 703         // Every leaf (or null) is black.
 704
 705         if (node->color() == Red) {
 706             // Both of its children are black.
 707             if (!((!node->left() || node->left()->color() == Black)))
 708                 return false;
 709             if (!((!node->right() || node->right()->color() == Black)))
 710                 return false;
 711         }
 712
 713         // Every simple path to a leaf node contains the same number of
 714         // black nodes.
 715         int leftCount = 0, rightCount = 0;
 716         bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
 717         bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
 718         if (!leftValid || !rightValid)
 719             return false;
 720         *blackCount = leftCount + (node->color() == Black ? 1 : 0);
 721         return leftCount == rightCount;
 722     }
 723
 724 #ifdef NDEBUG
 725     void logIfVerbose(const char*) const { }
 726 #else
 727     void logIfVerbose(const char* output) const
 728     {
 729         if (m_verboseDebugging)
 730             LOG_ERROR("%s", output);
 731     }
 732 #endif
 733
 734 #ifndef NDEBUG
 735     // Dumps the subtree rooted at the given node.
 736     void dumpFromNode(Node* node, int indentation) const
 737     {
 738         StringBuilder builder;
 739         for (int i = 0; i < indentation; i++)
 740             builder.append(' ');
 741         builder.append('-');
 742         if (node) {
 743             builder.append(' ');
 744             builder.append(ValueToString<T>::string(node->data()));
 745             builder.append((node->color() == Black) ? " (black)" : " (red)");
 746         }
 747         LOG_ERROR("%s", builder.toString().ascii().data());
 748         if (node) {
 749             dumpFromNode(node->left(), indentation + 2);
 750             dumpFromNode(node->right(), indentation + 2);
 751         }
 752     }
 753 #endif
 754
 755     //----------------------------------------------------------------------
 756     // Data members
 757
 758     Node* m_root;
 759     bool m_needsFullOrderingComparisons;
 760 #ifndef NDEBUG
 761     bool m_verboseDebugging;
 762 #endif
 763 };
 764
 765 } // namespace WebCore
 766
 767 #endif // PODRedBlackTree_h