"Fossies" - the Fresh Open Source Software Archive

Member "dhcpcd-9.4.1/compat/rb.c" (22 Oct 2021, 40263 Bytes) of package /linux/misc/dhcpcd-9.4.1.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /*  $NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $  */
    2 
    3 /*-
    4  * Copyright (c) 2001 The NetBSD Foundation, Inc.
    5  * All rights reserved.
    6  *
    7  * This code is derived from software contributed to The NetBSD Foundation
    8  * by Matt Thomas <matt@3am-software.com>.
    9  *
   10  * Redistribution and use in source and binary forms, with or without
   11  * modification, are permitted provided that the following conditions
   12  * are met:
   13  * 1. Redistributions of source code must retain the above copyright
   14  *    notice, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  *
   19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   29  * POSSIBILITY OF SUCH DAMAGE.
   30  */
   31 
   32 #include "config.h"
   33 #include "common.h"
   34 
   35 #if !defined(_KERNEL) && !defined(_STANDALONE)
   36 #include <sys/types.h>
   37 #include <stddef.h>
   38 #include <assert.h>
   39 #include <stdbool.h>
   40 #ifdef RBDEBUG
   41 #define KASSERT(s)  assert(s)
   42 #define __rbt_unused
   43 #else
   44 #define KASSERT(s)  do { } while (/*CONSTCOND*/ 0)
   45 #define __rbt_unused    __unused
   46 #endif
   47 __RCSID("$NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $");
   48 #else
   49 #include <lib/libkern/libkern.h>
   50 __KERNEL_RCSID(0, "$NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $");
   51 #ifndef DIAGNOSTIC
   52 #define __rbt_unused    __unused
   53 #else
   54 #define __rbt_unused
   55 #endif
   56 #endif
   57 
   58 #ifdef _LIBC
   59 __weak_alias(rb_tree_init, _rb_tree_init)
   60 __weak_alias(rb_tree_find_node, _rb_tree_find_node)
   61 __weak_alias(rb_tree_find_node_geq, _rb_tree_find_node_geq)
   62 __weak_alias(rb_tree_find_node_leq, _rb_tree_find_node_leq)
   63 __weak_alias(rb_tree_insert_node, _rb_tree_insert_node)
   64 __weak_alias(rb_tree_remove_node, _rb_tree_remove_node)
   65 __weak_alias(rb_tree_iterate, _rb_tree_iterate)
   66 #ifdef RBDEBUG
   67 __weak_alias(rb_tree_check, _rb_tree_check)
   68 __weak_alias(rb_tree_depths, _rb_tree_depths)
   69 #endif
   70 
   71 #include "namespace.h"
   72 #endif
   73 
   74 #ifdef RBTEST
   75 #include "rbtree.h"
   76 #else
   77 #include <sys/rbtree.h>
   78 #endif
   79 
   80 static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
   81 static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
   82     unsigned int);
   83 #ifdef RBDEBUG
   84 static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
   85     const struct rb_node *, const unsigned int);
   86 static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
   87     const struct rb_node *, bool);
   88 #else
   89 #define rb_tree_check_node(a, b, c, d)  true
   90 #endif
   91 
   92 #define RB_NODETOITEM(rbto, rbn)    \
   93     ((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
   94 #define RB_ITEMTONODE(rbto, rbn)    \
   95     ((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
   96 
   97 #define RB_SENTINEL_NODE    NULL
   98 
   99 void
  100 rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
  101 {
  102 
  103     rbt->rbt_ops = ops;
  104     rbt->rbt_root = RB_SENTINEL_NODE;
  105     RB_TAILQ_INIT(&rbt->rbt_nodes);
  106 #ifndef RBSMALL
  107     rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root;   /* minimum node */
  108     rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root;  /* maximum node */
  109 #endif
  110 #ifdef RBSTATS
  111     rbt->rbt_count = 0;
  112     rbt->rbt_insertions = 0;
  113     rbt->rbt_removals = 0;
  114     rbt->rbt_insertion_rebalance_calls = 0;
  115     rbt->rbt_insertion_rebalance_passes = 0;
  116     rbt->rbt_removal_rebalance_calls = 0;
  117     rbt->rbt_removal_rebalance_passes = 0;
  118 #endif
  119 }
  120 
  121 void *
  122 rb_tree_find_node(struct rb_tree *rbt, const void *key)
  123 {
  124     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  125     rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
  126     struct rb_node *parent = rbt->rbt_root;
  127 
  128     while (!RB_SENTINEL_P(parent)) {
  129         void *pobj = RB_NODETOITEM(rbto, parent);
  130         const signed int diff = (*compare_key)(rbto->rbto_context,
  131             pobj, key);
  132         if (diff == 0)
  133             return pobj;
  134         parent = parent->rb_nodes[diff < 0];
  135     }
  136 
  137     return NULL;
  138 }
  139 
  140 void *
  141 rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
  142 {
  143     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  144     rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
  145     struct rb_node *parent = rbt->rbt_root, *last = NULL;
  146 
  147     while (!RB_SENTINEL_P(parent)) {
  148         void *pobj = RB_NODETOITEM(rbto, parent);
  149         const signed int diff = (*compare_key)(rbto->rbto_context,
  150             pobj, key);
  151         if (diff == 0)
  152             return pobj;
  153         if (diff > 0)
  154             last = parent;
  155         parent = parent->rb_nodes[diff < 0];
  156     }
  157 
  158     return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
  159 }
  160 
  161 void *
  162 rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
  163 {
  164     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  165     rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
  166     struct rb_node *parent = rbt->rbt_root, *last = NULL;
  167 
  168     while (!RB_SENTINEL_P(parent)) {
  169         void *pobj = RB_NODETOITEM(rbto, parent);
  170         const signed int diff = (*compare_key)(rbto->rbto_context,
  171             pobj, key);
  172         if (diff == 0)
  173             return pobj;
  174         if (diff < 0)
  175             last = parent;
  176         parent = parent->rb_nodes[diff < 0];
  177     }
  178 
  179     return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
  180 }
  181 
  182 void *
  183 rb_tree_insert_node(struct rb_tree *rbt, void *object)
  184 {
  185     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  186     rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
  187     struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
  188     unsigned int position;
  189     bool rebalance;
  190 
  191     RBSTAT_INC(rbt->rbt_insertions);
  192 
  193     tmp = rbt->rbt_root;
  194     /*
  195      * This is a hack.  Because rbt->rbt_root is just a struct rb_node *,
  196      * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
  197      * avoid a lot of tests for root and know that even at root,
  198      * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
  199      * update rbt->rbt_root.
  200      */
  201     parent = (struct rb_node *)(void *)&rbt->rbt_root;
  202     position = RB_DIR_LEFT;
  203 
  204     /*
  205      * Find out where to place this new leaf.
  206      */
  207     while (!RB_SENTINEL_P(tmp)) {
  208         void *tobj = RB_NODETOITEM(rbto, tmp);
  209         const signed int diff = (*compare_nodes)(rbto->rbto_context,
  210             tobj, object);
  211         if (__predict_false(diff == 0)) {
  212             /*
  213              * Node already exists; return it.
  214              */
  215             return tobj;
  216         }
  217         parent = tmp;
  218         position = (diff < 0);
  219         tmp = parent->rb_nodes[position];
  220     }
  221 
  222 #ifdef RBDEBUG
  223     {
  224         struct rb_node *prev = NULL, *next = NULL;
  225 
  226         if (position == RB_DIR_RIGHT)
  227             prev = parent;
  228         else if (tmp != rbt->rbt_root)
  229             next = parent;
  230 
  231         /*
  232          * Verify our sequential position
  233          */
  234         KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
  235         KASSERT(next == NULL || !RB_SENTINEL_P(next));
  236         if (prev != NULL && next == NULL)
  237             next = TAILQ_NEXT(prev, rb_link);
  238         if (prev == NULL && next != NULL)
  239             prev = TAILQ_PREV(next, rb_node_qh, rb_link);
  240         KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
  241         KASSERT(next == NULL || !RB_SENTINEL_P(next));
  242         KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
  243             RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
  244         KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
  245             RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
  246     }
  247 #endif
  248 
  249     /*
  250      * Initialize the node and insert as a leaf into the tree.
  251      */
  252     RB_SET_FATHER(self, parent);
  253     RB_SET_POSITION(self, position);
  254     if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
  255         RB_MARK_BLACK(self);        /* root is always black */
  256 #ifndef RBSMALL
  257         rbt->rbt_minmax[RB_DIR_LEFT] = self;
  258         rbt->rbt_minmax[RB_DIR_RIGHT] = self;
  259 #endif
  260         rebalance = false;
  261     } else {
  262         KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
  263 #ifndef RBSMALL
  264         /*
  265          * Keep track of the minimum and maximum nodes.  If our
  266          * parent is a minmax node and we on their min/max side,
  267          * we must be the new min/max node.
  268          */
  269         if (parent == rbt->rbt_minmax[position])
  270             rbt->rbt_minmax[position] = self;
  271 #endif /* !RBSMALL */
  272         /*
  273          * All new nodes are colored red.  We only need to rebalance
  274          * if our parent is also red.
  275          */
  276         RB_MARK_RED(self);
  277         rebalance = RB_RED_P(parent);
  278     }
  279     KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
  280     self->rb_left = parent->rb_nodes[position];
  281     self->rb_right = parent->rb_nodes[position];
  282     parent->rb_nodes[position] = self;
  283     KASSERT(RB_CHILDLESS_P(self));
  284 
  285     /*
  286      * Insert the new node into a sorted list for easy sequential access
  287      */
  288     RBSTAT_INC(rbt->rbt_count);
  289 #ifdef RBDEBUG
  290     if (RB_ROOT_P(rbt, self)) {
  291         RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
  292     } else if (position == RB_DIR_LEFT) {
  293         KASSERT((*compare_nodes)(rbto->rbto_context,
  294             RB_NODETOITEM(rbto, self),
  295             RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
  296         RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
  297     } else {
  298         KASSERT((*compare_nodes)(rbto->rbto_context,
  299             RB_NODETOITEM(rbto, RB_FATHER(self)),
  300             RB_NODETOITEM(rbto, self)) < 0);
  301         RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
  302             self, rb_link);
  303     }
  304 #endif
  305     KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
  306 
  307     /*
  308      * Rebalance tree after insertion
  309      */
  310     if (rebalance) {
  311         rb_tree_insert_rebalance(rbt, self);
  312         KASSERT(rb_tree_check_node(rbt, self, NULL, true));
  313     }
  314 
  315     /* Succesfully inserted, return our node pointer. */
  316     return object;
  317 }
  318 
  319 /*
  320  * Swap the location and colors of 'self' and its child @ which.  The child
  321  * can not be a sentinel node.  This is our rotation function.  However,
  322  * since it preserves coloring, it great simplifies both insertion and
  323  * removal since rotation almost always involves the exchanging of colors
  324  * as a separate step.
  325  */
  326 static void
  327 rb_tree_reparent_nodes(__rbt_unused struct rb_tree *rbt,
  328     struct rb_node *old_father, const unsigned int which)
  329 {
  330     const unsigned int other = which ^ RB_DIR_OTHER;
  331     struct rb_node * const grandpa = RB_FATHER(old_father);
  332     struct rb_node * const old_child = old_father->rb_nodes[which];
  333     struct rb_node * const new_father = old_child;
  334     struct rb_node * const new_child = old_father;
  335 
  336     KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
  337 
  338     KASSERT(!RB_SENTINEL_P(old_child));
  339     KASSERT(RB_FATHER(old_child) == old_father);
  340 
  341     KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
  342     KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
  343     KASSERT(RB_ROOT_P(rbt, old_father) ||
  344         rb_tree_check_node(rbt, grandpa, NULL, false));
  345 
  346     /*
  347      * Exchange descendant linkages.
  348      */
  349     grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
  350     new_child->rb_nodes[which] = old_child->rb_nodes[other];
  351     new_father->rb_nodes[other] = new_child;
  352 
  353     /*
  354      * Update ancestor linkages
  355      */
  356     RB_SET_FATHER(new_father, grandpa);
  357     RB_SET_FATHER(new_child, new_father);
  358 
  359     /*
  360      * Exchange properties between new_father and new_child.  The only
  361      * change is that new_child's position is now on the other side.
  362      */
  363 #if 0
  364     {
  365         struct rb_node tmp;
  366         tmp.rb_info = 0;
  367         RB_COPY_PROPERTIES(&tmp, old_child);
  368         RB_COPY_PROPERTIES(new_father, old_father);
  369         RB_COPY_PROPERTIES(new_child, &tmp);
  370     }
  371 #else
  372     RB_SWAP_PROPERTIES(new_father, new_child);
  373 #endif
  374     RB_SET_POSITION(new_child, other);
  375 
  376     /*
  377      * Make sure to reparent the new child to ourself.
  378      */
  379     if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
  380         RB_SET_FATHER(new_child->rb_nodes[which], new_child);
  381         RB_SET_POSITION(new_child->rb_nodes[which], which);
  382     }
  383 
  384     KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
  385     KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
  386     KASSERT(RB_ROOT_P(rbt, new_father) ||
  387         rb_tree_check_node(rbt, grandpa, NULL, false));
  388 }
  389 
  390 static void
  391 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
  392 {
  393     struct rb_node * father = RB_FATHER(self);
  394     struct rb_node * grandpa = RB_FATHER(father);
  395     struct rb_node * uncle;
  396     unsigned int which;
  397     unsigned int other;
  398 
  399     KASSERT(!RB_ROOT_P(rbt, self));
  400     KASSERT(RB_RED_P(self));
  401     KASSERT(RB_RED_P(father));
  402     RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);
  403 
  404     for (;;) {
  405         KASSERT(!RB_SENTINEL_P(self));
  406 
  407         KASSERT(RB_RED_P(self));
  408         KASSERT(RB_RED_P(father));
  409         /*
  410          * We are red and our parent is red, therefore we must have a
  411          * grandfather and he must be black.
  412          */
  413         grandpa = RB_FATHER(father);
  414         KASSERT(RB_BLACK_P(grandpa));
  415         KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
  416         which = (father == grandpa->rb_right);
  417         other = which ^ RB_DIR_OTHER;
  418         uncle = grandpa->rb_nodes[other];
  419 
  420         if (RB_BLACK_P(uncle))
  421             break;
  422 
  423         RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);
  424         /*
  425          * Case 1: our uncle is red
  426          *   Simply invert the colors of our parent and
  427          *   uncle and make our grandparent red.  And
  428          *   then solve the problem up at his level.
  429          */
  430         RB_MARK_BLACK(uncle);
  431         RB_MARK_BLACK(father);
  432         if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
  433             /*
  434              * If our grandpa is root, don't bother
  435              * setting him to red, just return.
  436              */
  437             KASSERT(RB_BLACK_P(grandpa));
  438             return;
  439         }
  440         RB_MARK_RED(grandpa);
  441         self = grandpa;
  442         father = RB_FATHER(self);
  443         KASSERT(RB_RED_P(self));
  444         if (RB_BLACK_P(father)) {
  445             /*
  446              * If our greatgrandpa is black, we're done.
  447              */
  448             KASSERT(RB_BLACK_P(rbt->rbt_root));
  449             return;
  450         }
  451     }
  452 
  453     KASSERT(!RB_ROOT_P(rbt, self));
  454     KASSERT(RB_RED_P(self));
  455     KASSERT(RB_RED_P(father));
  456     KASSERT(RB_BLACK_P(uncle));
  457     KASSERT(RB_BLACK_P(grandpa));
  458     /*
  459      * Case 2&3: our uncle is black.
  460      */
  461     if (self == father->rb_nodes[other]) {
  462         /*
  463          * Case 2: we are on the same side as our uncle
  464          *   Swap ourselves with our parent so this case
  465          *   becomes case 3.  Basically our parent becomes our
  466          *   child.
  467          */
  468         rb_tree_reparent_nodes(rbt, father, other);
  469         KASSERT(RB_FATHER(father) == self);
  470         KASSERT(self->rb_nodes[which] == father);
  471         KASSERT(RB_FATHER(self) == grandpa);
  472         self = father;
  473         father = RB_FATHER(self);
  474     }
  475     KASSERT(RB_RED_P(self) && RB_RED_P(father));
  476     KASSERT(grandpa->rb_nodes[which] == father);
  477     /*
  478      * Case 3: we are opposite a child of a black uncle.
  479      *   Swap our parent and grandparent.  Since our grandfather
  480      *   is black, our father will become black and our new sibling
  481      *   (former grandparent) will become red.
  482      */
  483     rb_tree_reparent_nodes(rbt, grandpa, which);
  484     KASSERT(RB_FATHER(self) == father);
  485     KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
  486     KASSERT(RB_RED_P(self));
  487     KASSERT(RB_BLACK_P(father));
  488     KASSERT(RB_RED_P(grandpa));
  489 
  490     /*
  491      * Final step: Set the root to black.
  492      */
  493     RB_MARK_BLACK(rbt->rbt_root);
  494 }
  495 
  496 static void
  497 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
  498 {
  499     const unsigned int which = RB_POSITION(self);
  500     struct rb_node *father = RB_FATHER(self);
  501 #ifndef RBSMALL
  502     const bool was_root = RB_ROOT_P(rbt, self);
  503 #endif
  504 
  505     KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
  506     KASSERT(!rebalance || RB_BLACK_P(self));
  507     KASSERT(RB_CHILDLESS_P(self));
  508     KASSERT(rb_tree_check_node(rbt, self, NULL, false));
  509 
  510     /*
  511      * Since we are childless, we know that self->rb_left is pointing
  512      * to the sentinel node.
  513      */
  514     father->rb_nodes[which] = self->rb_left;
  515 
  516     /*
  517      * Remove ourselves from the node list, decrement the count,
  518      * and update min/max.
  519      */
  520     RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
  521     RBSTAT_DEC(rbt->rbt_count);
  522 #ifndef RBSMALL
  523     if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
  524         rbt->rbt_minmax[RB_POSITION(self)] = father;
  525         /*
  526          * When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
  527          * updated automatically, but we also need to update 
  528          * rbt->rbt_minmax[RB_DIR_RIGHT];
  529          */
  530         if (__predict_false(was_root)) {
  531             rbt->rbt_minmax[RB_DIR_RIGHT] = father;
  532         }
  533     }
  534     RB_SET_FATHER(self, NULL);
  535 #endif
  536 
  537     /*
  538      * Rebalance if requested.
  539      */
  540     if (rebalance)
  541         rb_tree_removal_rebalance(rbt, father, which);
  542     KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
  543 }
  544 
  545 /*
  546  * When deleting an interior node
  547  */
  548 static void
  549 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
  550     struct rb_node *standin)
  551 {
  552     const unsigned int standin_which = RB_POSITION(standin);
  553     unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
  554     struct rb_node *standin_son;
  555     struct rb_node *standin_father = RB_FATHER(standin);
  556     bool rebalance = RB_BLACK_P(standin);
  557 
  558     if (standin_father == self) {
  559         /*
  560          * As a child of self, any childen would be opposite of
  561          * our parent.
  562          */
  563         KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
  564         standin_son = standin->rb_nodes[standin_which];
  565     } else {
  566         /*
  567          * Since we aren't a child of self, any childen would be
  568          * on the same side as our parent.
  569          */
  570         KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
  571         standin_son = standin->rb_nodes[standin_other];
  572     }
  573 
  574     /*
  575      * the node we are removing must have two children.
  576      */
  577     KASSERT(RB_TWOCHILDREN_P(self));
  578     /*
  579      * If standin has a child, it must be red.
  580      */
  581     KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
  582 
  583     /*
  584      * Verify things are sane.
  585      */
  586     KASSERT(rb_tree_check_node(rbt, self, NULL, false));
  587     KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
  588 
  589     if (__predict_false(RB_RED_P(standin_son))) {
  590         /*
  591          * We know we have a red child so if we flip it to black
  592          * we don't have to rebalance.
  593          */
  594         KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
  595         RB_MARK_BLACK(standin_son);
  596         rebalance = false;
  597 
  598         if (standin_father == self) {
  599             KASSERT(RB_POSITION(standin_son) == standin_which);
  600         } else {
  601             KASSERT(RB_POSITION(standin_son) == standin_other);
  602             /*
  603              * Change the son's parentage to point to his grandpa.
  604              */
  605             RB_SET_FATHER(standin_son, standin_father);
  606             RB_SET_POSITION(standin_son, standin_which);
  607         }
  608     }
  609 
  610     if (standin_father == self) {
  611         /*
  612          * If we are about to delete the standin's father, then when
  613          * we call rebalance, we need to use ourselves as our father.
  614          * Otherwise remember our original father.  Also, sincef we are
  615          * our standin's father we only need to reparent the standin's
  616          * brother.
  617          *
  618          * |    R      -->     S    |
  619          * |  Q   S    -->   Q   T  |
  620          * |        t  -->          |
  621          */
  622         KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
  623         KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
  624         KASSERT(self->rb_nodes[standin_which] == standin);
  625         /*
  626          * Have our son/standin adopt his brother as his new son.
  627          */
  628         standin_father = standin;
  629     } else {
  630         /*
  631          * |    R          -->    S       .  |
  632          * |   / \  |   T  -->   / \  |  /   |
  633          * |  ..... | S    -->  ..... | T    |
  634          *
  635          * Sever standin's connection to his father.
  636          */
  637         standin_father->rb_nodes[standin_which] = standin_son;
  638         /*
  639          * Adopt the far son.
  640          */
  641         standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
  642         RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
  643         KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
  644         /*
  645          * Use standin_other because we need to preserve standin_which
  646          * for the removal_rebalance.
  647          */
  648         standin_other = standin_which;
  649     }
  650 
  651     /*
  652      * Move the only remaining son to our standin.  If our standin is our
  653      * son, this will be the only son needed to be moved.
  654      */
  655     KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
  656     standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
  657     RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
  658 
  659     /*
  660      * Now copy the result of self to standin and then replace
  661      * self with standin in the tree.
  662      */
  663     RB_COPY_PROPERTIES(standin, self);
  664     RB_SET_FATHER(standin, RB_FATHER(self));
  665     RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
  666 
  667     /*
  668      * Remove ourselves from the node list, decrement the count,
  669      * and update min/max.
  670      */
  671     RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
  672     RBSTAT_DEC(rbt->rbt_count);
  673 #ifndef RBSMALL
  674     if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
  675         rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
  676     RB_SET_FATHER(self, NULL);
  677 #endif
  678 
  679     KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
  680     KASSERT(RB_FATHER_SENTINEL_P(standin)
  681         || rb_tree_check_node(rbt, standin_father, NULL, false));
  682     KASSERT(RB_LEFT_SENTINEL_P(standin)
  683         || rb_tree_check_node(rbt, standin->rb_left, NULL, false));
  684     KASSERT(RB_RIGHT_SENTINEL_P(standin)
  685         || rb_tree_check_node(rbt, standin->rb_right, NULL, false));
  686 
  687     if (!rebalance)
  688         return;
  689 
  690     rb_tree_removal_rebalance(rbt, standin_father, standin_which);
  691     KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
  692 }
  693 
  694 /*
  695  * We could do this by doing
  696  *  rb_tree_node_swap(rbt, self, which);
  697  *  rb_tree_prune_node(rbt, self, false);
  698  *
  699  * But it's more efficient to just evalate and recolor the child.
  700  */
  701 static void
  702 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
  703     unsigned int which)
  704 {
  705     struct rb_node *father = RB_FATHER(self);
  706     struct rb_node *son = self->rb_nodes[which];
  707 #ifndef RBSMALL
  708     const bool was_root = RB_ROOT_P(rbt, self);
  709 #endif
  710 
  711     KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
  712     KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
  713     KASSERT(!RB_TWOCHILDREN_P(son));
  714     KASSERT(RB_CHILDLESS_P(son));
  715     KASSERT(rb_tree_check_node(rbt, self, NULL, false));
  716     KASSERT(rb_tree_check_node(rbt, son, NULL, false));
  717 
  718     /*
  719      * Remove ourselves from the tree and give our former child our
  720      * properties (position, color, root).
  721      */
  722     RB_COPY_PROPERTIES(son, self);
  723     father->rb_nodes[RB_POSITION(son)] = son;
  724     RB_SET_FATHER(son, father);
  725 
  726     /*
  727      * Remove ourselves from the node list, decrement the count,
  728      * and update minmax.
  729      */
  730     RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
  731     RBSTAT_DEC(rbt->rbt_count);
  732 #ifndef RBSMALL
  733     if (__predict_false(was_root)) {
  734         KASSERT(rbt->rbt_minmax[which] == son);
  735         rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;
  736     } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
  737         rbt->rbt_minmax[RB_POSITION(self)] = son;
  738     }
  739     RB_SET_FATHER(self, NULL);
  740 #endif
  741 
  742     KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
  743     KASSERT(rb_tree_check_node(rbt, son, NULL, true));
  744 }
  745 
  746 void
  747 rb_tree_remove_node(struct rb_tree *rbt, void *object)
  748 {
  749     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  750     struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
  751     unsigned int which;
  752 
  753     KASSERT(!RB_SENTINEL_P(self));
  754     RBSTAT_INC(rbt->rbt_removals);
  755 
  756     /*
  757      * In the following diagrams, we (the node to be removed) are S.  Red
  758      * nodes are lowercase.  T could be either red or black.
  759      *
  760      * Remember the major axiom of the red-black tree: the number of
  761      * black nodes from the root to each leaf is constant across all
  762      * leaves, only the number of red nodes varies.
  763      *
  764      * Thus removing a red leaf doesn't require any other changes to a
  765      * red-black tree.  So if we must remove a node, attempt to rearrange
  766      * the tree so we can remove a red node.
  767      *
  768      * The simpliest case is a childless red node or a childless root node:
  769      *
  770      * |    T  -->    T  |    or    |  R  -->  *  |
  771      * |  s    -->  *    |
  772      */
  773     if (RB_CHILDLESS_P(self)) {
  774         const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
  775         rb_tree_prune_node(rbt, self, rebalance);
  776         return;
  777     }
  778     KASSERT(!RB_CHILDLESS_P(self));
  779     if (!RB_TWOCHILDREN_P(self)) {
  780         /*
  781          * The next simpliest case is the node we are deleting is
  782          * black and has one red child.
  783          *
  784          * |      T  -->      T  -->      T  |
  785          * |    S    -->  R      -->  R      |
  786          * |  r      -->    s    -->    *    |
  787          */
  788         which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
  789         KASSERT(RB_BLACK_P(self));
  790         KASSERT(RB_RED_P(self->rb_nodes[which]));
  791         KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
  792         rb_tree_prune_blackred_branch(rbt, self, which);
  793         return;
  794     }
  795     KASSERT(RB_TWOCHILDREN_P(self));
  796 
  797     /*
  798      * We invert these because we prefer to remove from the inside of
  799      * the tree.
  800      */
  801     which = RB_POSITION(self) ^ RB_DIR_OTHER;
  802 
  803     /*
  804      * Let's find the node closes to us opposite of our parent
  805      * Now swap it with ourself, "prune" it, and rebalance, if needed.
  806      */
  807     standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));
  808     rb_tree_swap_prune_and_rebalance(rbt, self, standin);
  809 }
  810 
  811 static void
  812 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
  813     unsigned int which)
  814 {
  815     KASSERT(!RB_SENTINEL_P(parent));
  816     KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
  817     KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
  818     RBSTAT_INC(rbt->rbt_removal_rebalance_calls);
  819 
  820     while (RB_BLACK_P(parent->rb_nodes[which])) {
  821         unsigned int other = which ^ RB_DIR_OTHER;
  822         struct rb_node *brother = parent->rb_nodes[other];
  823 
  824         RBSTAT_INC(rbt->rbt_removal_rebalance_passes);
  825 
  826         KASSERT(!RB_SENTINEL_P(brother));
  827         /*
  828          * For cases 1, 2a, and 2b, our brother's children must
  829          * be black and our father must be black
  830          */
  831         if (RB_BLACK_P(parent)
  832             && RB_BLACK_P(brother->rb_left)
  833             && RB_BLACK_P(brother->rb_right)) {
  834             if (RB_RED_P(brother)) {
  835                 /*
  836                  * Case 1: Our brother is red, swap its
  837                  * position (and colors) with our parent. 
  838                  * This should now be case 2b (unless C or E
  839                  * has a red child which is case 3; thus no
  840                  * explicit branch to case 2b).
  841                  *
  842                  *    B         ->        D
  843                  *  A     d     ->    b     E
  844                  *      C   E   ->  A   C
  845                  */
  846                 KASSERT(RB_BLACK_P(parent));
  847                 rb_tree_reparent_nodes(rbt, parent, other);
  848                 brother = parent->rb_nodes[other];
  849                 KASSERT(!RB_SENTINEL_P(brother));
  850                 KASSERT(RB_RED_P(parent));
  851                 KASSERT(RB_BLACK_P(brother));
  852                 KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
  853                 KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
  854             } else {
  855                 /*
  856                  * Both our parent and brother are black.
  857                  * Change our brother to red, advance up rank
  858                  * and go through the loop again.
  859                  *
  860                  *    B         ->   *B
  861                  * *A     D     ->  A     d
  862                  *      C   E   ->      C   E
  863                  */
  864                 RB_MARK_RED(brother);
  865                 KASSERT(RB_BLACK_P(brother->rb_left));
  866                 KASSERT(RB_BLACK_P(brother->rb_right));
  867                 if (RB_ROOT_P(rbt, parent))
  868                     return; /* root == parent == black */
  869                 KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
  870                 KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
  871                 which = RB_POSITION(parent);
  872                 parent = RB_FATHER(parent);
  873                 continue;
  874             }
  875         }
  876         /*
  877          * Avoid an else here so that case 2a above can hit either
  878          * case 2b, 3, or 4.
  879          */
  880         if (RB_RED_P(parent)
  881             && RB_BLACK_P(brother)
  882             && RB_BLACK_P(brother->rb_left)
  883             && RB_BLACK_P(brother->rb_right)) {
  884             KASSERT(RB_RED_P(parent));
  885             KASSERT(RB_BLACK_P(brother));
  886             KASSERT(RB_BLACK_P(brother->rb_left));
  887             KASSERT(RB_BLACK_P(brother->rb_right));
  888             /*
  889              * We are black, our father is red, our brother and
  890              * both nephews are black.  Simply invert/exchange the
  891              * colors of our father and brother (to black and red
  892              * respectively).
  893              *
  894              *  |    f        -->    F        |
  895              *  |  *     B    -->  *     b    |
  896              *  |      N   N  -->      N   N  |
  897              */
  898             RB_MARK_BLACK(parent);
  899             RB_MARK_RED(brother);
  900             KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
  901             break;      /* We're done! */
  902         } else {
  903             /*
  904              * Our brother must be black and have at least one
  905              * red child (it may have two).
  906              */
  907             KASSERT(RB_BLACK_P(brother));
  908             KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
  909                 RB_RED_P(brother->rb_nodes[other]));
  910             if (RB_BLACK_P(brother->rb_nodes[other])) {
  911                 /*
  912                  * Case 3: our brother is black, our near
  913                  * nephew is red, and our far nephew is black.
  914                  * Swap our brother with our near nephew.  
  915                  * This result in a tree that matches case 4.
  916                  * (Our father could be red or black).
  917                  *
  918                  *  |    F      -->    F      |
  919                  *  |  x     B  -->  x   B    |
  920                  *  |      n    -->        n  |
  921                  */
  922                 KASSERT(RB_RED_P(brother->rb_nodes[which]));
  923                 rb_tree_reparent_nodes(rbt, brother, which);
  924                 KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
  925                 brother = parent->rb_nodes[other];
  926                 KASSERT(RB_RED_P(brother->rb_nodes[other]));
  927             }
  928             /*
  929              * Case 4: our brother is black and our far nephew
  930              * is red.  Swap our father and brother locations and
  931              * change our far nephew to black.  (these can be
  932              * done in either order so we change the color first).
  933              * The result is a valid red-black tree and is a
  934              * terminal case.  (again we don't care about the
  935              * father's color)
  936              *
  937              * If the father is red, we will get a red-black-black
  938              * tree:
  939              *  |  f      ->  f      -->    b    |
  940              *  |    B    ->    B    -->  F   N  |
  941              *  |      n  ->      N  -->         |
  942              *
  943              * If the father is black, we will get an all black
  944              * tree:
  945              *  |  F      ->  F      -->    B    |
  946              *  |    B    ->    B    -->  F   N  |
  947              *  |      n  ->      N  -->         |
  948              *
  949              * If we had two red nephews, then after the swap,
  950              * our former father would have a red grandson. 
  951              */
  952             KASSERT(RB_BLACK_P(brother));
  953             KASSERT(RB_RED_P(brother->rb_nodes[other]));
  954             RB_MARK_BLACK(brother->rb_nodes[other]);
  955             rb_tree_reparent_nodes(rbt, parent, other);
  956             break;      /* We're done! */
  957         }
  958     }
  959     KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
  960 }
  961 
  962 void *
  963 rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)
  964 {
  965     const rb_tree_ops_t *rbto = rbt->rbt_ops;
  966     const unsigned int other = direction ^ RB_DIR_OTHER;
  967     struct rb_node *self;
  968 
  969     KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
  970 
  971     if (object == NULL) {
  972 #ifndef RBSMALL
  973         if (RB_SENTINEL_P(rbt->rbt_root))
  974             return NULL;
  975         return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
  976 #else
  977         self = rbt->rbt_root;
  978         if (RB_SENTINEL_P(self))
  979             return NULL;
  980         while (!RB_SENTINEL_P(self->rb_nodes[direction]))
  981             self = self->rb_nodes[direction];
  982         return RB_NODETOITEM(rbto, self);
  983 #endif /* !RBSMALL */
  984     }
  985     self = RB_ITEMTONODE(rbto, object);
  986     KASSERT(!RB_SENTINEL_P(self));
  987     /*
  988      * We can't go any further in this direction.  We proceed up in the
  989      * opposite direction until our parent is in direction we want to go.
  990      */
  991     if (RB_SENTINEL_P(self->rb_nodes[direction])) {
  992         while (!RB_ROOT_P(rbt, self)) {
  993             if (other == RB_POSITION(self))
  994                 return RB_NODETOITEM(rbto, RB_FATHER(self));
  995             self = RB_FATHER(self);
  996         }
  997         return NULL;
  998     }
  999 
 1000     /*
 1001      * Advance down one in current direction and go down as far as possible
 1002      * in the opposite direction.
 1003      */
 1004     self = self->rb_nodes[direction];
 1005     KASSERT(!RB_SENTINEL_P(self));
 1006     while (!RB_SENTINEL_P(self->rb_nodes[other]))
 1007         self = self->rb_nodes[other];
 1008     return RB_NODETOITEM(rbto, self);
 1009 }
 1010 
 1011 #ifdef RBDEBUG
 1012 static const struct rb_node *
 1013 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
 1014     const unsigned int direction)
 1015 {
 1016     const unsigned int other = direction ^ RB_DIR_OTHER;
 1017     KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
 1018 
 1019     if (self == NULL) {
 1020 #ifndef RBSMALL
 1021         if (RB_SENTINEL_P(rbt->rbt_root))
 1022             return NULL;
 1023         return rbt->rbt_minmax[direction];
 1024 #else
 1025         self = rbt->rbt_root;
 1026         if (RB_SENTINEL_P(self))
 1027             return NULL;
 1028         while (!RB_SENTINEL_P(self->rb_nodes[direction]))
 1029             self = self->rb_nodes[direction];
 1030         return self;
 1031 #endif /* !RBSMALL */
 1032     }
 1033     KASSERT(!RB_SENTINEL_P(self));
 1034     /*
 1035      * We can't go any further in this direction.  We proceed up in the
 1036      * opposite direction until our parent is in direction we want to go.
 1037      */
 1038     if (RB_SENTINEL_P(self->rb_nodes[direction])) {
 1039         while (!RB_ROOT_P(rbt, self)) {
 1040             if (other == RB_POSITION(self))
 1041                 return RB_FATHER(self);
 1042             self = RB_FATHER(self);
 1043         }
 1044         return NULL;
 1045     }
 1046 
 1047     /*
 1048      * Advance down one in current direction and go down as far as possible
 1049      * in the opposite direction.
 1050      */
 1051     self = self->rb_nodes[direction];
 1052     KASSERT(!RB_SENTINEL_P(self));
 1053     while (!RB_SENTINEL_P(self->rb_nodes[other]))
 1054         self = self->rb_nodes[other];
 1055     return self;
 1056 }
 1057 
 1058 static unsigned int
 1059 rb_tree_count_black(const struct rb_node *self)
 1060 {
 1061     unsigned int left, right;
 1062 
 1063     if (RB_SENTINEL_P(self))
 1064         return 0;
 1065 
 1066     left = rb_tree_count_black(self->rb_left);
 1067     right = rb_tree_count_black(self->rb_right);
 1068 
 1069     KASSERT(left == right);
 1070 
 1071     return left + RB_BLACK_P(self);
 1072 }
 1073 
 1074 static bool
 1075 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
 1076     const struct rb_node *prev, bool red_check)
 1077 {
 1078     const rb_tree_ops_t *rbto = rbt->rbt_ops;
 1079     rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
 1080 
 1081     KASSERT(!RB_SENTINEL_P(self));
 1082     KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
 1083         RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
 1084 
 1085     /*
 1086      * Verify our relationship to our parent.
 1087      */
 1088     if (RB_ROOT_P(rbt, self)) {
 1089         KASSERT(self == rbt->rbt_root);
 1090         KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
 1091         KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
 1092         KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
 1093     } else {
 1094         int diff = (*compare_nodes)(rbto->rbto_context,
 1095             RB_NODETOITEM(rbto, self),
 1096             RB_NODETOITEM(rbto, RB_FATHER(self)));
 1097 
 1098         KASSERT(self != rbt->rbt_root);
 1099         KASSERT(!RB_FATHER_SENTINEL_P(self));
 1100         if (RB_POSITION(self) == RB_DIR_LEFT) {
 1101             KASSERT(diff < 0);
 1102             KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
 1103         } else {
 1104             KASSERT(diff > 0);
 1105             KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
 1106         }
 1107     }
 1108 
 1109     /*
 1110      * Verify our position in the linked list against the tree itself.
 1111      */
 1112     {
 1113         const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
 1114         const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
 1115         KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
 1116         KASSERT(next0 == TAILQ_NEXT(self, rb_link));
 1117 #ifndef RBSMALL
 1118         KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
 1119         KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
 1120 #endif
 1121     }
 1122 
 1123     /*
 1124      * The root must be black.
 1125      * There can never be two adjacent red nodes. 
 1126      */
 1127     if (red_check) {
 1128         KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
 1129         (void) rb_tree_count_black(self);
 1130         if (RB_RED_P(self)) {
 1131             const struct rb_node *brother;
 1132             KASSERT(!RB_ROOT_P(rbt, self));
 1133             brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
 1134             KASSERT(RB_BLACK_P(RB_FATHER(self)));
 1135             /* 
 1136              * I'm red and have no children, then I must either
 1137              * have no brother or my brother also be red and
 1138              * also have no children.  (black count == 0)
 1139              */
 1140             KASSERT(!RB_CHILDLESS_P(self)
 1141                 || RB_SENTINEL_P(brother)
 1142                 || RB_RED_P(brother)
 1143                 || RB_CHILDLESS_P(brother));
 1144             /*
 1145              * If I'm not childless, I must have two children
 1146              * and they must be both be black.
 1147              */
 1148             KASSERT(RB_CHILDLESS_P(self)
 1149                 || (RB_TWOCHILDREN_P(self)
 1150                     && RB_BLACK_P(self->rb_left)
 1151                     && RB_BLACK_P(self->rb_right)));
 1152             /*
 1153              * If I'm not childless, thus I have black children,
 1154              * then my brother must either be black or have two
 1155              * black children.
 1156              */
 1157             KASSERT(RB_CHILDLESS_P(self)
 1158                 || RB_BLACK_P(brother)
 1159                 || (RB_TWOCHILDREN_P(brother)
 1160                     && RB_BLACK_P(brother->rb_left)
 1161                     && RB_BLACK_P(brother->rb_right)));
 1162         } else {
 1163             /*
 1164              * If I'm black and have one child, that child must
 1165              * be red and childless.
 1166              */
 1167             KASSERT(RB_CHILDLESS_P(self)
 1168                 || RB_TWOCHILDREN_P(self)
 1169                 || (!RB_LEFT_SENTINEL_P(self)
 1170                     && RB_RIGHT_SENTINEL_P(self)
 1171                     && RB_RED_P(self->rb_left)
 1172                     && RB_CHILDLESS_P(self->rb_left))
 1173                 || (!RB_RIGHT_SENTINEL_P(self)
 1174                     && RB_LEFT_SENTINEL_P(self)
 1175                     && RB_RED_P(self->rb_right)
 1176                     && RB_CHILDLESS_P(self->rb_right)));
 1177 
 1178             /*
 1179              * If I'm a childless black node and my parent is
 1180              * black, my 2nd closet relative away from my parent
 1181              * is either red or has a red parent or red children.
 1182              */
 1183             if (!RB_ROOT_P(rbt, self)
 1184                 && RB_CHILDLESS_P(self)
 1185                 && RB_BLACK_P(RB_FATHER(self))) {
 1186                 const unsigned int which = RB_POSITION(self);
 1187                 const unsigned int other = which ^ RB_DIR_OTHER;
 1188                 const struct rb_node *relative0, *relative;
 1189 
 1190                 relative0 = rb_tree_iterate_const(rbt,
 1191                     self, other);
 1192                 KASSERT(relative0 != NULL);
 1193                 relative = rb_tree_iterate_const(rbt,
 1194                     relative0, other);
 1195                 KASSERT(relative != NULL);
 1196                 KASSERT(RB_SENTINEL_P(relative->rb_nodes[which]));
 1197 #if 0
 1198                 KASSERT(RB_RED_P(relative)
 1199                     || RB_RED_P(relative->rb_left)
 1200                     || RB_RED_P(relative->rb_right)
 1201                     || RB_RED_P(RB_FATHER(relative)));
 1202 #endif
 1203             }
 1204         }
 1205         /*
 1206          * A grandparent's children must be real nodes and not
 1207          * sentinels.  First check out grandparent.
 1208          */
 1209         KASSERT(RB_ROOT_P(rbt, self)
 1210             || RB_ROOT_P(rbt, RB_FATHER(self))
 1211             || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
 1212         /*
 1213          * If we are have grandchildren on our left, then
 1214          * we must have a child on our right.
 1215          */
 1216         KASSERT(RB_LEFT_SENTINEL_P(self)
 1217             || RB_CHILDLESS_P(self->rb_left)
 1218             || !RB_RIGHT_SENTINEL_P(self));
 1219         /*
 1220          * If we are have grandchildren on our right, then
 1221          * we must have a child on our left.
 1222          */
 1223         KASSERT(RB_RIGHT_SENTINEL_P(self)
 1224             || RB_CHILDLESS_P(self->rb_right)
 1225             || !RB_LEFT_SENTINEL_P(self));
 1226 
 1227         /*
 1228          * If we have a child on the left and it doesn't have two
 1229          * children make sure we don't have great-great-grandchildren on
 1230          * the right.
 1231          */
 1232         KASSERT(RB_TWOCHILDREN_P(self->rb_left)
 1233             || RB_CHILDLESS_P(self->rb_right)
 1234             || RB_CHILDLESS_P(self->rb_right->rb_left)
 1235             || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
 1236             || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
 1237             || RB_CHILDLESS_P(self->rb_right->rb_right)
 1238             || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
 1239             || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
 1240 
 1241         /*
 1242          * If we have a child on the right and it doesn't have two
 1243          * children make sure we don't have great-great-grandchildren on
 1244          * the left.
 1245          */
 1246         KASSERT(RB_TWOCHILDREN_P(self->rb_right)
 1247             || RB_CHILDLESS_P(self->rb_left)
 1248             || RB_CHILDLESS_P(self->rb_left->rb_left)
 1249             || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
 1250             || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
 1251             || RB_CHILDLESS_P(self->rb_left->rb_right)
 1252             || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
 1253             || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
 1254 
 1255         /*
 1256          * If we are fully interior node, then our predecessors and
 1257          * successors must have no children in our direction.
 1258          */
 1259         if (RB_TWOCHILDREN_P(self)) {
 1260             const struct rb_node *prev0;
 1261             const struct rb_node *next0;
 1262 
 1263             prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
 1264             KASSERT(prev0 != NULL);
 1265             KASSERT(RB_RIGHT_SENTINEL_P(prev0));
 1266 
 1267             next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
 1268             KASSERT(next0 != NULL);
 1269             KASSERT(RB_LEFT_SENTINEL_P(next0));
 1270         }
 1271     }
 1272 
 1273     return true;
 1274 }
 1275 
 1276 void
 1277 rb_tree_check(const struct rb_tree *rbt, bool red_check)
 1278 {
 1279     const struct rb_node *self;
 1280     const struct rb_node *prev;
 1281 #ifdef RBSTATS
 1282     unsigned int count = 0;
 1283 #endif
 1284 
 1285     KASSERT(rbt->rbt_root != NULL);
 1286     KASSERT(RB_LEFT_P(rbt->rbt_root));
 1287 
 1288 #if defined(RBSTATS) && !defined(RBSMALL)
 1289     KASSERT(rbt->rbt_count > 1
 1290         || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);
 1291 #endif
 1292 
 1293     prev = NULL;
 1294     TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
 1295         rb_tree_check_node(rbt, self, prev, false);
 1296 #ifdef RBSTATS
 1297         count++;
 1298 #endif
 1299     }
 1300 #ifdef RBSTATS
 1301     KASSERT(rbt->rbt_count == count);
 1302 #endif
 1303     if (red_check) {
 1304         KASSERT(RB_BLACK_P(rbt->rbt_root));
 1305         KASSERT(RB_SENTINEL_P(rbt->rbt_root)
 1306             || rb_tree_count_black(rbt->rbt_root));
 1307 
 1308         /*
 1309          * The root must be black.
 1310          * There can never be two adjacent red nodes. 
 1311          */
 1312         TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
 1313             rb_tree_check_node(rbt, self, NULL, true);
 1314         }
 1315     }
 1316 }
 1317 #endif /* RBDEBUG */
 1318 
 1319 #ifdef RBSTATS
 1320 static void
 1321 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
 1322     size_t *depths, size_t depth)
 1323 {
 1324     if (RB_SENTINEL_P(self))
 1325         return;
 1326 
 1327     if (RB_TWOCHILDREN_P(self)) {
 1328         rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
 1329         rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
 1330         return;
 1331     }
 1332     depths[depth]++;
 1333     if (!RB_LEFT_SENTINEL_P(self)) {
 1334         rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
 1335     }
 1336     if (!RB_RIGHT_SENTINEL_P(self)) {
 1337         rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
 1338     }
 1339 }
 1340 
 1341 void
 1342 rb_tree_depths(const struct rb_tree *rbt, size_t *depths)
 1343 {
 1344     rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);
 1345 }
 1346 #endif /* RBSTATS */