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