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