The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libprop/prop_rb.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 655ef5906d233eadeec77062a93904de


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.