blob: e3d9688bc5395c4e73a624ed55bf2846145eae10 [file] [log] [blame]
/*
* Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of Apple Inc. ("Apple") nor the names of
* its contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#pragma once
#include <wtf/Assertions.h>
#include <wtf/Noncopyable.h>
namespace WTF {
// This implements a red-black tree with the following properties:
// - The allocation of nodes in the tree is entirely up to the user.
// - If you are in possession of a pointer to a node, you can delete
// it from the tree. The tree will subsequently no longer have a
// reference to this node.
// - The key type must implement operator< and ==.
template<class NodeType, typename KeyType>
class RedBlackTree final {
WTF_MAKE_NONCOPYABLE(RedBlackTree);
WTF_MAKE_FAST_ALLOCATED;
private:
enum Color {
Red = 1,
Black
};
public:
class Node {
friend class RedBlackTree;
public:
const NodeType* successor() const
{
const Node* x = this;
if (x->right())
return treeMinimum(x->right());
const NodeType* y = x->parent();
while (y && x == y->right()) {
x = y;
y = y->parent();
}
return y;
}
const NodeType* predecessor() const
{
const Node* x = this;
if (x->left())
return treeMaximum(x->left());
const NodeType* y = x->parent();
while (y && x == y->left()) {
x = y;
y = y->parent();
}
return y;
}
NodeType* successor()
{
return const_cast<NodeType*>(const_cast<const Node*>(this)->successor());
}
NodeType* predecessor()
{
return const_cast<NodeType*>(const_cast<const Node*>(this)->predecessor());
}
private:
void reset()
{
m_left = 0;
m_right = 0;
m_parentAndRed = 1; // initialize to red
}
// NOTE: these methods should pack the parent and red into a single
// word. But doing so appears to reveal a bug in the compiler.
NodeType* parent() const
{
return reinterpret_cast<NodeType*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
}
void setParent(NodeType* newParent)
{
m_parentAndRed = reinterpret_cast<uintptr_t>(newParent) | (m_parentAndRed & 1);
}
NodeType* left() const
{
return m_left;
}
void setLeft(NodeType* node)
{
m_left = node;
}
NodeType* right() const
{
return m_right;
}
void setRight(NodeType* node)
{
m_right = node;
}
Color color() const
{
if (m_parentAndRed & 1)
return Red;
return Black;
}
void setColor(Color value)
{
if (value == Red)
m_parentAndRed |= 1;
else
m_parentAndRed &= ~static_cast<uintptr_t>(1);
}
NodeType* m_left;
NodeType* m_right;
uintptr_t m_parentAndRed;
};
RedBlackTree()
: m_root(0)
{
}
void insert(NodeType* x)
{
x->reset();
treeInsert(x);
x->setColor(Red);
while (x != m_root && x->parent()->color() == Red) {
if (x->parent() == x->parent()->parent()->left()) {
NodeType* y = x->parent()->parent()->right();
if (y && y->color() == Red) {
// Case 1
x->parent()->setColor(Black);
y->setColor(Black);
x->parent()->parent()->setColor(Red);
x = x->parent()->parent();
} else {
if (x == x->parent()->right()) {
// Case 2
x = x->parent();
leftRotate(x);
}
// Case 3
x->parent()->setColor(Black);
x->parent()->parent()->setColor(Red);
rightRotate(x->parent()->parent());
}
} else {
// Same as "then" clause with "right" and "left" exchanged.
NodeType* y = x->parent()->parent()->left();
if (y && y->color() == Red) {
// Case 1
x->parent()->setColor(Black);
y->setColor(Black);
x->parent()->parent()->setColor(Red);
x = x->parent()->parent();
} else {
if (x == x->parent()->left()) {
// Case 2
x = x->parent();
rightRotate(x);
}
// Case 3
x->parent()->setColor(Black);
x->parent()->parent()->setColor(Red);
leftRotate(x->parent()->parent());
}
}
}
m_root->setColor(Black);
}
NodeType* remove(NodeType* z)
{
ASSERT(z);
ASSERT(z->parent() || z == m_root);
// Y is the node to be unlinked from the tree.
NodeType* y;
if (!z->left() || !z->right())
y = z;
else
y = z->successor();
// Y is guaranteed to be non-null at this point.
NodeType* x;
if (y->left())
x = y->left();
else
x = y->right();
// X is the child of y which might potentially replace y in
// the tree. X might be null at this point.
NodeType* xParent;
if (x) {
x->setParent(y->parent());
xParent = x->parent();
} else
xParent = y->parent();
if (!y->parent())
m_root = x;
else {
if (y == y->parent()->left())
y->parent()->setLeft(x);
else
y->parent()->setRight(x);
}
if (y != z) {
if (y->color() == Black)
removeFixup(x, xParent);
y->setParent(z->parent());
y->setColor(z->color());
y->setLeft(z->left());
y->setRight(z->right());
if (z->left())
z->left()->setParent(y);
if (z->right())
z->right()->setParent(y);
if (z->parent()) {
if (z->parent()->left() == z)
z->parent()->setLeft(y);
else
z->parent()->setRight(y);
} else {
ASSERT(m_root == z);
m_root = y;
}
} else if (y->color() == Black)
removeFixup(x, xParent);
return z;
}
NodeType* remove(const KeyType& key)
{
NodeType* result = findExact(key);
if (!result)
return 0;
return remove(result);
}
NodeType* findExact(const KeyType& key) const
{
for (NodeType* current = m_root; current;) {
if (current->key() == key)
return current;
if (key < current->key())
current = current->left();
else
current = current->right();
}
return 0;
}
NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const
{
NodeType* best = 0;
for (NodeType* current = m_root; current;) {
if (current->key() == key)
return current;
if (current->key() < key)
current = current->right();
else {
best = current;
current = current->left();
}
}
return best;
}
NodeType* findGreatestLessThanOrEqual(const KeyType& key) const
{
NodeType* best = 0;
for (NodeType* current = m_root; current;) {
if (current->key() == key)
return current;
if (current->key() > key)
current = current->left();
else {
best = current;
current = current->right();
}
}
return best;
}
NodeType* first() const
{
if (!m_root)
return 0;
return treeMinimum(m_root);
}
NodeType* last() const
{
if (!m_root)
return 0;
return treeMaximum(m_root);
}
// This is an O(n) operation.
size_t size()
{
size_t result = 0;
for (NodeType* current = first(); current; current = current->successor())
result++;
return result;
}
// This is an O(1) operation.
bool isEmpty()
{
return !m_root;
}
private:
// Finds the minimum element in the sub-tree rooted at the given
// node.
static NodeType* treeMinimum(NodeType* x)
{
while (x->left())
x = x->left();
return x;
}
static NodeType* treeMaximum(NodeType* x)
{
while (x->right())
x = x->right();
return x;
}
static const NodeType* treeMinimum(const NodeType* x)
{
while (x->left())
x = x->left();
return x;
}
static const NodeType* treeMaximum(const NodeType* x)
{
while (x->right())
x = x->right();
return x;
}
void treeInsert(NodeType* z)
{
ASSERT(!z->left());
ASSERT(!z->right());
ASSERT(!z->parent());
ASSERT(z->color() == Red);
NodeType* y = 0;
NodeType* x = m_root;
while (x) {
y = x;
if (z->key() < x->key())
x = x->left();
else
x = x->right();
}
z->setParent(y);
if (!y)
m_root = z;
else {
if (z->key() < y->key())
y->setLeft(z);
else
y->setRight(z);
}
}
//----------------------------------------------------------------------
// Red-Black tree operations
//
// Left-rotates the subtree rooted at x.
// Returns the new root of the subtree (x's right child).
NodeType* leftRotate(NodeType* x)
{
// Set y.
NodeType* y = x->right();
// Turn y's left subtree into x's right subtree.
x->setRight(y->left());
if (y->left())
y->left()->setParent(x);
// Link x's parent to y.
y->setParent(x->parent());
if (!x->parent())
m_root = y;
else {
if (x == x->parent()->left())
x->parent()->setLeft(y);
else
x->parent()->setRight(y);
}
// Put x on y's left.
y->setLeft(x);
x->setParent(y);
return y;
}
// Right-rotates the subtree rooted at y.
// Returns the new root of the subtree (y's left child).
NodeType* rightRotate(NodeType* y)
{
// Set x.
NodeType* x = y->left();
// Turn x's right subtree into y's left subtree.
y->setLeft(x->right());
if (x->right())
x->right()->setParent(y);
// Link y's parent to x.
x->setParent(y->parent());
if (!y->parent())
m_root = x;
else {
if (y == y->parent()->left())
y->parent()->setLeft(x);
else
y->parent()->setRight(x);
}
// Put y on x's right.
x->setRight(y);
y->setParent(x);
return x;
}
// Restores the red-black property to the tree after splicing out
// a node. Note that x may be null, which is why xParent must be
// supplied.
void removeFixup(NodeType* x, NodeType* xParent)
{
while (x != m_root && (!x || x->color() == Black)) {
if (x == xParent->left()) {
// Note: the text points out that w can not be null.
// The reason is not obvious from simply looking at
// the code; it comes about from the properties of the
// red-black tree.
NodeType* w = xParent->right();
ASSERT(w); // x's sibling should not be null.
if (w->color() == Red) {
// Case 1
w->setColor(Black);
xParent->setColor(Red);
leftRotate(xParent);
w = xParent->right();
}
if ((!w->left() || w->left()->color() == Black)
&& (!w->right() || w->right()->color() == Black)) {
// Case 2
w->setColor(Red);
x = xParent;
xParent = x->parent();
} else {
if (!w->right() || w->right()->color() == Black) {
// Case 3
w->left()->setColor(Black);
w->setColor(Red);
rightRotate(w);
w = xParent->right();
}
// Case 4
w->setColor(xParent->color());
xParent->setColor(Black);
if (w->right())
w->right()->setColor(Black);
leftRotate(xParent);
x = m_root;
xParent = x->parent();
}
} else {
// Same as "then" clause with "right" and "left"
// exchanged.
// Note: the text points out that w can not be null.
// The reason is not obvious from simply looking at
// the code; it comes about from the properties of the
// red-black tree.
NodeType* w = xParent->left();
ASSERT(w); // x's sibling should not be null.
if (w->color() == Red) {
// Case 1
w->setColor(Black);
xParent->setColor(Red);
rightRotate(xParent);
w = xParent->left();
}
if ((!w->right() || w->right()->color() == Black)
&& (!w->left() || w->left()->color() == Black)) {
// Case 2
w->setColor(Red);
x = xParent;
xParent = x->parent();
} else {
if (!w->left() || w->left()->color() == Black) {
// Case 3
w->right()->setColor(Black);
w->setColor(Red);
leftRotate(w);
w = xParent->left();
}
// Case 4
w->setColor(xParent->color());
xParent->setColor(Black);
if (w->left())
w->left()->setColor(Black);
rightRotate(xParent);
x = m_root;
xParent = x->parent();
}
}
}
if (x)
x->setColor(Black);
}
NodeType* m_root;
};
}