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