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