Changeset View
Changeset View
Standalone View
Standalone View
contrib/dhcpcd/compat/rb.c
- This file was added.
/* $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 */ |