90 rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)  in rb_tree_init()  argument
93 	rbt->rbt_ops = ops;  in rb_tree_init()
94 	rbt->rbt_root = RB_SENTINEL_NODE;  in rb_tree_init()
95 	RB_TAILQ_INIT(&rbt->rbt_nodes);  in rb_tree_init()
97 	rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root;	/* minimum node */  in rb_tree_init()
98 	rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root;	/* maximum node */  in rb_tree_init()
101 	rbt->rbt_count = 0;  in rb_tree_init()
102 	rbt->rbt_insertions = 0;  in rb_tree_init()
103 	rbt->rbt_removals = 0;  in rb_tree_init()
104 	rbt->rbt_insertion_rebalance_calls = 0;  in rb_tree_init()
105 	rbt->rbt_insertion_rebalance_passes = 0;  in rb_tree_init()
106 	rbt->rbt_removal_rebalance_calls = 0;  in rb_tree_init()
107 	rbt->rbt_removal_rebalance_passes = 0;  in rb_tree_init()
112 rb_tree_find_node(struct rb_tree *rbt, const void *key)  in rb_tree_find_node()  argument
114 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node()
116 	struct rb_node *parent = rbt->rbt_root;  in rb_tree_find_node()
131 rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)  in rb_tree_find_node_geq()  argument
133 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node_geq()
135 	struct rb_node *parent = rbt->rbt_root, *last = NULL;  in rb_tree_find_node_geq()
152 rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)  in rb_tree_find_node_leq()  argument
154 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node_leq()
156 	struct rb_node *parent = rbt->rbt_root, *last = NULL;  in rb_tree_find_node_leq()
173 rb_tree_insert_node(struct rb_tree *rbt, void *object)  in rb_tree_insert_node()  argument
175 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_insert_node()
181 	RBSTAT_INC(rbt->rbt_insertions);  in rb_tree_insert_node()
183 	tmp = rbt->rbt_root;  in rb_tree_insert_node()
191 	parent = (struct rb_node *)(void *)&rbt->rbt_root;  in rb_tree_insert_node()
218 		else if (tmp != rbt->rbt_root)  in rb_tree_insert_node()
244 	if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {  in rb_tree_insert_node()
247 		rbt->rbt_minmax[RB_DIR_LEFT] = self;  in rb_tree_insert_node()
248 		rbt->rbt_minmax[RB_DIR_RIGHT] = self;  in rb_tree_insert_node()
259 		if (parent == rbt->rbt_minmax[position])  in rb_tree_insert_node()
260 			rbt->rbt_minmax[position] = self;  in rb_tree_insert_node()
278 	RBSTAT_INC(rbt->rbt_count);  in rb_tree_insert_node()
280 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_insert_node()
281 		RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);  in rb_tree_insert_node()
291 		RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),  in rb_tree_insert_node()
295 	KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));  in rb_tree_insert_node()
301 		rb_tree_insert_rebalance(rbt, self);  in rb_tree_insert_node()
302 		KASSERT(rb_tree_check_node(rbt, self, NULL, true));  in rb_tree_insert_node()
318 rb_tree_reparent_nodes(struct rb_tree *rbt, struct rb_node *old_father,  in rb_tree_reparent_nodes()  argument
332 	KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));  in rb_tree_reparent_nodes()
333 	KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));  in rb_tree_reparent_nodes()
334 	KASSERT(RB_ROOT_P(rbt, old_father) ||  in rb_tree_reparent_nodes()
335 	    rb_tree_check_node(rbt, grandpa, NULL, false));  in rb_tree_reparent_nodes()
375 	KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));  in rb_tree_reparent_nodes()
376 	KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));  in rb_tree_reparent_nodes()
377 	KASSERT(RB_ROOT_P(rbt, new_father) ||  in rb_tree_reparent_nodes()
378 	    rb_tree_check_node(rbt, grandpa, NULL, false));  in rb_tree_reparent_nodes()
382 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)  in rb_tree_insert_rebalance()  argument
390 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
393 	RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);  in rb_tree_insert_rebalance()
414 		RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);  in rb_tree_insert_rebalance()
423 		if (__predict_false(RB_ROOT_P(rbt, grandpa))) {  in rb_tree_insert_rebalance()
439 			KASSERT(RB_BLACK_P(rbt->rbt_root));  in rb_tree_insert_rebalance()
444 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
459 		rb_tree_reparent_nodes(rbt, father, other);  in rb_tree_insert_rebalance()
474 	rb_tree_reparent_nodes(rbt, grandpa, which);  in rb_tree_insert_rebalance()
484 	RB_MARK_BLACK(rbt->rbt_root);  in rb_tree_insert_rebalance()
488 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)  in rb_tree_prune_node()  argument
493 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_node()
496 	KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));  in rb_tree_prune_node()
499 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_node()
511 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_node()
512 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_prune_node()
514 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {  in rb_tree_prune_node()
515 		rbt->rbt_minmax[RB_POSITION(self)] = father;  in rb_tree_prune_node()
522 			rbt->rbt_minmax[RB_DIR_RIGHT] = father;  in rb_tree_prune_node()
532 		rb_tree_removal_rebalance(rbt, father, which);  in rb_tree_prune_node()
533 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));  in rb_tree_prune_node()
540 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_swap_prune_and_rebalance()  argument
577 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_swap_prune_and_rebalance()
578 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));  in rb_tree_swap_prune_and_rebalance()
585 		KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));  in rb_tree_swap_prune_and_rebalance()
662 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_swap_prune_and_rebalance()
663 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_swap_prune_and_rebalance()
665 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))  in rb_tree_swap_prune_and_rebalance()
666 		rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);  in rb_tree_swap_prune_and_rebalance()
670 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));  in rb_tree_swap_prune_and_rebalance()
672 		|| rb_tree_check_node(rbt, standin_father, NULL, false));  in rb_tree_swap_prune_and_rebalance()
674 		|| rb_tree_check_node(rbt, standin->rb_left, NULL, false));  in rb_tree_swap_prune_and_rebalance()
676 		|| rb_tree_check_node(rbt, standin->rb_right, NULL, false));  in rb_tree_swap_prune_and_rebalance()
681 	rb_tree_removal_rebalance(rbt, standin_father, standin_which);  in rb_tree_swap_prune_and_rebalance()
682 	KASSERT(rb_tree_check_node(rbt, standin, NULL, true));  in rb_tree_swap_prune_and_rebalance()
693 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_prune_blackred_branch()  argument
699 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_blackred_branch()
706 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_blackred_branch()
707 	KASSERT(rb_tree_check_node(rbt, son, NULL, false));  in rb_tree_prune_blackred_branch()
721 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_blackred_branch()
722 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_prune_blackred_branch()
725 		KASSERT(rbt->rbt_minmax[which] == son);  in rb_tree_prune_blackred_branch()
726 		rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;  in rb_tree_prune_blackred_branch()
727 	} else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {  in rb_tree_prune_blackred_branch()
728 		rbt->rbt_minmax[RB_POSITION(self)] = son;  in rb_tree_prune_blackred_branch()
733 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));  in rb_tree_prune_blackred_branch()
734 	KASSERT(rb_tree_check_node(rbt, son, NULL, true));  in rb_tree_prune_blackred_branch()
738 rb_tree_remove_node(struct rb_tree *rbt, void *object)  in rb_tree_remove_node()  argument
740 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_remove_node()
745 	RBSTAT_INC(rbt->rbt_removals);  in rb_tree_remove_node()
765 		const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);  in rb_tree_remove_node()
766 		rb_tree_prune_node(rbt, self, rebalance);  in rb_tree_remove_node()
783 		rb_tree_prune_blackred_branch(rbt, self, which);  in rb_tree_remove_node()
798 	standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));  in rb_tree_remove_node()
799 	rb_tree_swap_prune_and_rebalance(rbt, self, standin);  in rb_tree_remove_node()
803 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,  in rb_tree_removal_rebalance()  argument
809 	RBSTAT_INC(rbt->rbt_removal_rebalance_calls);  in rb_tree_removal_rebalance()
815 		RBSTAT_INC(rbt->rbt_removal_rebalance_passes);  in rb_tree_removal_rebalance()
838 				rb_tree_reparent_nodes(rbt, parent, other);  in rb_tree_removal_rebalance()
843 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));  in rb_tree_removal_rebalance()
844 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));  in rb_tree_removal_rebalance()
858 				if (RB_ROOT_P(rbt, parent))  in rb_tree_removal_rebalance()
860 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));  in rb_tree_removal_rebalance()
861 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));  in rb_tree_removal_rebalance()
891 			KASSERT(rb_tree_check_node(rbt, brother, NULL, true));  in rb_tree_removal_rebalance()
914 				rb_tree_reparent_nodes(rbt, brother, which);  in rb_tree_removal_rebalance()
946 			rb_tree_reparent_nodes(rbt, parent, other);  in rb_tree_removal_rebalance()
950 	KASSERT(rb_tree_check_node(rbt, parent, NULL, true));  in rb_tree_removal_rebalance()
954 rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)  in rb_tree_iterate()  argument
956 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_iterate()
964 		if (RB_SENTINEL_P(rbt->rbt_root))  in rb_tree_iterate()
966 		return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);  in rb_tree_iterate()
968 		self = rbt->rbt_root;  in rb_tree_iterate()
983 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate()
1004 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_iterate_const()  argument
1012 		if (RB_SENTINEL_P(rbt->rbt_root))  in rb_tree_iterate_const()
1014 		return rbt->rbt_minmax[direction];  in rb_tree_iterate_const()
1016 		self = rbt->rbt_root;  in rb_tree_iterate_const()
1030 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate_const()
1066 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_check_node()  argument
1069 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_check_node()
1079 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_check_node()
1080 		KASSERT(self == rbt->rbt_root);  in rb_tree_check_node()
1083 		KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);  in rb_tree_check_node()
1089 		KASSERT(self != rbt->rbt_root);  in rb_tree_check_node()
1104 		const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1105 		const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1109 		KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);  in rb_tree_check_node()
1110 		KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);  in rb_tree_check_node()
1119 		KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));  in rb_tree_check_node()
1123 			KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_check_node()
1174 			if (!RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1181 				relative0 = rb_tree_iterate_const(rbt,  in rb_tree_check_node()
1184 				relative = rb_tree_iterate_const(rbt,  in rb_tree_check_node()
1200 		KASSERT(RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1201 			|| RB_ROOT_P(rbt, RB_FATHER(self))  in rb_tree_check_node()
1254 			prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1258 			next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1268 rb_tree_check(const struct rb_tree *rbt, bool red_check)  in rb_tree_check()  argument
1276 	KASSERT(rbt->rbt_root != NULL);  in rb_tree_check()
1277 	KASSERT(RB_LEFT_P(rbt->rbt_root));  in rb_tree_check()
1280 	KASSERT(rbt->rbt_count > 1  in rb_tree_check()
1281 	    || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);  in rb_tree_check()
1285 	TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1286 		rb_tree_check_node(rbt, self, prev, false);  in rb_tree_check()
1292 	KASSERT(rbt->rbt_count == count);  in rb_tree_check()
1295 		KASSERT(RB_BLACK_P(rbt->rbt_root));  in rb_tree_check()
1296 		KASSERT(RB_SENTINEL_P(rbt->rbt_root)  in rb_tree_check()
1297 			|| rb_tree_count_black(rbt->rbt_root));  in rb_tree_check()
1303 		TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1304 			rb_tree_check_node(rbt, self, NULL, true);  in rb_tree_check()
1312 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_mark_depth()  argument
1319 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1320 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()
1325 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1328 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()
1333 rb_tree_depths(const struct rb_tree *rbt, size_t *depths)  in rb_tree_depths()  argument
1335 	rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);  in rb_tree_depths()