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