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