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
83namespace WebCore {
84
85template<class T>
86class PODRedBlackTree {
87 WTF_MAKE_FAST_ALLOCATED;
88public:
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
241protected:
242 // Returns the root of the tree, which is needed by some subclasses.
243 Node* root() const { return m_root; }
244
245private:
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
768