2 * Copyright (C) 2010 Google Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
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:
31 // Insertion: O(lg(n))
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
41 // Type T must supply a default constructor, a copy constructor, and
42 // the "<" and "==" operators.
44 // In debug mode, printing of the data contained in the tree is
45 // enabled. This requires the template specialization to be available:
47 // template<> struct WebCore::ValueToString<T> {
48 // static String string(const T& t);
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
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.
69 // The design of this red-black tree comes from Cormen, Leiserson,
70 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
72 #ifndef PODRedBlackTree_h
73 #define PODRedBlackTree_h
76 #include <wtf/Assertions.h>
77 #include <wtf/Noncopyable.h>
78 #include <wtf/RefPtr.h>
81 #include <wtf/text/CString.h>
82 #include <wtf/text/StringBuilder.h>
83 #include <wtf/text/WTFString.h>
93 enum UninitializedTreeEnum {
98 class PODRedBlackTree {
100 // Visitor interface for walking all of the tree's elements.
103 virtual void visit(const T& data) = 0;
105 virtual ~Visitor() { }
108 // Constructs a new red-black tree without allocating an arena.
109 // isInitialized will return false in this case. initIfNeeded can be used
110 // to init the structure. This constructor is usefull for creating
111 // lazy initialized tree.
112 PODRedBlackTree(UninitializedTreeEnum)
114 , m_needsFullOrderingComparisons(false)
116 , m_verboseDebugging(false)
121 // Constructs a new red-black tree, allocating temporary objects
122 // from a newly constructed PODArena.
124 : m_arena(PODArena::create())
126 , m_needsFullOrderingComparisons(false)
128 , m_verboseDebugging(false)
133 // Constructs a new red-black tree, allocating temporary objects
134 // from the given PODArena.
135 explicit PODRedBlackTree(PassRefPtr<PODArena> arena)
138 , m_needsFullOrderingComparisons(false)
140 , m_verboseDebugging(false)
145 virtual ~PODRedBlackTree() { }
147 // Clearing will delete the contents of the tree. After this call
148 // isInitialized will return false.
155 bool isInitialized() const
163 m_arena = PODArena::create();
166 void add(const T& data)
168 ASSERT(isInitialized());
169 Node* node = m_arena->allocateObject<Node, T>(data);
173 // Returns true if the datum was found in the tree.
174 bool remove(const T& data)
176 ASSERT(isInitialized());
177 Node* node = treeSearch(data);
185 bool contains(const T& data) const
187 ASSERT(isInitialized());
188 return treeSearch(data);
191 void visitInorder(Visitor* visitor) const
193 ASSERT(isInitialized());
196 visitInorderImpl(m_root, visitor);
201 ASSERT(isInitialized());
203 visitInorder(&counter);
204 return counter.count();
207 // See the class documentation for an explanation of this property.
208 void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
210 m_needsFullOrderingComparisons = needsFullOrderingComparisons;
213 virtual bool checkInvariants() const
215 ASSERT(isInitialized());
217 return checkInvariantsFromNode(m_root, &blackCount);
221 // Dumps the tree's contents to the logging info stream for
222 // debugging purposes.
226 dumpFromNode(m_root, 0);
229 // Turns on or off verbose debugging of the tree, causing many
230 // messages to be logged during insertion and other operations in
232 void setVerboseDebugging(bool verboseDebugging)
234 m_verboseDebugging = verboseDebugging;
244 // The base Node class which is stored in the tree. Nodes are only
245 // an internal concept; users of the tree deal only with the data
248 WTF_MAKE_NONCOPYABLE(Node);
250 // Constructor. Newly-created nodes are colored red.
251 explicit Node(const T& data)
262 Color color() const { return m_color; }
263 void setColor(Color color) { m_color = color; }
265 // Fetches the user data.
266 T& data() { return m_data; }
268 // Copies all user-level fields from the source node, but not
269 // internal fields. For example, the base implementation of this
270 // method copies the "m_data" field, but not the child or parent
271 // fields. Any augmentation information also does not need to be
272 // copied, as it will be recomputed. Subclasses must call the
273 // superclass implementation.
274 virtual void copyFrom(Node* src) { m_data = src->data(); }
276 Node* left() const { return m_left; }
277 void setLeft(Node* node) { m_left = node; }
279 Node* right() const { return m_right; }
280 void setRight(Node* node) { m_right = node; }
282 Node* parent() const { return m_parent; }
283 void setParent(Node* node) { m_parent = node; }
293 // Returns the root of the tree, which is needed by some subclasses.
294 Node* root() const { return m_root; }
297 // This virtual method is the hook that subclasses should use when
298 // augmenting the red-black tree with additional per-node summary
299 // information. For example, in the case of an interval tree, this
300 // is used to compute the maximum endpoint of the subtree below the
301 // given node based on the values in the left and right children. It
302 // is guaranteed that this will be called in the correct order to
303 // properly update such summary information based only on the values
304 // in the left and right children. This method should return true if
305 // the node's summary information changed.
306 virtual bool updateNode(Node*) { return false; }
308 //----------------------------------------------------------------------
309 // Generic binary search tree operations
312 // Searches the tree for the given datum.
313 Node* treeSearch(const T& data) const
315 if (m_needsFullOrderingComparisons)
316 return treeSearchFullComparisons(m_root, data);
318 return treeSearchNormal(m_root, data);
321 // Searches the tree using the normal comparison operations,
322 // suitable for simple data types such as numbers.
323 Node* treeSearchNormal(Node* current, const T& data) const
326 if (current->data() == data)
328 if (data < current->data())
329 current = current->left();
331 current = current->right();
336 // Searches the tree using multiple comparison operations, required
337 // for data types with more complex behavior such as intervals.
338 Node* treeSearchFullComparisons(Node* current, const T& data) const
342 if (data < current->data())
343 return treeSearchFullComparisons(current->left(), data);
344 if (current->data() < data)
345 return treeSearchFullComparisons(current->right(), data);
346 if (data == current->data())
349 // We may need to traverse both the left and right subtrees.
350 Node* result = treeSearchFullComparisons(current->left(), data);
352 result = treeSearchFullComparisons(current->right(), data);
356 void treeInsert(Node* z)
362 if (z->data() < x->data())
371 if (z->data() < y->data())
378 // Finds the node following the given one in sequential ordering of
379 // their data, or null if none exists.
380 Node* treeSuccessor(Node* x)
383 return treeMinimum(x->right());
384 Node* y = x->parent();
385 while (y && x == y->right()) {
392 // Finds the minimum element in the sub-tree rooted at the given
394 Node* treeMinimum(Node* x)
401 // Helper for maintaining the augmented red-black tree.
402 void propagateUpdates(Node* start)
404 bool shouldContinue = true;
405 while (start && shouldContinue) {
406 shouldContinue = updateNode(start);
407 start = start->parent();
411 //----------------------------------------------------------------------
412 // Red-Black tree operations
415 // Left-rotates the subtree rooted at x.
416 // Returns the new root of the subtree (x's right child).
417 Node* leftRotate(Node* x)
420 Node* y = x->right();
422 // Turn y's left subtree into x's right subtree.
423 x->setRight(y->left());
425 y->left()->setParent(x);
427 // Link x's parent to y.
428 y->setParent(x->parent());
432 if (x == x->parent()->left())
433 x->parent()->setLeft(y);
435 x->parent()->setRight(y);
438 // Put x on y's left.
442 // Update nodes lowest to highest.
448 // Right-rotates the subtree rooted at y.
449 // Returns the new root of the subtree (y's left child).
450 Node* rightRotate(Node* y)
455 // Turn x's right subtree into y's left subtree.
456 y->setLeft(x->right());
458 x->right()->setParent(y);
460 // Link y's parent to x.
461 x->setParent(y->parent());
465 if (y == y->parent()->left())
466 y->parent()->setLeft(x);
468 y->parent()->setRight(x);
471 // Put y on x's right.
475 // Update nodes lowest to highest.
481 // Inserts the given node into the tree.
482 void insertNode(Node* x)
488 logIfVerbose(" PODRedBlackTree::InsertNode");
490 // The node from which to start propagating updates upwards.
491 Node* updateStart = x->parent();
493 while (x != m_root && x->parent()->color() == Red) {
494 if (x->parent() == x->parent()->parent()->left()) {
495 Node* y = x->parent()->parent()->right();
496 if (y && y->color() == Red) {
498 logIfVerbose(" Case 1/1");
499 x->parent()->setColor(Black);
501 x->parent()->parent()->setColor(Red);
502 updateNode(x->parent());
503 x = x->parent()->parent();
505 updateStart = x->parent();
507 if (x == x->parent()->right()) {
508 logIfVerbose(" Case 1/2");
514 logIfVerbose(" Case 1/3");
515 x->parent()->setColor(Black);
516 x->parent()->parent()->setColor(Red);
517 Node* newSubTreeRoot = rightRotate(x->parent()->parent());
518 updateStart = newSubTreeRoot->parent();
521 // Same as "then" clause with "right" and "left" exchanged.
522 Node* y = x->parent()->parent()->left();
523 if (y && y->color() == Red) {
525 logIfVerbose(" Case 2/1");
526 x->parent()->setColor(Black);
528 x->parent()->parent()->setColor(Red);
529 updateNode(x->parent());
530 x = x->parent()->parent();
532 updateStart = x->parent();
534 if (x == x->parent()->left()) {
536 logIfVerbose(" Case 2/2");
541 logIfVerbose(" Case 2/3");
542 x->parent()->setColor(Black);
543 x->parent()->parent()->setColor(Red);
544 Node* newSubTreeRoot = leftRotate(x->parent()->parent());
545 updateStart = newSubTreeRoot->parent();
550 propagateUpdates(updateStart);
552 m_root->setColor(Black);
555 // Restores the red-black property to the tree after splicing out
556 // a node. Note that x may be null, which is why xParent must be
558 void deleteFixup(Node* x, Node* xParent)
560 while (x != m_root && (!x || x->color() == Black)) {
561 if (x == xParent->left()) {
562 // Note: the text points out that w can not be null.
563 // The reason is not obvious from simply looking at
564 // the code; it comes about from the properties of the
566 Node* w = xParent->right();
567 ASSERT(w); // x's sibling should not be null.
568 if (w->color() == Red) {
571 xParent->setColor(Red);
573 w = xParent->right();
575 if ((!w->left() || w->left()->color() == Black)
576 && (!w->right() || w->right()->color() == Black)) {
580 xParent = x->parent();
582 if (!w->right() || w->right()->color() == Black) {
584 w->left()->setColor(Black);
587 w = xParent->right();
590 w->setColor(xParent->color());
591 xParent->setColor(Black);
593 w->right()->setColor(Black);
596 xParent = x->parent();
599 // Same as "then" clause with "right" and "left"
602 // Note: the text points out that w can not be null.
603 // The reason is not obvious from simply looking at
604 // the code; it comes about from the properties of the
606 Node* w = xParent->left();
607 ASSERT(w); // x's sibling should not be null.
608 if (w->color() == Red) {
611 xParent->setColor(Red);
612 rightRotate(xParent);
615 if ((!w->right() || w->right()->color() == Black)
616 && (!w->left() || w->left()->color() == Black)) {
620 xParent = x->parent();
622 if (!w->left() || w->left()->color() == Black) {
624 w->right()->setColor(Black);
630 w->setColor(xParent->color());
631 xParent->setColor(Black);
633 w->left()->setColor(Black);
634 rightRotate(xParent);
636 xParent = x->parent();
644 // Deletes the given node from the tree. Note that this
645 // particular node may not actually be removed from the tree;
646 // instead, another node might be removed and its contents
648 void deleteNode(Node* z)
650 // Y is the node to be unlinked from the tree.
652 if (!z->left() || !z->right())
655 y = treeSuccessor(z);
657 // Y is guaranteed to be non-null at this point.
664 // X is the child of y which might potentially replace y in
665 // the tree. X might be null at this point.
668 x->setParent(y->parent());
669 xParent = x->parent();
671 xParent = y->parent();
675 if (y == y->parent()->left())
676 y->parent()->setLeft(x);
678 y->parent()->setRight(x);
682 // This node has changed location in the tree and must be updated.
684 // The parent and its parents may now be out of date.
685 propagateUpdates(z->parent());
688 // If we haven't already updated starting from xParent, do so now.
689 if (xParent && xParent != y && xParent != z)
690 propagateUpdates(xParent);
691 if (y->color() == Black)
692 deleteFixup(x, xParent);
695 // Visits the subtree rooted at the given node in order.
696 void visitInorderImpl(Node* node, Visitor* visitor) const
699 visitInorderImpl(node->left(), visitor);
700 visitor->visit(node->data());
702 visitInorderImpl(node->right(), visitor);
705 //----------------------------------------------------------------------
706 // Helper class for size()
708 // A Visitor which simply counts the number of visited elements.
709 class Counter : public Visitor {
710 WTF_MAKE_NONCOPYABLE(Counter);
715 virtual void visit(const T&) { ++m_count; }
716 int count() const { return m_count; }
722 //----------------------------------------------------------------------
723 // Verification and debugging routines
726 // Returns in the "blackCount" parameter the number of black
727 // children along all paths to all leaves of the given node.
728 bool checkInvariantsFromNode(Node* node, int* blackCount) const
730 // Base case is a leaf node.
736 // Each node is either red or black.
737 if (!(node->color() == Red || node->color() == Black))
740 // Every leaf (or null) is black.
742 if (node->color() == Red) {
743 // Both of its children are black.
744 if (!((!node->left() || node->left()->color() == Black)))
746 if (!((!node->right() || node->right()->color() == Black)))
750 // Every simple path to a leaf node contains the same number of
752 int leftCount = 0, rightCount = 0;
753 bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
754 bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
755 if (!leftValid || !rightValid)
757 *blackCount = leftCount + (node->color() == Black ? 1 : 0);
758 return leftCount == rightCount;
762 void logIfVerbose(const char*) const { }
764 void logIfVerbose(const char* output) const
766 if (m_verboseDebugging)
767 LOG_ERROR("%s", output);
772 // Dumps the subtree rooted at the given node.
773 void dumpFromNode(Node* node, int indentation) const
775 StringBuilder builder;
776 for (int i = 0; i < indentation; i++)
781 builder.append(ValueToString<T>::string(node->data()));
782 builder.append((node->color() == Black) ? " (black)" : " (red)");
784 LOG_ERROR("%s", builder.toString().ascii().data());
786 dumpFromNode(node->left(), indentation + 2);
787 dumpFromNode(node->right(), indentation + 2);
792 //----------------------------------------------------------------------
795 RefPtr<PODArena> m_arena;
797 bool m_needsFullOrderingComparisons;
799 bool m_verboseDebugging;
803 } // namespace WebCore
805 #endif // PODRedBlackTree_h