/* $NetBSD: rb.c,v 1.15 2019/05/09 10:56:24 skrll Exp $ */
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Matt Thomas <matt@3am-software.com>.
*
* 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.
*
* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND 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 THE FOUNDATION OR 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.
*/
#if HAVE_NBTOOL_CONFIG_H
#include "nbtool_config.h"
#endif
#if !defined(_KERNEL) && !defined(_STANDALONE)
#include <sys/types.h>
#include <stddef.h>
#include <assert.h>
#include <stdbool.h>
#ifdef RBDEBUG
#define KASSERT(s) assert(s)
#define __rbt_unused
#else
#define KASSERT(s) do { } while (/*CONSTCOND*/ 0)
#define __rbt_unused __unused
#endif
__RCSID("$NetBSD: rb.c,v 1.15 2019/05/09 10:56:24 skrll Exp $");
#else
#include <lib/libkern/libkern.h>
__KERNEL_RCSID(0, "$NetBSD: rb.c,v 1.15 2019/05/09 10:56:24 skrll Exp $");
#ifndef DIAGNOSTIC
#define __rbt_unused __unused
#else
#define __rbt_unused
#endif
#endif
#ifdef _LIBC
__weak_alias(rb_tree_init, _rb_tree_init)
__weak_alias(rb_tree_find_node, _rb_tree_find_node)
__weak_alias(rb_tree_find_node_geq, _rb_tree_find_node_geq)
__weak_alias(rb_tree_find_node_leq, _rb_tree_find_node_leq)
__weak_alias(rb_tree_insert_node, _rb_tree_insert_node)
__weak_alias(rb_tree_remove_node, _rb_tree_remove_node)
__weak_alias(rb_tree_iterate, _rb_tree_iterate)
#ifdef RBDEBUG
__weak_alias(rb_tree_check, _rb_tree_check)
__weak_alias(rb_tree_depths, _rb_tree_depths)
#endif
#include "namespace.h"
#endif
#ifdef RBTEST
#include "rbtree.h"
#else
#include <sys/rbtree.h>
#endif
static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
unsigned int);
#ifdef RBDEBUG
static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
const struct rb_node *, const unsigned int);
static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
const struct rb_node *, bool);
#else
#define rb_tree_check_node(a, b, c, d) true
#endif
#define RB_NODETOITEM(rbto, rbn) \
((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
#define RB_ITEMTONODE(rbto, rbn) \
((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
#define RB_SENTINEL_NODE NULL
void
rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
{
rbt->rbt_ops = ops;
rbt->rbt_root = RB_SENTINEL_NODE;
RB_TAILQ_INIT(&rbt->rbt_nodes);
#ifndef RBSMALL
rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root; /* minimum node */
rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root; /* maximum node */
#endif
#ifdef RBSTATS
rbt->rbt_count = 0;
rbt->rbt_insertions = 0;
rbt->rbt_removals = 0;
rbt->rbt_insertion_rebalance_calls = 0;
rbt->rbt_insertion_rebalance_passes = 0;
rbt->rbt_removal_rebalance_calls = 0;
rbt->rbt_removal_rebalance_passes = 0;
#endif
}
void *
rb_tree_find_node(struct rb_tree *rbt, const void *key)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root;
while (!RB_SENTINEL_P(parent)) {
void *pobj = RB_NODETOITEM(rbto, parent);
const signed int diff = (*compare_key)(rbto->rbto_context,
pobj, key);
if (diff == 0)
return pobj;
parent = parent->rb_nodes[diff < 0];
}
return NULL;
}
void *
rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root, *last = NULL;
while (!RB_SENTINEL_P(parent)) {
void *pobj = RB_NODETOITEM(rbto, parent);
const signed int diff = (*compare_key)(rbto->rbto_context,
pobj, key);
if (diff == 0)
return pobj;
if (diff > 0)
last = parent;
parent = parent->rb_nodes[diff < 0];
}
return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
}
void *
rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root, *last = NULL;
while (!RB_SENTINEL_P(parent)) {
void *pobj = RB_NODETOITEM(rbto, parent);
const signed int diff = (*compare_key)(rbto->rbto_context,
pobj, key);
if (diff == 0)
return pobj;
if (diff < 0)
last = parent;
parent = parent->rb_nodes[diff < 0];
}
return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
}
void *
rb_tree_insert_node(struct rb_tree *rbt, void *object)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
unsigned int position;
bool rebalance;
RBSTAT_INC(rbt->rbt_insertions);
tmp = rbt->rbt_root;
/*
* This is a hack. Because rbt->rbt_root is just a struct rb_node *,
* just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
* avoid a lot of tests for root and know that even at root,
* updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
* update rbt->rbt_root.
*/
parent = (struct rb_node *)(void *)&rbt->rbt_root;
position = RB_DIR_LEFT;
/*
* Find out where to place this new leaf.
*/
while (!RB_SENTINEL_P(tmp)) {
void *tobj = RB_NODETOITEM(rbto, tmp);
const signed int diff = (*compare_nodes)(rbto->rbto_context,
tobj, object);
if (__predict_false(diff == 0)) {
/*
* Node already exists; return it.
*/
return tobj;
}
parent = tmp;
position = (diff < 0);
tmp = parent->rb_nodes[position];
}
#ifdef RBDEBUG
{
struct rb_node *prev = NULL, *next = NULL;
if (position == RB_DIR_RIGHT)
prev = parent;
else if (tmp != rbt->rbt_root)
next = parent;
/*
* Verify our sequential position
*/
KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
KASSERT(next == NULL || !RB_SENTINEL_P(next));
if (prev != NULL && next == NULL)
next = TAILQ_NEXT(prev, rb_link);
if (prev == NULL && next != NULL)
prev = TAILQ_PREV(next, rb_node_qh, rb_link);
KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
KASSERT(next == NULL || !RB_SENTINEL_P(next));
KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
}
#endif
/*
* Initialize the node and insert as a leaf into the tree.
*/
RB_SET_FATHER(self, parent);
RB_SET_POSITION(self, position);
if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
RB_MARK_BLACK(self); /* root is always black */
#ifndef RBSMALL
rbt->rbt_minmax[RB_DIR_LEFT] = self;
rbt->rbt_minmax[RB_DIR_RIGHT] = self;
#endif
rebalance = false;
} else {
KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
#ifndef RBSMALL
/*
* Keep track of the minimum and maximum nodes. If our
* parent is a minmax node and we on their min/max side,
* we must be the new min/max node.
*/
if (parent == rbt->rbt_minmax[position])
rbt->rbt_minmax[position] = self;
#endif /* !RBSMALL */
/*
* All new nodes are colored red. We only need to rebalance
* if our parent is also red.
*/
RB_MARK_RED(self);
rebalance = RB_RED_P(parent);
}
KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
self->rb_left = parent->rb_nodes[position];
self->rb_right = parent->rb_nodes[position];
parent->rb_nodes[position] = self;
KASSERT(RB_CHILDLESS_P(self));
/*
* Insert the new node into a sorted list for easy sequential access
*/
RBSTAT_INC(rbt->rbt_count);
#ifdef RBDEBUG
if (RB_ROOT_P(rbt, self)) {
RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
} else if (position == RB_DIR_LEFT) {
KASSERT((*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, self),
RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
} else {
KASSERT((*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, RB_FATHER(self)),
RB_NODETOITEM(rbto, self)) < 0);
RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
self, rb_link);
}
#endif
KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
/*
* Rebalance tree after insertion
*/
if (rebalance) {
rb_tree_insert_rebalance(rbt, self);
KASSERT(rb_tree_check_node(rbt, self, NULL, true));
}
/* Succesfully inserted, return our node pointer. */
return object;
}
/*
* Swap the location and colors of 'self' and its child @ which. The child
* can not be a sentinel node. This is our rotation function. However,
* since it preserves coloring, it great simplifies both insertion and
* removal since rotation almost always involves the exchanging of colors
* as a separate step.
*/
static void
rb_tree_reparent_nodes(__rbt_unused struct rb_tree *rbt,
struct rb_node *old_father, const unsigned int which)
{
const unsigned int other = which ^ RB_DIR_OTHER;
struct rb_node * const grandpa = RB_FATHER(old_father);
struct rb_node * const old_child = old_father->rb_nodes[which];
struct rb_node * const new_father = old_child;
struct rb_node * const new_child = old_father;
KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
KASSERT(!RB_SENTINEL_P(old_child));
KASSERT(RB_FATHER(old_child) == old_father);
KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
KASSERT(RB_ROOT_P(rbt, old_father) ||
rb_tree_check_node(rbt, grandpa, NULL, false));
/*
* Exchange descendant linkages.
*/
grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
new_child->rb_nodes[which] = old_child->rb_nodes[other];
new_father->rb_nodes[other] = new_child;
/*
* Update ancestor linkages
*/
RB_SET_FATHER(new_father, grandpa);
RB_SET_FATHER(new_child, new_father);
/*
* Exchange properties between new_father and new_child. The only
* change is that new_child's position is now on the other side.
*/
#if 0
{
struct rb_node tmp;
tmp.rb_info = 0;
RB_COPY_PROPERTIES(&tmp, old_child);
RB_COPY_PROPERTIES(new_father, old_father);
RB_COPY_PROPERTIES(new_child, &tmp);
}
#else
RB_SWAP_PROPERTIES(new_father, new_child);
#endif
RB_SET_POSITION(new_child, other);
/*
* Make sure to reparent the new child to ourself.
*/
if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
RB_SET_FATHER(new_child->rb_nodes[which], new_child);
RB_SET_POSITION(new_child->rb_nodes[which], which);
}
KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
KASSERT(RB_ROOT_P(rbt, new_father) ||
rb_tree_check_node(rbt, grandpa, NULL, false));
}
static void
rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
{
struct rb_node * father = RB_FATHER(self);
struct rb_node * grandpa = RB_FATHER(father);
struct rb_node * uncle;
unsigned int which;
unsigned int other;
KASSERT(!RB_ROOT_P(rbt, self));
KASSERT(RB_RED_P(self));
KASSERT(RB_RED_P(father));
RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);
for (;;) {
KASSERT(!RB_SENTINEL_P(self));
KASSERT(RB_RED_P(self));
KASSERT(RB_RED_P(father));
/*
* We are red and our parent is red, therefore we must have a
* grandfather and he must be black.
*/
grandpa = RB_FATHER(father);
KASSERT(RB_BLACK_P(grandpa));
KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
which = (father == grandpa->rb_right);
other = which ^ RB_DIR_OTHER;
uncle = grandpa->rb_nodes[other];
if (RB_BLACK_P(uncle))
break;
RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);
/*
* Case 1: our uncle is red
* Simply invert the colors of our parent and
* uncle and make our grandparent red. And
* then solve the problem up at his level.
*/
RB_MARK_BLACK(uncle);
RB_MARK_BLACK(father);
if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
/*
* If our grandpa is root, don't bother
* setting him to red, just return.
*/
KASSERT(RB_BLACK_P(grandpa));
return;
}
RB_MARK_RED(grandpa);
self = grandpa;
father = RB_FATHER(self);
KASSERT(RB_RED_P(self));
if (RB_BLACK_P(father)) {
/*
* If our greatgrandpa is black, we're done.
*/
KASSERT(RB_BLACK_P(rbt->rbt_root));
return;
}
}
KASSERT(!RB_ROOT_P(rbt, self));
KASSERT(RB_RED_P(self));
KASSERT(RB_RED_P(father));
KASSERT(RB_BLACK_P(uncle));
KASSERT(RB_BLACK_P(grandpa));
/*
* Case 2&3: our uncle is black.
*/
if (self == father->rb_nodes[other]) {
/*
* Case 2: we are on the same side as our uncle
* Swap ourselves with our parent so this case
* becomes case 3. Basically our parent becomes our
* child.
*/
rb_tree_reparent_nodes(rbt, father, other);
KASSERT(RB_FATHER(father) == self);
KASSERT(self->rb_nodes[which] == father);
KASSERT(RB_FATHER(self) == grandpa);
self = father;
father = RB_FATHER(self);
}
KASSERT(RB_RED_P(self) && RB_RED_P(father));
KASSERT(grandpa->rb_nodes[which] == father);
/*
* Case 3: we are opposite a child of a black uncle.
* Swap our parent and grandparent. Since our grandfather
* is black, our father will become black and our new sibling
* (former grandparent) will become red.
*/
rb_tree_reparent_nodes(rbt, grandpa, which);
KASSERT(RB_FATHER(self) == father);
KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
KASSERT(RB_RED_P(self));
KASSERT(RB_BLACK_P(father));
KASSERT(RB_RED_P(grandpa));
/*
* Final step: Set the root to black.
*/
RB_MARK_BLACK(rbt->rbt_root);
}
static void
rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
{
const unsigned int which = RB_POSITION(self);
struct rb_node *father = RB_FATHER(self);
#ifndef RBSMALL
const bool was_root = RB_ROOT_P(rbt, self);
#endif
KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
KASSERT(!rebalance || RB_BLACK_P(self));
KASSERT(RB_CHILDLESS_P(self));
KASSERT(rb_tree_check_node(rbt, self, NULL, false));
/*
* Since we are childless, we know that self->rb_left is pointing
* to the sentinel node.
*/
father->rb_nodes[which] = self->rb_left;
/*
* Remove ourselves from the node list, decrement the count,
* and update min/max.
*/
RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
RBSTAT_DEC(rbt->rbt_count);
#ifndef RBSMALL
if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
rbt->rbt_minmax[RB_POSITION(self)] = father;
/*
* When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
* updated automatically, but we also need to update
* rbt->rbt_minmax[RB_DIR_RIGHT];
*/
if (__predict_false(was_root)) {
rbt->rbt_minmax[RB_DIR_RIGHT] = father;
}
}
RB_SET_FATHER(self, NULL);
#endif
/*
* Rebalance if requested.
*/
if (rebalance)
rb_tree_removal_rebalance(rbt, father, which);
KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
}
/*
* When deleting an interior node
*/
static void
rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
struct rb_node *standin)
{
const unsigned int standin_which = RB_POSITION(standin);
unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
struct rb_node *standin_son;
struct rb_node *standin_father = RB_FATHER(standin);
bool rebalance = RB_BLACK_P(standin);
if (standin_father == self) {
/*
* As a child of self, any childen would be opposite of
* our parent.
*/
KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
standin_son = standin->rb_nodes[standin_which];
} else {
/*
* Since we aren't a child of self, any childen would be
* on the same side as our parent.
*/
KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
standin_son = standin->rb_nodes[standin_other];
}
/*
* the node we are removing must have two children.
*/
KASSERT(RB_TWOCHILDREN_P(self));
/*
* If standin has a child, it must be red.
*/
KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
/*
* Verify things are sane.
*/
KASSERT(rb_tree_check_node(rbt, self, NULL, false));
KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
if (__predict_false(RB_RED_P(standin_son))) {
/*
* We know we have a red child so if we flip it to black
* we don't have to rebalance.
*/
KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
RB_MARK_BLACK(standin_son);
rebalance = false;
if (standin_father == self) {
KASSERT(RB_POSITION(standin_son) == standin_which);
} else {
KASSERT(RB_POSITION(standin_son) == standin_other);
/*
* Change the son's parentage to point to his grandpa.
*/
RB_SET_FATHER(standin_son, standin_father);
RB_SET_POSITION(standin_son, standin_which);
}
}
if (standin_father == self) {
/*
* If we are about to delete the standin's father, then when
* we call rebalance, we need to use ourselves as our father.
* Otherwise remember our original father. Also, sincef we are
* our standin's father we only need to reparent the standin's
* brother.
*
* | R --> S |
* | Q S --> Q T |
* | t --> |
*/
KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
KASSERT(self->rb_nodes[standin_which] == standin);
/*
* Have our son/standin adopt his brother as his new son.
*/
standin_father = standin;
} else {
/*
* | R --> S . |
* | / \ | T --> / \ | / |
* | ..... | S --> ..... | T |
*
* Sever standin's connection to his father.
*/
standin_father->rb_nodes[standin_which] = standin_son;
/*
* Adopt the far son.
*/
standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
/*
* Use standin_other because we need to preserve standin_which
* for the removal_rebalance.
*/
standin_other = standin_which;
}
/*
* Move the only remaining son to our standin. If our standin is our
* son, this will be the only son needed to be moved.
*/
KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
/*
* Now copy the result of self to standin and then replace
* self with standin in the tree.
*/
RB_COPY_PROPERTIES(standin, self);
RB_SET_FATHER(standin, RB_FATHER(self));
RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
/*
* Remove ourselves from the node list, decrement the count,
* and update min/max.
*/
RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
RBSTAT_DEC(rbt->rbt_count);
#ifndef RBSMALL
if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
RB_SET_FATHER(self, NULL);
#endif
KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
KASSERT(RB_FATHER_SENTINEL_P(standin)
|| rb_tree_check_node(rbt, standin_father, NULL, false));
KASSERT(RB_LEFT_SENTINEL_P(standin)
|| rb_tree_check_node(rbt, standin->rb_left, NULL, false));
KASSERT(RB_RIGHT_SENTINEL_P(standin)
|| rb_tree_check_node(rbt, standin->rb_right, NULL, false));
if (!rebalance)
return;
rb_tree_removal_rebalance(rbt, standin_father, standin_which);
KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
}
/*
* We could do this by doing
* rb_tree_node_swap(rbt, self, which);
* rb_tree_prune_node(rbt, self, false);
*
* But it's more efficient to just evalate and recolor the child.
*/
static void
rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
unsigned int which)
{
struct rb_node *father = RB_FATHER(self);
struct rb_node *son = self->rb_nodes[which];
#ifndef RBSMALL
const bool was_root = RB_ROOT_P(rbt, self);
#endif
KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
KASSERT(!RB_TWOCHILDREN_P(son));
KASSERT(RB_CHILDLESS_P(son));
KASSERT(rb_tree_check_node(rbt, self, NULL, false));
KASSERT(rb_tree_check_node(rbt, son, NULL, false));
/*
* Remove ourselves from the tree and give our former child our
* properties (position, color, root).
*/
RB_COPY_PROPERTIES(son, self);
father->rb_nodes[RB_POSITION(son)] = son;
RB_SET_FATHER(son, father);
/*
* Remove ourselves from the node list, decrement the count,
* and update minmax.
*/
RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
RBSTAT_DEC(rbt->rbt_count);
#ifndef RBSMALL
if (__predict_false(was_root)) {
KASSERT(rbt->rbt_minmax[which] == son);
rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;
} else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
rbt->rbt_minmax[RB_POSITION(self)] = son;
}
RB_SET_FATHER(self, NULL);
#endif
KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
KASSERT(rb_tree_check_node(rbt, son, NULL, true));
}
void
rb_tree_remove_node(struct rb_tree *rbt, void *object)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
unsigned int which;
KASSERT(!RB_SENTINEL_P(self));
RBSTAT_INC(rbt->rbt_removals);
/*
* In the following diagrams, we (the node to be removed) are S. Red
* nodes are lowercase. T could be either red or black.
*
* Remember the major axiom of the red-black tree: the number of
* black nodes from the root to each leaf is constant across all
* leaves, only the number of red nodes varies.
*
* Thus removing a red leaf doesn't require any other changes to a
* red-black tree. So if we must remove a node, attempt to rearrange
* the tree so we can remove a red node.
*
* The simpliest case is a childless red node or a childless root node:
*
* | T --> T | or | R --> * |
* | s --> * |
*/
if (RB_CHILDLESS_P(self)) {
const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
rb_tree_prune_node(rbt, self, rebalance);
return;
}
KASSERT(!RB_CHILDLESS_P(self));
if (!RB_TWOCHILDREN_P(self)) {
/*
* The next simpliest case is the node we are deleting is
* black and has one red child.
*
* | T --> T --> T |
* | S --> R --> R |
* | r --> s --> * |
*/
which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
KASSERT(RB_BLACK_P(self));
KASSERT(RB_RED_P(self->rb_nodes[which]));
KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
rb_tree_prune_blackred_branch(rbt, self, which);
return;
}
KASSERT(RB_TWOCHILDREN_P(self));
/*
* We invert these because we prefer to remove from the inside of
* the tree.
*/
which = RB_POSITION(self) ^ RB_DIR_OTHER;
/*
* Let's find the node closes to us opposite of our parent
* Now swap it with ourself, "prune" it, and rebalance, if needed.
*/
standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));
rb_tree_swap_prune_and_rebalance(rbt, self, standin);
}
static void
rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
unsigned int which)
{
KASSERT(!RB_SENTINEL_P(parent));
KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
RBSTAT_INC(rbt->rbt_removal_rebalance_calls);
while (RB_BLACK_P(parent->rb_nodes[which])) {
unsigned int other = which ^ RB_DIR_OTHER;
struct rb_node *brother = parent->rb_nodes[other];
RBSTAT_INC(rbt->rbt_removal_rebalance_passes);
KASSERT(!RB_SENTINEL_P(brother));
/*
* For cases 1, 2a, and 2b, our brother's children must
* be black and our father must be black
*/
if (RB_BLACK_P(parent)
&& RB_BLACK_P(brother->rb_left)
&& RB_BLACK_P(brother->rb_right)) {
if (RB_RED_P(brother)) {
/*
* Case 1: Our brother is red, swap its
* position (and colors) with our parent.
* This should now be case 2b (unless C or E
* has a red child which is case 3; thus no
* explicit branch to case 2b).
*
* B -> D
* A d -> b E
* C E -> A C
*/
KASSERT(RB_BLACK_P(parent));
rb_tree_reparent_nodes(rbt, parent, other);
brother = parent->rb_nodes[other];
KASSERT(!RB_SENTINEL_P(brother));
KASSERT(RB_RED_P(parent));
KASSERT(RB_BLACK_P(brother));
KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
} else {
/*
* Both our parent and brother are black.
* Change our brother to red, advance up rank
* and go through the loop again.
*
* B -> *B
* *A D -> A d
* C E -> C E
*/
RB_MARK_RED(brother);
KASSERT(RB_BLACK_P(brother->rb_left));
KASSERT(RB_BLACK_P(brother->rb_right));
if (RB_ROOT_P(rbt, parent))
return; /* root == parent == black */
KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
which = RB_POSITION(parent);
parent = RB_FATHER(parent);
continue;
}
}
/*
* Avoid an else here so that case 2a above can hit either
* case 2b, 3, or 4.
*/
if (RB_RED_P(parent)
&& RB_BLACK_P(brother)
&& RB_BLACK_P(brother->rb_left)
&& RB_BLACK_P(brother->rb_right)) {
KASSERT(RB_RED_P(parent));
KASSERT(RB_BLACK_P(brother));
KASSERT(RB_BLACK_P(brother->rb_left));
KASSERT(RB_BLACK_P(brother->rb_right));
/*
* We are black, our father is red, our brother and
* both nephews are black. Simply invert/exchange the
* colors of our father and brother (to black and red
* respectively).
*
* | f --> F |
* | * B --> * b |
* | N N --> N N |
*/
RB_MARK_BLACK(parent);
RB_MARK_RED(brother);
KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
break; /* We're done! */
} else {
/*
* Our brother must be black and have at least one
* red child (it may have two).
*/
KASSERT(RB_BLACK_P(brother));
KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
RB_RED_P(brother->rb_nodes[other]));
if (RB_BLACK_P(brother->rb_nodes[other])) {
/*
* Case 3: our brother is black, our near
* nephew is red, and our far nephew is black.
* Swap our brother with our near nephew.
* This result in a tree that matches case 4.
* (Our father could be red or black).
*
* | F --> F |
* | x B --> x B |
* | n --> n |
*/
KASSERT(RB_RED_P(brother->rb_nodes[which]));
rb_tree_reparent_nodes(rbt, brother, which);
KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
brother = parent->rb_nodes[other];
KASSERT(RB_RED_P(brother->rb_nodes[other]));
}
/*
* Case 4: our brother is black and our far nephew
* is red. Swap our father and brother locations and
* change our far nephew to black. (these can be
* done in either order so we change the color first).
* The result is a valid red-black tree and is a
* terminal case. (again we don't care about the
* father's color)
*
* If the father is red, we will get a red-black-black
* tree:
* | f -> f --> b |
* | B -> B --> F N |
* | n -> N --> |
*
* If the father is black, we will get an all black
* tree:
* | F -> F --> B |
* | B -> B --> F N |
* | n -> N --> |
*
* If we had two red nephews, then after the swap,
* our former father would have a red grandson.
*/
KASSERT(RB_BLACK_P(brother));
KASSERT(RB_RED_P(brother->rb_nodes[other]));
RB_MARK_BLACK(brother->rb_nodes[other]);
rb_tree_reparent_nodes(rbt, parent, other);
break; /* We're done! */
}
}
KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
}
void *
rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
const unsigned int other = direction ^ RB_DIR_OTHER;
struct rb_node *self;
KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
if (object == NULL) {
#ifndef RBSMALL
if (RB_SENTINEL_P(rbt->rbt_root))
return NULL;
return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
#else
self = rbt->rbt_root;
if (RB_SENTINEL_P(self))
return NULL;
while (!RB_SENTINEL_P(self->rb_nodes[direction]))
self = self->rb_nodes[direction];
return RB_NODETOITEM(rbto, self);
#endif /* !RBSMALL */
}
self = RB_ITEMTONODE(rbto, object);
KASSERT(!RB_SENTINEL_P(self));
/*
* We can't go any further in this direction. We proceed up in the
* opposite direction until our parent is in direction we want to go.
*/
if (RB_SENTINEL_P(self->rb_nodes[direction])) {
while (!RB_ROOT_P(rbt, self)) {
if (other == RB_POSITION(self))
return RB_NODETOITEM(rbto, RB_FATHER(self));
self = RB_FATHER(self);
}
return NULL;
}
/*
* Advance down one in current direction and go down as far as possible
* in the opposite direction.
*/
self = self->rb_nodes[direction];
KASSERT(!RB_SENTINEL_P(self));
while (!RB_SENTINEL_P(self->rb_nodes[other]))
self = self->rb_nodes[other];
return RB_NODETOITEM(rbto, self);
}
#ifdef RBDEBUG
static const struct rb_node *
rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
const unsigned int direction)
{
const unsigned int other = direction ^ RB_DIR_OTHER;
KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
if (self == NULL) {
#ifndef RBSMALL
if (RB_SENTINEL_P(rbt->rbt_root))
return NULL;
return rbt->rbt_minmax[direction];
#else
self = rbt->rbt_root;
if (RB_SENTINEL_P(self))
return NULL;
while (!RB_SENTINEL_P(self->rb_nodes[direction]))
self = self->rb_nodes[direction];
return self;
#endif /* !RBSMALL */
}
KASSERT(!RB_SENTINEL_P(self));
/*
* We can't go any further in this direction. We proceed up in the
* opposite direction until our parent is in direction we want to go.
*/
if (RB_SENTINEL_P(self->rb_nodes[direction])) {
while (!RB_ROOT_P(rbt, self)) {
if (other == RB_POSITION(self))
return RB_FATHER(self);
self = RB_FATHER(self);
}
return NULL;
}
/*
* Advance down one in current direction and go down as far as possible
* in the opposite direction.
*/
self = self->rb_nodes[direction];
KASSERT(!RB_SENTINEL_P(self));
while (!RB_SENTINEL_P(self->rb_nodes[other]))
self = self->rb_nodes[other];
return self;
}
static unsigned int
rb_tree_count_black(const struct rb_node *self)
{
unsigned int left, right;
if (RB_SENTINEL_P(self))
return 0;
left = rb_tree_count_black(self->rb_left);
right = rb_tree_count_black(self->rb_right);
KASSERT(left == right);
return left + RB_BLACK_P(self);
}
static bool
rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
const struct rb_node *prev, bool red_check)
{
const rb_tree_ops_t *rbto = rbt->rbt_ops;
rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
KASSERT(!RB_SENTINEL_P(self));
KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
/*
* Verify our relationship to our parent.
*/
if (RB_ROOT_P(rbt, self)) {
KASSERT(self == rbt->rbt_root);
KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
} else {
int diff = (*compare_nodes)(rbto->rbto_context,
RB_NODETOITEM(rbto, self),
RB_NODETOITEM(rbto, RB_FATHER(self)));
KASSERT(self != rbt->rbt_root);
KASSERT(!RB_FATHER_SENTINEL_P(self));
if (RB_POSITION(self) == RB_DIR_LEFT) {
KASSERT(diff < 0);
KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
} else {
KASSERT(diff > 0);
KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
}
}
/*
* Verify our position in the linked list against the tree itself.
*/
{
const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
KASSERT(next0 == TAILQ_NEXT(self, rb_link));
#ifndef RBSMALL
KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
#endif
}
/*
* The root must be black.
* There can never be two adjacent red nodes.
*/
if (red_check) {
KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
(void) rb_tree_count_black(self);
if (RB_RED_P(self)) {
const struct rb_node *brother;
KASSERT(!RB_ROOT_P(rbt, self));
brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
KASSERT(RB_BLACK_P(RB_FATHER(self)));
/*
* I'm red and have no children, then I must either
* have no brother or my brother also be red and
* also have no children. (black count == 0)
*/
KASSERT(!RB_CHILDLESS_P(self)
|| RB_SENTINEL_P(brother)
|| RB_RED_P(brother)
|| RB_CHILDLESS_P(brother));
/*
* If I'm not childless, I must have two children
* and they must be both be black.
*/
KASSERT(RB_CHILDLESS_P(self)
|| (RB_TWOCHILDREN_P(self)
&& RB_BLACK_P(self->rb_left)
&& RB_BLACK_P(self->rb_right)));
/*
* If I'm not childless, thus I have black children,
* then my brother must either be black or have two
* black children.
*/
KASSERT(RB_CHILDLESS_P(self)
|| RB_BLACK_P(brother)
|| (RB_TWOCHILDREN_P(brother)
&& RB_BLACK_P(brother->rb_left)
&& RB_BLACK_P(brother->rb_right)));
} else {
/*
* If I'm black and have one child, that child must
* be red and childless.
*/
KASSERT(RB_CHILDLESS_P(self)
|| RB_TWOCHILDREN_P(self)
|| (!RB_LEFT_SENTINEL_P(self)
&& RB_RIGHT_SENTINEL_P(self)
&& RB_RED_P(self->rb_left)
&& RB_CHILDLESS_P(self->rb_left))
|| (!RB_RIGHT_SENTINEL_P(self)
&& RB_LEFT_SENTINEL_P(self)
&& RB_RED_P(self->rb_right)
&& RB_CHILDLESS_P(self->rb_right)));
/*
* If I'm a childless black node and my parent is
* black, my 2nd closet relative away from my parent
* is either red or has a red parent or red children.
*/
if (!RB_ROOT_P(rbt, self)
&& RB_CHILDLESS_P(self)
&& RB_BLACK_P(RB_FATHER(self))) {
const unsigned int which = RB_POSITION(self);
const unsigned int other = which ^ RB_DIR_OTHER;
const struct rb_node *relative0, *relative;
relative0 = rb_tree_iterate_const(rbt,
self, other);
KASSERT(relative0 != NULL);
relative = rb_tree_iterate_const(rbt,
relative0, other);
KASSERT(relative != NULL);
KASSERT(RB_SENTINEL_P(relative->rb_nodes[which]));
#if 0
KASSERT(RB_RED_P(relative)
|| RB_RED_P(relative->rb_left)
|| RB_RED_P(relative->rb_right)
|| RB_RED_P(RB_FATHER(relative)));
#endif
}
}
/*
* A grandparent's children must be real nodes and not
* sentinels. First check out grandparent.
*/
KASSERT(RB_ROOT_P(rbt, self)
|| RB_ROOT_P(rbt, RB_FATHER(self))
|| RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
/*
* If we are have grandchildren on our left, then
* we must have a child on our right.
*/
KASSERT(RB_LEFT_SENTINEL_P(self)
|| RB_CHILDLESS_P(self->rb_left)
|| !RB_RIGHT_SENTINEL_P(self));
/*
* If we are have grandchildren on our right, then
* we must have a child on our left.
*/
KASSERT(RB_RIGHT_SENTINEL_P(self)
|| RB_CHILDLESS_P(self->rb_right)
|| !RB_LEFT_SENTINEL_P(self));
/*
* If we have a child on the left and it doesn't have two
* children make sure we don't have great-great-grandchildren on
* the right.
*/
KASSERT(RB_TWOCHILDREN_P(self->rb_left)
|| RB_CHILDLESS_P(self->rb_right)
|| RB_CHILDLESS_P(self->rb_right->rb_left)
|| RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
|| RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
|| RB_CHILDLESS_P(self->rb_right->rb_right)
|| RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
|| RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
/*
* If we have a child on the right and it doesn't have two
* children make sure we don't have great-great-grandchildren on
* the left.
*/
KASSERT(RB_TWOCHILDREN_P(self->rb_right)
|| RB_CHILDLESS_P(self->rb_left)
|| RB_CHILDLESS_P(self->rb_left->rb_left)
|| RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
|| RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
|| RB_CHILDLESS_P(self->rb_left->rb_right)
|| RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
|| RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
/*
* If we are fully interior node, then our predecessors and
* successors must have no children in our direction.
*/
if (RB_TWOCHILDREN_P(self)) {
const struct rb_node *prev0;
const struct rb_node *next0;
prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
KASSERT(prev0 != NULL);
KASSERT(RB_RIGHT_SENTINEL_P(prev0));
next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
KASSERT(next0 != NULL);
KASSERT(RB_LEFT_SENTINEL_P(next0));
}
}
return true;
}
void
rb_tree_check(const struct rb_tree *rbt, bool red_check)
{
const struct rb_node *self;
const struct rb_node *prev;
#ifdef RBSTATS
unsigned int count = 0;
#endif
KASSERT(rbt->rbt_root != NULL);
KASSERT(RB_LEFT_P(rbt->rbt_root));
#if defined(RBSTATS) && !defined(RBSMALL)
KASSERT(rbt->rbt_count > 1
|| rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);
#endif
prev = NULL;
TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
rb_tree_check_node(rbt, self, prev, false);
#ifdef RBSTATS
count++;
#endif
}
#ifdef RBSTATS
KASSERT(rbt->rbt_count == count);
#endif
if (red_check) {
KASSERT(RB_BLACK_P(rbt->rbt_root));
KASSERT(RB_SENTINEL_P(rbt->rbt_root)
|| rb_tree_count_black(rbt->rbt_root));
/*
* The root must be black.
* There can never be two adjacent red nodes.
*/
TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
rb_tree_check_node(rbt, self, NULL, true);
}
}
}
#endif /* RBDEBUG */
#ifdef RBSTATS
static void
rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
size_t *depths, size_t depth)
{
if (RB_SENTINEL_P(self))
return;
if (RB_TWOCHILDREN_P(self)) {
rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
return;
}
depths[depth]++;
if (!RB_LEFT_SENTINEL_P(self)) {
rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
}
if (!RB_RIGHT_SENTINEL_P(self)) {
rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
}
}
void
rb_tree_depths(const struct rb_tree *rbt, size_t *depths)
{
rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);
}
#endif /* RBSTATS */