lib/libprop/prop_rb.c

157 	struct rb_node *parent, *tmp;
171 	parent = (struct rb_node *)&rbt->rbt_root;
185 		parent = tmp;
192 		tmp = parent->rb_nodes[position];
200 			prev = parent;
202 			next = parent;
225 	self->rb_parent = parent;
228 	if (__predict_false(parent == (struct rb_node *) &rbt->rbt_root)) {
234 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
235 	self->rb_left = parent->rb_nodes[position];
236 	self->rb_right = parent->rb_nodes[position];
237 	parent->rb_nodes[position] = self;
298 		 * We are red and our parent is red, therefore we must have a
308 			 *   Simply invert the colors of our parent and
324 			 *   Swap ourselves with our parent so this case
325 			 *   becomes case 3.  Basically our parent becomes our
339 		 *   Swap our parent and grandparent.  Since our grandfather
362 	struct rb_node *parent = rbt->rbt_root;
365 	while (!RB_SENTINEL_P(parent)) {
366 		const int diff = (*compare_key)(parent, key);
368 			return parent;
369 		parent = parent->rb_nodes[diff > 0];
413 		 * our parent (self).
420 		 * on the same side as our parent (self).
538 	struct rb_node *parent = self->rb_parent;
552 	parent->rb_nodes[self->rb_position] = child;
553 	child->rb_parent = parent;
562 	KASSERT(RB_ROOT_P(self) || rb_tree_check_node(rbt, parent, NULL, true));
624 	 * Let's find the node closes to us opposite of our parent
632 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
635 	KASSERT(!RB_SENTINEL_P(parent));
636 	KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
639 	while (RB_BLACK_P(parent->rb_nodes[which])) {
641 		struct rb_node *brother = parent->rb_nodes[other];
648 		if (RB_BLACK_P(parent)
653 			 * (and colors) with our parent.  This is now case 2b.
660 				KASSERT(RB_BLACK_P(parent));
661 				rb_tree_reparent_nodes(rbt, parent, other);
662 				brother = parent->rb_nodes[other];
665 				KASSERT(RB_RED_P(parent));
667 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
670 				 * Both our parent and brother are black.
681 				if (RB_ROOT_P(parent))
684 				KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
685 				which = parent->rb_position;
686 				parent = parent->rb_parent;
688 		} else if (RB_RED_P(parent)
695 			RB_MARK_BLACK(parent);
715 				KASSERT(brother->rb_parent == parent->rb_nodes[other]);
716 				brother = parent->rb_nodes[other];
721 			 * is red.  Swap our parent and brother locations and
732 			rb_tree_reparent_nodes(rbt, parent, other);
736 	KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
757 	 * opposite direction until our parent is in direction we want to go.
798 	 * opposite direction until our parent is in direction we want to go.
831 	 * Verify our relationship to our parent.
917 			 * If I'm a childless black node and my parent is
918 			 * black, my 2nd closet relative away from my parent
919 			 * is either red or has a red parent or red children.