46 #define	KASSERT(s)	assert(s)
48 #define	KASSERT(s)	do { } while (/*CONSTCOND*/ 0)
244 		KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
245 		KASSERT(next == NULL || !RB_SENTINEL_P(next));
250 		KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
251 		KASSERT(next == NULL || !RB_SENTINEL_P(next));
252 		KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
254 		KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
272 		KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
289 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
293 	KASSERT(RB_CHILDLESS_P(self));
303 		KASSERT((*compare_nodes)(rbto->rbto_context,
308 		KASSERT((*compare_nodes)(rbto->rbto_context,
315 	KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
322 		KASSERT(rb_tree_check_node(rbt, self, NULL, true));
346 	KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
348 	KASSERT(!RB_SENTINEL_P(old_child));
349 	KASSERT(RB_FATHER(old_child) == old_father);
351 	KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
352 	KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
353 	KASSERT(RB_ROOT_P(rbt, old_father) ||
394 	KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
395 	KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
396 	KASSERT(RB_ROOT_P(rbt, new_father) ||
409 	KASSERT(!RB_ROOT_P(rbt, self));
410 	KASSERT(RB_RED_P(self));
411 	KASSERT(RB_RED_P(father));
415 		KASSERT(!RB_SENTINEL_P(self));
417 		KASSERT(RB_RED_P(self));
418 		KASSERT(RB_RED_P(father));
424 		KASSERT(RB_BLACK_P(grandpa));
425 		KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
447 			KASSERT(RB_BLACK_P(grandpa));
453 		KASSERT(RB_RED_P(self));
458 			KASSERT(RB_BLACK_P(rbt->rbt_root));
463 	KASSERT(!RB_ROOT_P(rbt, self));
464 	KASSERT(RB_RED_P(self));
465 	KASSERT(RB_RED_P(father));
466 	KASSERT(RB_BLACK_P(uncle));
467 	KASSERT(RB_BLACK_P(grandpa));
479 		KASSERT(RB_FATHER(father) == self);
480 		KASSERT(self->rb_nodes[which] == father);
481 		KASSERT(RB_FATHER(self) == grandpa);
485 	KASSERT(RB_RED_P(self) && RB_RED_P(father));
486 	KASSERT(grandpa->rb_nodes[which] == father);
494 	KASSERT(RB_FATHER(self) == father);
495 	KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
496 	KASSERT(RB_RED_P(self));
497 	KASSERT(RB_BLACK_P(father));
498 	KASSERT(RB_RED_P(grandpa));
515 	KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
516 	KASSERT(!rebalance || RB_BLACK_P(self));
517 	KASSERT(RB_CHILDLESS_P(self));
518 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));
552 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
573 		KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
580 		KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
587 	KASSERT(RB_TWOCHILDREN_P(self));
591 	KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
596 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));
597 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
604 		KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
609 			KASSERT(RB_POSITION(standin_son) == standin_which);
611 			KASSERT(RB_POSITION(standin_son) == standin_other);
632 		KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
633 		KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
634 		KASSERT(self->rb_nodes[standin_which] == standin);
653 		KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
665 	KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
689 	KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
690 	KASSERT(RB_FATHER_SENTINEL_P(standin)
692 	KASSERT(RB_LEFT_SENTINEL_P(standin)
694 	KASSERT(RB_RIGHT_SENTINEL_P(standin)
701 	KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
721 	KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
722 	KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
723 	KASSERT(!RB_TWOCHILDREN_P(son));
724 	KASSERT(RB_CHILDLESS_P(son));
725 	KASSERT(rb_tree_check_node(rbt, self, NULL, false));
726 	KASSERT(rb_tree_check_node(rbt, son, NULL, false));
744 		KASSERT(rbt->rbt_minmax[which] == son);
752 	KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
753 	KASSERT(rb_tree_check_node(rbt, son, NULL, true));
763 	KASSERT(!RB_SENTINEL_P(self));
788 	KASSERT(!RB_CHILDLESS_P(self));
799 		KASSERT(RB_BLACK_P(self));
800 		KASSERT(RB_RED_P(self->rb_nodes[which]));
801 		KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
805 	KASSERT(RB_TWOCHILDREN_P(self));
825 	KASSERT(!RB_SENTINEL_P(parent));
826 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
827 	KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
836 		KASSERT(!RB_SENTINEL_P(brother));
856 				KASSERT(RB_BLACK_P(parent));
859 				KASSERT(!RB_SENTINEL_P(brother));
860 				KASSERT(RB_RED_P(parent));
861 				KASSERT(RB_BLACK_P(brother));
862 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
863 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
875 				KASSERT(RB_BLACK_P(brother->rb_left));
876 				KASSERT(RB_BLACK_P(brother->rb_right));
879 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
880 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
894 			KASSERT(RB_RED_P(parent));
895 			KASSERT(RB_BLACK_P(brother));
896 			KASSERT(RB_BLACK_P(brother->rb_left));
897 			KASSERT(RB_BLACK_P(brother->rb_right));
910 			KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
917 			KASSERT(RB_BLACK_P(brother));
918 			KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
932 				KASSERT(RB_RED_P(brother->rb_nodes[which]));
934 				KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
936 				KASSERT(RB_RED_P(brother->rb_nodes[other]));
962 			KASSERT(RB_BLACK_P(brother));
963 			KASSERT(RB_RED_P(brother->rb_nodes[other]));
969 	KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
979 	KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
996 	KASSERT(!RB_SENTINEL_P(self));
1015 	KASSERT(!RB_SENTINEL_P(self));
1027 	KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
1043 	KASSERT(!RB_SENTINEL_P(self));
1062 	KASSERT(!RB_SENTINEL_P(self));
1079 	KASSERT(left == right);
1091 	KASSERT(!RB_SENTINEL_P(self));
1092 	KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
1099 		KASSERT(self == rbt->rbt_root);
1100 		KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
1101 		KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1102 		KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
1108 		KASSERT(self != rbt->rbt_root);
1109 		KASSERT(!RB_FATHER_SENTINEL_P(self));
1111 			KASSERT(diff < 0);
1112 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1114 			KASSERT(diff > 0);
1115 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
1125 		KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
1126 		KASSERT(next0 == TAILQ_NEXT(self, rb_link));
1128 		KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
1129 		KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
1138 		KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
1142 			KASSERT(!RB_ROOT_P(rbt, self));
1144 			KASSERT(RB_BLACK_P(RB_FATHER(self)));
1150 			KASSERT(!RB_CHILDLESS_P(self)
1158 			KASSERT(RB_CHILDLESS_P(self)
1167 			KASSERT(RB_CHILDLESS_P(self)
1177 			KASSERT(RB_CHILDLESS_P(self)
1202 				KASSERT(relative0 != NULL);
1205 				KASSERT(relative != NULL);
1206 				KASSERT(RB_SENTINEL_P(relative->rb_nodes[which]));
1208 				KASSERT(RB_RED_P(relative)
1219 		KASSERT(RB_ROOT_P(rbt, self)
1226 		KASSERT(RB_LEFT_SENTINEL_P(self)
1233 		KASSERT(RB_RIGHT_SENTINEL_P(self)
1242 		KASSERT(RB_TWOCHILDREN_P(self->rb_left)
1256 		KASSERT(RB_TWOCHILDREN_P(self->rb_right)
1274 			KASSERT(prev0 != NULL);
1275 			KASSERT(RB_RIGHT_SENTINEL_P(prev0));
1278 			KASSERT(next0 != NULL);
1279 			KASSERT(RB_LEFT_SENTINEL_P(next0));
1295 	KASSERT(rbt->rbt_root != NULL);
1296 	KASSERT(RB_LEFT_P(rbt->rbt_root));
1299 	KASSERT(rbt->rbt_count > 1
1311 	KASSERT(rbt->rbt_count == count);
1314 		KASSERT(RB_BLACK_P(rbt->rbt_root));
1315 		KASSERT(RB_SENTINEL_P(rbt->rbt_root)

Indexes created Mon Nov 10 17:20:41 GMT 2025