28 	struct rb_node *parent = ext2fs_rb_parent(node);  in __rb_rotate_left()  local
34 	ext2fs_rb_set_parent(right, parent);  in __rb_rotate_left()
36 	if (parent)  in __rb_rotate_left()
38 		if (node == parent->rb_left)  in __rb_rotate_left()
39 			parent->rb_left = right;  in __rb_rotate_left()
41 			parent->rb_right = right;  in __rb_rotate_left()
51 	struct rb_node *parent = ext2fs_rb_parent(node);  in __rb_rotate_right()  local
57 	ext2fs_rb_set_parent(left, parent);  in __rb_rotate_right()
59 	if (parent)  in __rb_rotate_right()
61 		if (node == parent->rb_right)  in __rb_rotate_right()
62 			parent->rb_right = left;  in __rb_rotate_right()
64 			parent->rb_left = left;  in __rb_rotate_right()
73 	struct rb_node *parent, *gparent;  in ext2fs_rb_insert_color()  local
75 	while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent))  in ext2fs_rb_insert_color()
77 		gparent = ext2fs_rb_parent(parent);  in ext2fs_rb_insert_color()
79 		if (parent == gparent->rb_left)  in ext2fs_rb_insert_color()
86 					ext2fs_rb_set_black(parent);  in ext2fs_rb_insert_color()
93 			if (parent->rb_right == node)  in ext2fs_rb_insert_color()
96 				__rb_rotate_left(parent, root);  in ext2fs_rb_insert_color()
97 				tmp = parent;  in ext2fs_rb_insert_color()
98 				parent = node;  in ext2fs_rb_insert_color()
102 			ext2fs_rb_set_black(parent);  in ext2fs_rb_insert_color()
111 					ext2fs_rb_set_black(parent);  in ext2fs_rb_insert_color()
118 			if (parent->rb_left == node)  in ext2fs_rb_insert_color()
121 				__rb_rotate_right(parent, root);  in ext2fs_rb_insert_color()
122 				tmp = parent;  in ext2fs_rb_insert_color()
123 				parent = node;  in ext2fs_rb_insert_color()
127 			ext2fs_rb_set_black(parent);  in ext2fs_rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()  argument
143 		if (parent->rb_left == node)  in __rb_erase_color()
145 			other = parent->rb_right;  in __rb_erase_color()
149 				ext2fs_rb_set_red(parent);  in __rb_erase_color()
150 				__rb_rotate_left(parent, root);  in __rb_erase_color()
151 				other = parent->rb_right;  in __rb_erase_color()
157 				node = parent;  in __rb_erase_color()
158 				parent = ext2fs_rb_parent(node);  in __rb_erase_color()
167 					other = parent->rb_right;  in __rb_erase_color()
169 				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));  in __rb_erase_color()
170 				ext2fs_rb_set_black(parent);  in __rb_erase_color()
172 				__rb_rotate_left(parent, root);  in __rb_erase_color()
179 			other = parent->rb_left;  in __rb_erase_color()
183 				ext2fs_rb_set_red(parent);  in __rb_erase_color()
184 				__rb_rotate_right(parent, root);  in __rb_erase_color()
185 				other = parent->rb_left;  in __rb_erase_color()
191 				node = parent;  in __rb_erase_color()
192 				parent = ext2fs_rb_parent(node);  in __rb_erase_color()
201 					other = parent->rb_left;  in __rb_erase_color()
203 				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));  in __rb_erase_color()
204 				ext2fs_rb_set_black(parent);  in __rb_erase_color()
206 				__rb_rotate_right(parent, root);  in __rb_erase_color()
218 	struct rb_node *child, *parent;  in ext2fs_rb_erase()  local
242 		parent = ext2fs_rb_parent(node);  in ext2fs_rb_erase()
245 		if (parent == old) {  in ext2fs_rb_erase()
246 			parent = node;  in ext2fs_rb_erase()
249 				ext2fs_rb_set_parent(child, parent);  in ext2fs_rb_erase()
250 			parent->rb_left = child;  in ext2fs_rb_erase()
263 	parent = ext2fs_rb_parent(node);  in ext2fs_rb_erase()
267 		ext2fs_rb_set_parent(child, parent);  in ext2fs_rb_erase()
268 	if (parent)  in ext2fs_rb_erase()
270 		if (parent->rb_left == node)  in ext2fs_rb_erase()
271 			parent->rb_left = child;  in ext2fs_rb_erase()
273 			parent->rb_right = child;  in ext2fs_rb_erase()
280 		__rb_erase_color(child, parent, root);  in ext2fs_rb_erase()
285 	struct rb_node *parent;  in ext2fs_rb_augment_path()  local
289 	parent = ext2fs_rb_parent(node);  in ext2fs_rb_augment_path()
290 	if (!parent)  in ext2fs_rb_augment_path()
293 	if (node == parent->rb_left && parent->rb_right)  in ext2fs_rb_augment_path()
294 		func(parent->rb_right, data);  in ext2fs_rb_augment_path()
295 	else if (parent->rb_left)  in ext2fs_rb_augment_path()
296 		func(parent->rb_left, data);  in ext2fs_rb_augment_path()
298 	node = parent;  in ext2fs_rb_augment_path()
380 	struct rb_node *parent;  in ext2fs_rb_next()  local
400 	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right)  in ext2fs_rb_next()
401 		node = parent;  in ext2fs_rb_next()
403 	return parent;  in ext2fs_rb_next()
408 	struct rb_node *parent;  in ext2fs_rb_prev()  local
424 	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left)  in ext2fs_rb_prev()
425 		node = parent;  in ext2fs_rb_prev()
427 	return parent;  in ext2fs_rb_prev()
433 	struct rb_node *parent = ext2fs_rb_parent(victim);  in ext2fs_rb_replace_node()  local
436 	if (parent) {  in ext2fs_rb_replace_node()
437 		if (victim == parent->rb_left)  in ext2fs_rb_replace_node()
438 			parent->rb_left = new;  in ext2fs_rb_replace_node()
440 			parent->rb_right = new;  in ext2fs_rb_replace_node()