#if !defined(_KERNEL) && !defined(_STANDALONE)
#include <sys/types.h>
#include <sys/types.h>
#include <stddef.h>
#include <assert.h>
#include <stdbool.h>
#ifdef RBDEBUG
#define KASSERT(s) assert(s)
#else
#define KASSERT(s) do { } while ( 0)
#endif
#else
#include <lib/libkern/libkern.h>
#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
#define rb_tree_init _rb_tree_init
#define rb_tree_find_node _rb_tree_find_node
#define rb_tree_find_node_geq _rb_tree_find_node_geq
#define rb_tree_find_node_leq _rb_tree_find_node_leq
#define rb_tree_insert_node _rb_tree_insert_node
#define rb_tree_remove_node _rb_tree_remove_node
#define rb_tree_iterate _rb_tree_iterate
#ifdef RBDEBUG
#define rb_tree_check _rb_tree_check
#define rb_tree_depths _rb_tree_depths
#endif
#endif
#if defined(RBTEST) || defined(__APPLE__)
#include "rb.h"
#else
#include <sys/rb.h>
#endif
#ifdef __APPLE__
#define __predict_true(exp) (__builtin_expect((exp) != 0, 1))
#define __predict_false(exp) (__builtin_expect((exp) != 0, 0))
#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_SENTINEL_NODE NULL
void
rb_tree_init(struct rb_tree *rbt, const struct rb_tree_ops *ops)
{
rbt->rbt_ops = ops;
*((const struct rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
RB_TAILQ_INIT(&rbt->rbt_nodes);
#ifndef RBSMALL
rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root;
rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root;
#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
}
struct rb_node *
rb_tree_find_node(struct rb_tree *rbt, const void *key)
{
rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root;
while (!RB_SENTINEL_P(parent)) {
const signed int diff = (*compare_key)(parent, key);
if (diff == 0)
return parent;
parent = parent->rb_nodes[diff > 0];
}
return NULL;
}
struct rb_node *
rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
{
rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root;
struct rb_node *last = NULL;
while (!RB_SENTINEL_P(parent)) {
const signed int diff = (*compare_key)(parent, key);
if (diff == 0)
return parent;
if (diff < 0)
last = parent;
parent = parent->rb_nodes[diff > 0];
}
return last;
}
struct rb_node *
rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
{
rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
struct rb_node *parent = rbt->rbt_root;
struct rb_node *last = NULL;
while (!RB_SENTINEL_P(parent)) {
const signed int diff = (*compare_key)(parent, key);
if (diff == 0)
return parent;
if (diff > 0)
last = parent;
parent = parent->rb_nodes[diff > 0];
}
return last;
}
bool
rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
{
rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
struct rb_node *parent, *tmp;
unsigned int position;
bool rebalance;
RBSTAT_INC(rbt->rbt_insertions);
tmp = rbt->rbt_root;
parent = (struct rb_node *)(void *)&rbt->rbt_root;
position = RB_DIR_LEFT;
while (!RB_SENTINEL_P(tmp)) {
const signed int diff = (*compare_nodes)(tmp, self);
if (__predict_false(diff == 0)) {
return false;
}
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;
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)(prev, self) > 0);
KASSERT(next == NULL || (*compare_nodes)(self, next) > 0);
}
#endif
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);
#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
if (parent == rbt->rbt_minmax[position])
rbt->rbt_minmax[position] = self;
#endif
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));
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)(self, RB_FATHER(self)) > 0);
RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
} else {
KASSERT((*compare_nodes)(RB_FATHER(self), 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));
if (rebalance) {
rb_tree_insert_rebalance(rbt, self);
KASSERT(rb_tree_check_node(rbt, self, NULL, true));
}
return true;
}
static void
rb_tree_reparent_nodes(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));
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;
RB_SET_FATHER(new_father, grandpa);
RB_SET_FATHER(new_child, new_father);
#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);
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));
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);
RB_MARK_BLACK(uncle);
RB_MARK_BLACK(father);
if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
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)) {
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));
if (self == father->rb_nodes[other]) {
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);
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));
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);
const bool was_root = RB_ROOT_P(rbt, self);
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));
father->rb_nodes[which] = self->rb_left;
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;
if (__predict_false(was_root)) {
rbt->rbt_minmax[RB_DIR_RIGHT] = father;
}
}
RB_SET_FATHER(self, NULL);
#endif
if (rebalance)
rb_tree_removal_rebalance(rbt, father, which);
KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
}
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) {
KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
standin_son = standin->rb_nodes[standin_which];
} else {
KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
standin_son = standin->rb_nodes[standin_other];
}
KASSERT(RB_TWOCHILDREN_P(self));
KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
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))) {
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);
RB_SET_FATHER(standin_son, standin_father);
RB_SET_POSITION(standin_son, standin_which);
}
}
if (standin_father == self) {
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);
standin_father = standin;
} else {
standin_father->rb_nodes[standin_which] = standin_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);
standin_other = standin_which;
}
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);
RB_COPY_PROPERTIES(standin, self);
RB_SET_FATHER(standin, RB_FATHER(self));
RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
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));
}
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];
const bool was_root = RB_ROOT_P(rbt, self);
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));
RB_COPY_PROPERTIES(son, self);
father->rb_nodes[RB_POSITION(son)] = son;
RB_SET_FATHER(son, father);
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, struct rb_node *self)
{
struct rb_node *standin;
unsigned int which;
KASSERT(!RB_SENTINEL_P(self));
RBSTAT_INC(rbt->rbt_removals);
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)) {
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));
which = RB_POSITION(self) ^ RB_DIR_OTHER;
standin = rb_tree_iterate(rbt, self, 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));
if (RB_BLACK_P(parent)
&& RB_BLACK_P(brother->rb_left)
&& RB_BLACK_P(brother->rb_right)) {
if (RB_RED_P(brother)) {
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 {
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;
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;
}
}
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));
RB_MARK_BLACK(parent);
RB_MARK_RED(brother);
KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
break;
} else {
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])) {
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]));
}
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;
}
}
KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
}
struct rb_node *
rb_tree_iterate(struct rb_tree *rbt, 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[other]))
self = self->rb_nodes[other];
return self;
#endif
}
KASSERT(!RB_SENTINEL_P(self));
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;
}
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;
}
#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[other]))
self = self->rb_nodes[other];
return self;
#endif
}
KASSERT(!RB_SENTINEL_P(self));
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;
}
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)
{
rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
KASSERT(!RB_SENTINEL_P(self));
KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
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 {
KASSERT(self != rbt->rbt_root);
KASSERT(!RB_FATHER_SENTINEL_P(self));
if (RB_POSITION(self) == RB_DIR_LEFT) {
KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
} else {
KASSERT((*compare_nodes)(self, RB_FATHER(self)) < 0);
KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
}
}
{
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
}
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)));
KASSERT(!RB_CHILDLESS_P(self)
|| RB_SENTINEL_P(brother)
|| RB_RED_P(brother)
|| RB_CHILDLESS_P(brother));
KASSERT(RB_CHILDLESS_P(self)
|| (RB_TWOCHILDREN_P(self)
&& RB_BLACK_P(self->rb_left)
&& RB_BLACK_P(self->rb_right)));
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 {
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 (!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
}
}
KASSERT(RB_ROOT_P(rbt, self)
|| RB_ROOT_P(rbt, RB_FATHER(self))
|| RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
KASSERT(RB_LEFT_SENTINEL_P(self)
|| RB_CHILDLESS_P(self->rb_left)
|| !RB_RIGHT_SENTINEL_P(self));
KASSERT(RB_RIGHT_SENTINEL_P(self)
|| RB_CHILDLESS_P(self->rb_right)
|| !RB_LEFT_SENTINEL_P(self));
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));
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 (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));
TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
rb_tree_check_node(rbt, self, NULL, true);
}
}
}
#endif
#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