25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  in __rb_rotate_left()  argument
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()
30 	if ((node->rb_right = right->rb_left))  in __rb_rotate_left()
31 		ext2fs_rb_set_parent(right->rb_left, node);  in __rb_rotate_left()
32 	right->rb_left = node;  in __rb_rotate_left()
38 		if (node == parent->rb_left)  in __rb_rotate_left()
45 	ext2fs_rb_set_parent(node, right);  in __rb_rotate_left()
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  in __rb_rotate_right()  argument
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()
53 	if ((node->rb_left = left->rb_right))  in __rb_rotate_right()
54 		ext2fs_rb_set_parent(left->rb_right, node);  in __rb_rotate_right()
55 	left->rb_right = node;  in __rb_rotate_right()
61 		if (node == parent->rb_right)  in __rb_rotate_right()
68 	ext2fs_rb_set_parent(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()  argument
75 	while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent))  in ext2fs_rb_insert_color()
88 					node = gparent;  in ext2fs_rb_insert_color()
93 			if (parent->rb_right == node)  in ext2fs_rb_insert_color()
98 				parent = node;  in ext2fs_rb_insert_color()
99 				node = tmp;  in ext2fs_rb_insert_color()
113 					node = gparent;  in ext2fs_rb_insert_color()
118 			if (parent->rb_left == node)  in ext2fs_rb_insert_color()
123 				parent = node;  in ext2fs_rb_insert_color()
124 				node = tmp;  in ext2fs_rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()  argument
141 	while ((!node || ext2fs_rb_is_black(node)) && node != root->rb_node)  in __rb_erase_color()
143 		if (parent->rb_left == node)  in __rb_erase_color()
157 				node = parent;  in __rb_erase_color()
158 				parent = ext2fs_rb_parent(node);  in __rb_erase_color()
173 				node = root->rb_node;  in __rb_erase_color()
191 				node = parent;  in __rb_erase_color()
192 				parent = ext2fs_rb_parent(node);  in __rb_erase_color()
207 				node = root->rb_node;  in __rb_erase_color()
212 	if (node)  in __rb_erase_color()
213 		ext2fs_rb_set_black(node);  in __rb_erase_color()
216 void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)  in ext2fs_rb_erase()  argument
221 	if (!node->rb_left)  in ext2fs_rb_erase()
222 		child = node->rb_right;  in ext2fs_rb_erase()
223 	else if (!node->rb_right)  in ext2fs_rb_erase()
224 		child = node->rb_left;  in ext2fs_rb_erase()
227 		struct rb_node *old = node, *left;  in ext2fs_rb_erase()
229 		node = node->rb_right;  in ext2fs_rb_erase()
230 		while ((left = node->rb_left) != NULL)  in ext2fs_rb_erase()
231 			node = left;  in ext2fs_rb_erase()
235 				ext2fs_rb_parent(old)->rb_left = node;  in ext2fs_rb_erase()
237 				ext2fs_rb_parent(old)->rb_right = node;  in ext2fs_rb_erase()
239 			root->rb_node = node;  in ext2fs_rb_erase()
241 		child = node->rb_right;  in ext2fs_rb_erase()
242 		parent = ext2fs_rb_parent(node);  in ext2fs_rb_erase()
243 		color = ext2fs_rb_color(node);  in ext2fs_rb_erase()
246 			parent = node;  in ext2fs_rb_erase()
252 			node->rb_right = old->rb_right;  in ext2fs_rb_erase()
253 			ext2fs_rb_set_parent(old->rb_right, node);  in ext2fs_rb_erase()
256 		node->rb_parent_color = old->rb_parent_color;  in ext2fs_rb_erase()
257 		node->rb_left = old->rb_left;  in ext2fs_rb_erase()
258 		ext2fs_rb_set_parent(old->rb_left, node);  in ext2fs_rb_erase()
263 	parent = ext2fs_rb_parent(node);  in ext2fs_rb_erase()
264 	color = ext2fs_rb_color(node);  in ext2fs_rb_erase()
270 		if (parent->rb_left == node)  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()  argument
288 	func(node, data);  in ext2fs_rb_augment_path()
289 	parent = ext2fs_rb_parent(node);  in ext2fs_rb_augment_path()
293 	if (node == parent->rb_left && parent->rb_right)  in ext2fs_rb_augment_path()
298 	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()  argument
308 	if (node->rb_left)  in ext2fs_rb_augment_insert()
309 		node = node->rb_left;  in ext2fs_rb_augment_insert()
310 	else if (node->rb_right)  in ext2fs_rb_augment_insert()
311 		node = node->rb_right;  in ext2fs_rb_augment_insert()
313 	ext2fs_rb_augment_path(node, func, 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()  argument
324 	if (!node->rb_right && !node->rb_left)  in ext2fs_rb_augment_erase_begin()
325 		deepest = ext2fs_rb_parent(node);  in ext2fs_rb_augment_erase_begin()
326 	else if (!node->rb_right)  in ext2fs_rb_augment_erase_begin()
327 		deepest = node->rb_left;  in ext2fs_rb_augment_erase_begin()
328 	else if (!node->rb_left)  in ext2fs_rb_augment_erase_begin()
329 		deepest = node->rb_right;  in ext2fs_rb_augment_erase_begin()
331 		deepest = ext2fs_rb_next(node);  in ext2fs_rb_augment_erase_begin()
334 		else if (ext2fs_rb_parent(deepest) != node)  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()  argument
347 	if (node)  in ext2fs_rb_augment_erase_end()
348 		ext2fs_rb_augment_path(node, func, data);  in ext2fs_rb_augment_erase_end()
378 struct rb_node *ext2fs_rb_next(struct rb_node *node)  in ext2fs_rb_next()  argument
382 	if (ext2fs_rb_parent(node) == node)  in ext2fs_rb_next()
387 	if (node->rb_right) {  in ext2fs_rb_next()
388 		node = node->rb_right;  in ext2fs_rb_next()
389 		while (node->rb_left)  in ext2fs_rb_next()
390 			node=node->rb_left;  in ext2fs_rb_next()
391 		return (struct rb_node *)node;  in ext2fs_rb_next()
400 	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right)  in ext2fs_rb_next()
401 		node = parent;  in ext2fs_rb_next()
406 struct rb_node *ext2fs_rb_prev(struct rb_node *node)  in ext2fs_rb_prev()  argument
410 	if (ext2fs_rb_parent(node) == node)  in ext2fs_rb_prev()
415 	if (node->rb_left) {  in ext2fs_rb_prev()
416 		node = node->rb_left;  in ext2fs_rb_prev()
417 		while (node->rb_right)  in ext2fs_rb_prev()
418 			node=node->rb_right;  in ext2fs_rb_prev()
419 		return (struct rb_node *)node;  in ext2fs_rb_prev()
424 	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left)  in ext2fs_rb_prev()
425 		node = parent;  in ext2fs_rb_prev()