191 	struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);  in rb_tree_insert_node()  local
247 		    RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);  in rb_tree_insert_node()
249 		    RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);  in rb_tree_insert_node()
256 	RB_SET_FATHER(self, parent);  in rb_tree_insert_node()
257 	RB_SET_POSITION(self, position);  in rb_tree_insert_node()
259 		RB_MARK_BLACK(self);		/* root is always black */  in rb_tree_insert_node()
261 		rbt->rbt_minmax[RB_DIR_LEFT] = self;  in rb_tree_insert_node()
262 		rbt->rbt_minmax[RB_DIR_RIGHT] = self;  in rb_tree_insert_node()
274 			rbt->rbt_minmax[position] = self;  in rb_tree_insert_node()
280 		RB_MARK_RED(self);  in rb_tree_insert_node()
284 	self->rb_left = parent->rb_nodes[position];  in rb_tree_insert_node()
285 	self->rb_right = parent->rb_nodes[position];  in rb_tree_insert_node()
286 	parent->rb_nodes[position] = self;  in rb_tree_insert_node()
287 	KASSERT(RB_CHILDLESS_P(self));  in rb_tree_insert_node()
294 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_insert_node()
295 		RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);  in rb_tree_insert_node()
298 		    RB_NODETOITEM(rbto, self),  in rb_tree_insert_node()
299 		    RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);  in rb_tree_insert_node()
300 		RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);  in rb_tree_insert_node()
303 		    RB_NODETOITEM(rbto, RB_FATHER(self)),  in rb_tree_insert_node()
304 		    RB_NODETOITEM(rbto, self)) < 0);  in rb_tree_insert_node()
305 		RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),  in rb_tree_insert_node()
306 		    self, rb_link);  in rb_tree_insert_node()
309 	KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));  in rb_tree_insert_node()
315 		rb_tree_insert_rebalance(rbt, self);  in rb_tree_insert_node()
316 		KASSERT(rb_tree_check_node(rbt, self, NULL, true));  in rb_tree_insert_node()
395 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)  in rb_tree_insert_rebalance()  argument
397 	struct rb_node * father = RB_FATHER(self);  in rb_tree_insert_rebalance()
403 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
404 	KASSERT(RB_RED_P(self));  in rb_tree_insert_rebalance()
409 		KASSERT(!RB_SENTINEL_P(self));  in rb_tree_insert_rebalance()
411 		KASSERT(RB_RED_P(self));  in rb_tree_insert_rebalance()
445 		self = grandpa;  in rb_tree_insert_rebalance()
446 		father = RB_FATHER(self);  in rb_tree_insert_rebalance()
447 		KASSERT(RB_RED_P(self));  in rb_tree_insert_rebalance()
457 	KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_insert_rebalance()
458 	KASSERT(RB_RED_P(self));  in rb_tree_insert_rebalance()
465 	if (self == father->rb_nodes[other]) {  in rb_tree_insert_rebalance()
473 		KASSERT(RB_FATHER(father) == self);  in rb_tree_insert_rebalance()
474 		KASSERT(self->rb_nodes[which] == father);  in rb_tree_insert_rebalance()
475 		KASSERT(RB_FATHER(self) == grandpa);  in rb_tree_insert_rebalance()
476 		self = father;  in rb_tree_insert_rebalance()
477 		father = RB_FATHER(self);  in rb_tree_insert_rebalance()
479 	KASSERT(RB_RED_P(self) && RB_RED_P(father));  in rb_tree_insert_rebalance()
488 	KASSERT(RB_FATHER(self) == father);  in rb_tree_insert_rebalance()
489 	KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);  in rb_tree_insert_rebalance()
490 	KASSERT(RB_RED_P(self));  in rb_tree_insert_rebalance()
501 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)  in rb_tree_prune_node()  argument
503 	const unsigned int which = RB_POSITION(self);  in rb_tree_prune_node()
504 	struct rb_node *father = RB_FATHER(self);  in rb_tree_prune_node()
506 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_node()
509 	KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));  in rb_tree_prune_node()
510 	KASSERT(!rebalance || RB_BLACK_P(self));  in rb_tree_prune_node()
511 	KASSERT(RB_CHILDLESS_P(self));  in rb_tree_prune_node()
512 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_node()
518 	father->rb_nodes[which] = self->rb_left;  in rb_tree_prune_node()
524 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_node()
527 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {  in rb_tree_prune_node()
528 		rbt->rbt_minmax[RB_POSITION(self)] = father;  in rb_tree_prune_node()
538 	RB_SET_FATHER(self, NULL);  in rb_tree_prune_node()
553 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_swap_prune_and_rebalance()  argument
562 	if (standin_father == self) {  in rb_tree_swap_prune_and_rebalance()
581 	KASSERT(RB_TWOCHILDREN_P(self));  in rb_tree_swap_prune_and_rebalance()
590 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_swap_prune_and_rebalance()
602 		if (standin_father == self) {  in rb_tree_swap_prune_and_rebalance()
614 	if (standin_father == self) {  in rb_tree_swap_prune_and_rebalance()
627 		KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));  in rb_tree_swap_prune_and_rebalance()
628 		KASSERT(self->rb_nodes[standin_which] == standin);  in rb_tree_swap_prune_and_rebalance()
645 		standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];  in rb_tree_swap_prune_and_rebalance()
647 		KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);  in rb_tree_swap_prune_and_rebalance()
659 	KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);  in rb_tree_swap_prune_and_rebalance()
660 	standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];  in rb_tree_swap_prune_and_rebalance()
667 	RB_COPY_PROPERTIES(standin, self);  in rb_tree_swap_prune_and_rebalance()
668 	RB_SET_FATHER(standin, RB_FATHER(self));  in rb_tree_swap_prune_and_rebalance()
675 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_swap_prune_and_rebalance()
678 	if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))  in rb_tree_swap_prune_and_rebalance()
679 		rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);  in rb_tree_swap_prune_and_rebalance()
680 	RB_SET_FATHER(self, NULL);  in rb_tree_swap_prune_and_rebalance()
706 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,  in rb_tree_prune_blackred_branch()  argument
709 	struct rb_node *father = RB_FATHER(self);  in rb_tree_prune_blackred_branch()
710 	struct rb_node *son = self->rb_nodes[which];  in rb_tree_prune_blackred_branch()
712 	const bool was_root = RB_ROOT_P(rbt, self);  in rb_tree_prune_blackred_branch()
716 	KASSERT(RB_BLACK_P(self) && RB_RED_P(son));  in rb_tree_prune_blackred_branch()
719 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));  in rb_tree_prune_blackred_branch()
726 	RB_COPY_PROPERTIES(son, self);  in rb_tree_prune_blackred_branch()
734 	RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);  in rb_tree_prune_blackred_branch()
740 	} else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {  in rb_tree_prune_blackred_branch()
741 		rbt->rbt_minmax[RB_POSITION(self)] = son;  in rb_tree_prune_blackred_branch()
743 	RB_SET_FATHER(self, NULL);  in rb_tree_prune_blackred_branch()
754 	struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);  in rb_tree_remove_node()  local
757 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_remove_node()
777 	if (RB_CHILDLESS_P(self)) {  in rb_tree_remove_node()
778 		const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);  in rb_tree_remove_node()
779 		rb_tree_prune_node(rbt, self, rebalance);  in rb_tree_remove_node()
782 	KASSERT(!RB_CHILDLESS_P(self));  in rb_tree_remove_node()
783 	if (!RB_TWOCHILDREN_P(self)) {  in rb_tree_remove_node()
792 		which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;  in rb_tree_remove_node()
793 		KASSERT(RB_BLACK_P(self));  in rb_tree_remove_node()
794 		KASSERT(RB_RED_P(self->rb_nodes[which]));  in rb_tree_remove_node()
795 		KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));  in rb_tree_remove_node()
796 		rb_tree_prune_blackred_branch(rbt, self, which);  in rb_tree_remove_node()
799 	KASSERT(RB_TWOCHILDREN_P(self));  in rb_tree_remove_node()
805 	which = RB_POSITION(self) ^ RB_DIR_OTHER;  in rb_tree_remove_node()
812 	rb_tree_swap_prune_and_rebalance(rbt, self, standin);  in rb_tree_remove_node()
971 	struct rb_node *self;  in rb_tree_iterate()  local
981 		self = rbt->rbt_root;  in rb_tree_iterate()
982 		if (RB_SENTINEL_P(self))  in rb_tree_iterate()
984 		while (!RB_SENTINEL_P(self->rb_nodes[direction]))  in rb_tree_iterate()
985 			self = self->rb_nodes[direction];  in rb_tree_iterate()
986 		return RB_NODETOITEM(rbto, self);  in rb_tree_iterate()
989 	self = RB_ITEMTONODE(rbto, object);  in rb_tree_iterate()
990 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_iterate()
995 	if (RB_SENTINEL_P(self->rb_nodes[direction])) {  in rb_tree_iterate()
996 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate()
997 			if (other == RB_POSITION(self))  in rb_tree_iterate()
998 				return RB_NODETOITEM(rbto, RB_FATHER(self));  in rb_tree_iterate()
999 			self = RB_FATHER(self);  in rb_tree_iterate()
1008 	self = self->rb_nodes[direction];  in rb_tree_iterate()
1009 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_iterate()
1010 	while (!RB_SENTINEL_P(self->rb_nodes[other]))  in rb_tree_iterate()
1011 		self = self->rb_nodes[other];  in rb_tree_iterate()
1012 	return RB_NODETOITEM(rbto, self);  in rb_tree_iterate()
1017 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_iterate_const()  argument
1023 	if (self == NULL) {  in rb_tree_iterate_const()
1029 		self = rbt->rbt_root;  in rb_tree_iterate_const()
1030 		if (RB_SENTINEL_P(self))  in rb_tree_iterate_const()
1032 		while (!RB_SENTINEL_P(self->rb_nodes[direction]))  in rb_tree_iterate_const()
1033 			self = self->rb_nodes[direction];  in rb_tree_iterate_const()
1034 		return self;  in rb_tree_iterate_const()
1037 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_iterate_const()
1042 	if (RB_SENTINEL_P(self->rb_nodes[direction])) {  in rb_tree_iterate_const()
1043 		while (!RB_ROOT_P(rbt, self)) {  in rb_tree_iterate_const()
1044 			if (other == RB_POSITION(self))  in rb_tree_iterate_const()
1045 				return RB_FATHER(self);  in rb_tree_iterate_const()
1046 			self = RB_FATHER(self);  in rb_tree_iterate_const()
1055 	self = self->rb_nodes[direction];  in rb_tree_iterate_const()
1056 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_iterate_const()
1057 	while (!RB_SENTINEL_P(self->rb_nodes[other]))  in rb_tree_iterate_const()
1058 		self = self->rb_nodes[other];  in rb_tree_iterate_const()
1059 	return self;  in rb_tree_iterate_const()
1063 rb_tree_count_black(const struct rb_node *self)  in rb_tree_count_black()  argument
1067 	if (RB_SENTINEL_P(self))  in rb_tree_count_black()
1070 	left = rb_tree_count_black(self->rb_left);  in rb_tree_count_black()
1071 	right = rb_tree_count_black(self->rb_right);  in rb_tree_count_black()
1075 	return left + RB_BLACK_P(self);  in rb_tree_count_black()
1079 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_check_node()  argument
1085 	KASSERT(!RB_SENTINEL_P(self));  in rb_tree_check_node()
1087 	    RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);  in rb_tree_check_node()
1092 	if (RB_ROOT_P(rbt, self)) {  in rb_tree_check_node()
1093 		KASSERT(self == rbt->rbt_root);  in rb_tree_check_node()
1094 		KASSERT(RB_POSITION(self) == RB_DIR_LEFT);  in rb_tree_check_node()
1095 		KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);  in rb_tree_check_node()
1096 		KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);  in rb_tree_check_node()
1099 		    RB_NODETOITEM(rbto, self),  in rb_tree_check_node()
1100 		    RB_NODETOITEM(rbto, RB_FATHER(self)));  in rb_tree_check_node()
1102 		KASSERT(self != rbt->rbt_root);  in rb_tree_check_node()
1103 		KASSERT(!RB_FATHER_SENTINEL_P(self));  in rb_tree_check_node()
1104 		if (RB_POSITION(self) == RB_DIR_LEFT) {  in rb_tree_check_node()
1106 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);  in rb_tree_check_node()
1109 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);  in rb_tree_check_node()
1117 		const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1118 		const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1119 		KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));  in rb_tree_check_node()
1120 		KASSERT(next0 == TAILQ_NEXT(self, rb_link));  in rb_tree_check_node()
1122 		KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);  in rb_tree_check_node()
1123 		KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);  in rb_tree_check_node()
1132 		KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));  in rb_tree_check_node()
1133 		(void) rb_tree_count_black(self);  in rb_tree_check_node()
1134 		if (RB_RED_P(self)) {  in rb_tree_check_node()
1136 			KASSERT(!RB_ROOT_P(rbt, self));  in rb_tree_check_node()
1137 			brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];  in rb_tree_check_node()
1138 			KASSERT(RB_BLACK_P(RB_FATHER(self)));  in rb_tree_check_node()
1144 			KASSERT(!RB_CHILDLESS_P(self)  in rb_tree_check_node()
1152 			KASSERT(RB_CHILDLESS_P(self)  in rb_tree_check_node()
1153 				|| (RB_TWOCHILDREN_P(self)  in rb_tree_check_node()
1154 				    && RB_BLACK_P(self->rb_left)  in rb_tree_check_node()
1155 				    && RB_BLACK_P(self->rb_right)));  in rb_tree_check_node()
1161 			KASSERT(RB_CHILDLESS_P(self)  in rb_tree_check_node()
1171 			KASSERT(RB_CHILDLESS_P(self)  in rb_tree_check_node()
1172 				|| RB_TWOCHILDREN_P(self)  in rb_tree_check_node()
1173 				|| (!RB_LEFT_SENTINEL_P(self)  in rb_tree_check_node()
1174 				    && RB_RIGHT_SENTINEL_P(self)  in rb_tree_check_node()
1175 				    && RB_RED_P(self->rb_left)  in rb_tree_check_node()
1176 				    && RB_CHILDLESS_P(self->rb_left))  in rb_tree_check_node()
1177 				|| (!RB_RIGHT_SENTINEL_P(self)  in rb_tree_check_node()
1178 				    && RB_LEFT_SENTINEL_P(self)  in rb_tree_check_node()
1179 				    && RB_RED_P(self->rb_right)  in rb_tree_check_node()
1180 				    && RB_CHILDLESS_P(self->rb_right)));  in rb_tree_check_node()
1187 			if (!RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1188 			    && RB_CHILDLESS_P(self)  in rb_tree_check_node()
1189 			    && RB_BLACK_P(RB_FATHER(self))) {  in rb_tree_check_node()
1190 				const unsigned int which = RB_POSITION(self);  in rb_tree_check_node()
1195 				    self, other);  in rb_tree_check_node()
1213 		KASSERT(RB_ROOT_P(rbt, self)  in rb_tree_check_node()
1214 			|| RB_ROOT_P(rbt, RB_FATHER(self))  in rb_tree_check_node()
1215 			|| RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));  in rb_tree_check_node()
1220 		KASSERT(RB_LEFT_SENTINEL_P(self)  in rb_tree_check_node()
1221 			|| RB_CHILDLESS_P(self->rb_left)  in rb_tree_check_node()
1222 			|| !RB_RIGHT_SENTINEL_P(self));  in rb_tree_check_node()
1227 		KASSERT(RB_RIGHT_SENTINEL_P(self)  in rb_tree_check_node()
1228 			|| RB_CHILDLESS_P(self->rb_right)  in rb_tree_check_node()
1229 			|| !RB_LEFT_SENTINEL_P(self));  in rb_tree_check_node()
1236 		KASSERT(RB_TWOCHILDREN_P(self->rb_left)  in rb_tree_check_node()
1237 			|| RB_CHILDLESS_P(self->rb_right)  in rb_tree_check_node()
1238 			|| RB_CHILDLESS_P(self->rb_right->rb_left)  in rb_tree_check_node()
1239 			|| RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)  in rb_tree_check_node()
1240 			|| RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)  in rb_tree_check_node()
1241 			|| RB_CHILDLESS_P(self->rb_right->rb_right)  in rb_tree_check_node()
1242 			|| RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)  in rb_tree_check_node()
1243 			|| RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));  in rb_tree_check_node()
1250 		KASSERT(RB_TWOCHILDREN_P(self->rb_right)  in rb_tree_check_node()
1251 			|| RB_CHILDLESS_P(self->rb_left)  in rb_tree_check_node()
1252 			|| RB_CHILDLESS_P(self->rb_left->rb_left)  in rb_tree_check_node()
1253 			|| RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)  in rb_tree_check_node()
1254 			|| RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)  in rb_tree_check_node()
1255 			|| RB_CHILDLESS_P(self->rb_left->rb_right)  in rb_tree_check_node()
1256 			|| RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)  in rb_tree_check_node()
1257 			|| RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));  in rb_tree_check_node()
1263 		if (RB_TWOCHILDREN_P(self)) {  in rb_tree_check_node()
1267 			prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);  in rb_tree_check_node()
1271 			next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);  in rb_tree_check_node()
1283 	const struct rb_node *self;  in rb_tree_check()  local
1298 	TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1299 		rb_tree_check_node(rbt, self, prev, false);  in rb_tree_check()
1316 		TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {  in rb_tree_check()
1317 			rb_tree_check_node(rbt, self, NULL, true);  in rb_tree_check()
1325 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,  in rb_tree_mark_depth()  argument
1328 	if (RB_SENTINEL_P(self))  in rb_tree_mark_depth()
1331 	if (RB_TWOCHILDREN_P(self)) {  in rb_tree_mark_depth()
1332 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1333 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()
1337 	if (!RB_LEFT_SENTINEL_P(self)) {  in rb_tree_mark_depth()
1338 		rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);  in rb_tree_mark_depth()
1340 	if (!RB_RIGHT_SENTINEL_P(self)) {  in rb_tree_mark_depth()
1341 		rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);  in rb_tree_mark_depth()