25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  in __rb_rotate_left()
27 	struct rb_node *right = node->rb_right;  in __rb_rotate_left()
28 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_left()
44 		root->rb_node = right;  in __rb_rotate_left()
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  in __rb_rotate_right()
50 	struct rb_node *left = node->rb_left;  in __rb_rotate_right()
51 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_right()
67 		root->rb_node = left;  in __rb_rotate_right()
71 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()
73 	struct rb_node *parent, *gparent;  in rb_insert_color()
82 				register struct rb_node *uncle = gparent->rb_right;  in rb_insert_color()
95 				register struct rb_node *tmp;  in rb_insert_color()
107 				register struct rb_node *uncle = gparent->rb_left;  in rb_insert_color()
120 				register struct rb_node *tmp;  in rb_insert_color()
133 	rb_set_black(root->rb_node);  in rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()
139 	struct rb_node *other;  in __rb_erase_color()
141 	while ((!node || rb_is_black(node)) && node != root->rb_node)  in __rb_erase_color()
164 					struct rb_node *o_left;  in __rb_erase_color()
176 				node = root->rb_node;  in __rb_erase_color()
201 					register struct rb_node *o_right;  in __rb_erase_color()
213 				node = root->rb_node;  in __rb_erase_color()
222 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()
224 	struct rb_node *child, *parent;  in rb_erase()
233 		struct rb_node *old = node, *left;  in rb_erase()
261 			root->rb_node = node;  in rb_erase()
282 		root->rb_node = child;  in rb_erase()
292 struct rb_node *rb_first(struct rb_root *root)  in rb_first()
294 	struct rb_node	*n;  in rb_first()
296 	n = root->rb_node;  in rb_first()
304 struct rb_node *rb_last(struct rb_root *root)  in rb_last()
306 	struct rb_node	*n;  in rb_last()
308 	n = root->rb_node;  in rb_last()
316 struct rb_node *rb_next(struct rb_node *node)  in rb_next()
318 	struct rb_node *parent;  in rb_next()
344 struct rb_node *rb_prev(struct rb_node *node)  in rb_prev()
346 	struct rb_node *parent;  in rb_prev()
368 void rb_replace_node(struct rb_node *victim, struct rb_node *new,  in rb_replace_node()
371 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()
380 		root->rb_node = new;  in rb_replace_node()