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