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