65 	struct rb_node *parent = rb_parent(old);  in __rb_rotate_set_parents()  local
68 	__rb_change_child(old, new, parent, root);  in __rb_rotate_set_parents()
75 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()  local
85 		if (!parent) {  in __rb_insert()
88 		} else if (rb_is_black(parent))  in __rb_insert()
91 		gparent = rb_red_parent(parent);  in __rb_insert()
94 		if (parent != tmp) {	/* parent == gparent->rb_left */  in __rb_insert()
110 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
112 				parent = rb_parent(node);  in __rb_insert()
113 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
117 			tmp = parent->rb_right;  in __rb_insert()
131 				parent->rb_right = tmp = node->rb_left;  in __rb_insert()
132 				node->rb_left = parent;  in __rb_insert()
134 					rb_set_parent_color(tmp, parent,  in __rb_insert()
136 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
137 				augment_rotate(parent, node);  in __rb_insert()
138 				parent = node;  in __rb_insert()
152 			parent->rb_right = gparent;  in __rb_insert()
155 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
156 			augment_rotate(gparent, parent);  in __rb_insert()
163 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
165 				parent = rb_parent(node);  in __rb_insert()
166 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
170 			tmp = parent->rb_left;  in __rb_insert()
173 				parent->rb_left = tmp = node->rb_right;  in __rb_insert()
174 				node->rb_right = parent;  in __rb_insert()
176 					rb_set_parent_color(tmp, parent,  in __rb_insert()
178 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
179 				augment_rotate(parent, node);  in __rb_insert()
180 				parent = node;  in __rb_insert()
186 			parent->rb_left = gparent;  in __rb_insert()
189 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
190 			augment_rotate(gparent, parent);  in __rb_insert()
201 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,  in ____rb_erase_color()  argument
214 		sibling = parent->rb_right;  in ____rb_erase_color()
226 				parent->rb_right = tmp1 = sibling->rb_left;  in ____rb_erase_color()
227 				sibling->rb_left = parent;  in ____rb_erase_color()
228 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
229 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
231 				augment_rotate(parent, sibling);  in ____rb_erase_color()
253 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
255 					if (rb_is_red(parent))  in ____rb_erase_color()
256 						rb_set_black(parent);  in ____rb_erase_color()
258 						node = parent;  in ____rb_erase_color()
259 						parent = rb_parent(node);  in ____rb_erase_color()
260 						if (parent)  in ____rb_erase_color()
279 				parent->rb_right = tmp2;  in ____rb_erase_color()
299 			parent->rb_right = tmp2 = sibling->rb_left;  in ____rb_erase_color()
300 			sibling->rb_left = parent;  in ____rb_erase_color()
303 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
304 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
306 			augment_rotate(parent, sibling);  in ____rb_erase_color()
309 			sibling = parent->rb_left;  in ____rb_erase_color()
312 				parent->rb_left = tmp1 = sibling->rb_right;  in ____rb_erase_color()
313 				sibling->rb_right = parent;  in ____rb_erase_color()
314 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
315 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
317 				augment_rotate(parent, sibling);  in ____rb_erase_color()
325 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
327 					if (rb_is_red(parent))  in ____rb_erase_color()
328 						rb_set_black(parent);  in ____rb_erase_color()
330 						node = parent;  in ____rb_erase_color()
331 						parent = rb_parent(node);  in ____rb_erase_color()
332 						if (parent)  in ____rb_erase_color()
340 				parent->rb_left = tmp2;  in ____rb_erase_color()
349 			parent->rb_left = tmp2 = sibling->rb_right;  in ____rb_erase_color()
350 			sibling->rb_right = parent;  in ____rb_erase_color()
353 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
354 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
356 			augment_rotate(parent, sibling);  in ____rb_erase_color()
363 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,  in __rb_erase_color()  argument
366 	____rb_erase_color(parent, root, augment_rotate);  in __rb_erase_color()
439 	struct rb_node *parent;  in rb_next()  local
462 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
463 		node = parent;  in rb_next()
465 	return parent;  in rb_next()
470 	struct rb_node *parent;  in rb_prev()  local
490 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
491 		node = parent;  in rb_prev()
493 	return parent;  in rb_prev()
499 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()  local
502 	__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()