Differential D22012 Diff 63228 contrib/dhcpcd/compat/rb.c

Changeset View

Standalone View

contrib/dhcpcd/compat/rb.c

This file was added.

Property	Old Value	New Value
svn:eol-style	null	native \ No newline at end of property
svn:keywords	null	FreeBSD=%H \ No newline at end of property
svn:mime-type	null	text/plain \ No newline at end of property

				/* $NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy 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.
				*/

				#include "config.h"
				#include "common.h"

				#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.14 2019/03/08 09:14:54 roy Exp $");
				#else
				#include <lib/libkern/libkern.h>
				__KERNEL_RCSID(0, "$NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy 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 */