1*f14fb602SLionel Sambuc /* $NetBSD: prop_rb.c,v 1.10 2012/07/27 09:10:59 pooka Exp $ */
26b6d114aSBen Gras
36b6d114aSBen Gras /*-
46b6d114aSBen Gras * Copyright (c) 2001 The NetBSD Foundation, Inc.
56b6d114aSBen Gras * All rights reserved.
66b6d114aSBen Gras *
76b6d114aSBen Gras * This code is derived from software contributed to The NetBSD Foundation
86b6d114aSBen Gras * by Matt Thomas <matt@3am-software.com>.
96b6d114aSBen Gras *
106b6d114aSBen Gras * Redistribution and use in source and binary forms, with or without
116b6d114aSBen Gras * modification, are permitted provided that the following conditions
126b6d114aSBen Gras * are met:
136b6d114aSBen Gras * 1. Redistributions of source code must retain the above copyright
146b6d114aSBen Gras * notice, this list of conditions and the following disclaimer.
156b6d114aSBen Gras * 2. Redistributions in binary form must reproduce the above copyright
166b6d114aSBen Gras * notice, this list of conditions and the following disclaimer in the
176b6d114aSBen Gras * documentation and/or other materials provided with the distribution.
186b6d114aSBen Gras *
196b6d114aSBen Gras * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
206b6d114aSBen Gras * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
216b6d114aSBen Gras * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
226b6d114aSBen Gras * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
236b6d114aSBen Gras * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
246b6d114aSBen Gras * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
256b6d114aSBen Gras * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
266b6d114aSBen Gras * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
276b6d114aSBen Gras * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
286b6d114aSBen Gras * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
296b6d114aSBen Gras * POSSIBILITY OF SUCH DAMAGE.
30*f14fb602SLionel Sambuc *
31*f14fb602SLionel Sambuc * NetBSD: rb.c,v 1.11 2011/06/20 09:11:16 mrg Exp
326b6d114aSBen Gras */
336b6d114aSBen Gras
34*f14fb602SLionel Sambuc #include "prop_object_impl.h"
356b6d114aSBen Gras #include <prop/proplib.h>
366b6d114aSBen Gras
376b6d114aSBen Gras #include "prop_rb_impl.h"
386b6d114aSBen Gras
396b6d114aSBen Gras #ifdef RBDEBUG
40*f14fb602SLionel Sambuc #define KASSERT(s) _PROP_ASSERT(s)
416b6d114aSBen Gras #else
42*f14fb602SLionel Sambuc #define KASSERT(s) do { } while (/*CONSTCOND*/ 0)
436b6d114aSBen Gras #endif
446b6d114aSBen Gras
456b6d114aSBen Gras #ifndef __predict_false
466b6d114aSBen Gras #define __predict_false(x) (x)
476b6d114aSBen Gras #endif
486b6d114aSBen Gras
496b6d114aSBen Gras static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
506b6d114aSBen Gras static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
516b6d114aSBen Gras unsigned int);
526b6d114aSBen Gras #ifdef RBDEBUG
536b6d114aSBen Gras static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
54*f14fb602SLionel Sambuc const struct rb_node *, const unsigned int);
556b6d114aSBen Gras static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
566b6d114aSBen Gras const struct rb_node *, bool);
576b6d114aSBen Gras #else
58*f14fb602SLionel Sambuc #define rb_tree_check_node(a, b, c, d) true
596b6d114aSBen Gras #endif
606b6d114aSBen Gras
61*f14fb602SLionel Sambuc #define RB_NODETOITEM(rbto, rbn) \
62*f14fb602SLionel Sambuc ((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
63*f14fb602SLionel Sambuc #define RB_ITEMTONODE(rbto, rbn) \
64*f14fb602SLionel Sambuc ((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
656b6d114aSBen Gras
66*f14fb602SLionel Sambuc #define RB_SENTINEL_NODE NULL
676b6d114aSBen Gras
686b6d114aSBen Gras void
_prop_rb_tree_init(struct rb_tree * rbt,const rb_tree_ops_t * ops)69*f14fb602SLionel Sambuc _prop_rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
706b6d114aSBen Gras {
71*f14fb602SLionel Sambuc
726b6d114aSBen Gras rbt->rbt_ops = ops;
73*f14fb602SLionel Sambuc rbt->rbt_root = RB_SENTINEL_NODE;
74*f14fb602SLionel Sambuc RB_TAILQ_INIT(&rbt->rbt_nodes);
75*f14fb602SLionel Sambuc #ifndef RBSMALL
76*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root; /* minimum node */
77*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root; /* maximum node */
78*f14fb602SLionel Sambuc #endif
79*f14fb602SLionel Sambuc #ifdef RBSTATS
80*f14fb602SLionel Sambuc rbt->rbt_count = 0;
81*f14fb602SLionel Sambuc rbt->rbt_insertions = 0;
82*f14fb602SLionel Sambuc rbt->rbt_removals = 0;
83*f14fb602SLionel Sambuc rbt->rbt_insertion_rebalance_calls = 0;
84*f14fb602SLionel Sambuc rbt->rbt_insertion_rebalance_passes = 0;
85*f14fb602SLionel Sambuc rbt->rbt_removal_rebalance_calls = 0;
86*f14fb602SLionel Sambuc rbt->rbt_removal_rebalance_passes = 0;
87*f14fb602SLionel Sambuc #endif
886b6d114aSBen Gras }
896b6d114aSBen Gras
90*f14fb602SLionel Sambuc void *
_prop_rb_tree_find(struct rb_tree * rbt,const void * key)91*f14fb602SLionel Sambuc _prop_rb_tree_find(struct rb_tree *rbt, const void *key)
926b6d114aSBen Gras {
93*f14fb602SLionel Sambuc const rb_tree_ops_t *rbto = rbt->rbt_ops;
94*f14fb602SLionel Sambuc rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
95*f14fb602SLionel Sambuc struct rb_node *parent = rbt->rbt_root;
966b6d114aSBen Gras
97*f14fb602SLionel Sambuc while (!RB_SENTINEL_P(parent)) {
98*f14fb602SLionel Sambuc void *pobj = RB_NODETOITEM(rbto, parent);
99*f14fb602SLionel Sambuc const signed int diff = (*compare_key)(rbto->rbto_context,
100*f14fb602SLionel Sambuc pobj, key);
101*f14fb602SLionel Sambuc if (diff == 0)
102*f14fb602SLionel Sambuc return pobj;
103*f14fb602SLionel Sambuc parent = parent->rb_nodes[diff < 0];
1046b6d114aSBen Gras }
1056b6d114aSBen Gras
106*f14fb602SLionel Sambuc return NULL;
1076b6d114aSBen Gras }
1086b6d114aSBen Gras
109*f14fb602SLionel Sambuc void *
_prop_rb_tree_insert_node(struct rb_tree * rbt,void * object)110*f14fb602SLionel Sambuc _prop_rb_tree_insert_node(struct rb_tree *rbt, void *object)
1116b6d114aSBen Gras {
112*f14fb602SLionel Sambuc const rb_tree_ops_t *rbto = rbt->rbt_ops;
113*f14fb602SLionel Sambuc rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
114*f14fb602SLionel Sambuc struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
1156b6d114aSBen Gras unsigned int position;
116*f14fb602SLionel Sambuc bool rebalance;
1176b6d114aSBen Gras
118*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_insertions);
119*f14fb602SLionel Sambuc
1206b6d114aSBen Gras tmp = rbt->rbt_root;
1216b6d114aSBen Gras /*
1226b6d114aSBen Gras * This is a hack. Because rbt->rbt_root is just a struct rb_node *,
123*f14fb602SLionel Sambuc * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
1246b6d114aSBen Gras * avoid a lot of tests for root and know that even at root,
125*f14fb602SLionel Sambuc * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
126*f14fb602SLionel Sambuc * update rbt->rbt_root.
1276b6d114aSBen Gras */
128*f14fb602SLionel Sambuc parent = (struct rb_node *)(void *)&rbt->rbt_root;
129*f14fb602SLionel Sambuc position = RB_DIR_LEFT;
1306b6d114aSBen Gras
1316b6d114aSBen Gras /*
1326b6d114aSBen Gras * Find out where to place this new leaf.
1336b6d114aSBen Gras */
1346b6d114aSBen Gras while (!RB_SENTINEL_P(tmp)) {
135*f14fb602SLionel Sambuc void *tobj = RB_NODETOITEM(rbto, tmp);
136*f14fb602SLionel Sambuc const signed int diff = (*compare_nodes)(rbto->rbto_context,
137*f14fb602SLionel Sambuc tobj, object);
1386b6d114aSBen Gras if (__predict_false(diff == 0)) {
1396b6d114aSBen Gras /*
140*f14fb602SLionel Sambuc * Node already exists; return it.
1416b6d114aSBen Gras */
142*f14fb602SLionel Sambuc return tobj;
1436b6d114aSBen Gras }
1446b6d114aSBen Gras parent = tmp;
145*f14fb602SLionel Sambuc position = (diff < 0);
1466b6d114aSBen Gras tmp = parent->rb_nodes[position];
1476b6d114aSBen Gras }
1486b6d114aSBen Gras
1496b6d114aSBen Gras #ifdef RBDEBUG
1506b6d114aSBen Gras {
1516b6d114aSBen Gras struct rb_node *prev = NULL, *next = NULL;
1526b6d114aSBen Gras
153*f14fb602SLionel Sambuc if (position == RB_DIR_RIGHT)
1546b6d114aSBen Gras prev = parent;
1556b6d114aSBen Gras else if (tmp != rbt->rbt_root)
1566b6d114aSBen Gras next = parent;
1576b6d114aSBen Gras
1586b6d114aSBen Gras /*
1596b6d114aSBen Gras * Verify our sequential position
1606b6d114aSBen Gras */
1616b6d114aSBen Gras KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
1626b6d114aSBen Gras KASSERT(next == NULL || !RB_SENTINEL_P(next));
1636b6d114aSBen Gras if (prev != NULL && next == NULL)
1646b6d114aSBen Gras next = TAILQ_NEXT(prev, rb_link);
1656b6d114aSBen Gras if (prev == NULL && next != NULL)
1666b6d114aSBen Gras prev = TAILQ_PREV(next, rb_node_qh, rb_link);
1676b6d114aSBen Gras KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
1686b6d114aSBen Gras KASSERT(next == NULL || !RB_SENTINEL_P(next));
169*f14fb602SLionel Sambuc KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
170*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
171*f14fb602SLionel Sambuc KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
172*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
1736b6d114aSBen Gras }
1746b6d114aSBen Gras #endif
1756b6d114aSBen Gras
1766b6d114aSBen Gras /*
1776b6d114aSBen Gras * Initialize the node and insert as a leaf into the tree.
1786b6d114aSBen Gras */
179*f14fb602SLionel Sambuc RB_SET_FATHER(self, parent);
180*f14fb602SLionel Sambuc RB_SET_POSITION(self, position);
181*f14fb602SLionel Sambuc if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
182*f14fb602SLionel Sambuc RB_MARK_BLACK(self); /* root is always black */
183*f14fb602SLionel Sambuc #ifndef RBSMALL
184*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_DIR_LEFT] = self;
185*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_DIR_RIGHT] = self;
186*f14fb602SLionel Sambuc #endif
187*f14fb602SLionel Sambuc rebalance = false;
1886b6d114aSBen Gras } else {
189*f14fb602SLionel Sambuc KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
190*f14fb602SLionel Sambuc #ifndef RBSMALL
191*f14fb602SLionel Sambuc /*
192*f14fb602SLionel Sambuc * Keep track of the minimum and maximum nodes. If our
193*f14fb602SLionel Sambuc * parent is a minmax node and we on their min/max side,
194*f14fb602SLionel Sambuc * we must be the new min/max node.
195*f14fb602SLionel Sambuc */
196*f14fb602SLionel Sambuc if (parent == rbt->rbt_minmax[position])
197*f14fb602SLionel Sambuc rbt->rbt_minmax[position] = self;
198*f14fb602SLionel Sambuc #endif /* !RBSMALL */
199*f14fb602SLionel Sambuc /*
200*f14fb602SLionel Sambuc * All new nodes are colored red. We only need to rebalance
201*f14fb602SLionel Sambuc * if our parent is also red.
202*f14fb602SLionel Sambuc */
203*f14fb602SLionel Sambuc RB_MARK_RED(self);
204*f14fb602SLionel Sambuc rebalance = RB_RED_P(parent);
2056b6d114aSBen Gras }
2066b6d114aSBen Gras KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
2076b6d114aSBen Gras self->rb_left = parent->rb_nodes[position];
2086b6d114aSBen Gras self->rb_right = parent->rb_nodes[position];
2096b6d114aSBen Gras parent->rb_nodes[position] = self;
210*f14fb602SLionel Sambuc KASSERT(RB_CHILDLESS_P(self));
2116b6d114aSBen Gras
2126b6d114aSBen Gras /*
2136b6d114aSBen Gras * Insert the new node into a sorted list for easy sequential access
2146b6d114aSBen Gras */
215*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_count);
2166b6d114aSBen Gras #ifdef RBDEBUG
217*f14fb602SLionel Sambuc if (RB_ROOT_P(rbt, self)) {
2186b6d114aSBen Gras RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
219*f14fb602SLionel Sambuc } else if (position == RB_DIR_LEFT) {
220*f14fb602SLionel Sambuc KASSERT((*compare_nodes)(rbto->rbto_context,
221*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, self),
222*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
223*f14fb602SLionel Sambuc RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
2246b6d114aSBen Gras } else {
225*f14fb602SLionel Sambuc KASSERT((*compare_nodes)(rbto->rbto_context,
226*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, RB_FATHER(self)),
227*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, self)) < 0);
228*f14fb602SLionel Sambuc RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
2296b6d114aSBen Gras self, rb_link);
2306b6d114aSBen Gras }
2316b6d114aSBen Gras #endif
232*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
2336b6d114aSBen Gras
2346b6d114aSBen Gras /*
2356b6d114aSBen Gras * Rebalance tree after insertion
2366b6d114aSBen Gras */
237*f14fb602SLionel Sambuc if (rebalance) {
2386b6d114aSBen Gras rb_tree_insert_rebalance(rbt, self);
239*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, self, NULL, true));
2406b6d114aSBen Gras }
241*f14fb602SLionel Sambuc
242*f14fb602SLionel Sambuc /* Succesfully inserted, return our node pointer. */
243*f14fb602SLionel Sambuc return object;
244*f14fb602SLionel Sambuc }
245*f14fb602SLionel Sambuc
246*f14fb602SLionel Sambuc /*
247*f14fb602SLionel Sambuc * Swap the location and colors of 'self' and its child @ which. The child
248*f14fb602SLionel Sambuc * can not be a sentinel node. This is our rotation function. However,
249*f14fb602SLionel Sambuc * since it preserves coloring, it great simplifies both insertion and
250*f14fb602SLionel Sambuc * removal since rotation almost always involves the exchanging of colors
251*f14fb602SLionel Sambuc * as a separate step.
252*f14fb602SLionel Sambuc */
253*f14fb602SLionel Sambuc /*ARGSUSED*/
254*f14fb602SLionel Sambuc static void
rb_tree_reparent_nodes(struct rb_tree * rbt,struct rb_node * old_father,const unsigned int which)255*f14fb602SLionel Sambuc rb_tree_reparent_nodes(struct rb_tree *rbt, struct rb_node *old_father,
256*f14fb602SLionel Sambuc const unsigned int which)
257*f14fb602SLionel Sambuc {
258*f14fb602SLionel Sambuc const unsigned int other = which ^ RB_DIR_OTHER;
259*f14fb602SLionel Sambuc struct rb_node * const grandpa = RB_FATHER(old_father);
260*f14fb602SLionel Sambuc struct rb_node * const old_child = old_father->rb_nodes[which];
261*f14fb602SLionel Sambuc struct rb_node * const new_father = old_child;
262*f14fb602SLionel Sambuc struct rb_node * const new_child = old_father;
263*f14fb602SLionel Sambuc
264*f14fb602SLionel Sambuc KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
265*f14fb602SLionel Sambuc
266*f14fb602SLionel Sambuc KASSERT(!RB_SENTINEL_P(old_child));
267*f14fb602SLionel Sambuc KASSERT(RB_FATHER(old_child) == old_father);
268*f14fb602SLionel Sambuc
269*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
270*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
271*f14fb602SLionel Sambuc KASSERT(RB_ROOT_P(rbt, old_father) ||
272*f14fb602SLionel Sambuc rb_tree_check_node(rbt, grandpa, NULL, false));
273*f14fb602SLionel Sambuc
274*f14fb602SLionel Sambuc /*
275*f14fb602SLionel Sambuc * Exchange descendant linkages.
276*f14fb602SLionel Sambuc */
277*f14fb602SLionel Sambuc grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
278*f14fb602SLionel Sambuc new_child->rb_nodes[which] = old_child->rb_nodes[other];
279*f14fb602SLionel Sambuc new_father->rb_nodes[other] = new_child;
280*f14fb602SLionel Sambuc
281*f14fb602SLionel Sambuc /*
282*f14fb602SLionel Sambuc * Update ancestor linkages
283*f14fb602SLionel Sambuc */
284*f14fb602SLionel Sambuc RB_SET_FATHER(new_father, grandpa);
285*f14fb602SLionel Sambuc RB_SET_FATHER(new_child, new_father);
286*f14fb602SLionel Sambuc
287*f14fb602SLionel Sambuc /*
288*f14fb602SLionel Sambuc * Exchange properties between new_father and new_child. The only
289*f14fb602SLionel Sambuc * change is that new_child's position is now on the other side.
290*f14fb602SLionel Sambuc */
291*f14fb602SLionel Sambuc #if 0
292*f14fb602SLionel Sambuc {
293*f14fb602SLionel Sambuc struct rb_node tmp;
294*f14fb602SLionel Sambuc tmp.rb_info = 0;
295*f14fb602SLionel Sambuc RB_COPY_PROPERTIES(&tmp, old_child);
296*f14fb602SLionel Sambuc RB_COPY_PROPERTIES(new_father, old_father);
297*f14fb602SLionel Sambuc RB_COPY_PROPERTIES(new_child, &tmp);
298*f14fb602SLionel Sambuc }
299*f14fb602SLionel Sambuc #else
300*f14fb602SLionel Sambuc RB_SWAP_PROPERTIES(new_father, new_child);
301*f14fb602SLionel Sambuc #endif
302*f14fb602SLionel Sambuc RB_SET_POSITION(new_child, other);
303*f14fb602SLionel Sambuc
304*f14fb602SLionel Sambuc /*
305*f14fb602SLionel Sambuc * Make sure to reparent the new child to ourself.
306*f14fb602SLionel Sambuc */
307*f14fb602SLionel Sambuc if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
308*f14fb602SLionel Sambuc RB_SET_FATHER(new_child->rb_nodes[which], new_child);
309*f14fb602SLionel Sambuc RB_SET_POSITION(new_child->rb_nodes[which], which);
310*f14fb602SLionel Sambuc }
311*f14fb602SLionel Sambuc
312*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
313*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
314*f14fb602SLionel Sambuc KASSERT(RB_ROOT_P(rbt, new_father) ||
315*f14fb602SLionel Sambuc rb_tree_check_node(rbt, grandpa, NULL, false));
316*f14fb602SLionel Sambuc }
317*f14fb602SLionel Sambuc
3186b6d114aSBen Gras static void
rb_tree_insert_rebalance(struct rb_tree * rbt,struct rb_node * self)3196b6d114aSBen Gras rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
3206b6d114aSBen Gras {
321*f14fb602SLionel Sambuc struct rb_node * father = RB_FATHER(self);
322*f14fb602SLionel Sambuc struct rb_node * grandpa = RB_FATHER(father);
323*f14fb602SLionel Sambuc struct rb_node * uncle;
324*f14fb602SLionel Sambuc unsigned int which;
325*f14fb602SLionel Sambuc unsigned int other;
3266b6d114aSBen Gras
327*f14fb602SLionel Sambuc KASSERT(!RB_ROOT_P(rbt, self));
328*f14fb602SLionel Sambuc KASSERT(RB_RED_P(self));
329*f14fb602SLionel Sambuc KASSERT(RB_RED_P(father));
330*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);
3316b6d114aSBen Gras
332*f14fb602SLionel Sambuc for (;;) {
3336b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self));
334*f14fb602SLionel Sambuc
335*f14fb602SLionel Sambuc KASSERT(RB_RED_P(self));
336*f14fb602SLionel Sambuc KASSERT(RB_RED_P(father));
3376b6d114aSBen Gras /*
3386b6d114aSBen Gras * We are red and our parent is red, therefore we must have a
3396b6d114aSBen Gras * grandfather and he must be black.
3406b6d114aSBen Gras */
341*f14fb602SLionel Sambuc grandpa = RB_FATHER(father);
342*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(grandpa));
343*f14fb602SLionel Sambuc KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
344*f14fb602SLionel Sambuc which = (father == grandpa->rb_right);
345*f14fb602SLionel Sambuc other = which ^ RB_DIR_OTHER;
346*f14fb602SLionel Sambuc uncle = grandpa->rb_nodes[other];
3476b6d114aSBen Gras
348*f14fb602SLionel Sambuc if (RB_BLACK_P(uncle))
349*f14fb602SLionel Sambuc break;
350*f14fb602SLionel Sambuc
351*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);
3526b6d114aSBen Gras /*
3536b6d114aSBen Gras * Case 1: our uncle is red
3546b6d114aSBen Gras * Simply invert the colors of our parent and
3556b6d114aSBen Gras * uncle and make our grandparent red. And
3566b6d114aSBen Gras * then solve the problem up at his level.
3576b6d114aSBen Gras */
3586b6d114aSBen Gras RB_MARK_BLACK(uncle);
3596b6d114aSBen Gras RB_MARK_BLACK(father);
360*f14fb602SLionel Sambuc if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
361*f14fb602SLionel Sambuc /*
362*f14fb602SLionel Sambuc * If our grandpa is root, don't bother
363*f14fb602SLionel Sambuc * setting him to red, just return.
364*f14fb602SLionel Sambuc */
365*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(grandpa));
366*f14fb602SLionel Sambuc return;
367*f14fb602SLionel Sambuc }
3686b6d114aSBen Gras RB_MARK_RED(grandpa);
3696b6d114aSBen Gras self = grandpa;
370*f14fb602SLionel Sambuc father = RB_FATHER(self);
371*f14fb602SLionel Sambuc KASSERT(RB_RED_P(self));
372*f14fb602SLionel Sambuc if (RB_BLACK_P(father)) {
373*f14fb602SLionel Sambuc /*
374*f14fb602SLionel Sambuc * If our greatgrandpa is black, we're done.
375*f14fb602SLionel Sambuc */
376*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(rbt->rbt_root));
377*f14fb602SLionel Sambuc return;
3786b6d114aSBen Gras }
379*f14fb602SLionel Sambuc }
380*f14fb602SLionel Sambuc
381*f14fb602SLionel Sambuc KASSERT(!RB_ROOT_P(rbt, self));
382*f14fb602SLionel Sambuc KASSERT(RB_RED_P(self));
383*f14fb602SLionel Sambuc KASSERT(RB_RED_P(father));
384*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(uncle));
385*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(grandpa));
3866b6d114aSBen Gras /*
3876b6d114aSBen Gras * Case 2&3: our uncle is black.
3886b6d114aSBen Gras */
3896b6d114aSBen Gras if (self == father->rb_nodes[other]) {
3906b6d114aSBen Gras /*
3916b6d114aSBen Gras * Case 2: we are on the same side as our uncle
3926b6d114aSBen Gras * Swap ourselves with our parent so this case
3936b6d114aSBen Gras * becomes case 3. Basically our parent becomes our
3946b6d114aSBen Gras * child.
3956b6d114aSBen Gras */
3966b6d114aSBen Gras rb_tree_reparent_nodes(rbt, father, other);
397*f14fb602SLionel Sambuc KASSERT(RB_FATHER(father) == self);
3986b6d114aSBen Gras KASSERT(self->rb_nodes[which] == father);
399*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self) == grandpa);
4006b6d114aSBen Gras self = father;
401*f14fb602SLionel Sambuc father = RB_FATHER(self);
4026b6d114aSBen Gras }
4036b6d114aSBen Gras KASSERT(RB_RED_P(self) && RB_RED_P(father));
4046b6d114aSBen Gras KASSERT(grandpa->rb_nodes[which] == father);
4056b6d114aSBen Gras /*
4066b6d114aSBen Gras * Case 3: we are opposite a child of a black uncle.
4076b6d114aSBen Gras * Swap our parent and grandparent. Since our grandfather
4086b6d114aSBen Gras * is black, our father will become black and our new sibling
4096b6d114aSBen Gras * (former grandparent) will become red.
4106b6d114aSBen Gras */
4116b6d114aSBen Gras rb_tree_reparent_nodes(rbt, grandpa, which);
412*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self) == father);
413*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
4146b6d114aSBen Gras KASSERT(RB_RED_P(self));
4156b6d114aSBen Gras KASSERT(RB_BLACK_P(father));
4166b6d114aSBen Gras KASSERT(RB_RED_P(grandpa));
4176b6d114aSBen Gras
4186b6d114aSBen Gras /*
4196b6d114aSBen Gras * Final step: Set the root to black.
4206b6d114aSBen Gras */
4216b6d114aSBen Gras RB_MARK_BLACK(rbt->rbt_root);
4226b6d114aSBen Gras }
4236b6d114aSBen Gras
4246b6d114aSBen Gras static void
rb_tree_prune_node(struct rb_tree * rbt,struct rb_node * self,bool rebalance)425*f14fb602SLionel Sambuc rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
4266b6d114aSBen Gras {
427*f14fb602SLionel Sambuc const unsigned int which = RB_POSITION(self);
428*f14fb602SLionel Sambuc struct rb_node *father = RB_FATHER(self);
429*f14fb602SLionel Sambuc #ifndef RBSMALL
430*f14fb602SLionel Sambuc const bool was_root = RB_ROOT_P(rbt, self);
431*f14fb602SLionel Sambuc #endif
4326b6d114aSBen Gras
433*f14fb602SLionel Sambuc KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
4346b6d114aSBen Gras KASSERT(!rebalance || RB_BLACK_P(self));
4356b6d114aSBen Gras KASSERT(RB_CHILDLESS_P(self));
4366b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, self, NULL, false));
4376b6d114aSBen Gras
438*f14fb602SLionel Sambuc /*
439*f14fb602SLionel Sambuc * Since we are childless, we know that self->rb_left is pointing
440*f14fb602SLionel Sambuc * to the sentinel node.
441*f14fb602SLionel Sambuc */
4426b6d114aSBen Gras father->rb_nodes[which] = self->rb_left;
4436b6d114aSBen Gras
4446b6d114aSBen Gras /*
445*f14fb602SLionel Sambuc * Remove ourselves from the node list, decrement the count,
446*f14fb602SLionel Sambuc * and update min/max.
4476b6d114aSBen Gras */
4486b6d114aSBen Gras RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
449*f14fb602SLionel Sambuc RBSTAT_DEC(rbt->rbt_count);
450*f14fb602SLionel Sambuc #ifndef RBSMALL
451*f14fb602SLionel Sambuc if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
452*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_POSITION(self)] = father;
453*f14fb602SLionel Sambuc /*
454*f14fb602SLionel Sambuc * When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
455*f14fb602SLionel Sambuc * updated automatically, but we also need to update
456*f14fb602SLionel Sambuc * rbt->rbt_minmax[RB_DIR_RIGHT];
457*f14fb602SLionel Sambuc */
458*f14fb602SLionel Sambuc if (__predict_false(was_root)) {
459*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_DIR_RIGHT] = father;
460*f14fb602SLionel Sambuc }
461*f14fb602SLionel Sambuc }
462*f14fb602SLionel Sambuc RB_SET_FATHER(self, NULL);
463*f14fb602SLionel Sambuc #endif
4646b6d114aSBen Gras
465*f14fb602SLionel Sambuc /*
466*f14fb602SLionel Sambuc * Rebalance if requested.
467*f14fb602SLionel Sambuc */
4686b6d114aSBen Gras if (rebalance)
4696b6d114aSBen Gras rb_tree_removal_rebalance(rbt, father, which);
470*f14fb602SLionel Sambuc KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
4716b6d114aSBen Gras }
4726b6d114aSBen Gras
473*f14fb602SLionel Sambuc /*
474*f14fb602SLionel Sambuc * When deleting an interior node
475*f14fb602SLionel Sambuc */
4766b6d114aSBen Gras static void
rb_tree_swap_prune_and_rebalance(struct rb_tree * rbt,struct rb_node * self,struct rb_node * standin)4776b6d114aSBen Gras rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
4786b6d114aSBen Gras struct rb_node *standin)
4796b6d114aSBen Gras {
480*f14fb602SLionel Sambuc const unsigned int standin_which = RB_POSITION(standin);
481*f14fb602SLionel Sambuc unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
482*f14fb602SLionel Sambuc struct rb_node *standin_son;
483*f14fb602SLionel Sambuc struct rb_node *standin_father = RB_FATHER(standin);
4846b6d114aSBen Gras bool rebalance = RB_BLACK_P(standin);
4856b6d114aSBen Gras
486*f14fb602SLionel Sambuc if (standin_father == self) {
4876b6d114aSBen Gras /*
4886b6d114aSBen Gras * As a child of self, any childen would be opposite of
489*f14fb602SLionel Sambuc * our parent.
4906b6d114aSBen Gras */
4916b6d114aSBen Gras KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
492*f14fb602SLionel Sambuc standin_son = standin->rb_nodes[standin_which];
4936b6d114aSBen Gras } else {
4946b6d114aSBen Gras /*
4956b6d114aSBen Gras * Since we aren't a child of self, any childen would be
496*f14fb602SLionel Sambuc * on the same side as our parent.
4976b6d114aSBen Gras */
4986b6d114aSBen Gras KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
499*f14fb602SLionel Sambuc standin_son = standin->rb_nodes[standin_other];
5006b6d114aSBen Gras }
5016b6d114aSBen Gras
5026b6d114aSBen Gras /*
5036b6d114aSBen Gras * the node we are removing must have two children.
5046b6d114aSBen Gras */
5056b6d114aSBen Gras KASSERT(RB_TWOCHILDREN_P(self));
5066b6d114aSBen Gras /*
5076b6d114aSBen Gras * If standin has a child, it must be red.
5086b6d114aSBen Gras */
509*f14fb602SLionel Sambuc KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
5106b6d114aSBen Gras
5116b6d114aSBen Gras /*
5126b6d114aSBen Gras * Verify things are sane.
5136b6d114aSBen Gras */
5146b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, self, NULL, false));
5156b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
5166b6d114aSBen Gras
517*f14fb602SLionel Sambuc if (__predict_false(RB_RED_P(standin_son))) {
5186b6d114aSBen Gras /*
519*f14fb602SLionel Sambuc * We know we have a red child so if we flip it to black
520*f14fb602SLionel Sambuc * we don't have to rebalance.
5216b6d114aSBen Gras */
522*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
523*f14fb602SLionel Sambuc RB_MARK_BLACK(standin_son);
5246b6d114aSBen Gras rebalance = false;
5256b6d114aSBen Gras
526*f14fb602SLionel Sambuc if (standin_father == self) {
527*f14fb602SLionel Sambuc KASSERT(RB_POSITION(standin_son) == standin_which);
528*f14fb602SLionel Sambuc } else {
529*f14fb602SLionel Sambuc KASSERT(RB_POSITION(standin_son) == standin_other);
5306b6d114aSBen Gras /*
531*f14fb602SLionel Sambuc * Change the son's parentage to point to his grandpa.
5326b6d114aSBen Gras */
533*f14fb602SLionel Sambuc RB_SET_FATHER(standin_son, standin_father);
534*f14fb602SLionel Sambuc RB_SET_POSITION(standin_son, standin_which);
535*f14fb602SLionel Sambuc }
536*f14fb602SLionel Sambuc }
537*f14fb602SLionel Sambuc
538*f14fb602SLionel Sambuc if (standin_father == self) {
5396b6d114aSBen Gras /*
540*f14fb602SLionel Sambuc * If we are about to delete the standin's father, then when
541*f14fb602SLionel Sambuc * we call rebalance, we need to use ourselves as our father.
542*f14fb602SLionel Sambuc * Otherwise remember our original father. Also, sincef we are
543*f14fb602SLionel Sambuc * our standin's father we only need to reparent the standin's
544*f14fb602SLionel Sambuc * brother.
545*f14fb602SLionel Sambuc *
5466b6d114aSBen Gras * | R --> S |
547*f14fb602SLionel Sambuc * | Q S --> Q T |
548*f14fb602SLionel Sambuc * | t --> |
5496b6d114aSBen Gras */
5506b6d114aSBen Gras KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
5516b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
5526b6d114aSBen Gras KASSERT(self->rb_nodes[standin_which] == standin);
5536b6d114aSBen Gras /*
554*f14fb602SLionel Sambuc * Have our son/standin adopt his brother as his new son.
5556b6d114aSBen Gras */
556*f14fb602SLionel Sambuc standin_father = standin;
5576b6d114aSBen Gras } else {
5586b6d114aSBen Gras /*
559*f14fb602SLionel Sambuc * | R --> S . |
560*f14fb602SLionel Sambuc * | / \ | T --> / \ | / |
561*f14fb602SLionel Sambuc * | ..... | S --> ..... | T |
562*f14fb602SLionel Sambuc *
563*f14fb602SLionel Sambuc * Sever standin's connection to his father.
5646b6d114aSBen Gras */
565*f14fb602SLionel Sambuc standin_father->rb_nodes[standin_which] = standin_son;
566*f14fb602SLionel Sambuc /*
567*f14fb602SLionel Sambuc * Adopt the far son.
568*f14fb602SLionel Sambuc */
569*f14fb602SLionel Sambuc standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
570*f14fb602SLionel Sambuc RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
571*f14fb602SLionel Sambuc KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
572*f14fb602SLionel Sambuc /*
573*f14fb602SLionel Sambuc * Use standin_other because we need to preserve standin_which
574*f14fb602SLionel Sambuc * for the removal_rebalance.
575*f14fb602SLionel Sambuc */
576*f14fb602SLionel Sambuc standin_other = standin_which;
5776b6d114aSBen Gras }
5786b6d114aSBen Gras
5796b6d114aSBen Gras /*
580*f14fb602SLionel Sambuc * Move the only remaining son to our standin. If our standin is our
581*f14fb602SLionel Sambuc * son, this will be the only son needed to be moved.
582*f14fb602SLionel Sambuc */
583*f14fb602SLionel Sambuc KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
584*f14fb602SLionel Sambuc standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
585*f14fb602SLionel Sambuc RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
586*f14fb602SLionel Sambuc
587*f14fb602SLionel Sambuc /*
5886b6d114aSBen Gras * Now copy the result of self to standin and then replace
5896b6d114aSBen Gras * self with standin in the tree.
5906b6d114aSBen Gras */
591*f14fb602SLionel Sambuc RB_COPY_PROPERTIES(standin, self);
592*f14fb602SLionel Sambuc RB_SET_FATHER(standin, RB_FATHER(self));
593*f14fb602SLionel Sambuc RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
5946b6d114aSBen Gras
5956b6d114aSBen Gras /*
596*f14fb602SLionel Sambuc * Remove ourselves from the node list, decrement the count,
597*f14fb602SLionel Sambuc * and update min/max.
5986b6d114aSBen Gras */
5996b6d114aSBen Gras RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
600*f14fb602SLionel Sambuc RBSTAT_DEC(rbt->rbt_count);
601*f14fb602SLionel Sambuc #ifndef RBSMALL
602*f14fb602SLionel Sambuc if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
603*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
604*f14fb602SLionel Sambuc RB_SET_FATHER(self, NULL);
605*f14fb602SLionel Sambuc #endif
6066b6d114aSBen Gras
6076b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
608*f14fb602SLionel Sambuc KASSERT(RB_FATHER_SENTINEL_P(standin)
609*f14fb602SLionel Sambuc || rb_tree_check_node(rbt, standin_father, NULL, false));
610*f14fb602SLionel Sambuc KASSERT(RB_LEFT_SENTINEL_P(standin)
611*f14fb602SLionel Sambuc || rb_tree_check_node(rbt, standin->rb_left, NULL, false));
612*f14fb602SLionel Sambuc KASSERT(RB_RIGHT_SENTINEL_P(standin)
613*f14fb602SLionel Sambuc || rb_tree_check_node(rbt, standin->rb_right, NULL, false));
6146b6d114aSBen Gras
6156b6d114aSBen Gras if (!rebalance)
6166b6d114aSBen Gras return;
6176b6d114aSBen Gras
6186b6d114aSBen Gras rb_tree_removal_rebalance(rbt, standin_father, standin_which);
6196b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
6206b6d114aSBen Gras }
6216b6d114aSBen Gras
6226b6d114aSBen Gras /*
6236b6d114aSBen Gras * We could do this by doing
6246b6d114aSBen Gras * rb_tree_node_swap(rbt, self, which);
6256b6d114aSBen Gras * rb_tree_prune_node(rbt, self, false);
6266b6d114aSBen Gras *
6276b6d114aSBen Gras * But it's more efficient to just evalate and recolor the child.
6286b6d114aSBen Gras */
6296b6d114aSBen Gras static void
rb_tree_prune_blackred_branch(struct rb_tree * rbt,struct rb_node * self,unsigned int which)630*f14fb602SLionel Sambuc rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
631*f14fb602SLionel Sambuc unsigned int which)
6326b6d114aSBen Gras {
633*f14fb602SLionel Sambuc struct rb_node *father = RB_FATHER(self);
634*f14fb602SLionel Sambuc struct rb_node *son = self->rb_nodes[which];
635*f14fb602SLionel Sambuc #ifndef RBSMALL
636*f14fb602SLionel Sambuc const bool was_root = RB_ROOT_P(rbt, self);
637*f14fb602SLionel Sambuc #endif
6386b6d114aSBen Gras
639*f14fb602SLionel Sambuc KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
640*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
641*f14fb602SLionel Sambuc KASSERT(!RB_TWOCHILDREN_P(son));
642*f14fb602SLionel Sambuc KASSERT(RB_CHILDLESS_P(son));
6436b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, self, NULL, false));
644*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, son, NULL, false));
6456b6d114aSBen Gras
6466b6d114aSBen Gras /*
6476b6d114aSBen Gras * Remove ourselves from the tree and give our former child our
6486b6d114aSBen Gras * properties (position, color, root).
6496b6d114aSBen Gras */
650*f14fb602SLionel Sambuc RB_COPY_PROPERTIES(son, self);
651*f14fb602SLionel Sambuc father->rb_nodes[RB_POSITION(son)] = son;
652*f14fb602SLionel Sambuc RB_SET_FATHER(son, father);
6536b6d114aSBen Gras
6546b6d114aSBen Gras /*
655*f14fb602SLionel Sambuc * Remove ourselves from the node list, decrement the count,
656*f14fb602SLionel Sambuc * and update minmax.
6576b6d114aSBen Gras */
6586b6d114aSBen Gras RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
659*f14fb602SLionel Sambuc RBSTAT_DEC(rbt->rbt_count);
660*f14fb602SLionel Sambuc #ifndef RBSMALL
661*f14fb602SLionel Sambuc if (__predict_false(was_root)) {
662*f14fb602SLionel Sambuc KASSERT(rbt->rbt_minmax[which] == son);
663*f14fb602SLionel Sambuc rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;
664*f14fb602SLionel Sambuc } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
665*f14fb602SLionel Sambuc rbt->rbt_minmax[RB_POSITION(self)] = son;
6666b6d114aSBen Gras }
667*f14fb602SLionel Sambuc RB_SET_FATHER(self, NULL);
668*f14fb602SLionel Sambuc #endif
669*f14fb602SLionel Sambuc
670*f14fb602SLionel Sambuc KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
671*f14fb602SLionel Sambuc KASSERT(rb_tree_check_node(rbt, son, NULL, true));
672*f14fb602SLionel Sambuc }
673*f14fb602SLionel Sambuc
6746b6d114aSBen Gras void
_prop_rb_tree_remove_node(struct rb_tree * rbt,void * object)675*f14fb602SLionel Sambuc _prop_rb_tree_remove_node(struct rb_tree *rbt, void *object)
6766b6d114aSBen Gras {
677*f14fb602SLionel Sambuc const rb_tree_ops_t *rbto = rbt->rbt_ops;
678*f14fb602SLionel Sambuc struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
6796b6d114aSBen Gras unsigned int which;
680*f14fb602SLionel Sambuc
681*f14fb602SLionel Sambuc KASSERT(!RB_SENTINEL_P(self));
682*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_removals);
683*f14fb602SLionel Sambuc
6846b6d114aSBen Gras /*
6856b6d114aSBen Gras * In the following diagrams, we (the node to be removed) are S. Red
6866b6d114aSBen Gras * nodes are lowercase. T could be either red or black.
6876b6d114aSBen Gras *
6886b6d114aSBen Gras * Remember the major axiom of the red-black tree: the number of
6896b6d114aSBen Gras * black nodes from the root to each leaf is constant across all
6906b6d114aSBen Gras * leaves, only the number of red nodes varies.
6916b6d114aSBen Gras *
6926b6d114aSBen Gras * Thus removing a red leaf doesn't require any other changes to a
6936b6d114aSBen Gras * red-black tree. So if we must remove a node, attempt to rearrange
6946b6d114aSBen Gras * the tree so we can remove a red node.
6956b6d114aSBen Gras *
6966b6d114aSBen Gras * The simpliest case is a childless red node or a childless root node:
6976b6d114aSBen Gras *
6986b6d114aSBen Gras * | T --> T | or | R --> * |
6996b6d114aSBen Gras * | s --> * |
7006b6d114aSBen Gras */
7016b6d114aSBen Gras if (RB_CHILDLESS_P(self)) {
702*f14fb602SLionel Sambuc const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
703*f14fb602SLionel Sambuc rb_tree_prune_node(rbt, self, rebalance);
7046b6d114aSBen Gras return;
7056b6d114aSBen Gras }
7066b6d114aSBen Gras KASSERT(!RB_CHILDLESS_P(self));
7076b6d114aSBen Gras if (!RB_TWOCHILDREN_P(self)) {
7086b6d114aSBen Gras /*
7096b6d114aSBen Gras * The next simpliest case is the node we are deleting is
7106b6d114aSBen Gras * black and has one red child.
7116b6d114aSBen Gras *
7126b6d114aSBen Gras * | T --> T --> T |
7136b6d114aSBen Gras * | S --> R --> R |
7146b6d114aSBen Gras * | r --> s --> * |
7156b6d114aSBen Gras */
716*f14fb602SLionel Sambuc which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
7176b6d114aSBen Gras KASSERT(RB_BLACK_P(self));
7186b6d114aSBen Gras KASSERT(RB_RED_P(self->rb_nodes[which]));
7196b6d114aSBen Gras KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
7206b6d114aSBen Gras rb_tree_prune_blackred_branch(rbt, self, which);
7216b6d114aSBen Gras return;
7226b6d114aSBen Gras }
7236b6d114aSBen Gras KASSERT(RB_TWOCHILDREN_P(self));
7246b6d114aSBen Gras
7256b6d114aSBen Gras /*
7266b6d114aSBen Gras * We invert these because we prefer to remove from the inside of
7276b6d114aSBen Gras * the tree.
7286b6d114aSBen Gras */
729*f14fb602SLionel Sambuc which = RB_POSITION(self) ^ RB_DIR_OTHER;
7306b6d114aSBen Gras
7316b6d114aSBen Gras /*
7326b6d114aSBen Gras * Let's find the node closes to us opposite of our parent
7336b6d114aSBen Gras * Now swap it with ourself, "prune" it, and rebalance, if needed.
7346b6d114aSBen Gras */
735*f14fb602SLionel Sambuc standin = RB_ITEMTONODE(rbto,_prop_rb_tree_iterate(rbt, object, which));
7366b6d114aSBen Gras rb_tree_swap_prune_and_rebalance(rbt, self, standin);
7376b6d114aSBen Gras }
7386b6d114aSBen Gras
7396b6d114aSBen Gras static void
rb_tree_removal_rebalance(struct rb_tree * rbt,struct rb_node * parent,unsigned int which)7406b6d114aSBen Gras rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
7416b6d114aSBen Gras unsigned int which)
7426b6d114aSBen Gras {
7436b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(parent));
7446b6d114aSBen Gras KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
745*f14fb602SLionel Sambuc KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
746*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_removal_rebalance_calls);
7476b6d114aSBen Gras
7486b6d114aSBen Gras while (RB_BLACK_P(parent->rb_nodes[which])) {
749*f14fb602SLionel Sambuc unsigned int other = which ^ RB_DIR_OTHER;
7506b6d114aSBen Gras struct rb_node *brother = parent->rb_nodes[other];
7516b6d114aSBen Gras
752*f14fb602SLionel Sambuc RBSTAT_INC(rbt->rbt_removal_rebalance_passes);
753*f14fb602SLionel Sambuc
7546b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(brother));
7556b6d114aSBen Gras /*
7566b6d114aSBen Gras * For cases 1, 2a, and 2b, our brother's children must
7576b6d114aSBen Gras * be black and our father must be black
7586b6d114aSBen Gras */
7596b6d114aSBen Gras if (RB_BLACK_P(parent)
7606b6d114aSBen Gras && RB_BLACK_P(brother->rb_left)
7616b6d114aSBen Gras && RB_BLACK_P(brother->rb_right)) {
762*f14fb602SLionel Sambuc if (RB_RED_P(brother)) {
7636b6d114aSBen Gras /*
764*f14fb602SLionel Sambuc * Case 1: Our brother is red, swap its
765*f14fb602SLionel Sambuc * position (and colors) with our parent.
766*f14fb602SLionel Sambuc * This should now be case 2b (unless C or E
767*f14fb602SLionel Sambuc * has a red child which is case 3; thus no
768*f14fb602SLionel Sambuc * explicit branch to case 2b).
7696b6d114aSBen Gras *
7706b6d114aSBen Gras * B -> D
771*f14fb602SLionel Sambuc * A d -> b E
772*f14fb602SLionel Sambuc * C E -> A C
7736b6d114aSBen Gras */
7746b6d114aSBen Gras KASSERT(RB_BLACK_P(parent));
7756b6d114aSBen Gras rb_tree_reparent_nodes(rbt, parent, other);
7766b6d114aSBen Gras brother = parent->rb_nodes[other];
7776b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(brother));
7786b6d114aSBen Gras KASSERT(RB_RED_P(parent));
779*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(brother));
7806b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
7816b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
7826b6d114aSBen Gras } else {
7836b6d114aSBen Gras /*
7846b6d114aSBen Gras * Both our parent and brother are black.
7856b6d114aSBen Gras * Change our brother to red, advance up rank
7866b6d114aSBen Gras * and go through the loop again.
7876b6d114aSBen Gras *
788*f14fb602SLionel Sambuc * B -> *B
789*f14fb602SLionel Sambuc * *A D -> A d
7906b6d114aSBen Gras * C E -> C E
7916b6d114aSBen Gras */
7926b6d114aSBen Gras RB_MARK_RED(brother);
7936b6d114aSBen Gras KASSERT(RB_BLACK_P(brother->rb_left));
7946b6d114aSBen Gras KASSERT(RB_BLACK_P(brother->rb_right));
795*f14fb602SLionel Sambuc if (RB_ROOT_P(rbt, parent))
796*f14fb602SLionel Sambuc return; /* root == parent == black */
7976b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
7986b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
799*f14fb602SLionel Sambuc which = RB_POSITION(parent);
800*f14fb602SLionel Sambuc parent = RB_FATHER(parent);
801*f14fb602SLionel Sambuc continue;
8026b6d114aSBen Gras }
803*f14fb602SLionel Sambuc }
804*f14fb602SLionel Sambuc /*
805*f14fb602SLionel Sambuc * Avoid an else here so that case 2a above can hit either
806*f14fb602SLionel Sambuc * case 2b, 3, or 4.
807*f14fb602SLionel Sambuc */
808*f14fb602SLionel Sambuc if (RB_RED_P(parent)
8096b6d114aSBen Gras && RB_BLACK_P(brother)
8106b6d114aSBen Gras && RB_BLACK_P(brother->rb_left)
8116b6d114aSBen Gras && RB_BLACK_P(brother->rb_right)) {
812*f14fb602SLionel Sambuc KASSERT(RB_RED_P(parent));
8136b6d114aSBen Gras KASSERT(RB_BLACK_P(brother));
8146b6d114aSBen Gras KASSERT(RB_BLACK_P(brother->rb_left));
8156b6d114aSBen Gras KASSERT(RB_BLACK_P(brother->rb_right));
816*f14fb602SLionel Sambuc /*
817*f14fb602SLionel Sambuc * We are black, our father is red, our brother and
818*f14fb602SLionel Sambuc * both nephews are black. Simply invert/exchange the
819*f14fb602SLionel Sambuc * colors of our father and brother (to black and red
820*f14fb602SLionel Sambuc * respectively).
821*f14fb602SLionel Sambuc *
822*f14fb602SLionel Sambuc * | f --> F |
823*f14fb602SLionel Sambuc * | * B --> * b |
824*f14fb602SLionel Sambuc * | N N --> N N |
825*f14fb602SLionel Sambuc */
8266b6d114aSBen Gras RB_MARK_BLACK(parent);
8276b6d114aSBen Gras RB_MARK_RED(brother);
8286b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
8296b6d114aSBen Gras break; /* We're done! */
8306b6d114aSBen Gras } else {
8316b6d114aSBen Gras /*
832*f14fb602SLionel Sambuc * Our brother must be black and have at least one
833*f14fb602SLionel Sambuc * red child (it may have two).
8346b6d114aSBen Gras */
835*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(brother));
836*f14fb602SLionel Sambuc KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
837*f14fb602SLionel Sambuc RB_RED_P(brother->rb_nodes[other]));
8386b6d114aSBen Gras if (RB_BLACK_P(brother->rb_nodes[other])) {
839*f14fb602SLionel Sambuc /*
840*f14fb602SLionel Sambuc * Case 3: our brother is black, our near
841*f14fb602SLionel Sambuc * nephew is red, and our far nephew is black.
842*f14fb602SLionel Sambuc * Swap our brother with our near nephew.
843*f14fb602SLionel Sambuc * This result in a tree that matches case 4.
844*f14fb602SLionel Sambuc * (Our father could be red or black).
845*f14fb602SLionel Sambuc *
846*f14fb602SLionel Sambuc * | F --> F |
847*f14fb602SLionel Sambuc * | x B --> x B |
848*f14fb602SLionel Sambuc * | n --> n |
849*f14fb602SLionel Sambuc */
8506b6d114aSBen Gras KASSERT(RB_RED_P(brother->rb_nodes[which]));
8516b6d114aSBen Gras rb_tree_reparent_nodes(rbt, brother, which);
852*f14fb602SLionel Sambuc KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
8536b6d114aSBen Gras brother = parent->rb_nodes[other];
8546b6d114aSBen Gras KASSERT(RB_RED_P(brother->rb_nodes[other]));
8556b6d114aSBen Gras }
8566b6d114aSBen Gras /*
857*f14fb602SLionel Sambuc * Case 4: our brother is black and our far nephew
858*f14fb602SLionel Sambuc * is red. Swap our father and brother locations and
859*f14fb602SLionel Sambuc * change our far nephew to black. (these can be
8606b6d114aSBen Gras * done in either order so we change the color first).
8616b6d114aSBen Gras * The result is a valid red-black tree and is a
862*f14fb602SLionel Sambuc * terminal case. (again we don't care about the
863*f14fb602SLionel Sambuc * father's color)
8646b6d114aSBen Gras *
865*f14fb602SLionel Sambuc * If the father is red, we will get a red-black-black
866*f14fb602SLionel Sambuc * tree:
867*f14fb602SLionel Sambuc * | f -> f --> b |
868*f14fb602SLionel Sambuc * | B -> B --> F N |
869*f14fb602SLionel Sambuc * | n -> N --> |
870*f14fb602SLionel Sambuc *
871*f14fb602SLionel Sambuc * If the father is black, we will get an all black
872*f14fb602SLionel Sambuc * tree:
873*f14fb602SLionel Sambuc * | F -> F --> B |
874*f14fb602SLionel Sambuc * | B -> B --> F N |
875*f14fb602SLionel Sambuc * | n -> N --> |
876*f14fb602SLionel Sambuc *
877*f14fb602SLionel Sambuc * If we had two red nephews, then after the swap,
878*f14fb602SLionel Sambuc * our former father would have a red grandson.
8796b6d114aSBen Gras */
880*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(brother));
881*f14fb602SLionel Sambuc KASSERT(RB_RED_P(brother->rb_nodes[other]));
8826b6d114aSBen Gras RB_MARK_BLACK(brother->rb_nodes[other]);
8836b6d114aSBen Gras rb_tree_reparent_nodes(rbt, parent, other);
8846b6d114aSBen Gras break; /* We're done! */
8856b6d114aSBen Gras }
8866b6d114aSBen Gras }
8876b6d114aSBen Gras KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
8886b6d114aSBen Gras }
8896b6d114aSBen Gras
890*f14fb602SLionel Sambuc void *
_prop_rb_tree_iterate(struct rb_tree * rbt,void * object,const unsigned int direction)891*f14fb602SLionel Sambuc _prop_rb_tree_iterate(struct rb_tree *rbt, void *object,
892*f14fb602SLionel Sambuc const unsigned int direction)
8936b6d114aSBen Gras {
894*f14fb602SLionel Sambuc const rb_tree_ops_t *rbto = rbt->rbt_ops;
895*f14fb602SLionel Sambuc const unsigned int other = direction ^ RB_DIR_OTHER;
896*f14fb602SLionel Sambuc struct rb_node *self;
8976b6d114aSBen Gras
898*f14fb602SLionel Sambuc KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
899*f14fb602SLionel Sambuc
900*f14fb602SLionel Sambuc if (object == NULL) {
901*f14fb602SLionel Sambuc #ifndef RBSMALL
902*f14fb602SLionel Sambuc if (RB_SENTINEL_P(rbt->rbt_root))
903*f14fb602SLionel Sambuc return NULL;
904*f14fb602SLionel Sambuc return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
905*f14fb602SLionel Sambuc #else
9066b6d114aSBen Gras self = rbt->rbt_root;
9076b6d114aSBen Gras if (RB_SENTINEL_P(self))
9086b6d114aSBen Gras return NULL;
909*f14fb602SLionel Sambuc while (!RB_SENTINEL_P(self->rb_nodes[direction]))
910*f14fb602SLionel Sambuc self = self->rb_nodes[direction];
911*f14fb602SLionel Sambuc return RB_NODETOITEM(rbto, self);
912*f14fb602SLionel Sambuc #endif /* !RBSMALL */
9136b6d114aSBen Gras }
914*f14fb602SLionel Sambuc self = RB_ITEMTONODE(rbto, object);
9156b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self));
9166b6d114aSBen Gras /*
9176b6d114aSBen Gras * We can't go any further in this direction. We proceed up in the
9186b6d114aSBen Gras * opposite direction until our parent is in direction we want to go.
9196b6d114aSBen Gras */
9206b6d114aSBen Gras if (RB_SENTINEL_P(self->rb_nodes[direction])) {
921*f14fb602SLionel Sambuc while (!RB_ROOT_P(rbt, self)) {
922*f14fb602SLionel Sambuc if (other == RB_POSITION(self))
923*f14fb602SLionel Sambuc return RB_NODETOITEM(rbto, RB_FATHER(self));
924*f14fb602SLionel Sambuc self = RB_FATHER(self);
9256b6d114aSBen Gras }
9266b6d114aSBen Gras return NULL;
9276b6d114aSBen Gras }
9286b6d114aSBen Gras
9296b6d114aSBen Gras /*
9306b6d114aSBen Gras * Advance down one in current direction and go down as far as possible
9316b6d114aSBen Gras * in the opposite direction.
9326b6d114aSBen Gras */
9336b6d114aSBen Gras self = self->rb_nodes[direction];
9346b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self));
9356b6d114aSBen Gras while (!RB_SENTINEL_P(self->rb_nodes[other]))
9366b6d114aSBen Gras self = self->rb_nodes[other];
937*f14fb602SLionel Sambuc return RB_NODETOITEM(rbto, self);
9386b6d114aSBen Gras }
9396b6d114aSBen Gras
9406b6d114aSBen Gras #ifdef RBDEBUG
9416b6d114aSBen Gras static const struct rb_node *
rb_tree_iterate_const(const struct rb_tree * rbt,const struct rb_node * self,const unsigned int direction)9426b6d114aSBen Gras rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
943*f14fb602SLionel Sambuc const unsigned int direction)
9446b6d114aSBen Gras {
945*f14fb602SLionel Sambuc const unsigned int other = direction ^ RB_DIR_OTHER;
946*f14fb602SLionel Sambuc KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
9476b6d114aSBen Gras
9486b6d114aSBen Gras if (self == NULL) {
949*f14fb602SLionel Sambuc #ifndef RBSMALL
950*f14fb602SLionel Sambuc if (RB_SENTINEL_P(rbt->rbt_root))
951*f14fb602SLionel Sambuc return NULL;
952*f14fb602SLionel Sambuc return rbt->rbt_minmax[direction];
953*f14fb602SLionel Sambuc #else
9546b6d114aSBen Gras self = rbt->rbt_root;
9556b6d114aSBen Gras if (RB_SENTINEL_P(self))
9566b6d114aSBen Gras return NULL;
957*f14fb602SLionel Sambuc while (!RB_SENTINEL_P(self->rb_nodes[direction]))
958*f14fb602SLionel Sambuc self = self->rb_nodes[direction];
9596b6d114aSBen Gras return self;
960*f14fb602SLionel Sambuc #endif /* !RBSMALL */
9616b6d114aSBen Gras }
9626b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self));
9636b6d114aSBen Gras /*
9646b6d114aSBen Gras * We can't go any further in this direction. We proceed up in the
9656b6d114aSBen Gras * opposite direction until our parent is in direction we want to go.
9666b6d114aSBen Gras */
9676b6d114aSBen Gras if (RB_SENTINEL_P(self->rb_nodes[direction])) {
968*f14fb602SLionel Sambuc while (!RB_ROOT_P(rbt, self)) {
969*f14fb602SLionel Sambuc if (other == RB_POSITION(self))
970*f14fb602SLionel Sambuc return RB_FATHER(self);
971*f14fb602SLionel Sambuc self = RB_FATHER(self);
9726b6d114aSBen Gras }
9736b6d114aSBen Gras return NULL;
9746b6d114aSBen Gras }
9756b6d114aSBen Gras
9766b6d114aSBen Gras /*
9776b6d114aSBen Gras * Advance down one in current direction and go down as far as possible
9786b6d114aSBen Gras * in the opposite direction.
9796b6d114aSBen Gras */
9806b6d114aSBen Gras self = self->rb_nodes[direction];
9816b6d114aSBen Gras KASSERT(!RB_SENTINEL_P(self));
9826b6d114aSBen Gras while (!RB_SENTINEL_P(self->rb_nodes[other]))
9836b6d114aSBen Gras self = self->rb_nodes[other];
9846b6d114aSBen Gras return self;
9856b6d114aSBen Gras }
9866b6d114aSBen Gras
987*f14fb602SLionel Sambuc static unsigned int
rb_tree_count_black(const struct rb_node * self)988*f14fb602SLionel Sambuc rb_tree_count_black(const struct rb_node *self)
989*f14fb602SLionel Sambuc {
990*f14fb602SLionel Sambuc unsigned int left, right;
991*f14fb602SLionel Sambuc
992*f14fb602SLionel Sambuc if (RB_SENTINEL_P(self))
993*f14fb602SLionel Sambuc return 0;
994*f14fb602SLionel Sambuc
995*f14fb602SLionel Sambuc left = rb_tree_count_black(self->rb_left);
996*f14fb602SLionel Sambuc right = rb_tree_count_black(self->rb_right);
997*f14fb602SLionel Sambuc
998*f14fb602SLionel Sambuc KASSERT(left == right);
999*f14fb602SLionel Sambuc
1000*f14fb602SLionel Sambuc return left + RB_BLACK_P(self);
1001*f14fb602SLionel Sambuc }
1002*f14fb602SLionel Sambuc
10036b6d114aSBen Gras static bool
rb_tree_check_node(const struct rb_tree * rbt,const struct rb_node * self,const struct rb_node * prev,bool red_check)10046b6d114aSBen Gras rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
10056b6d114aSBen Gras const struct rb_node *prev, bool red_check)
10066b6d114aSBen Gras {
1007*f14fb602SLionel Sambuc const rb_tree_ops_t *rbto = rbt->rbt_ops;
1008*f14fb602SLionel Sambuc rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
1009*f14fb602SLionel Sambuc
1010*f14fb602SLionel Sambuc KASSERT(!RB_SENTINEL_P(self));
1011*f14fb602SLionel Sambuc KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
1012*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
10136b6d114aSBen Gras
10146b6d114aSBen Gras /*
10156b6d114aSBen Gras * Verify our relationship to our parent.
10166b6d114aSBen Gras */
1017*f14fb602SLionel Sambuc if (RB_ROOT_P(rbt, self)) {
10186b6d114aSBen Gras KASSERT(self == rbt->rbt_root);
1019*f14fb602SLionel Sambuc KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
1020*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1021*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
10226b6d114aSBen Gras } else {
1023*f14fb602SLionel Sambuc int diff = (*compare_nodes)(rbto->rbto_context,
1024*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, self),
1025*f14fb602SLionel Sambuc RB_NODETOITEM(rbto, RB_FATHER(self)));
1026*f14fb602SLionel Sambuc
10276b6d114aSBen Gras KASSERT(self != rbt->rbt_root);
1028*f14fb602SLionel Sambuc KASSERT(!RB_FATHER_SENTINEL_P(self));
1029*f14fb602SLionel Sambuc if (RB_POSITION(self) == RB_DIR_LEFT) {
1030*f14fb602SLionel Sambuc KASSERT(diff < 0);
1031*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
10326b6d114aSBen Gras } else {
1033*f14fb602SLionel Sambuc KASSERT(diff > 0);
1034*f14fb602SLionel Sambuc KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
10356b6d114aSBen Gras }
10366b6d114aSBen Gras }
10376b6d114aSBen Gras
10386b6d114aSBen Gras /*
10396b6d114aSBen Gras * Verify our position in the linked list against the tree itself.
10406b6d114aSBen Gras */
10416b6d114aSBen Gras {
1042*f14fb602SLionel Sambuc const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1043*f14fb602SLionel Sambuc const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
10446b6d114aSBen Gras KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
10456b6d114aSBen Gras KASSERT(next0 == TAILQ_NEXT(self, rb_link));
1046*f14fb602SLionel Sambuc #ifndef RBSMALL
1047*f14fb602SLionel Sambuc KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
1048*f14fb602SLionel Sambuc KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
1049*f14fb602SLionel Sambuc #endif
10506b6d114aSBen Gras }
10516b6d114aSBen Gras
10526b6d114aSBen Gras /*
10536b6d114aSBen Gras * The root must be black.
10546b6d114aSBen Gras * There can never be two adjacent red nodes.
10556b6d114aSBen Gras */
10566b6d114aSBen Gras if (red_check) {
1057*f14fb602SLionel Sambuc KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
1058*f14fb602SLionel Sambuc (void) rb_tree_count_black(self);
10596b6d114aSBen Gras if (RB_RED_P(self)) {
10606b6d114aSBen Gras const struct rb_node *brother;
1061*f14fb602SLionel Sambuc KASSERT(!RB_ROOT_P(rbt, self));
1062*f14fb602SLionel Sambuc brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
1063*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(RB_FATHER(self)));
10646b6d114aSBen Gras /*
10656b6d114aSBen Gras * I'm red and have no children, then I must either
10666b6d114aSBen Gras * have no brother or my brother also be red and
10676b6d114aSBen Gras * also have no children. (black count == 0)
10686b6d114aSBen Gras */
10696b6d114aSBen Gras KASSERT(!RB_CHILDLESS_P(self)
10706b6d114aSBen Gras || RB_SENTINEL_P(brother)
10716b6d114aSBen Gras || RB_RED_P(brother)
10726b6d114aSBen Gras || RB_CHILDLESS_P(brother));
10736b6d114aSBen Gras /*
10746b6d114aSBen Gras * If I'm not childless, I must have two children
10756b6d114aSBen Gras * and they must be both be black.
10766b6d114aSBen Gras */
10776b6d114aSBen Gras KASSERT(RB_CHILDLESS_P(self)
10786b6d114aSBen Gras || (RB_TWOCHILDREN_P(self)
10796b6d114aSBen Gras && RB_BLACK_P(self->rb_left)
10806b6d114aSBen Gras && RB_BLACK_P(self->rb_right)));
10816b6d114aSBen Gras /*
10826b6d114aSBen Gras * If I'm not childless, thus I have black children,
10836b6d114aSBen Gras * then my brother must either be black or have two
10846b6d114aSBen Gras * black children.
10856b6d114aSBen Gras */
10866b6d114aSBen Gras KASSERT(RB_CHILDLESS_P(self)
10876b6d114aSBen Gras || RB_BLACK_P(brother)
10886b6d114aSBen Gras || (RB_TWOCHILDREN_P(brother)
10896b6d114aSBen Gras && RB_BLACK_P(brother->rb_left)
10906b6d114aSBen Gras && RB_BLACK_P(brother->rb_right)));
10916b6d114aSBen Gras } else {
10926b6d114aSBen Gras /*
10936b6d114aSBen Gras * If I'm black and have one child, that child must
10946b6d114aSBen Gras * be red and childless.
10956b6d114aSBen Gras */
10966b6d114aSBen Gras KASSERT(RB_CHILDLESS_P(self)
10976b6d114aSBen Gras || RB_TWOCHILDREN_P(self)
10986b6d114aSBen Gras || (!RB_LEFT_SENTINEL_P(self)
10996b6d114aSBen Gras && RB_RIGHT_SENTINEL_P(self)
11006b6d114aSBen Gras && RB_RED_P(self->rb_left)
11016b6d114aSBen Gras && RB_CHILDLESS_P(self->rb_left))
11026b6d114aSBen Gras || (!RB_RIGHT_SENTINEL_P(self)
11036b6d114aSBen Gras && RB_LEFT_SENTINEL_P(self)
11046b6d114aSBen Gras && RB_RED_P(self->rb_right)
11056b6d114aSBen Gras && RB_CHILDLESS_P(self->rb_right)));
11066b6d114aSBen Gras
11076b6d114aSBen Gras /*
11086b6d114aSBen Gras * If I'm a childless black node and my parent is
11096b6d114aSBen Gras * black, my 2nd closet relative away from my parent
11106b6d114aSBen Gras * is either red or has a red parent or red children.
11116b6d114aSBen Gras */
1112*f14fb602SLionel Sambuc if (!RB_ROOT_P(rbt, self)
11136b6d114aSBen Gras && RB_CHILDLESS_P(self)
1114*f14fb602SLionel Sambuc && RB_BLACK_P(RB_FATHER(self))) {
1115*f14fb602SLionel Sambuc const unsigned int which = RB_POSITION(self);
1116*f14fb602SLionel Sambuc const unsigned int other = which ^ RB_DIR_OTHER;
11176b6d114aSBen Gras const struct rb_node *relative0, *relative;
11186b6d114aSBen Gras
11196b6d114aSBen Gras relative0 = rb_tree_iterate_const(rbt,
11206b6d114aSBen Gras self, other);
11216b6d114aSBen Gras KASSERT(relative0 != NULL);
11226b6d114aSBen Gras relative = rb_tree_iterate_const(rbt,
11236b6d114aSBen Gras relative0, other);
11246b6d114aSBen Gras KASSERT(relative != NULL);
11256b6d114aSBen Gras KASSERT(RB_SENTINEL_P(relative->rb_nodes[which]));
11266b6d114aSBen Gras #if 0
11276b6d114aSBen Gras KASSERT(RB_RED_P(relative)
11286b6d114aSBen Gras || RB_RED_P(relative->rb_left)
11296b6d114aSBen Gras || RB_RED_P(relative->rb_right)
1130*f14fb602SLionel Sambuc || RB_RED_P(RB_FATHER(relative)));
11316b6d114aSBen Gras #endif
11326b6d114aSBen Gras }
11336b6d114aSBen Gras }
11346b6d114aSBen Gras /*
11356b6d114aSBen Gras * A grandparent's children must be real nodes and not
11366b6d114aSBen Gras * sentinels. First check out grandparent.
11376b6d114aSBen Gras */
1138*f14fb602SLionel Sambuc KASSERT(RB_ROOT_P(rbt, self)
1139*f14fb602SLionel Sambuc || RB_ROOT_P(rbt, RB_FATHER(self))
1140*f14fb602SLionel Sambuc || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
11416b6d114aSBen Gras /*
11426b6d114aSBen Gras * If we are have grandchildren on our left, then
11436b6d114aSBen Gras * we must have a child on our right.
11446b6d114aSBen Gras */
11456b6d114aSBen Gras KASSERT(RB_LEFT_SENTINEL_P(self)
11466b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left)
11476b6d114aSBen Gras || !RB_RIGHT_SENTINEL_P(self));
11486b6d114aSBen Gras /*
11496b6d114aSBen Gras * If we are have grandchildren on our right, then
11506b6d114aSBen Gras * we must have a child on our left.
11516b6d114aSBen Gras */
11526b6d114aSBen Gras KASSERT(RB_RIGHT_SENTINEL_P(self)
11536b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right)
11546b6d114aSBen Gras || !RB_LEFT_SENTINEL_P(self));
11556b6d114aSBen Gras
11566b6d114aSBen Gras /*
11576b6d114aSBen Gras * If we have a child on the left and it doesn't have two
11586b6d114aSBen Gras * children make sure we don't have great-great-grandchildren on
11596b6d114aSBen Gras * the right.
11606b6d114aSBen Gras */
11616b6d114aSBen Gras KASSERT(RB_TWOCHILDREN_P(self->rb_left)
11626b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right)
11636b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_left)
11646b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
11656b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
11666b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_right)
11676b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
11686b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
11696b6d114aSBen Gras
11706b6d114aSBen Gras /*
11716b6d114aSBen Gras * If we have a child on the right and it doesn't have two
11726b6d114aSBen Gras * children make sure we don't have great-great-grandchildren on
11736b6d114aSBen Gras * the left.
11746b6d114aSBen Gras */
11756b6d114aSBen Gras KASSERT(RB_TWOCHILDREN_P(self->rb_right)
11766b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left)
11776b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_left)
11786b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
11796b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
11806b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_right)
11816b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
11826b6d114aSBen Gras || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
11836b6d114aSBen Gras
11846b6d114aSBen Gras /*
11856b6d114aSBen Gras * If we are fully interior node, then our predecessors and
11866b6d114aSBen Gras * successors must have no children in our direction.
11876b6d114aSBen Gras */
11886b6d114aSBen Gras if (RB_TWOCHILDREN_P(self)) {
11896b6d114aSBen Gras const struct rb_node *prev0;
11906b6d114aSBen Gras const struct rb_node *next0;
11916b6d114aSBen Gras
1192*f14fb602SLionel Sambuc prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
11936b6d114aSBen Gras KASSERT(prev0 != NULL);
11946b6d114aSBen Gras KASSERT(RB_RIGHT_SENTINEL_P(prev0));
11956b6d114aSBen Gras
1196*f14fb602SLionel Sambuc next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
11976b6d114aSBen Gras KASSERT(next0 != NULL);
11986b6d114aSBen Gras KASSERT(RB_LEFT_SENTINEL_P(next0));
11996b6d114aSBen Gras }
12006b6d114aSBen Gras }
12016b6d114aSBen Gras
12026b6d114aSBen Gras return true;
12036b6d114aSBen Gras }
12046b6d114aSBen Gras
12056b6d114aSBen Gras void
_prop_rb_tree_check(const struct rb_tree * rbt,bool red_check)12066b6d114aSBen Gras _prop_rb_tree_check(const struct rb_tree *rbt, bool red_check)
12076b6d114aSBen Gras {
12086b6d114aSBen Gras const struct rb_node *self;
12096b6d114aSBen Gras const struct rb_node *prev;
1210*f14fb602SLionel Sambuc #ifdef RBSTATS
1211*f14fb602SLionel Sambuc unsigned int count = 0;
1212*f14fb602SLionel Sambuc #endif
12136b6d114aSBen Gras
1214*f14fb602SLionel Sambuc KASSERT(rbt->rbt_root != NULL);
1215*f14fb602SLionel Sambuc KASSERT(RB_LEFT_P(rbt->rbt_root));
1216*f14fb602SLionel Sambuc
1217*f14fb602SLionel Sambuc #if defined(RBSTATS) && !defined(RBSMALL)
1218*f14fb602SLionel Sambuc KASSERT(rbt->rbt_count > 1
1219*f14fb602SLionel Sambuc || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);
1220*f14fb602SLionel Sambuc #endif
12216b6d114aSBen Gras
12226b6d114aSBen Gras prev = NULL;
12236b6d114aSBen Gras TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
12246b6d114aSBen Gras rb_tree_check_node(rbt, self, prev, false);
1225*f14fb602SLionel Sambuc #ifdef RBSTATS
12266b6d114aSBen Gras count++;
1227*f14fb602SLionel Sambuc #endif
12286b6d114aSBen Gras }
1229*f14fb602SLionel Sambuc #ifdef RBSTATS
12306b6d114aSBen Gras KASSERT(rbt->rbt_count == count);
1231*f14fb602SLionel Sambuc #endif
1232*f14fb602SLionel Sambuc if (red_check) {
1233*f14fb602SLionel Sambuc KASSERT(RB_BLACK_P(rbt->rbt_root));
12346b6d114aSBen Gras KASSERT(RB_SENTINEL_P(rbt->rbt_root)
12356b6d114aSBen Gras || rb_tree_count_black(rbt->rbt_root));
12366b6d114aSBen Gras
12376b6d114aSBen Gras /*
12386b6d114aSBen Gras * The root must be black.
12396b6d114aSBen Gras * There can never be two adjacent red nodes.
12406b6d114aSBen Gras */
12416b6d114aSBen Gras TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
12426b6d114aSBen Gras rb_tree_check_node(rbt, self, NULL, true);
12436b6d114aSBen Gras }
12446b6d114aSBen Gras }
12456b6d114aSBen Gras }
12466b6d114aSBen Gras #endif /* RBDEBUG */
1247*f14fb602SLionel Sambuc
1248*f14fb602SLionel Sambuc #ifdef RBSTATS
1249*f14fb602SLionel Sambuc static void
rb_tree_mark_depth(const struct rb_tree * rbt,const struct rb_node * self,size_t * depths,size_t depth)1250*f14fb602SLionel Sambuc rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
1251*f14fb602SLionel Sambuc size_t *depths, size_t depth)
1252*f14fb602SLionel Sambuc {
1253*f14fb602SLionel Sambuc if (RB_SENTINEL_P(self))
1254*f14fb602SLionel Sambuc return;
1255*f14fb602SLionel Sambuc
1256*f14fb602SLionel Sambuc if (RB_TWOCHILDREN_P(self)) {
1257*f14fb602SLionel Sambuc rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1258*f14fb602SLionel Sambuc rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
1259*f14fb602SLionel Sambuc return;
1260*f14fb602SLionel Sambuc }
1261*f14fb602SLionel Sambuc depths[depth]++;
1262*f14fb602SLionel Sambuc if (!RB_LEFT_SENTINEL_P(self)) {
1263*f14fb602SLionel Sambuc rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1264*f14fb602SLionel Sambuc }
1265*f14fb602SLionel Sambuc if (!RB_RIGHT_SENTINEL_P(self)) {
1266*f14fb602SLionel Sambuc rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
1267*f14fb602SLionel Sambuc }
1268*f14fb602SLionel Sambuc }
1269*f14fb602SLionel Sambuc
1270*f14fb602SLionel Sambuc void
rb_tree_depths(const struct rb_tree * rbt,size_t * depths)1271*f14fb602SLionel Sambuc rb_tree_depths(const struct rb_tree *rbt, size_t *depths)
1272*f14fb602SLionel Sambuc {
1273*f14fb602SLionel Sambuc rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);
1274*f14fb602SLionel Sambuc }
1275*f14fb602SLionel Sambuc #endif /* RBSTATS */
1276