sys/libprop/prop_rb.c

   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 */