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