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