29 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_left()  local
35 	rb_set_parent(right, parent);  in __rb_rotate_left()
37 	if (parent)  in __rb_rotate_left()
39 		if (node == parent->rb_left)  in __rb_rotate_left()
40 			parent->rb_left = right;  in __rb_rotate_left()
42 			parent->rb_right = right;  in __rb_rotate_left()
52 	struct rb_node *parent = rb_parent(node);  in __rb_rotate_right()  local
58 	rb_set_parent(left, parent);  in __rb_rotate_right()
60 	if (parent)  in __rb_rotate_right()
62 		if (node == parent->rb_right)  in __rb_rotate_right()
63 			parent->rb_right = left;  in __rb_rotate_right()
65 			parent->rb_left = left;  in __rb_rotate_right()
74 	struct rb_node *parent, *gparent;  in rb_insert_color()  local
76 	while ((parent = rb_parent(node)) && rb_is_red(parent))  in rb_insert_color()
78 		gparent = rb_parent(parent);  in rb_insert_color()
80 		if (parent == gparent->rb_left)  in rb_insert_color()
87 					rb_set_black(parent);  in rb_insert_color()
94 			if (parent->rb_right == node)  in rb_insert_color()
97 				__rb_rotate_left(parent, root);  in rb_insert_color()
98 				tmp = parent;  in rb_insert_color()
99 				parent = node;  in rb_insert_color()
103 			rb_set_black(parent);  in rb_insert_color()
112 					rb_set_black(parent);  in rb_insert_color()
119 			if (parent->rb_left == node)  in rb_insert_color()
122 				__rb_rotate_right(parent, root);  in rb_insert_color()
123 				tmp = parent;  in rb_insert_color()
124 				parent = node;  in rb_insert_color()
128 			rb_set_black(parent);  in rb_insert_color()
138 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  in __rb_erase_color()  argument
145 		if (parent->rb_left == node)  in __rb_erase_color()
147 			other = parent->rb_right;  in __rb_erase_color()
151 				rb_set_red(parent);  in __rb_erase_color()
152 				__rb_rotate_left(parent, root);  in __rb_erase_color()
153 				other = parent->rb_right;  in __rb_erase_color()
159 				node = parent;  in __rb_erase_color()
160 				parent = rb_parent(node);  in __rb_erase_color()
169 					other = parent->rb_right;  in __rb_erase_color()
171 				rb_set_color(other, rb_color(parent));  in __rb_erase_color()
172 				rb_set_black(parent);  in __rb_erase_color()
174 				__rb_rotate_left(parent, root);  in __rb_erase_color()
181 			other = parent->rb_left;  in __rb_erase_color()
185 				rb_set_red(parent);  in __rb_erase_color()
186 				__rb_rotate_right(parent, root);  in __rb_erase_color()
187 				other = parent->rb_left;  in __rb_erase_color()
193 				node = parent;  in __rb_erase_color()
194 				parent = rb_parent(node);  in __rb_erase_color()
203 					other = parent->rb_left;  in __rb_erase_color()
205 				rb_set_color(other, rb_color(parent));  in __rb_erase_color()
206 				rb_set_black(parent);  in __rb_erase_color()
208 				__rb_rotate_right(parent, root);  in __rb_erase_color()
220 	struct rb_node *child, *parent;  in rb_erase()  local
244 		parent = rb_parent(node);  in rb_erase()
247 		if (parent == old) {  in rb_erase()
248 			parent = node;  in rb_erase()
251 				rb_set_parent(child, parent);  in rb_erase()
252 			parent->rb_left = child;  in rb_erase()
265 	parent = rb_parent(node);  in rb_erase()
269 		rb_set_parent(child, parent);  in rb_erase()
270 	if (parent)  in rb_erase()
272 		if (parent->rb_left == node)  in rb_erase()
273 			parent->rb_left = child;  in rb_erase()
275 			parent->rb_right = child;  in rb_erase()
282 		__rb_erase_color(child, parent, root);  in rb_erase()
288 	struct rb_node *parent;  in rb_augment_path()  local
292 	parent = rb_parent(node);  in rb_augment_path()
293 	if (!parent)  in rb_augment_path()
296 	if (node == parent->rb_left && parent->rb_right)  in rb_augment_path()
297 		func(parent->rb_right, data);  in rb_augment_path()
298 	else if (parent->rb_left)  in rb_augment_path()
299 		func(parent->rb_left, data);  in rb_augment_path()
301 	node = parent;  in rb_augment_path()
385 	struct rb_node *parent;  in rb_next()  local
405 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
406 		node = parent;  in rb_next()
408 	return parent;  in rb_next()
414 	struct rb_node *parent;  in rb_prev()  local
430 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
431 		node = parent;  in rb_prev()
433 	return parent;  in rb_prev()
440 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()  local
443 	if (parent) {  in rb_replace_node()
444 		if (victim == parent->rb_left)  in rb_replace_node()
445 			parent->rb_left = new;  in rb_replace_node()
447 			parent->rb_right = new;  in rb_replace_node()