78 	struct rb_node *parent = rb_parent(old);  in __rb_rotate_set_parents()  local
81 	__rb_change_child(old, new, parent, root);  in __rb_rotate_set_parents()
88 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()  local
94 		if (unlikely(!parent)) {  in __rb_insert()
110 		if(rb_is_black(parent))  in __rb_insert()
113 		gparent = rb_red_parent(parent);  in __rb_insert()
116 		if (parent != tmp) {	/* parent == gparent->rb_left */  in __rb_insert()
132 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
134 				parent = rb_parent(node);  in __rb_insert()
135 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
139 			tmp = parent->rb_right;  in __rb_insert()
155 				WRITE_ONCE(parent->rb_right, tmp);  in __rb_insert()
156 				WRITE_ONCE(node->rb_left, parent);  in __rb_insert()
158 					rb_set_parent_color(tmp, parent,  in __rb_insert()
160 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
161 				augment_rotate(parent, node);  in __rb_insert()
162 				parent = node;  in __rb_insert()
177 			WRITE_ONCE(parent->rb_right, 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()
188 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
190 				parent = rb_parent(node);  in __rb_insert()
191 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
195 			tmp = parent->rb_left;  in __rb_insert()
199 				WRITE_ONCE(parent->rb_left, tmp);  in __rb_insert()
200 				WRITE_ONCE(node->rb_right, parent);  in __rb_insert()
202 					rb_set_parent_color(tmp, parent,  in __rb_insert()
204 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
205 				augment_rotate(parent, node);  in __rb_insert()
206 				parent = node;  in __rb_insert()
212 			WRITE_ONCE(parent->rb_left, gparent);  in __rb_insert()
215 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
216 			augment_rotate(gparent, parent);  in __rb_insert()
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,  in ____rb_erase_color()  argument
240 		sibling = parent->rb_right;  in ____rb_erase_color()
253 				WRITE_ONCE(parent->rb_right, tmp1);  in ____rb_erase_color()
254 				WRITE_ONCE(sibling->rb_left, parent);  in ____rb_erase_color()
255 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
256 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
258 				augment_rotate(parent, sibling);  in ____rb_erase_color()
280 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
282 					if (rb_is_red(parent))  in ____rb_erase_color()
283 						rb_set_black(parent);  in ____rb_erase_color()
285 						node = parent;  in ____rb_erase_color()
286 						parent = rb_parent(node);  in ____rb_erase_color()
287 						if (parent)  in ____rb_erase_color()
322 				WRITE_ONCE(parent->rb_right, tmp2);  in ____rb_erase_color()
343 			WRITE_ONCE(parent->rb_right, tmp2);  in ____rb_erase_color()
344 			WRITE_ONCE(sibling->rb_left, parent);  in ____rb_erase_color()
347 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
348 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
350 			augment_rotate(parent, sibling);  in ____rb_erase_color()
353 			sibling = parent->rb_left;  in ____rb_erase_color()
357 				WRITE_ONCE(parent->rb_left, tmp1);  in ____rb_erase_color()
358 				WRITE_ONCE(sibling->rb_right, parent);  in ____rb_erase_color()
359 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
360 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
362 				augment_rotate(parent, sibling);  in ____rb_erase_color()
370 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
372 					if (rb_is_red(parent))  in ____rb_erase_color()
373 						rb_set_black(parent);  in ____rb_erase_color()
375 						node = parent;  in ____rb_erase_color()
376 						parent = rb_parent(node);  in ____rb_erase_color()
377 						if (parent)  in ____rb_erase_color()
386 				WRITE_ONCE(parent->rb_left, tmp2);  in ____rb_erase_color()
396 			WRITE_ONCE(parent->rb_left, tmp2);  in ____rb_erase_color()
397 			WRITE_ONCE(sibling->rb_right, parent);  in ____rb_erase_color()
400 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
401 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
403 			augment_rotate(parent, sibling);  in ____rb_erase_color()
410 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,  in __rb_erase_color()  argument
413 	____rb_erase_color(parent, root, augment_rotate);  in __rb_erase_color()
488 	struct rb_node *parent;  in rb_next()  local
511 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
512 		node = parent;  in rb_next()
514 	return parent;  in rb_next()
519 	struct rb_node *parent;  in rb_prev()  local
539 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
540 		node = parent;  in rb_prev()
542 	return parent;  in rb_prev()
548 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()  local
558 	__rb_change_child(victim, new, parent, root);  in rb_replace_node()
575 	const struct rb_node *parent;  in rb_next_postorder()  local
578 	parent = rb_parent(node);  in rb_next_postorder()
581 	if (parent && node == parent->rb_left && parent->rb_right) {  in rb_next_postorder()
584 		return rb_left_deepest_node(parent->rb_right);  in rb_next_postorder()
588 		return (struct rb_node *)parent;  in rb_next_postorder()