56 	struct rb_node *parent = rb_parent(old);  in __rb_rotate_set_parents()  local
59 	__rb_change_child(old, new, parent, root);  in __rb_rotate_set_parents()
66 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()  local
76 		if (!parent) {  in __rb_insert()
79 		} else if (rb_is_black(parent))  in __rb_insert()
82 		gparent = rb_red_parent(parent);  in __rb_insert()
85 		if (parent != tmp) {	/* parent == gparent->rb_left */  in __rb_insert()
101 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
103 				parent = rb_parent(node);  in __rb_insert()
104 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
108 			tmp = parent->rb_right;  in __rb_insert()
122 				parent->rb_right = tmp = node->rb_left;  in __rb_insert()
123 				node->rb_left = parent;  in __rb_insert()
125 					rb_set_parent_color(tmp, parent,  in __rb_insert()
127 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
128 				augment_rotate(parent, node);  in __rb_insert()
129 				parent = node;  in __rb_insert()
143 			parent->rb_right = gparent;  in __rb_insert()
146 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
147 			augment_rotate(gparent, parent);  in __rb_insert()
154 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
156 				parent = rb_parent(node);  in __rb_insert()
157 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
161 			tmp = parent->rb_left;  in __rb_insert()
164 				parent->rb_left = tmp = node->rb_right;  in __rb_insert()
165 				node->rb_right = parent;  in __rb_insert()
167 					rb_set_parent_color(tmp, parent,  in __rb_insert()
169 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
170 				augment_rotate(parent, node);  in __rb_insert()
171 				parent = node;  in __rb_insert()
177 			parent->rb_left = gparent;  in __rb_insert()
180 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
181 			augment_rotate(gparent, parent);  in __rb_insert()
192 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,  in ____rb_erase_color()  argument
205 		sibling = parent->rb_right;  in ____rb_erase_color()
217 				parent->rb_right = tmp1 = sibling->rb_left;  in ____rb_erase_color()
218 				sibling->rb_left = parent;  in ____rb_erase_color()
219 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
220 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
222 				augment_rotate(parent, sibling);  in ____rb_erase_color()
244 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
246 					if (rb_is_red(parent))  in ____rb_erase_color()
247 						rb_set_black(parent);  in ____rb_erase_color()
249 						node = parent;  in ____rb_erase_color()
250 						parent = rb_parent(node);  in ____rb_erase_color()
251 						if (parent)  in ____rb_erase_color()
270 				parent->rb_right = tmp2;  in ____rb_erase_color()
290 			parent->rb_right = tmp2 = sibling->rb_left;  in ____rb_erase_color()
291 			sibling->rb_left = parent;  in ____rb_erase_color()
294 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
295 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
297 			augment_rotate(parent, sibling);  in ____rb_erase_color()
300 			sibling = parent->rb_left;  in ____rb_erase_color()
303 				parent->rb_left = tmp1 = sibling->rb_right;  in ____rb_erase_color()
304 				sibling->rb_right = parent;  in ____rb_erase_color()
305 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
306 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
308 				augment_rotate(parent, sibling);  in ____rb_erase_color()
316 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
318 					if (rb_is_red(parent))  in ____rb_erase_color()
319 						rb_set_black(parent);  in ____rb_erase_color()
321 						node = parent;  in ____rb_erase_color()
322 						parent = rb_parent(node);  in ____rb_erase_color()
323 						if (parent)  in ____rb_erase_color()
331 				parent->rb_left = tmp2;  in ____rb_erase_color()
340 			parent->rb_left = tmp2 = sibling->rb_right;  in ____rb_erase_color()
341 			sibling->rb_right = parent;  in ____rb_erase_color()
344 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
345 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
347 			augment_rotate(parent, sibling);  in ____rb_erase_color()
354 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,  in __rb_erase_color()  argument
357 	____rb_erase_color(parent, root, augment_rotate);  in __rb_erase_color()
436 	struct rb_node *parent;  in rb_next()  local
459 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
460 		node = parent;  in rb_next()
462 	return parent;  in rb_next()
468 	struct rb_node *parent;  in rb_prev()  local
488 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
489 		node = parent;  in rb_prev()
491 	return parent;  in rb_prev()
498 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()  local
501 	__rb_change_child(victim, new, parent, root);  in rb_replace_node()
526 	const struct rb_node *parent;  in rb_next_postorder()  local
529 	parent = rb_parent(node);  in rb_next_postorder()
532 	if (parent && node == parent->rb_left && parent->rb_right) {  in rb_next_postorder()
535 		return rb_left_deepest_node(parent->rb_right);  in rb_next_postorder()
539 		return (struct rb_node *)parent;  in rb_next_postorder()