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