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