100 rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)  in rb_tree_init()  argument
103 	rbt->rbt_ops = ops;  in rb_tree_init()
104 	rbt->rbt_root = RB_SENTINEL_NODE;  in rb_tree_init()
105 	RB_TAILQ_INIT(&rbt->rbt_nodes);  in rb_tree_init()
107 	rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root;	/* minimum node */  in rb_tree_init()
108 	rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root;	/* maximum node */  in rb_tree_init()
111 	rbt->rbt_count = 0;  in rb_tree_init()
112 	rbt->rbt_insertions = 0;  in rb_tree_init()
113 	rbt->rbt_removals = 0;  in rb_tree_init()
114 	rbt->rbt_insertion_rebalance_calls = 0;  in rb_tree_init()
115 	rbt->rbt_insertion_rebalance_passes = 0;  in rb_tree_init()
116 	rbt->rbt_removal_rebalance_calls = 0;  in rb_tree_init()
117 	rbt->rbt_removal_rebalance_passes = 0;  in rb_tree_init()
122 rb_tree_find_node(struct rb_tree *rbt, const void *key)  in rb_tree_find_node()  argument
124 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node()
126 	struct rb_node *parent = rbt->rbt_root;  in rb_tree_find_node()
141 rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)  in rb_tree_find_node_geq()  argument
143 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node_geq()
145 	struct rb_node *parent = rbt->rbt_root, *last = NULL;  in rb_tree_find_node_geq()
162 rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)  in rb_tree_find_node_leq()  argument
164 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_find_node_leq()
166 	struct rb_node *parent = rbt->rbt_root, *last = NULL;  in rb_tree_find_node_leq()
183 rb_tree_insert_node(struct rb_tree *rbt, void *object)  in rb_tree_insert_node()  argument
185 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_insert_node()
191 	RBSTAT_INC(rbt->rbt_insertions);  in rb_tree_insert_node()
193 	tmp = rbt->rbt_root;  in rb_tree_insert_node()
201 	parent = (struct rb_node *)(void *)&rbt->rbt_root;  in rb_tree_insert_node()
228 		else if (tmp != rbt->rbt_root)  in rb_tree_insert_node()
254 	if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {  in rb_tree_insert_node()
257 		rbt->rbt_minmax[RB_DIR_LEFT] = self;  in rb_tree_insert_node()
258 		rbt->rbt_minmax[RB_DIR_RIGHT] = self;  in rb_tree_insert_node()
269 		if (parent == rbt->rbt_minmax[position])  in rb_tree_insert_node()
270 			rbt->rbt_minmax[position] = self;  in rb_tree_insert_node()
288 	RBSTAT_INC(rbt->rbt_count);  in rb_tree_insert_node()
290 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_insert_node()
291 		RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);  in rb_tree_insert_node()
301 		RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),  in rb_tree_insert_node()
305 	KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));  in rb_tree_insert_node()
311 		rb_tree_insert_rebalance(rbt, self);  in rb_tree_insert_node()
312 		KASSERT(rb_tree_check_node(rbt, self, NULL, true));  in rb_tree_insert_node()
327 rb_tree_reparent_nodes(__rbt_unused struct rb_tree *rbt,  in rb_tree_reparent_nodes()  argument
341 	KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));  in rb_tree_reparent_nodes()
342 	KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));  in rb_tree_reparent_nodes()
343 	KASSERT(RB_ROOT_P(rbt, old_father) ||  in rb_tree_reparent_nodes()
344 	    rb_tree_check_node(rbt, grandpa, NULL, false));  in rb_tree_reparent_nodes()
384 	KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));  in rb_tree_reparent_nodes()
385 	KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));  in rb_tree_reparent_nodes()
386 	KASSERT(RB_ROOT_P(rbt, new_father) ||  in rb_tree_reparent_nodes()
387 	    rb_tree_check_node(rbt, grandpa, NULL, false));  in rb_tree_reparent_nodes()
391 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)  in rb_tree_insert_rebalance()  argument
399 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
402 	RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);  in rb_tree_insert_rebalance()
423 		RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);  in rb_tree_insert_rebalance()
432 		if (__predict_false(RB_ROOT_P(rbt, grandpa))) {  in rb_tree_insert_rebalance()
448 			KASSERT(RB_BLACK_P(rbt->rbt_root));  in rb_tree_insert_rebalance()
453 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
468 		rb_tree_reparent_nodes(rbt, father, other);  in rb_tree_insert_rebalance()
483 	rb_tree_reparent_nodes(rbt, grandpa, which);  in rb_tree_insert_rebalance()
493 	RB_MARK_BLACK(rbt->rbt_root);  in rb_tree_insert_rebalance()
497 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)  in rb_tree_prune_node()  argument
502 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_node()
505 	KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));  in rb_tree_prune_node()
508 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_node()
520 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_node()
521 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_prune_node()
523 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {  in rb_tree_prune_node()
524 		rbt->rbt_minmax[RB_POSITION(self)] = father;  in rb_tree_prune_node()
531 			rbt->rbt_minmax[RB_DIR_RIGHT] = father;  in rb_tree_prune_node()
541 		rb_tree_removal_rebalance(rbt, father, which);  in rb_tree_prune_node()
542 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));  in rb_tree_prune_node()
549 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_swap_prune_and_rebalance()  argument
586 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_swap_prune_and_rebalance()
587 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));  in rb_tree_swap_prune_and_rebalance()
594 		KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));  in rb_tree_swap_prune_and_rebalance()
671 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_swap_prune_and_rebalance()
672 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_swap_prune_and_rebalance()
674 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))  in rb_tree_swap_prune_and_rebalance()
675 		rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);  in rb_tree_swap_prune_and_rebalance()
679 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));  in rb_tree_swap_prune_and_rebalance()
681 		|| rb_tree_check_node(rbt, standin_father, NULL, false));  in rb_tree_swap_prune_and_rebalance()
683 		|| rb_tree_check_node(rbt, standin->rb_left, NULL, false));  in rb_tree_swap_prune_and_rebalance()
685 		|| rb_tree_check_node(rbt, standin->rb_right, NULL, false));  in rb_tree_swap_prune_and_rebalance()
690 	rb_tree_removal_rebalance(rbt, standin_father, standin_which);  in rb_tree_swap_prune_and_rebalance()
691 	KASSERT(rb_tree_check_node(rbt, standin, NULL, true));  in rb_tree_swap_prune_and_rebalance()
702 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_prune_blackred_branch()  argument
708 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_blackred_branch()
715 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_blackred_branch()
716 	KASSERT(rb_tree_check_node(rbt, son, NULL, false));  in rb_tree_prune_blackred_branch()
730 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_blackred_branch()
731 	RBSTAT_DEC(rbt->rbt_count);  in rb_tree_prune_blackred_branch()
734 		KASSERT(rbt->rbt_minmax[which] == son);  in rb_tree_prune_blackred_branch()
735 		rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;  in rb_tree_prune_blackred_branch()
736 	} else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {  in rb_tree_prune_blackred_branch()
737 		rbt->rbt_minmax[RB_POSITION(self)] = son;  in rb_tree_prune_blackred_branch()
742 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));  in rb_tree_prune_blackred_branch()
743 	KASSERT(rb_tree_check_node(rbt, son, NULL, true));  in rb_tree_prune_blackred_branch()
747 rb_tree_remove_node(struct rb_tree *rbt, void *object)  in rb_tree_remove_node()  argument
749 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_remove_node()
754 	RBSTAT_INC(rbt->rbt_removals);  in rb_tree_remove_node()
774 		const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);  in rb_tree_remove_node()
775 		rb_tree_prune_node(rbt, self, rebalance);  in rb_tree_remove_node()
792 		rb_tree_prune_blackred_branch(rbt, self, which);  in rb_tree_remove_node()
807 	standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));  in rb_tree_remove_node()
808 	rb_tree_swap_prune_and_rebalance(rbt, self, standin);  in rb_tree_remove_node()
812 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,  in rb_tree_removal_rebalance()  argument
818 	RBSTAT_INC(rbt->rbt_removal_rebalance_calls);  in rb_tree_removal_rebalance()
824 		RBSTAT_INC(rbt->rbt_removal_rebalance_passes);  in rb_tree_removal_rebalance()
847 				rb_tree_reparent_nodes(rbt, parent, other);  in rb_tree_removal_rebalance()
852 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));  in rb_tree_removal_rebalance()
853 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));  in rb_tree_removal_rebalance()
867 				if (RB_ROOT_P(rbt, parent))  in rb_tree_removal_rebalance()
869 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));  in rb_tree_removal_rebalance()
870 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));  in rb_tree_removal_rebalance()
900 			KASSERT(rb_tree_check_node(rbt, brother, NULL, true));  in rb_tree_removal_rebalance()
923 				rb_tree_reparent_nodes(rbt, brother, which);  in rb_tree_removal_rebalance()
955 			rb_tree_reparent_nodes(rbt, parent, other);  in rb_tree_removal_rebalance()
959 	KASSERT(rb_tree_check_node(rbt, parent, NULL, true));  in rb_tree_removal_rebalance()
963 rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)  in rb_tree_iterate()  argument
965 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_iterate()
973 		if (RB_SENTINEL_P(rbt->rbt_root))  in rb_tree_iterate()
975 		return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);  in rb_tree_iterate()
977 		self = rbt->rbt_root;  in rb_tree_iterate()
992 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate()
1013 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_iterate_const()  argument
1021 		if (RB_SENTINEL_P(rbt->rbt_root))  in rb_tree_iterate_const()
1023 		return rbt->rbt_minmax[direction];  in rb_tree_iterate_const()
1025 		self = rbt->rbt_root;  in rb_tree_iterate_const()
1039 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate_const()
1075 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_check_node()  argument
1078 	const rb_tree_ops_t *rbto = rbt->rbt_ops;  in rb_tree_check_node()
1088 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_check_node()
1089 		KASSERT(self == rbt->rbt_root);  in rb_tree_check_node()
1092 		KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);  in rb_tree_check_node()
1098 		KASSERT(self != rbt->rbt_root);  in rb_tree_check_node()
1113 		const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1114 		const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1118 		KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);  in rb_tree_check_node()
1119 		KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);  in rb_tree_check_node()
1128 		KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));  in rb_tree_check_node()
1132 			KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_check_node()
1183 			if (!RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1190 				relative0 = rb_tree_iterate_const(rbt,  in rb_tree_check_node()
1193 				relative = rb_tree_iterate_const(rbt,  in rb_tree_check_node()
1209 		KASSERT(RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1210 			|| RB_ROOT_P(rbt, RB_FATHER(self))  in rb_tree_check_node()
1263 			prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1267 			next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1277 rb_tree_check(const struct rb_tree *rbt, bool red_check)  in rb_tree_check()  argument
1285 	KASSERT(rbt->rbt_root != NULL);  in rb_tree_check()
1286 	KASSERT(RB_LEFT_P(rbt->rbt_root));  in rb_tree_check()
1289 	KASSERT(rbt->rbt_count > 1  in rb_tree_check()
1290 	    || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);  in rb_tree_check()
1294 	TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1295 		rb_tree_check_node(rbt, self, prev, false);  in rb_tree_check()
1301 	KASSERT(rbt->rbt_count == count);  in rb_tree_check()
1304 		KASSERT(RB_BLACK_P(rbt->rbt_root));  in rb_tree_check()
1305 		KASSERT(RB_SENTINEL_P(rbt->rbt_root)  in rb_tree_check()
1306 			|| rb_tree_count_black(rbt->rbt_root));  in rb_tree_check()
1312 		TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1313 			rb_tree_check_node(rbt, self, NULL, true);  in rb_tree_check()
1321 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_mark_depth()  argument
1328 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1329 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()
1334 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1337 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()
1342 rb_tree_depths(const struct rb_tree *rbt, size_t *depths)  in rb_tree_depths()  argument
1344 	rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);  in rb_tree_depths()