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 = ext2fs_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 = ext2fs_rb_parent(node);  in __rb_rotate_right()
67 		root->rb_node = left;  in __rb_rotate_right()
71 void ext2fs_rb_insert_color(struct rb_node *node, struct rb_root *root)  in ext2fs_rb_insert_color()
73 	struct rb_node *parent, *gparent;  in ext2fs_rb_insert_color()
82 				register struct rb_node *uncle = gparent->rb_right;  in ext2fs_rb_insert_color()
95 				register struct rb_node *tmp;  in ext2fs_rb_insert_color()
107 				register struct rb_node *uncle = gparent->rb_left;  in ext2fs_rb_insert_color()
120 				register struct rb_node *tmp;  in ext2fs_rb_insert_color()
133 	ext2fs_rb_set_black(root->rb_node);  in ext2fs_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 || ext2fs_rb_is_black(node)) && node != root->rb_node)  in __rb_erase_color()
173 				node = root->rb_node;  in __rb_erase_color()
207 				node = root->rb_node;  in __rb_erase_color()
216 void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)  in ext2fs_rb_erase()
218 	struct rb_node *child, *parent;  in ext2fs_rb_erase()
227 		struct rb_node *old = node, *left;  in ext2fs_rb_erase()
239 			root->rb_node = node;  in ext2fs_rb_erase()
276 		root->rb_node = child;  in ext2fs_rb_erase()
283 static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)  in ext2fs_rb_augment_path()
285 	struct rb_node *parent;  in ext2fs_rb_augment_path()
306 void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)  in ext2fs_rb_augment_insert()
320 struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)  in ext2fs_rb_augment_erase_begin()
322 	struct rb_node *deepest;  in ext2fs_rb_augment_erase_begin()
345 void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)  in ext2fs_rb_augment_erase_end()
354 struct rb_node *ext2fs_rb_first(const struct rb_root *root)  in ext2fs_rb_first()
356 	struct rb_node	*n;  in ext2fs_rb_first()
358 	n = root->rb_node;  in ext2fs_rb_first()
366 struct rb_node *ext2fs_rb_last(const struct rb_root *root)  in ext2fs_rb_last()
368 	struct rb_node	*n;  in ext2fs_rb_last()
370 	n = root->rb_node;  in ext2fs_rb_last()
378 struct rb_node *ext2fs_rb_next(struct rb_node *node)  in ext2fs_rb_next()
380 	struct rb_node *parent;  in ext2fs_rb_next()
391 		return (struct rb_node *)node;  in ext2fs_rb_next()
406 struct rb_node *ext2fs_rb_prev(struct rb_node *node)  in ext2fs_rb_prev()
408 	struct rb_node *parent;  in ext2fs_rb_prev()
419 		return (struct rb_node *)node;  in ext2fs_rb_prev()
430 void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,  in ext2fs_rb_replace_node()
433 	struct rb_node *parent = ext2fs_rb_parent(victim);  in ext2fs_rb_replace_node()
442 		root->rb_node = new;  in ext2fs_rb_replace_node()