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