Cross Reference: /src/common/lib/libc/gen/rbtree.c

Lines Matching refs:brother
626 		 * brother.
636 		 * Have our son/standin adopt his brother as his new son.
832 		struct rb_node *brother = parent->rb_nodes[other];
836 		KASSERT(!RB_SENTINEL_P(brother));
838 		 * For cases 1, 2a, and 2b, our brother's children must
842 		    && RB_BLACK_P(brother->rb_left)
843 		    && RB_BLACK_P(brother->rb_right)) {
844 			if (RB_RED_P(brother)) {
846 				 * Case 1: Our brother is red, swap its
858 				brother = parent->rb_nodes[other];
859 				KASSERT(!RB_SENTINEL_P(brother));
861 				KASSERT(RB_BLACK_P(brother));
862 				KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
866 				 * Both our parent and brother are black.
867 				 * Change our brother to red, advance up rank
874 				RB_MARK_RED(brother);
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));
891 		    && RB_BLACK_P(brother)
892 		    && RB_BLACK_P(brother->rb_left)
893 		    && RB_BLACK_P(brother->rb_right)) {
895 			KASSERT(RB_BLACK_P(brother));
896 			KASSERT(RB_BLACK_P(brother->rb_left));
897 			KASSERT(RB_BLACK_P(brother->rb_right));
899 			 * We are black, our father is red, our brother and
901 			 * colors of our father and brother (to black and red
909 			RB_MARK_RED(brother);
910 			KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
914 			 * Our brother must be black and have at least one
917 			KASSERT(RB_BLACK_P(brother));
918 			KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
919 				RB_RED_P(brother->rb_nodes[other]));
920 			if (RB_BLACK_P(brother->rb_nodes[other])) {
922 				 * Case 3: our brother is black, our near
924 				 * Swap our brother with our near nephew.  
932 				KASSERT(RB_RED_P(brother->rb_nodes[which]));
933 				rb_tree_reparent_nodes(rbt, brother, which);
934 				KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
935 				brother = parent->rb_nodes[other];
936 				KASSERT(RB_RED_P(brother->rb_nodes[other]));
939 			 * Case 4: our brother is black and our far nephew
940 			 * is red.  Swap our father and brother locations and
962 			KASSERT(RB_BLACK_P(brother));
963 			KASSERT(RB_RED_P(brother->rb_nodes[other]));
964 			RB_MARK_BLACK(brother->rb_nodes[other]);
1141 			const struct rb_node *brother;
1143 			brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
1147 			 * have no brother or my brother also be red and
1151 				|| RB_SENTINEL_P(brother)
1152 				|| RB_RED_P(brother)
1153 				|| RB_CHILDLESS_P(brother));
1164 			 * then my brother must either be black or have two
1168 				|| RB_BLACK_P(brother)
1169 				|| (RB_TWOCHILDREN_P(brother)
1170 				    && RB_BLACK_P(brother->rb_left)
1171 				    && RB_BLACK_P(brother->rb_right)));
OpenGrok
