26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  in __rb_rotate_left()
28 	struct rb_node *right = node->rb_right;  in __rb_rotate_left()
29 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_left()
45 		root->rb_node = right;  in __rb_rotate_left()
49 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  in __rb_rotate_right()
51 	struct rb_node *left = node->rb_left;  in __rb_rotate_right()
52 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_right()
68 		root->rb_node = left;  in __rb_rotate_right()
72 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()
74 	struct rb_node *parent, *gparent;  in rb_insert_color()
83 				register struct rb_node *uncle = gparent->rb_right;  in rb_insert_color()
96 				register struct rb_node *tmp;  in rb_insert_color()
108 				register struct rb_node *uncle = gparent->rb_left;  in rb_insert_color()
121 				register struct rb_node *tmp;  in rb_insert_color()
134 	rb_set_black(root->rb_node);  in rb_insert_color()
138 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()
141 	struct rb_node *other;  in __rb_erase_color()
143 	while ((!node || rb_is_black(node)) && node != root->rb_node)  in __rb_erase_color()
175 				node = root->rb_node;  in __rb_erase_color()
209 				node = root->rb_node;  in __rb_erase_color()
218 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()
220 	struct rb_node *child, *parent;  in rb_erase()
229 		struct rb_node *old = node, *left;  in rb_erase()
241 			root->rb_node = node;  in rb_erase()
278 		root->rb_node = child;  in rb_erase()
286 static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)  in rb_augment_path()
288 	struct rb_node *parent;  in rb_augment_path()
309 void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)  in rb_augment_insert()
323 struct rb_node *rb_augment_erase_begin(struct rb_node *node)  in rb_augment_erase_begin()
325 	struct rb_node *deepest;  in rb_augment_erase_begin()
348 void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)  in rb_augment_erase_end()
357 struct rb_node *rb_first(const struct rb_root *root)  in rb_first()
359 	struct rb_node	*n;  in rb_first()
361 	n = root->rb_node;  in rb_first()
370 struct rb_node *rb_last(const struct rb_root *root)  in rb_last()
372 	struct rb_node	*n;  in rb_last()
374 	n = root->rb_node;  in rb_last()
383 struct rb_node *rb_next(const struct rb_node *node)  in rb_next()
385 	struct rb_node *parent;  in rb_next()
396 		return (struct rb_node *)node;  in rb_next()
412 struct rb_node *rb_prev(const struct rb_node *node)  in rb_prev()
414 	struct rb_node *parent;  in rb_prev()
425 		return (struct rb_node *)node;  in rb_prev()
437 void rb_replace_node(struct rb_node *victim, struct rb_node *new,  in rb_replace_node()
440 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()
449 		root->rb_node = new;  in rb_replace_node()