bd3de02436ad9dab6f680d8444bba9f5018fa049
[WebKit-https.git] / 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 "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         if (!y->parent())
681             m_root = x;
682         else {
683             if (y == y->parent()->left())
684                 y->parent()->setLeft(x);
685             else
686                 y->parent()->setRight(x);
687         }
688         if (y != z) {
689             z->copyFrom(y);
690             // This node has changed location in the tree and must be updated.
691             updateNode(z);
692             // The parent and its parents may now be out of date.
693             propagateUpdates(z->parent());
694         }
695
696         // If we haven't already updated starting from xParent, do so now.
697         if (xParent && xParent != y && xParent != z)
698             propagateUpdates(xParent);
699         if (y->color() == Black)
700             deleteFixup(x, xParent);
701
702         m_arena->freeObject(y);
703     }
704
705     // Visits the subtree rooted at the given node in order.
706     void visitInorderImpl(Node* node, Visitor* visitor) const
707     {
708         if (node->left())
709             visitInorderImpl(node->left(), visitor);
710         visitor->visit(node->data());
711         if (node->right())
712             visitInorderImpl(node->right(), visitor);
713     }
714
715     void markFree(Node *node)
716     {
717         if (!node)
718             return;
719
720         if (node->left())
721             markFree(node->left());
722         if (node->right())
723             markFree(node->right());
724         m_arena->freeObject(node);
725     }
726
727     //----------------------------------------------------------------------
728     // Helper class for size()
729
730     // A Visitor which simply counts the number of visited elements.
731     class Counter : public Visitor {
732         WTF_MAKE_NONCOPYABLE(Counter);
733     public:
734         Counter()
735             : m_count(0) { }
736
737         virtual void visit(const T&) OVERRIDE { ++m_count; }
738         int count() const { return m_count; }
739
740     private:
741         int m_count;
742     };
743
744     //----------------------------------------------------------------------
745     // Verification and debugging routines
746     //
747
748     // Returns in the "blackCount" parameter the number of black
749     // children along all paths to all leaves of the given node.
750     bool checkInvariantsFromNode(Node* node, int* blackCount) const
751     {
752         // Base case is a leaf node.
753         if (!node) {
754             *blackCount = 1;
755             return true;
756         }
757
758         // Each node is either red or black.
759         if (!(node->color() == Red || node->color() == Black))
760             return false;
761
762         // Every leaf (or null) is black.
763
764         if (node->color() == Red) {
765             // Both of its children are black.
766             if (!((!node->left() || node->left()->color() == Black)))
767                 return false;
768             if (!((!node->right() || node->right()->color() == Black)))
769                 return false;
770         }
771
772         // Every simple path to a leaf node contains the same number of
773         // black nodes.
774         int leftCount = 0, rightCount = 0;
775         bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
776         bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
777         if (!leftValid || !rightValid)
778             return false;
779         *blackCount = leftCount + (node->color() == Black ? 1 : 0);
780         return leftCount == rightCount;
781     }
782
783 #ifdef NDEBUG
784     void logIfVerbose(const char*) const { }
785 #else
786     void logIfVerbose(const char* output) const
787     {
788         if (m_verboseDebugging)
789             LOG_ERROR("%s", output);
790     }
791 #endif
792
793 #ifndef NDEBUG
794     // Dumps the subtree rooted at the given node.
795     void dumpFromNode(Node* node, int indentation) const
796     {
797         StringBuilder builder;
798         for (int i = 0; i < indentation; i++)
799             builder.append(" ");
800         builder.append("-");
801         if (node) {
802             builder.append(" ");
803             builder.append(ValueToString<T>::string(node->data()));
804             builder.append((node->color() == Black) ? " (black)" : " (red)");
805         }
806         LOG_ERROR("%s", builder.toString().ascii().data());
807         if (node) {
808             dumpFromNode(node->left(), indentation + 2);
809             dumpFromNode(node->right(), indentation + 2);
810         }
811     }
812 #endif
813
814     //----------------------------------------------------------------------
815     // Data members
816
817     RefPtr<PODFreeListArena<Node>> m_arena;
818     Node* m_root;
819     bool m_needsFullOrderingComparisons;
820 #ifndef NDEBUG
821     bool m_verboseDebugging;
822 #endif
823 };
824
825 } // namespace WebCore
826
827 #endif // PODRedBlackTree_h