25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  in __rb_rotate_left()  argument
27 	struct rb_node *right = node->rb_right;  in __rb_rotate_left()
28 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_left()
30 	if ((node->rb_right = right->rb_left))  in __rb_rotate_left()
31 		rb_set_parent(right->rb_left, node);  in __rb_rotate_left()
32 	right->rb_left = node;  in __rb_rotate_left()
38 		if (node == parent->rb_left)  in __rb_rotate_left()
45 	rb_set_parent(node, right);  in __rb_rotate_left()
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  in __rb_rotate_right()  argument
50 	struct rb_node *left = node->rb_left;  in __rb_rotate_right()
51 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_right()
53 	if ((node->rb_left = left->rb_right))  in __rb_rotate_right()
54 		rb_set_parent(left->rb_right, node);  in __rb_rotate_right()
55 	left->rb_right = node;  in __rb_rotate_right()
61 		if (node == parent->rb_right)  in __rb_rotate_right()
68 	rb_set_parent(node, left);  in __rb_rotate_right()
71 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()  argument
75 	while ((parent = rb_parent(node)) && rb_is_red(parent))  in rb_insert_color()
88 					node = gparent;  in rb_insert_color()
93 			if (parent->rb_right == node)  in rb_insert_color()
98 				parent = node;  in rb_insert_color()
99 				node = tmp;  in rb_insert_color()
113 					node = gparent;  in rb_insert_color()
118 			if (parent->rb_left == node)  in rb_insert_color()
123 				parent = node;  in rb_insert_color()
124 				node = tmp;  in rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()  argument
141 	while ((!node || rb_is_black(node)) && node != root->rb_node)  in __rb_erase_color()
143 		if (parent->rb_left == node)  in __rb_erase_color()
157 				node = parent;  in __rb_erase_color()
158 				parent = rb_parent(node);  in __rb_erase_color()
176 				node = root->rb_node;  in __rb_erase_color()
194 				node = parent;  in __rb_erase_color()
195 				parent = rb_parent(node);  in __rb_erase_color()
213 				node = root->rb_node;  in __rb_erase_color()
218 	if (node)  in __rb_erase_color()
219 		rb_set_black(node);  in __rb_erase_color()
222 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()  argument
227 	if (!node->rb_left)  in rb_erase()
228 		child = node->rb_right;  in rb_erase()
229 	else if (!node->rb_right)  in rb_erase()
230 		child = node->rb_left;  in rb_erase()
233 		struct rb_node *old = node, *left;  in rb_erase()
235 		node = node->rb_right;  in rb_erase()
236 		while ((left = node->rb_left) != NULL)  in rb_erase()
237 			node = left;  in rb_erase()
238 		child = node->rb_right;  in rb_erase()
239 		parent = rb_parent(node);  in rb_erase()
240 		color = rb_color(node);  in rb_erase()
246 			parent = node;  in rb_erase()
250 		node->rb_parent_color = old->rb_parent_color;  in rb_erase()
251 		node->rb_right = old->rb_right;  in rb_erase()
252 		node->rb_left = old->rb_left;  in rb_erase()
257 				rb_parent(old)->rb_left = node;  in rb_erase()
259 				rb_parent(old)->rb_right = node;  in rb_erase()
261 			root->rb_node = node;  in rb_erase()
263 		rb_set_parent(old->rb_left, node);  in rb_erase()
265 			rb_set_parent(old->rb_right, node);  in rb_erase()
269 	parent = rb_parent(node);  in rb_erase()
270 	color = rb_color(node);  in rb_erase()
276 		if (parent->rb_left == node)  in rb_erase()
316 struct rb_node *rb_next(struct rb_node *node)  in rb_next()  argument
320 	if (rb_parent(node) == node)  in rb_next()
325 	if (node->rb_right) {  in rb_next()
326 		node = node->rb_right;   in rb_next()
327 		while (node->rb_left)  in rb_next()
328 			node=node->rb_left;  in rb_next()
329 		return node;  in rb_next()
338 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
339 		node = parent;  in rb_next()
344 struct rb_node *rb_prev(struct rb_node *node)  in rb_prev()  argument
348 	if (rb_parent(node) == node)  in rb_prev()
353 	if (node->rb_left) {  in rb_prev()
354 		node = node->rb_left;   in rb_prev()
355 		while (node->rb_right)  in rb_prev()
356 			node=node->rb_right;  in rb_prev()
357 		return node;  in rb_prev()
362 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
363 		node = parent;  in rb_prev()