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