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