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