libc/gen/rb.c

116 	struct rb_node *parent = rbt->rbt_root;
118 	while (!RB_SENTINEL_P(parent)) {
119 		void *pobj = RB_NODETOITEM(rbto, parent);
124 		parent = parent->rb_nodes[diff < 0];
135 	struct rb_node *parent = rbt->rbt_root, *last = NULL;
137 	while (!RB_SENTINEL_P(parent)) {
138 		void *pobj = RB_NODETOITEM(rbto, parent);
144 			last = parent;
145 		parent = parent->rb_nodes[diff < 0];
156 	struct rb_node *parent = rbt->rbt_root, *last = NULL;
158 	while (!RB_SENTINEL_P(parent)) {
159 		void *pobj = RB_NODETOITEM(rbto, parent);
165 			last = parent;
166 		parent = parent->rb_nodes[diff < 0];
177 	struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
191 	parent = (struct rb_node *)(void *)&rbt->rbt_root;
207 		parent = tmp;
209 		tmp = parent->rb_nodes[position];
217 			prev = parent;
219 			next = parent;
242 	RB_SET_FATHER(self, parent);
244 	if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
256 		 * parent is a minmax node and we on their min/max side,
259 		if (parent == rbt->rbt_minmax[position])
264 		 * if our parent is also red.
267 		rebalance = RB_RED_P(parent);
269 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
270 	self->rb_left = parent->rb_nodes[position];
271 	self->rb_right = parent->rb_nodes[position];
272 	parent->rb_nodes[position] = self;
401 		 * We are red and our parent is red, therefore we must have a
417 		 *   Simply invert the colors of our parent and
455 		 *   Swap ourselves with our parent so this case
456 		 *   becomes case 3.  Basically our parent becomes our
470 	 *   Swap our parent and grandparent.  Since our grandfather
552 		 * our parent.
559 		 * on the same side as our parent.
795 	 * Let's find the node closes to us opposite of our parent
803 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
806 	KASSERT(!RB_SENTINEL_P(parent));
807 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
811 	while (RB_BLACK_P(parent->rb_nodes[which])) {
813 		struct rb_node *brother = parent->rb_nodes[other];
822 		if (RB_BLACK_P(parent)
828 				 * position (and colors) with our parent.
837 				KASSERT(RB_BLACK_P(parent));
838 				rb_tree_reparent_nodes(rbt, parent, other);
839 				brother = parent->rb_nodes[other];
841 				KASSERT(RB_RED_P(parent));
844 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
847 				 * Both our parent and brother are black.
858 				if (RB_ROOT_P(rbt, parent))
859 					return;	/* root == parent == black */
861 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
862 				which = RB_POSITION(parent);
863 				parent = RB_FATHER(parent);
871 		if (RB_RED_P(parent)
875 			KASSERT(RB_RED_P(parent));
889 			RB_MARK_BLACK(parent);
915 				KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
916 				brother = parent->rb_nodes[other];
946 			rb_tree_reparent_nodes(rbt, parent, other);
950 	KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
980 	 * opposite direction until our parent is in direction we want to go.
1027 	 * opposite direction until our parent is in direction we want to go.
1077 	 * Verify our relationship to our parent.
1170 			 * If I'm a childless black node and my parent is
1171 			 * black, my 2nd closet relative away from my parent
1172 			 * is either red or has a red parent or red children.