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()
286 struct rb_node *ext2fs_rb_first(const struct rb_root *root)  in ext2fs_rb_first()
288 	struct rb_node	*n;  in ext2fs_rb_first()
290 	n = root->rb_node;  in ext2fs_rb_first()
298 struct rb_node *ext2fs_rb_last(const struct rb_root *root)  in ext2fs_rb_last()
300 	struct rb_node	*n;  in ext2fs_rb_last()
302 	n = root->rb_node;  in ext2fs_rb_last()
310 struct rb_node *ext2fs_rb_next(struct rb_node *node)  in ext2fs_rb_next()
312 	struct rb_node *parent;  in ext2fs_rb_next()
323 		return (struct rb_node *)node;  in ext2fs_rb_next()
338 struct rb_node *ext2fs_rb_prev(struct rb_node *node)  in ext2fs_rb_prev()
340 	struct rb_node *parent;  in ext2fs_rb_prev()
351 		return (struct rb_node *)node;  in ext2fs_rb_prev()
362 void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,  in ext2fs_rb_replace_node()
365 	struct rb_node *parent = ext2fs_rb_parent(victim);  in ext2fs_rb_replace_node()
374 		root->rb_node = new;  in ext2fs_rb_replace_node()