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