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