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