422 lines
12 KiB
C
422 lines
12 KiB
C
/*
|
|
* Copyright © 2017 Jason Ekstrand
|
|
*
|
|
* Permission is hereby granted, free of charge, to any person obtaining a
|
|
* copy of this software and associated documentation files (the "Software"),
|
|
* to deal in the Software without restriction, including without limitation
|
|
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
|
|
* and/or sell copies of the Software, and to permit persons to whom the
|
|
* Software is furnished to do so, subject to the following conditions:
|
|
*
|
|
* The above copyright notice and this permission notice shall be included in
|
|
* all copies or substantial portions of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
|
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
|
|
* DEALINGS IN THE SOFTWARE.
|
|
*/
|
|
|
|
#include "rb_tree.h"
|
|
|
|
/** \file rb_tree.c
|
|
*
|
|
* An implementation of a red-black tree
|
|
*
|
|
* This file implements the guts of a red-black tree. The implementation
|
|
* is mostly based on the one in "Introduction to Algorithms", third
|
|
* edition, by Cormen, Leiserson, Rivest, and Stein. The primary
|
|
* divergence in our algorithms from those presented in CLRS is that we use
|
|
* NULL for the leaves instead of a sentinel. This means we have to do a
|
|
* tiny bit more tracking in our implementation of delete but it makes the
|
|
* algorithms far more explicit than stashing stuff in the sentinel.
|
|
*/
|
|
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
|
|
static bool
|
|
rb_node_is_black(struct rb_node *n)
|
|
{
|
|
/* NULL nodes are leaves and therefore black */
|
|
return (n == NULL) || (n->parent & 1);
|
|
}
|
|
|
|
static bool
|
|
rb_node_is_red(struct rb_node *n)
|
|
{
|
|
return !rb_node_is_black(n);
|
|
}
|
|
|
|
static void
|
|
rb_node_set_black(struct rb_node *n)
|
|
{
|
|
n->parent |= 1;
|
|
}
|
|
|
|
static void
|
|
rb_node_set_red(struct rb_node *n)
|
|
{
|
|
n->parent &= ~1ull;
|
|
}
|
|
|
|
static void
|
|
rb_node_copy_color(struct rb_node *dst, struct rb_node *src)
|
|
{
|
|
dst->parent = (dst->parent & ~1ull) | (src->parent & 1);
|
|
}
|
|
|
|
static void
|
|
rb_node_set_parent(struct rb_node *n, struct rb_node *p)
|
|
{
|
|
n->parent = (n->parent & 1) | (uintptr_t)p;
|
|
}
|
|
|
|
static struct rb_node *
|
|
rb_node_minimum(struct rb_node *node)
|
|
{
|
|
while (node->left)
|
|
node = node->left;
|
|
return node;
|
|
}
|
|
|
|
static struct rb_node *
|
|
rb_node_maximum(struct rb_node *node)
|
|
{
|
|
while (node->right)
|
|
node = node->right;
|
|
return node;
|
|
}
|
|
|
|
void
|
|
rb_tree_init(struct rb_tree *T)
|
|
{
|
|
T->root = NULL;
|
|
}
|
|
|
|
/**
|
|
* Replace the subtree of T rooted at u with the subtree rooted at v
|
|
*
|
|
* This is called RB-transplant in CLRS.
|
|
*
|
|
* The node to be replaced is assumed to be a non-leaf.
|
|
*/
|
|
static void
|
|
rb_tree_splice(struct rb_tree *T, struct rb_node *u, struct rb_node *v)
|
|
{
|
|
assert(u);
|
|
struct rb_node *p = rb_node_parent(u);
|
|
if (p == NULL) {
|
|
assert(T->root == u);
|
|
T->root = v;
|
|
} else if (u == p->left) {
|
|
p->left = v;
|
|
} else {
|
|
assert(u == p->right);
|
|
p->right = v;
|
|
}
|
|
if (v)
|
|
rb_node_set_parent(v, p);
|
|
}
|
|
|
|
static void
|
|
rb_tree_rotate_left(struct rb_tree *T, struct rb_node *x)
|
|
{
|
|
assert(x && x->right);
|
|
|
|
struct rb_node *y = x->right;
|
|
x->right = y->left;
|
|
if (y->left)
|
|
rb_node_set_parent(y->left, x);
|
|
rb_tree_splice(T, x, y);
|
|
y->left = x;
|
|
rb_node_set_parent(x, y);
|
|
}
|
|
|
|
static void
|
|
rb_tree_rotate_right(struct rb_tree *T, struct rb_node *y)
|
|
{
|
|
assert(y && y->left);
|
|
|
|
struct rb_node *x = y->left;
|
|
y->left = x->right;
|
|
if (x->right)
|
|
rb_node_set_parent(x->right, y);
|
|
rb_tree_splice(T, y, x);
|
|
x->right = y;
|
|
rb_node_set_parent(y, x);
|
|
}
|
|
|
|
void
|
|
rb_tree_insert_at(struct rb_tree *T, struct rb_node *parent,
|
|
struct rb_node *node, bool insert_left)
|
|
{
|
|
/* This sets null children, parent, and a color of red */
|
|
memset(node, 0, sizeof(*node));
|
|
|
|
if (parent == NULL) {
|
|
assert(T->root == NULL);
|
|
T->root = node;
|
|
rb_node_set_black(node);
|
|
return;
|
|
}
|
|
|
|
if (insert_left) {
|
|
assert(parent->left == NULL);
|
|
parent->left = node;
|
|
} else {
|
|
assert(parent->right == NULL);
|
|
parent->right = node;
|
|
}
|
|
rb_node_set_parent(node, parent);
|
|
|
|
/* Now we do the insertion fixup */
|
|
struct rb_node *z = node;
|
|
while (rb_node_is_red(rb_node_parent(z))) {
|
|
struct rb_node *z_p = rb_node_parent(z);
|
|
assert(z == z_p->left || z == z_p->right);
|
|
struct rb_node *z_p_p = rb_node_parent(z_p);
|
|
assert(z_p_p != NULL);
|
|
if (z_p == z_p_p->left) {
|
|
struct rb_node *y = z_p_p->right;
|
|
if (rb_node_is_red(y)) {
|
|
rb_node_set_black(z_p);
|
|
rb_node_set_black(y);
|
|
rb_node_set_red(z_p_p);
|
|
z = z_p_p;
|
|
} else {
|
|
if (z == z_p->right) {
|
|
z = z_p;
|
|
rb_tree_rotate_left(T, z);
|
|
/* We changed z */
|
|
z_p = rb_node_parent(z);
|
|
assert(z == z_p->left || z == z_p->right);
|
|
z_p_p = rb_node_parent(z_p);
|
|
}
|
|
rb_node_set_black(z_p);
|
|
rb_node_set_red(z_p_p);
|
|
rb_tree_rotate_right(T, z_p_p);
|
|
}
|
|
} else {
|
|
struct rb_node *y = z_p_p->left;
|
|
if (rb_node_is_red(y)) {
|
|
rb_node_set_black(z_p);
|
|
rb_node_set_black(y);
|
|
rb_node_set_red(z_p_p);
|
|
z = z_p_p;
|
|
} else {
|
|
if (z == z_p->left) {
|
|
z = z_p;
|
|
rb_tree_rotate_right(T, z);
|
|
/* We changed z */
|
|
z_p = rb_node_parent(z);
|
|
assert(z == z_p->left || z == z_p->right);
|
|
z_p_p = rb_node_parent(z_p);
|
|
}
|
|
rb_node_set_black(z_p);
|
|
rb_node_set_red(z_p_p);
|
|
rb_tree_rotate_left(T, z_p_p);
|
|
}
|
|
}
|
|
}
|
|
rb_node_set_black(T->root);
|
|
}
|
|
|
|
void
|
|
rb_tree_remove(struct rb_tree *T, struct rb_node *z)
|
|
{
|
|
/* x_p is always the parent node of X. We have to track this
|
|
* separately because x may be NULL.
|
|
*/
|
|
struct rb_node *x, *x_p;
|
|
struct rb_node *y = z;
|
|
bool y_was_black = rb_node_is_black(y);
|
|
if (z->left == NULL) {
|
|
x = z->right;
|
|
x_p = rb_node_parent(z);
|
|
rb_tree_splice(T, z, x);
|
|
} else if (z->right == NULL) {
|
|
x = z->left;
|
|
x_p = rb_node_parent(z);
|
|
rb_tree_splice(T, z, x);
|
|
} else {
|
|
/* Find the minimum sub-node of z->right */
|
|
y = rb_node_minimum(z->right);
|
|
y_was_black = rb_node_is_black(y);
|
|
|
|
x = y->right;
|
|
if (rb_node_parent(y) == z) {
|
|
x_p = y;
|
|
} else {
|
|
x_p = rb_node_parent(y);
|
|
rb_tree_splice(T, y, x);
|
|
y->right = z->right;
|
|
rb_node_set_parent(y->right, y);
|
|
}
|
|
assert(y->left == NULL);
|
|
rb_tree_splice(T, z, y);
|
|
y->left = z->left;
|
|
rb_node_set_parent(y->left, y);
|
|
rb_node_copy_color(y, z);
|
|
}
|
|
|
|
assert(x_p == NULL || x == x_p->left || x == x_p->right);
|
|
|
|
if (!y_was_black)
|
|
return;
|
|
|
|
/* Fixup RB tree after the delete */
|
|
while (x != T->root && rb_node_is_black(x)) {
|
|
if (x == x_p->left) {
|
|
struct rb_node *w = x_p->right;
|
|
if (rb_node_is_red(w)) {
|
|
rb_node_set_black(w);
|
|
rb_node_set_red(x_p);
|
|
rb_tree_rotate_left(T, x_p);
|
|
assert(x == x_p->left);
|
|
w = x_p->right;
|
|
}
|
|
if (rb_node_is_black(w->left) && rb_node_is_black(w->right)) {
|
|
rb_node_set_red(w);
|
|
x = x_p;
|
|
} else {
|
|
if (rb_node_is_black(w->right)) {
|
|
rb_node_set_black(w->left);
|
|
rb_node_set_red(w);
|
|
rb_tree_rotate_right(T, w);
|
|
w = x_p->right;
|
|
}
|
|
rb_node_copy_color(w, x_p);
|
|
rb_node_set_black(x_p);
|
|
rb_node_set_black(w->right);
|
|
rb_tree_rotate_left(T, x_p);
|
|
x = T->root;
|
|
}
|
|
} else {
|
|
struct rb_node *w = x_p->left;
|
|
if (rb_node_is_red(w)) {
|
|
rb_node_set_black(w);
|
|
rb_node_set_red(x_p);
|
|
rb_tree_rotate_right(T, x_p);
|
|
assert(x == x_p->right);
|
|
w = x_p->left;
|
|
}
|
|
if (rb_node_is_black(w->right) && rb_node_is_black(w->left)) {
|
|
rb_node_set_red(w);
|
|
x = x_p;
|
|
} else {
|
|
if (rb_node_is_black(w->left)) {
|
|
rb_node_set_black(w->right);
|
|
rb_node_set_red(w);
|
|
rb_tree_rotate_left(T, w);
|
|
w = x_p->left;
|
|
}
|
|
rb_node_copy_color(w, x_p);
|
|
rb_node_set_black(x_p);
|
|
rb_node_set_black(w->left);
|
|
rb_tree_rotate_right(T, x_p);
|
|
x = T->root;
|
|
}
|
|
}
|
|
x_p = rb_node_parent(x);
|
|
}
|
|
if (x)
|
|
rb_node_set_black(x);
|
|
}
|
|
|
|
struct rb_node *
|
|
rb_tree_first(struct rb_tree *T)
|
|
{
|
|
return T->root ? rb_node_minimum(T->root) : NULL;
|
|
}
|
|
|
|
struct rb_node *
|
|
rb_tree_last(struct rb_tree *T)
|
|
{
|
|
return T->root ? rb_node_maximum(T->root) : NULL;
|
|
}
|
|
|
|
struct rb_node *
|
|
rb_node_next(struct rb_node *node)
|
|
{
|
|
if (node->right) {
|
|
/* If we have a right child, then the next thing (compared to this
|
|
* node) is the left-most child of our right child.
|
|
*/
|
|
return rb_node_minimum(node->right);
|
|
} else {
|
|
/* If node doesn't have a right child, crawl back up the to the
|
|
* left until we hit a parent to the right.
|
|
*/
|
|
struct rb_node *p = rb_node_parent(node);
|
|
while (p && node == p->right) {
|
|
node = p;
|
|
p = rb_node_parent(node);
|
|
}
|
|
assert(p == NULL || node == p->left);
|
|
return p;
|
|
}
|
|
}
|
|
|
|
struct rb_node *
|
|
rb_node_prev(struct rb_node *node)
|
|
{
|
|
if (node->left) {
|
|
/* If we have a left child, then the previous thing (compared to
|
|
* this node) is the right-most child of our left child.
|
|
*/
|
|
return rb_node_maximum(node->left);
|
|
} else {
|
|
/* If node doesn't have a left child, crawl back up the to the
|
|
* right until we hit a parent to the left.
|
|
*/
|
|
struct rb_node *p = rb_node_parent(node);
|
|
while (p && node == p->left) {
|
|
node = p;
|
|
p = rb_node_parent(node);
|
|
}
|
|
assert(p == NULL || node == p->right);
|
|
return p;
|
|
}
|
|
}
|
|
|
|
static void
|
|
validate_rb_node(struct rb_node *n, int black_depth)
|
|
{
|
|
if (n == NULL) {
|
|
assert(black_depth == 0);
|
|
return;
|
|
}
|
|
|
|
if (rb_node_is_black(n)) {
|
|
black_depth--;
|
|
} else {
|
|
assert(rb_node_is_black(n->left));
|
|
assert(rb_node_is_black(n->right));
|
|
}
|
|
|
|
validate_rb_node(n->left, black_depth);
|
|
validate_rb_node(n->right, black_depth);
|
|
}
|
|
|
|
void
|
|
rb_tree_validate(struct rb_tree *T)
|
|
{
|
|
if (T->root == NULL)
|
|
return;
|
|
|
|
assert(rb_node_is_black(T->root));
|
|
|
|
unsigned black_depth = 0;
|
|
for (struct rb_node *n = T->root; n; n = n->left) {
|
|
if (rb_node_is_black(n))
|
|
black_depth++;
|
|
}
|
|
|
|
validate_rb_node(T->root, black_depth);
|
|
}
|