1 /* $NetBSD: rb.c,v 1.4 2009/05/19 22:48:19 yamt Exp $ */
4 * Copyright (c) 2001 The NetBSD Foundation, Inc.
7 * Portions Copyright (c) 2009 Apple Inc. All rights reserved.
9 * This code is derived from software contributed to The NetBSD Foundation
10 * by Matt Thomas <matt@3am-software.com>.
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
21 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
23 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
25 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
34 #if !defined(_KERNEL) && !defined(_STANDALONE)
35 #include <sys/types.h>
40 #define KASSERT(s) assert(s)
42 #define KASSERT(s) do { } while (/*CONSTCOND*/ 0)
45 #include <lib/libkern/libkern.h>
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
)
57 __weak_alias(rb_tree_check
, _rb_tree_check
)
58 __weak_alias(rb_tree_depths
, _rb_tree_depths
)
61 #define rb_tree_init _rb_tree_init
62 #define rb_tree_find_node _rb_tree_find_node
63 #define rb_tree_find_node_geq _rb_tree_find_node_geq
64 #define rb_tree_find_node_leq _rb_tree_find_node_leq
65 #define rb_tree_insert_node _rb_tree_insert_node
66 #define rb_tree_remove_node _rb_tree_remove_node
67 #define rb_tree_iterate _rb_tree_iterate
69 #define rb_tree_check _rb_tree_check
70 #define rb_tree_depths _rb_tree_depths
74 #if defined(RBTEST) || defined(__APPLE__)
81 #define __predict_true(exp) __builtin_expect((exp), 1)
82 #define __predict_false(exp) __builtin_expect((exp), 0)
85 static void rb_tree_insert_rebalance(struct rb_tree
*, struct rb_node
*);
86 static void rb_tree_removal_rebalance(struct rb_tree
*, struct rb_node
*,
89 static const struct rb_node
*rb_tree_iterate_const(const struct rb_tree
*,
90 const struct rb_node
*, const unsigned int);
91 static bool rb_tree_check_node(const struct rb_tree
*, const struct rb_node
*,
92 const struct rb_node
*, bool);
94 #define rb_tree_check_node(a, b, c, d) true
97 #define RB_SENTINEL_NODE NULL
100 rb_tree_init(struct rb_tree
*rbt
, const struct rb_tree_ops
*ops
)
103 *((const struct rb_node
**)&rbt
->rbt_root
) = RB_SENTINEL_NODE
;
104 RB_TAILQ_INIT(&rbt
->rbt_nodes
);
106 rbt
->rbt_minmax
[RB_DIR_LEFT
] = rbt
->rbt_root
; /* minimum node */
107 rbt
->rbt_minmax
[RB_DIR_RIGHT
] = rbt
->rbt_root
; /* maximum node */
111 rbt
->rbt_insertions
= 0;
112 rbt
->rbt_removals
= 0;
113 rbt
->rbt_insertion_rebalance_calls
= 0;
114 rbt
->rbt_insertion_rebalance_passes
= 0;
115 rbt
->rbt_removal_rebalance_calls
= 0;
116 rbt
->rbt_removal_rebalance_passes
= 0;
121 rb_tree_find_node(struct rb_tree
*rbt
, const void *key
)
123 rbto_compare_key_fn compare_key
= rbt
->rbt_ops
->rbto_compare_key
;
124 struct rb_node
*parent
= rbt
->rbt_root
;
126 while (!RB_SENTINEL_P(parent
)) {
127 const signed int diff
= (*compare_key
)(parent
, key
);
130 parent
= parent
->rb_nodes
[diff
> 0];
137 rb_tree_find_node_geq(struct rb_tree
*rbt
, const void *key
)
139 rbto_compare_key_fn compare_key
= rbt
->rbt_ops
->rbto_compare_key
;
140 struct rb_node
*parent
= rbt
->rbt_root
;
141 struct rb_node
*last
= NULL
;
143 while (!RB_SENTINEL_P(parent
)) {
144 const signed int diff
= (*compare_key
)(parent
, key
);
149 parent
= parent
->rb_nodes
[diff
> 0];
156 rb_tree_find_node_leq(struct rb_tree
*rbt
, const void *key
)
158 rbto_compare_key_fn compare_key
= rbt
->rbt_ops
->rbto_compare_key
;
159 struct rb_node
*parent
= rbt
->rbt_root
;
160 struct rb_node
*last
= NULL
;
162 while (!RB_SENTINEL_P(parent
)) {
163 const signed int diff
= (*compare_key
)(parent
, key
);
168 parent
= parent
->rb_nodes
[diff
> 0];
175 rb_tree_insert_node(struct rb_tree
*rbt
, struct rb_node
*self
)
177 rbto_compare_nodes_fn compare_nodes
= rbt
->rbt_ops
->rbto_compare_nodes
;
178 struct rb_node
*parent
, *tmp
;
179 unsigned int position
;
182 RBSTAT_INC(rbt
->rbt_insertions
);
186 * This is a hack. Because rbt->rbt_root is just a struct rb_node *,
187 * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
188 * avoid a lot of tests for root and know that even at root,
189 * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
190 * update rbt->rbt_root.
192 parent
= (struct rb_node
*)(void *)&rbt
->rbt_root
;
193 position
= RB_DIR_LEFT
;
196 * Find out where to place this new leaf.
198 while (!RB_SENTINEL_P(tmp
)) {
199 const signed int diff
= (*compare_nodes
)(tmp
, self
);
200 if (__predict_false(diff
== 0)) {
202 * Node already exists; don't insert.
207 position
= (diff
> 0);
208 tmp
= parent
->rb_nodes
[position
];
213 struct rb_node
*prev
= NULL
, *next
= NULL
;
215 if (position
== RB_DIR_RIGHT
)
217 else if (tmp
!= rbt
->rbt_root
)
221 * Verify our sequential position
223 KASSERT(prev
== NULL
|| !RB_SENTINEL_P(prev
));
224 KASSERT(next
== NULL
|| !RB_SENTINEL_P(next
));
225 if (prev
!= NULL
&& next
== NULL
)
226 next
= TAILQ_NEXT(prev
, rb_link
);
227 if (prev
== NULL
&& next
!= NULL
)
228 prev
= TAILQ_PREV(next
, rb_node_qh
, rb_link
);
229 KASSERT(prev
== NULL
|| !RB_SENTINEL_P(prev
));
230 KASSERT(next
== NULL
|| !RB_SENTINEL_P(next
));
231 KASSERT(prev
== NULL
|| (*compare_nodes
)(prev
, self
) > 0);
232 KASSERT(next
== NULL
|| (*compare_nodes
)(self
, next
) > 0);
237 * Initialize the node and insert as a leaf into the tree.
239 RB_SET_FATHER(self
, parent
);
240 RB_SET_POSITION(self
, position
);
241 if (__predict_false(parent
== (struct rb_node
*)(void *)&rbt
->rbt_root
)) {
242 RB_MARK_BLACK(self
); /* root is always black */
244 rbt
->rbt_minmax
[RB_DIR_LEFT
] = self
;
245 rbt
->rbt_minmax
[RB_DIR_RIGHT
] = self
;
249 KASSERT(position
== RB_DIR_LEFT
|| position
== RB_DIR_RIGHT
);
252 * Keep track of the minimum and maximum nodes. If our
253 * parent is a minmax node and we on their min/max side,
254 * we must be the new min/max node.
256 if (parent
== rbt
->rbt_minmax
[position
])
257 rbt
->rbt_minmax
[position
] = self
;
258 #endif /* !RBSMALL */
260 * All new nodes are colored red. We only need to rebalance
261 * if our parent is also red.
264 rebalance
= RB_RED_P(parent
);
266 KASSERT(RB_SENTINEL_P(parent
->rb_nodes
[position
]));
267 self
->rb_left
= parent
->rb_nodes
[position
];
268 self
->rb_right
= parent
->rb_nodes
[position
];
269 parent
->rb_nodes
[position
] = self
;
270 KASSERT(RB_CHILDLESS_P(self
));
273 * Insert the new node into a sorted list for easy sequential access
277 if (RB_ROOT_P(rbt
, self
)) {
278 RB_TAILQ_INSERT_HEAD(&rbt
->rbt_nodes
, self
, rb_link
);
279 } else if (position
== RB_DIR_LEFT
) {
280 KASSERT((*compare_nodes
)(self
, RB_FATHER(self
)) > 0);
281 RB_TAILQ_INSERT_BEFORE(RB_FATHER(self
), self
, rb_link
);
283 KASSERT((*compare_nodes
)(RB_FATHER(self
), self
) > 0);
284 RB_TAILQ_INSERT_AFTER(&rbt
->rbt_nodes
, RB_FATHER(self
),
288 KASSERT(rb_tree_check_node(rbt
, self
, NULL
, !rebalance
));
291 * Rebalance tree after insertion
294 rb_tree_insert_rebalance(rbt
, self
);
295 KASSERT(rb_tree_check_node(rbt
, self
, NULL
, true));
302 * Swap the location and colors of 'self' and its child @ which. The child
303 * can not be a sentinel node. This is our rotation function. However,
304 * since it preserves coloring, it great simplifies both insertion and
305 * removal since rotation almost always involves the exchanging of colors
306 * as a separate step.
310 rb_tree_reparent_nodes(struct rb_tree
*rbt
, struct rb_node
*old_father
,
311 const unsigned int which
)
313 const unsigned int other
= which
^ RB_DIR_OTHER
;
314 struct rb_node
* const grandpa
= RB_FATHER(old_father
);
315 struct rb_node
* const old_child
= old_father
->rb_nodes
[which
];
316 struct rb_node
* const new_father
= old_child
;
317 struct rb_node
* const new_child
= old_father
;
319 KASSERT(which
== RB_DIR_LEFT
|| which
== RB_DIR_RIGHT
);
321 KASSERT(!RB_SENTINEL_P(old_child
));
322 KASSERT(RB_FATHER(old_child
) == old_father
);
324 KASSERT(rb_tree_check_node(rbt
, old_father
, NULL
, false));
325 KASSERT(rb_tree_check_node(rbt
, old_child
, NULL
, false));
326 KASSERT(RB_ROOT_P(rbt
, old_father
) || rb_tree_check_node(rbt
, grandpa
, NULL
, false));
329 * Exchange descendant linkages.
331 grandpa
->rb_nodes
[RB_POSITION(old_father
)] = new_father
;
332 new_child
->rb_nodes
[which
] = old_child
->rb_nodes
[other
];
333 new_father
->rb_nodes
[other
] = new_child
;
336 * Update ancestor linkages
338 RB_SET_FATHER(new_father
, grandpa
);
339 RB_SET_FATHER(new_child
, new_father
);
342 * Exchange properties between new_father and new_child. The only
343 * change is that new_child's position is now on the other side.
349 RB_COPY_PROPERTIES(&tmp
, old_child
);
350 RB_COPY_PROPERTIES(new_father
, old_father
);
351 RB_COPY_PROPERTIES(new_child
, &tmp
);
354 RB_SWAP_PROPERTIES(new_father
, new_child
);
356 RB_SET_POSITION(new_child
, other
);
359 * Make sure to reparent the new child to ourself.
361 if (!RB_SENTINEL_P(new_child
->rb_nodes
[which
])) {
362 RB_SET_FATHER(new_child
->rb_nodes
[which
], new_child
);
363 RB_SET_POSITION(new_child
->rb_nodes
[which
], which
);
366 KASSERT(rb_tree_check_node(rbt
, new_father
, NULL
, false));
367 KASSERT(rb_tree_check_node(rbt
, new_child
, NULL
, false));
368 KASSERT(RB_ROOT_P(rbt
, new_father
) || rb_tree_check_node(rbt
, grandpa
, NULL
, false));
372 rb_tree_insert_rebalance(struct rb_tree
*rbt
, struct rb_node
*self
)
374 struct rb_node
* father
= RB_FATHER(self
);
375 struct rb_node
* grandpa
;
376 struct rb_node
* uncle
;
380 KASSERT(!RB_ROOT_P(rbt
, self
));
381 KASSERT(RB_RED_P(self
));
382 KASSERT(RB_RED_P(father
));
383 RBSTAT_INC(rbt
->rbt_insertion_rebalance_calls
);
386 KASSERT(!RB_SENTINEL_P(self
));
388 KASSERT(RB_RED_P(self
));
389 KASSERT(RB_RED_P(father
));
391 * We are red and our parent is red, therefore we must have a
392 * grandfather and he must be black.
394 grandpa
= RB_FATHER(father
);
395 KASSERT(RB_BLACK_P(grandpa
));
396 KASSERT(RB_DIR_RIGHT
== 1 && RB_DIR_LEFT
== 0);
397 which
= (father
== grandpa
->rb_right
);
398 other
= which
^ RB_DIR_OTHER
;
399 uncle
= grandpa
->rb_nodes
[other
];
401 if (RB_BLACK_P(uncle
))
404 RBSTAT_INC(rbt
->rbt_insertion_rebalance_passes
);
406 * Case 1: our uncle is red
407 * Simply invert the colors of our parent and
408 * uncle and make our grandparent red. And
409 * then solve the problem up at his level.
411 RB_MARK_BLACK(uncle
);
412 RB_MARK_BLACK(father
);
413 if (__predict_false(RB_ROOT_P(rbt
, grandpa
))) {
415 * If our grandpa is root, don't bother
416 * setting him to red, just return.
418 KASSERT(RB_BLACK_P(grandpa
));
421 RB_MARK_RED(grandpa
);
423 father
= RB_FATHER(self
);
424 KASSERT(RB_RED_P(self
));
425 if (RB_BLACK_P(father
)) {
427 * If our greatgrandpa is black, we're done.
429 KASSERT(RB_BLACK_P(rbt
->rbt_root
));
434 KASSERT(!RB_ROOT_P(rbt
, self
));
435 KASSERT(RB_RED_P(self
));
436 KASSERT(RB_RED_P(father
));
437 KASSERT(RB_BLACK_P(uncle
));
438 KASSERT(RB_BLACK_P(grandpa
));
440 * Case 2&3: our uncle is black.
442 if (self
== father
->rb_nodes
[other
]) {
444 * Case 2: we are on the same side as our uncle
445 * Swap ourselves with our parent so this case
446 * becomes case 3. Basically our parent becomes our
449 rb_tree_reparent_nodes(rbt
, father
, other
);
450 KASSERT(RB_FATHER(father
) == self
);
451 KASSERT(self
->rb_nodes
[which
] == father
);
452 KASSERT(RB_FATHER(self
) == grandpa
);
454 // only read when RBDEBUG is enabled with KASSERT
456 father
= RB_FATHER(self
);
459 KASSERT(RB_RED_P(self
) && RB_RED_P(father
));
460 KASSERT(grandpa
->rb_nodes
[which
] == father
);
462 * Case 3: we are opposite a child of a black uncle.
463 * Swap our parent and grandparent. Since our grandfather
464 * is black, our father will become black and our new sibling
465 * (former grandparent) will become red.
467 rb_tree_reparent_nodes(rbt
, grandpa
, which
);
468 KASSERT(RB_FATHER(self
) == father
);
469 KASSERT(RB_FATHER(self
)->rb_nodes
[RB_POSITION(self
) ^ RB_DIR_OTHER
] == grandpa
);
470 KASSERT(RB_RED_P(self
));
471 KASSERT(RB_BLACK_P(father
));
472 KASSERT(RB_RED_P(grandpa
));
475 * Final step: Set the root to black.
477 RB_MARK_BLACK(rbt
->rbt_root
);
481 rb_tree_prune_node(struct rb_tree
*rbt
, struct rb_node
*self
, bool rebalance
)
483 const unsigned int which
= RB_POSITION(self
);
484 struct rb_node
*father
= RB_FATHER(self
);
485 const bool was_root
= RB_ROOT_P(rbt
, self
);
487 KASSERT(rebalance
|| (RB_ROOT_P(rbt
, self
) || RB_RED_P(self
)));
488 KASSERT(!rebalance
|| RB_BLACK_P(self
));
489 KASSERT(RB_CHILDLESS_P(self
));
490 KASSERT(rb_tree_check_node(rbt
, self
, NULL
, false));
493 * Since we are childless, we know that self->rb_left is pointing
494 * to the sentinel node.
496 father
->rb_nodes
[which
] = self
->rb_left
;
499 * Remove ourselves from the node list, decrement the count,
500 * and update min/max.
502 RB_TAILQ_REMOVE(&rbt
->rbt_nodes
, self
, rb_link
);
505 if (__predict_false(rbt
->rbt_minmax
[RB_POSITION(self
)] == self
)) {
506 rbt
->rbt_minmax
[RB_POSITION(self
)] = father
;
508 * When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
509 * updated automatically, but we also need to update
510 * rbt->rbt_minmax[RB_DIR_RIGHT];
512 if (__predict_false(was_root
)) {
513 rbt
->rbt_minmax
[RB_DIR_RIGHT
] = father
;
516 RB_SET_FATHER(self
, NULL
);
520 * Rebalance if requested.
523 rb_tree_removal_rebalance(rbt
, father
, which
);
524 KASSERT(was_root
|| rb_tree_check_node(rbt
, father
, NULL
, true));
528 * When deleting an interior node
531 rb_tree_swap_prune_and_rebalance(struct rb_tree
*rbt
, struct rb_node
*self
,
532 struct rb_node
*standin
)
534 const unsigned int standin_which
= RB_POSITION(standin
);
535 unsigned int standin_other
= standin_which
^ RB_DIR_OTHER
;
536 struct rb_node
*standin_son
;
537 struct rb_node
*standin_father
= RB_FATHER(standin
);
538 bool rebalance
= RB_BLACK_P(standin
);
540 if (standin_father
== self
) {
542 * As a child of self, any childen would be opposite of
545 KASSERT(RB_SENTINEL_P(standin
->rb_nodes
[standin_other
]));
546 standin_son
= standin
->rb_nodes
[standin_which
];
549 * Since we aren't a child of self, any childen would be
550 * on the same side as our parent.
552 KASSERT(RB_SENTINEL_P(standin
->rb_nodes
[standin_which
]));
553 standin_son
= standin
->rb_nodes
[standin_other
];
557 * the node we are removing must have two children.
559 KASSERT(RB_TWOCHILDREN_P(self
));
561 * If standin has a child, it must be red.
563 KASSERT(RB_SENTINEL_P(standin_son
) || RB_RED_P(standin_son
));
566 * Verify things are sane.
568 KASSERT(rb_tree_check_node(rbt
, self
, NULL
, false));
569 KASSERT(rb_tree_check_node(rbt
, standin
, NULL
, false));
571 if (__predict_false(RB_RED_P(standin_son
))) {
573 * We know we have a red child so if we flip it to black
574 * we don't have to rebalance.
576 KASSERT(rb_tree_check_node(rbt
, standin_son
, NULL
, true));
577 RB_MARK_BLACK(standin_son
);
580 if (standin_father
== self
) {
581 KASSERT(RB_POSITION(standin_son
) == standin_which
);
583 KASSERT(RB_POSITION(standin_son
) == standin_other
);
585 * Change the son's parentage to point to his grandpa.
587 RB_SET_FATHER(standin_son
, standin_father
);
588 RB_SET_POSITION(standin_son
, standin_which
);
592 if (standin_father
== self
) {
594 * If we are about to delete the standin's father, then when
595 * we call rebalance, we need to use ourselves as our father.
596 * Otherwise remember our original father. Also, sincef we are
597 * our standin's father we only need to reparent the standin's
604 KASSERT(RB_SENTINEL_P(standin
->rb_nodes
[standin_other
]));
605 KASSERT(!RB_SENTINEL_P(self
->rb_nodes
[standin_other
]));
606 KASSERT(self
->rb_nodes
[standin_which
] == standin
);
608 * Have our son/standin adopt his brother as his new son.
610 standin_father
= standin
;
614 * | / \ | T --> / \ | / |
615 * | ..... | S --> ..... | T |
617 * Sever standin's connection to his father.
619 standin_father
->rb_nodes
[standin_which
] = standin_son
;
623 standin
->rb_nodes
[standin_other
] = self
->rb_nodes
[standin_other
];
624 RB_SET_FATHER(standin
->rb_nodes
[standin_other
], standin
);
625 KASSERT(RB_POSITION(self
->rb_nodes
[standin_other
]) == standin_other
);
627 * Use standin_other because we need to preserve standin_which
628 * for the removal_rebalance.
630 standin_other
= standin_which
;
634 * Move the only remaining son to our standin. If our standin is our
635 * son, this will be the only son needed to be moved.
637 KASSERT(standin
->rb_nodes
[standin_other
] != self
->rb_nodes
[standin_other
]);
638 standin
->rb_nodes
[standin_other
] = self
->rb_nodes
[standin_other
];
639 RB_SET_FATHER(standin
->rb_nodes
[standin_other
], standin
);
642 * Now copy the result of self to standin and then replace
643 * self with standin in the tree.
645 RB_COPY_PROPERTIES(standin
, self
);
646 RB_SET_FATHER(standin
, RB_FATHER(self
));
647 RB_FATHER(standin
)->rb_nodes
[RB_POSITION(standin
)] = standin
;
650 * Remove ourselves from the node list, decrement the count,
651 * and update min/max.
653 RB_TAILQ_REMOVE(&rbt
->rbt_nodes
, self
, rb_link
);
656 if (__predict_false(rbt
->rbt_minmax
[RB_POSITION(self
)] == self
))
657 rbt
->rbt_minmax
[RB_POSITION(self
)] = RB_FATHER(self
);
658 RB_SET_FATHER(self
, NULL
);
661 KASSERT(rb_tree_check_node(rbt
, standin
, NULL
, false));
662 KASSERT(RB_FATHER_SENTINEL_P(standin
)
663 || rb_tree_check_node(rbt
, standin_father
, NULL
, false));
664 KASSERT(RB_LEFT_SENTINEL_P(standin
)
665 || rb_tree_check_node(rbt
, standin
->rb_left
, NULL
, false));
666 KASSERT(RB_RIGHT_SENTINEL_P(standin
)
667 || rb_tree_check_node(rbt
, standin
->rb_right
, NULL
, false));
672 rb_tree_removal_rebalance(rbt
, standin_father
, standin_which
);
673 KASSERT(rb_tree_check_node(rbt
, standin
, NULL
, true));
677 * We could do this by doing
678 * rb_tree_node_swap(rbt, self, which);
679 * rb_tree_prune_node(rbt, self, false);
681 * But it's more efficient to just evalate and recolor the child.
684 rb_tree_prune_blackred_branch(struct rb_tree
*rbt
, struct rb_node
*self
,
687 struct rb_node
*father
= RB_FATHER(self
);
688 struct rb_node
*son
= self
->rb_nodes
[which
];
689 const bool was_root
= RB_ROOT_P(rbt
, self
);
691 KASSERT(which
== RB_DIR_LEFT
|| which
== RB_DIR_RIGHT
);
692 KASSERT(RB_BLACK_P(self
) && RB_RED_P(son
));
693 KASSERT(!RB_TWOCHILDREN_P(son
));
694 KASSERT(RB_CHILDLESS_P(son
));
695 KASSERT(rb_tree_check_node(rbt
, self
, NULL
, false));
696 KASSERT(rb_tree_check_node(rbt
, son
, NULL
, false));
699 * Remove ourselves from the tree and give our former child our
700 * properties (position, color, root).
702 RB_COPY_PROPERTIES(son
, self
);
703 father
->rb_nodes
[RB_POSITION(son
)] = son
;
704 RB_SET_FATHER(son
, father
);
707 * Remove ourselves from the node list, decrement the count,
710 RB_TAILQ_REMOVE(&rbt
->rbt_nodes
, self
, rb_link
);
713 if (__predict_false(was_root
)) {
714 KASSERT(rbt
->rbt_minmax
[which
] == son
);
715 rbt
->rbt_minmax
[which
^ RB_DIR_OTHER
] = son
;
716 } else if (rbt
->rbt_minmax
[RB_POSITION(self
)] == self
) {
717 rbt
->rbt_minmax
[RB_POSITION(self
)] = son
;
719 RB_SET_FATHER(self
, NULL
);
722 KASSERT(was_root
|| rb_tree_check_node(rbt
, father
, NULL
, true));
723 KASSERT(rb_tree_check_node(rbt
, son
, NULL
, true));
729 rb_tree_remove_node(struct rb_tree
*rbt
, struct rb_node
*self
)
731 struct rb_node
*standin
;
734 KASSERT(!RB_SENTINEL_P(self
));
735 RBSTAT_INC(rbt
->rbt_removals
);
738 * In the following diagrams, we (the node to be removed) are S. Red
739 * nodes are lowercase. T could be either red or black.
741 * Remember the major axiom of the red-black tree: the number of
742 * black nodes from the root to each leaf is constant across all
743 * leaves, only the number of red nodes varies.
745 * Thus removing a red leaf doesn't require any other changes to a
746 * red-black tree. So if we must remove a node, attempt to rearrange
747 * the tree so we can remove a red node.
749 * The simpliest case is a childless red node or a childless root node:
751 * | T --> T | or | R --> * |
754 if (RB_CHILDLESS_P(self
)) {
755 const bool rebalance
= RB_BLACK_P(self
) && !RB_ROOT_P(rbt
, self
);
756 rb_tree_prune_node(rbt
, self
, rebalance
);
759 KASSERT(!RB_CHILDLESS_P(self
));
760 if (!RB_TWOCHILDREN_P(self
)) {
762 * The next simpliest case is the node we are deleting is
763 * black and has one red child.
769 which
= RB_LEFT_SENTINEL_P(self
) ? RB_DIR_RIGHT
: RB_DIR_LEFT
;
770 KASSERT(RB_BLACK_P(self
));
771 KASSERT(RB_RED_P(self
->rb_nodes
[which
]));
772 KASSERT(RB_CHILDLESS_P(self
->rb_nodes
[which
]));
773 rb_tree_prune_blackred_branch(rbt
, self
, which
);
776 KASSERT(RB_TWOCHILDREN_P(self
));
779 * We invert these because we prefer to remove from the inside of
782 which
= RB_POSITION(self
) ^ RB_DIR_OTHER
;
785 * Let's find the node closes to us opposite of our parent
786 * Now swap it with ourself, "prune" it, and rebalance, if needed.
788 standin
= rb_tree_iterate(rbt
, self
, which
);
789 rb_tree_swap_prune_and_rebalance(rbt
, self
, standin
);
793 rb_tree_removal_rebalance(struct rb_tree
*rbt
, struct rb_node
*parent
,
796 KASSERT(!RB_SENTINEL_P(parent
));
797 KASSERT(RB_SENTINEL_P(parent
->rb_nodes
[which
]));
798 KASSERT(which
== RB_DIR_LEFT
|| which
== RB_DIR_RIGHT
);
799 RBSTAT_INC(rbt
->rbt_removal_rebalance_calls
);
801 while (RB_BLACK_P(parent
->rb_nodes
[which
])) {
802 unsigned int other
= which
^ RB_DIR_OTHER
;
803 struct rb_node
*brother
= parent
->rb_nodes
[other
];
805 RBSTAT_INC(rbt
->rbt_removal_rebalance_passes
);
807 KASSERT(!RB_SENTINEL_P(brother
));
809 * For cases 1, 2a, and 2b, our brother's children must
810 * be black and our father must be black
812 if (RB_BLACK_P(parent
)
813 && RB_BLACK_P(brother
->rb_left
)
814 && RB_BLACK_P(brother
->rb_right
)) {
815 if (RB_RED_P(brother
)) {
817 * Case 1: Our brother is red, swap its
818 * position (and colors) with our parent.
819 * This should now be case 2b (unless C or E
820 * has a red child which is case 3; thus no
821 * explicit branch to case 2b).
827 KASSERT(RB_BLACK_P(parent
));
828 rb_tree_reparent_nodes(rbt
, parent
, other
);
829 brother
= parent
->rb_nodes
[other
];
830 KASSERT(!RB_SENTINEL_P(brother
));
831 KASSERT(RB_RED_P(parent
));
832 KASSERT(RB_BLACK_P(brother
));
833 KASSERT(rb_tree_check_node(rbt
, brother
, NULL
, false));
834 KASSERT(rb_tree_check_node(rbt
, parent
, NULL
, false));
837 * Both our parent and brother are black.
838 * Change our brother to red, advance up rank
839 * and go through the loop again.
845 RB_MARK_RED(brother
);
846 KASSERT(RB_BLACK_P(brother
->rb_left
));
847 KASSERT(RB_BLACK_P(brother
->rb_right
));
848 if (RB_ROOT_P(rbt
, parent
))
849 return; /* root == parent == black */
850 KASSERT(rb_tree_check_node(rbt
, brother
, NULL
, false));
851 KASSERT(rb_tree_check_node(rbt
, parent
, NULL
, false));
852 if (parent
!= NULL
) {
853 which
= RB_POSITION(parent
);
854 parent
= RB_FATHER(parent
);
860 * Avoid an else here so that case 2a above can hit either
864 && (RB_SENTINEL_P(brother
)
865 || (RB_BLACK_P(brother
)
866 && RB_BLACK_P(brother
->rb_left
)
867 && RB_BLACK_P(brother
->rb_right
)))) {
868 KASSERT(RB_RED_P(parent
));
869 KASSERT(RB_BLACK_P(brother
));
870 KASSERT(RB_BLACK_P(brother
->rb_left
));
871 KASSERT(RB_BLACK_P(brother
->rb_right
));
873 * We are black, our father is red, our brother and
874 * both nephews are black. Simply invert/exchange the
875 * colors of our father and brother (to black and red
882 RB_MARK_BLACK(parent
);
883 if (!RB_SENTINEL_P(brother
)) {
884 RB_MARK_RED(brother
);
886 KASSERT(rb_tree_check_node(rbt
, brother
, NULL
, true));
887 break; /* We're done! */
890 * Our brother must be black and have at least one
891 * red child (it may have two).
893 KASSERT(RB_BLACK_P(brother
));
894 KASSERT(RB_RED_P(brother
->rb_nodes
[which
]) ||
895 RB_RED_P(brother
->rb_nodes
[other
]));
896 if (RB_BLACK_P(brother
->rb_nodes
[other
])) {
898 * Case 3: our brother is black, our near
899 * nephew is red, and our far nephew is black.
900 * Swap our brother with our near nephew.
901 * This result in a tree that matches case 4.
902 * (Our father could be red or black).
908 KASSERT(RB_RED_P(brother
->rb_nodes
[which
]));
909 rb_tree_reparent_nodes(rbt
, brother
, which
);
910 KASSERT(RB_FATHER(brother
) == parent
->rb_nodes
[other
]);
911 brother
= parent
->rb_nodes
[other
];
912 KASSERT(RB_RED_P(brother
->rb_nodes
[other
]));
915 * Case 4: our brother is black and our far nephew
916 * is red. Swap our father and brother locations and
917 * change our far nephew to black. (these can be
918 * done in either order so we change the color first).
919 * The result is a valid red-black tree and is a
920 * terminal case. (again we don't care about the
923 * If the father is red, we will get a red-black-black
929 * If the father is black, we will get an all black
935 * If we had two red nephews, then after the swap,
936 * our former father would have a red grandson.
938 KASSERT(RB_BLACK_P(brother
));
939 KASSERT(RB_RED_P(brother
->rb_nodes
[other
]));
940 RB_MARK_BLACK(brother
->rb_nodes
[other
]);
941 rb_tree_reparent_nodes(rbt
, parent
, other
);
942 break; /* We're done! */
945 KASSERT(rb_tree_check_node(rbt
, parent
, NULL
, true));
949 rb_tree_iterate(struct rb_tree
*rbt
, struct rb_node
*self
,
950 const unsigned int direction
)
952 const unsigned int other
= direction
^ RB_DIR_OTHER
;
953 KASSERT(direction
== RB_DIR_LEFT
|| direction
== RB_DIR_RIGHT
);
957 if (RB_SENTINEL_P(rbt
->rbt_root
))
959 return rbt
->rbt_minmax
[direction
];
961 self
= rbt
->rbt_root
;
962 if (RB_SENTINEL_P(self
))
964 while (!RB_SENTINEL_P(self
->rb_nodes
[other
]))
965 self
= self
->rb_nodes
[other
];
967 #endif /* !RBSMALL */
969 KASSERT(!RB_SENTINEL_P(self
));
971 * We can't go any further in this direction. We proceed up in the
972 * opposite direction until our parent is in direction we want to go.
974 if (RB_SENTINEL_P(self
->rb_nodes
[direction
])) {
975 while (!RB_ROOT_P(rbt
, self
)) {
976 if (other
== RB_POSITION(self
))
977 return RB_FATHER(self
);
978 self
= RB_FATHER(self
);
984 * Advance down one in current direction and go down as far as possible
985 * in the opposite direction.
987 self
= self
->rb_nodes
[direction
];
988 KASSERT(!RB_SENTINEL_P(self
));
989 while (!RB_SENTINEL_P(self
->rb_nodes
[other
]))
990 self
= self
->rb_nodes
[other
];
995 static const struct rb_node
*
996 rb_tree_iterate_const(const struct rb_tree
*rbt
, const struct rb_node
*self
,
997 const unsigned int direction
)
999 const unsigned int other
= direction
^ RB_DIR_OTHER
;
1000 KASSERT(direction
== RB_DIR_LEFT
|| direction
== RB_DIR_RIGHT
);
1004 if (RB_SENTINEL_P(rbt
->rbt_root
))
1006 return rbt
->rbt_minmax
[direction
];
1008 self
= rbt
->rbt_root
;
1009 if (RB_SENTINEL_P(self
))
1011 while (!RB_SENTINEL_P(self
->rb_nodes
[other
]))
1012 self
= self
->rb_nodes
[other
];
1014 #endif /* !RBSMALL */
1016 KASSERT(!RB_SENTINEL_P(self
));
1018 * We can't go any further in this direction. We proceed up in the
1019 * opposite direction until our parent is in direction we want to go.
1021 if (RB_SENTINEL_P(self
->rb_nodes
[direction
])) {
1022 while (!RB_ROOT_P(rbt
, self
)) {
1023 if (other
== RB_POSITION(self
))
1024 return RB_FATHER(self
);
1025 self
= RB_FATHER(self
);
1031 * Advance down one in current direction and go down as far as possible
1032 * in the opposite direction.
1034 self
= self
->rb_nodes
[direction
];
1035 KASSERT(!RB_SENTINEL_P(self
));
1036 while (!RB_SENTINEL_P(self
->rb_nodes
[other
]))
1037 self
= self
->rb_nodes
[other
];
1042 rb_tree_count_black(const struct rb_node
*self
)
1044 unsigned int left
, right
;
1046 if (RB_SENTINEL_P(self
))
1049 left
= rb_tree_count_black(self
->rb_left
);
1050 right
= rb_tree_count_black(self
->rb_right
);
1052 KASSERT(left
== right
);
1054 return left
+ RB_BLACK_P(self
);
1058 rb_tree_check_node(const struct rb_tree
*rbt
, const struct rb_node
*self
,
1059 const struct rb_node
*prev
, bool red_check
)
1061 rbto_compare_nodes_fn compare_nodes
= rbt
->rbt_ops
->rbto_compare_nodes
;
1063 KASSERT(!RB_SENTINEL_P(self
));
1064 KASSERT(prev
== NULL
|| (*compare_nodes
)(prev
, self
) > 0);
1067 * Verify our relationship to our parent.
1069 if (RB_ROOT_P(rbt
, self
)) {
1070 KASSERT(self
== rbt
->rbt_root
);
1071 KASSERT(RB_POSITION(self
) == RB_DIR_LEFT
);
1072 KASSERT(RB_FATHER(self
)->rb_nodes
[RB_DIR_LEFT
] == self
);
1073 KASSERT(RB_FATHER(self
) == (const struct rb_node
*) &rbt
->rbt_root
);
1075 KASSERT(self
!= rbt
->rbt_root
);
1076 KASSERT(!RB_FATHER_SENTINEL_P(self
));
1077 if (RB_POSITION(self
) == RB_DIR_LEFT
) {
1078 KASSERT((*compare_nodes
)(self
, RB_FATHER(self
)) > 0);
1079 KASSERT(RB_FATHER(self
)->rb_nodes
[RB_DIR_LEFT
] == self
);
1081 KASSERT((*compare_nodes
)(self
, RB_FATHER(self
)) < 0);
1082 KASSERT(RB_FATHER(self
)->rb_nodes
[RB_DIR_RIGHT
] == self
);
1087 * Verify our position in the linked list against the tree itself.
1090 const struct rb_node
*prev0
= rb_tree_iterate_const(rbt
, self
, RB_DIR_LEFT
);
1091 const struct rb_node
*next0
= rb_tree_iterate_const(rbt
, self
, RB_DIR_RIGHT
);
1092 KASSERT(prev0
== TAILQ_PREV(self
, rb_node_qh
, rb_link
));
1093 KASSERT(next0
== TAILQ_NEXT(self
, rb_link
));
1095 KASSERT(prev0
!= NULL
|| self
== rbt
->rbt_minmax
[RB_DIR_LEFT
]);
1096 KASSERT(next0
!= NULL
|| self
== rbt
->rbt_minmax
[RB_DIR_RIGHT
]);
1101 * The root must be black.
1102 * There can never be two adjacent red nodes.
1105 KASSERT(!RB_ROOT_P(rbt
, self
) || RB_BLACK_P(self
));
1106 (void) rb_tree_count_black(self
);
1107 if (RB_RED_P(self
)) {
1108 const struct rb_node
*brother
;
1109 KASSERT(!RB_ROOT_P(rbt
, self
));
1110 brother
= RB_FATHER(self
)->rb_nodes
[RB_POSITION(self
) ^ RB_DIR_OTHER
];
1111 KASSERT(RB_BLACK_P(RB_FATHER(self
)));
1113 * I'm red and have no children, then I must either
1114 * have no brother or my brother also be red and
1115 * also have no children. (black count == 0)
1117 KASSERT(!RB_CHILDLESS_P(self
)
1118 || RB_SENTINEL_P(brother
)
1119 || RB_RED_P(brother
)
1120 || RB_CHILDLESS_P(brother
));
1122 * If I'm not childless, I must have two children
1123 * and they must be both be black.
1125 KASSERT(RB_CHILDLESS_P(self
)
1126 || (RB_TWOCHILDREN_P(self
)
1127 && RB_BLACK_P(self
->rb_left
)
1128 && RB_BLACK_P(self
->rb_right
)));
1130 * If I'm not childless, thus I have black children,
1131 * then my brother must either be black or have two
1134 KASSERT(RB_CHILDLESS_P(self
)
1135 || RB_BLACK_P(brother
)
1136 || (RB_TWOCHILDREN_P(brother
)
1137 && RB_BLACK_P(brother
->rb_left
)
1138 && RB_BLACK_P(brother
->rb_right
)));
1141 * If I'm black and have one child, that child must
1142 * be red and childless.
1144 KASSERT(RB_CHILDLESS_P(self
)
1145 || RB_TWOCHILDREN_P(self
)
1146 || (!RB_LEFT_SENTINEL_P(self
)
1147 && RB_RIGHT_SENTINEL_P(self
)
1148 && RB_RED_P(self
->rb_left
)
1149 && RB_CHILDLESS_P(self
->rb_left
))
1150 || (!RB_RIGHT_SENTINEL_P(self
)
1151 && RB_LEFT_SENTINEL_P(self
)
1152 && RB_RED_P(self
->rb_right
)
1153 && RB_CHILDLESS_P(self
->rb_right
)));
1156 * If I'm a childless black node and my parent is
1157 * black, my 2nd closet relative away from my parent
1158 * is either red or has a red parent or red children.
1160 if (!RB_ROOT_P(rbt
, self
)
1161 && RB_CHILDLESS_P(self
)
1162 && RB_BLACK_P(RB_FATHER(self
))) {
1163 const unsigned int which
= RB_POSITION(self
);
1164 const unsigned int other
= which
^ RB_DIR_OTHER
;
1165 const struct rb_node
*relative0
, *relative
;
1167 relative0
= rb_tree_iterate_const(rbt
,
1169 KASSERT(relative0
!= NULL
);
1170 relative
= rb_tree_iterate_const(rbt
,
1172 KASSERT(relative
!= NULL
);
1173 KASSERT(RB_SENTINEL_P(relative
->rb_nodes
[which
]));
1175 KASSERT(RB_RED_P(relative
)
1176 || RB_RED_P(relative
->rb_left
)
1177 || RB_RED_P(relative
->rb_right
)
1178 || RB_RED_P(RB_FATHER(relative
)));
1183 * A grandparent's children must be real nodes and not
1184 * sentinels. First check out grandparent.
1186 KASSERT(RB_ROOT_P(rbt
, self
)
1187 || RB_ROOT_P(rbt
, RB_FATHER(self
))
1188 || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self
))));
1190 * If we are have grandchildren on our left, then
1191 * we must have a child on our right.
1193 KASSERT(RB_LEFT_SENTINEL_P(self
)
1194 || RB_CHILDLESS_P(self
->rb_left
)
1195 || !RB_RIGHT_SENTINEL_P(self
));
1197 * If we are have grandchildren on our right, then
1198 * we must have a child on our left.
1200 KASSERT(RB_RIGHT_SENTINEL_P(self
)
1201 || RB_CHILDLESS_P(self
->rb_right
)
1202 || !RB_LEFT_SENTINEL_P(self
));
1205 * If we have a child on the left and it doesn't have two
1206 * children make sure we don't have great-great-grandchildren on
1209 KASSERT(RB_TWOCHILDREN_P(self
->rb_left
)
1210 || RB_CHILDLESS_P(self
->rb_right
)
1211 || RB_CHILDLESS_P(self
->rb_right
->rb_left
)
1212 || RB_CHILDLESS_P(self
->rb_right
->rb_left
->rb_left
)
1213 || RB_CHILDLESS_P(self
->rb_right
->rb_left
->rb_right
)
1214 || RB_CHILDLESS_P(self
->rb_right
->rb_right
)
1215 || RB_CHILDLESS_P(self
->rb_right
->rb_right
->rb_left
)
1216 || RB_CHILDLESS_P(self
->rb_right
->rb_right
->rb_right
));
1219 * If we have a child on the right and it doesn't have two
1220 * children make sure we don't have great-great-grandchildren on
1223 KASSERT(RB_TWOCHILDREN_P(self
->rb_right
)
1224 || RB_CHILDLESS_P(self
->rb_left
)
1225 || RB_CHILDLESS_P(self
->rb_left
->rb_left
)
1226 || RB_CHILDLESS_P(self
->rb_left
->rb_left
->rb_left
)
1227 || RB_CHILDLESS_P(self
->rb_left
->rb_left
->rb_right
)
1228 || RB_CHILDLESS_P(self
->rb_left
->rb_right
)
1229 || RB_CHILDLESS_P(self
->rb_left
->rb_right
->rb_left
)
1230 || RB_CHILDLESS_P(self
->rb_left
->rb_right
->rb_right
));
1233 * If we are fully interior node, then our predecessors and
1234 * successors must have no children in our direction.
1236 if (RB_TWOCHILDREN_P(self
)) {
1237 const struct rb_node
*prev0
;
1238 const struct rb_node
*next0
;
1240 prev0
= rb_tree_iterate_const(rbt
, self
, RB_DIR_LEFT
);
1241 KASSERT(prev0
!= NULL
);
1242 KASSERT(RB_RIGHT_SENTINEL_P(prev0
));
1244 next0
= rb_tree_iterate_const(rbt
, self
, RB_DIR_RIGHT
);
1245 KASSERT(next0
!= NULL
);
1246 KASSERT(RB_LEFT_SENTINEL_P(next0
));
1254 rb_tree_check(const struct rb_tree
*rbt
, bool red_check
)
1256 const struct rb_node
*self
;
1257 const struct rb_node
*prev
;
1259 unsigned int count
= 0;
1262 KASSERT(rbt
->rbt_root
!= NULL
);
1263 KASSERT(RB_LEFT_P(rbt
->rbt_root
));
1265 #if defined(RBSTATS) && !defined(RBSMALL)
1266 KASSERT(rbt
->rbt_count
> 1
1267 || rbt
->rbt_minmax
[RB_DIR_LEFT
] == rbt
->rbt_minmax
[RB_DIR_RIGHT
]);
1271 TAILQ_FOREACH(self
, &rbt
->rbt_nodes
, rb_link
) {
1272 rb_tree_check_node(rbt
, self
, prev
, false);
1278 KASSERT(rbt
->rbt_count
== count
);
1281 KASSERT(RB_BLACK_P(rbt
->rbt_root
));
1282 KASSERT(RB_SENTINEL_P(rbt
->rbt_root
)
1283 || rb_tree_count_black(rbt
->rbt_root
));
1286 * The root must be black.
1287 * There can never be two adjacent red nodes.
1289 TAILQ_FOREACH(self
, &rbt
->rbt_nodes
, rb_link
) {
1290 rb_tree_check_node(rbt
, self
, NULL
, true);
1294 #endif /* RBDEBUG */
1298 rb_tree_mark_depth(const struct rb_tree
*rbt
, const struct rb_node
*self
,
1299 size_t *depths
, size_t depth
)
1301 if (RB_SENTINEL_P(self
))
1304 if (RB_TWOCHILDREN_P(self
)) {
1305 rb_tree_mark_depth(rbt
, self
->rb_left
, depths
, depth
+ 1);
1306 rb_tree_mark_depth(rbt
, self
->rb_right
, depths
, depth
+ 1);
1310 if (!RB_LEFT_SENTINEL_P(self
)) {
1311 rb_tree_mark_depth(rbt
, self
->rb_left
, depths
, depth
+ 1);
1313 if (!RB_RIGHT_SENTINEL_P(self
)) {
1314 rb_tree_mark_depth(rbt
, self
->rb_right
, depths
, depth
+ 1);
1319 rb_tree_depths(const struct rb_tree
*rbt
, size_t *depths
)
1321 rb_tree_mark_depth(rbt
, rbt
->rbt_root
, depths
, 1);
1323 #endif /* RBSTATS */