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