28 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_left()  local
34 	rb_set_parent(right, parent);  in __rb_rotate_left()
36 	if (parent)  in __rb_rotate_left()
38 		if (node == parent->rb_left)  in __rb_rotate_left()
39 			parent->rb_left = right;  in __rb_rotate_left()
41 			parent->rb_right = right;  in __rb_rotate_left()
51 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_right()  local
57 	rb_set_parent(left, parent);  in __rb_rotate_right()
59 	if (parent)  in __rb_rotate_right()
61 		if (node == parent->rb_right)  in __rb_rotate_right()
62 			parent->rb_right = left;  in __rb_rotate_right()
64 			parent->rb_left = left;  in __rb_rotate_right()
73 	struct rb_node *parent, *gparent;  in rb_insert_color()  local
75 	while ((parent = rb_parent(node)) && rb_is_red(parent))  in rb_insert_color()
77 		gparent = rb_parent(parent);  in rb_insert_color()
79 		if (parent == gparent->rb_left)  in rb_insert_color()
86 					rb_set_black(parent);  in rb_insert_color()
93 			if (parent->rb_right == node)  in rb_insert_color()
96 				__rb_rotate_left(parent, root);  in rb_insert_color()
97 				tmp = parent;  in rb_insert_color()
98 				parent = node;  in rb_insert_color()
102 			rb_set_black(parent);  in rb_insert_color()
111 					rb_set_black(parent);  in rb_insert_color()
118 			if (parent->rb_left == node)  in rb_insert_color()
121 				__rb_rotate_right(parent, root);  in rb_insert_color()
122 				tmp = parent;  in rb_insert_color()
123 				parent = node;  in rb_insert_color()
127 			rb_set_black(parent);  in rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()  argument
143 		if (parent->rb_left == node)  in __rb_erase_color()
145 			other = parent->rb_right;  in __rb_erase_color()
149 				rb_set_red(parent);  in __rb_erase_color()
150 				__rb_rotate_left(parent, root);  in __rb_erase_color()
151 				other = parent->rb_right;  in __rb_erase_color()
157 				node = parent;  in __rb_erase_color()
158 				parent = rb_parent(node);  in __rb_erase_color()
169 					other = parent->rb_right;  in __rb_erase_color()
171 				rb_set_color(other, rb_color(parent));  in __rb_erase_color()
172 				rb_set_black(parent);  in __rb_erase_color()
175 				__rb_rotate_left(parent, root);  in __rb_erase_color()
182 			other = parent->rb_left;  in __rb_erase_color()
186 				rb_set_red(parent);  in __rb_erase_color()
187 				__rb_rotate_right(parent, root);  in __rb_erase_color()
188 				other = parent->rb_left;  in __rb_erase_color()
194 				node = parent;  in __rb_erase_color()
195 				parent = rb_parent(node);  in __rb_erase_color()
206 					other = parent->rb_left;  in __rb_erase_color()
208 				rb_set_color(other, rb_color(parent));  in __rb_erase_color()
209 				rb_set_black(parent);  in __rb_erase_color()
212 				__rb_rotate_right(parent, root);  in __rb_erase_color()
224 	struct rb_node *child, *parent;  in rb_erase()  local
239 		parent = rb_parent(node);  in rb_erase()
243 			rb_set_parent(child, parent);  in rb_erase()
244 		if (parent == old) {  in rb_erase()
245 			parent->rb_right = child;  in rb_erase()
246 			parent = node;  in rb_erase()
248 			parent->rb_left = child;  in rb_erase()
269 	parent = rb_parent(node);  in rb_erase()
273 		rb_set_parent(child, parent);  in rb_erase()
274 	if (parent)  in rb_erase()
276 		if (parent->rb_left == node)  in rb_erase()
277 			parent->rb_left = child;  in rb_erase()
279 			parent->rb_right = child;  in rb_erase()
286 		__rb_erase_color(child, parent, root);  in rb_erase()
306 	struct rb_node *parent;  in rb_next()  local
329 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
330 		node = parent;  in rb_next()
332 	return parent;  in rb_next()