90 	struct rb_node *parent = rb_parent(old);  in __rb_rotate_set_parents()  local
93 	__rb_change_child(old, new, parent, root);  in __rb_rotate_set_parents()
101 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()  local
110 		if (unlikely(!parent)) {  in __rb_insert()
126 		if(rb_is_black(parent))  in __rb_insert()
129 		gparent = rb_red_parent(parent);  in __rb_insert()
132 		if (parent != tmp) {	/* parent == gparent->rb_left */  in __rb_insert()
148 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
150 				parent = rb_parent(node);  in __rb_insert()
151 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
155 			tmp = parent->rb_right;  in __rb_insert()
171 				WRITE_ONCE(parent->rb_right, tmp);  in __rb_insert()
172 				WRITE_ONCE(node->rb_left, parent);  in __rb_insert()
174 					rb_set_parent_color(tmp, parent,  in __rb_insert()
176 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
177 				augment_rotate(parent, node);  in __rb_insert()
178 				parent = node;  in __rb_insert()
193 			WRITE_ONCE(parent->rb_right, gparent);  in __rb_insert()
196 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
197 			augment_rotate(gparent, parent);  in __rb_insert()
204 				rb_set_parent_color(parent, gparent, RB_BLACK);  in __rb_insert()
206 				parent = rb_parent(node);  in __rb_insert()
207 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
211 			tmp = parent->rb_left;  in __rb_insert()
215 				WRITE_ONCE(parent->rb_left, tmp);  in __rb_insert()
216 				WRITE_ONCE(node->rb_right, parent);  in __rb_insert()
218 					rb_set_parent_color(tmp, parent,  in __rb_insert()
220 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
221 				augment_rotate(parent, node);  in __rb_insert()
222 				parent = node;  in __rb_insert()
228 			WRITE_ONCE(parent->rb_left, gparent);  in __rb_insert()
231 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);  in __rb_insert()
232 			augment_rotate(gparent, parent);  in __rb_insert()
243 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,  in ____rb_erase_color()  argument
256 		sibling = parent->rb_right;  in ____rb_erase_color()
269 				WRITE_ONCE(parent->rb_right, tmp1);  in ____rb_erase_color()
270 				WRITE_ONCE(sibling->rb_left, parent);  in ____rb_erase_color()
271 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
272 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
274 				augment_rotate(parent, sibling);  in ____rb_erase_color()
296 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
298 					if (rb_is_red(parent))  in ____rb_erase_color()
299 						rb_set_black(parent);  in ____rb_erase_color()
301 						node = parent;  in ____rb_erase_color()
302 						parent = rb_parent(node);  in ____rb_erase_color()
303 						if (parent)  in ____rb_erase_color()
338 				WRITE_ONCE(parent->rb_right, tmp2);  in ____rb_erase_color()
359 			WRITE_ONCE(parent->rb_right, tmp2);  in ____rb_erase_color()
360 			WRITE_ONCE(sibling->rb_left, parent);  in ____rb_erase_color()
363 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
364 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
366 			augment_rotate(parent, sibling);  in ____rb_erase_color()
369 			sibling = parent->rb_left;  in ____rb_erase_color()
373 				WRITE_ONCE(parent->rb_left, tmp1);  in ____rb_erase_color()
374 				WRITE_ONCE(sibling->rb_right, parent);  in ____rb_erase_color()
375 				rb_set_parent_color(tmp1, parent, RB_BLACK);  in ____rb_erase_color()
376 				__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
378 				augment_rotate(parent, sibling);  in ____rb_erase_color()
386 					rb_set_parent_color(sibling, parent,  in ____rb_erase_color()
388 					if (rb_is_red(parent))  in ____rb_erase_color()
389 						rb_set_black(parent);  in ____rb_erase_color()
391 						node = parent;  in ____rb_erase_color()
392 						parent = rb_parent(node);  in ____rb_erase_color()
393 						if (parent)  in ____rb_erase_color()
402 				WRITE_ONCE(parent->rb_left, tmp2);  in ____rb_erase_color()
412 			WRITE_ONCE(parent->rb_left, tmp2);  in ____rb_erase_color()
413 			WRITE_ONCE(sibling->rb_right, parent);  in ____rb_erase_color()
416 				rb_set_parent(tmp2, parent);  in ____rb_erase_color()
417 			__rb_rotate_set_parents(parent, sibling, root,  in ____rb_erase_color()
419 			augment_rotate(parent, sibling);  in ____rb_erase_color()
426 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,  in __rb_erase_color()  argument
429 	____rb_erase_color(parent, root, augment_rotate);  in __rb_erase_color()
530 	struct rb_node *parent;  in rb_next()  local
553 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
554 		node = parent;  in rb_next()
556 	return parent;  in rb_next()
562 	struct rb_node *parent;  in rb_prev()  local
582 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
583 		node = parent;  in rb_prev()
585 	return parent;  in rb_prev()
592 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()  local
602 	__rb_change_child(victim, new, parent, root);  in rb_replace_node()
619 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node_rcu()  local
634 	__rb_change_child_rcu(victim, new, parent, root);  in rb_replace_node_rcu()
652 	const struct rb_node *parent;  in rb_next_postorder()  local
655 	parent = rb_parent(node);  in rb_next_postorder()
658 	if (parent && node == parent->rb_left && parent->rb_right) {  in rb_next_postorder()
661 		return rb_left_deepest_node(parent->rb_right);  in rb_next_postorder()
665 		return (struct rb_node *)parent;  in rb_next_postorder()