contrib/dhcpcd/compat/rb.c

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