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