25 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)  in __rb_rotate_left()  argument
27 	rb_node_t * right = node->rb_right;  in __rb_rotate_left()
29 	if ((node->rb_right = right->rb_left))  in __rb_rotate_left()
30 		right->rb_left->rb_parent = node;  in __rb_rotate_left()
31 	right->rb_left = node;  in __rb_rotate_left()
33 	if ((right->rb_parent = node->rb_parent))  in __rb_rotate_left()
35 		if (node == node->rb_parent->rb_left)  in __rb_rotate_left()
36 			node->rb_parent->rb_left = right;  in __rb_rotate_left()
38 			node->rb_parent->rb_right = right;  in __rb_rotate_left()
42 	node->rb_parent = right;  in __rb_rotate_left()
45 static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)  in __rb_rotate_right()  argument
47 	rb_node_t * left = node->rb_left;  in __rb_rotate_right()
49 	if ((node->rb_left = left->rb_right))  in __rb_rotate_right()
50 		left->rb_right->rb_parent = node;  in __rb_rotate_right()
51 	left->rb_right = node;  in __rb_rotate_right()
53 	if ((left->rb_parent = node->rb_parent))  in __rb_rotate_right()
55 		if (node == node->rb_parent->rb_right)  in __rb_rotate_right()
56 			node->rb_parent->rb_right = left;  in __rb_rotate_right()
58 			node->rb_parent->rb_left = left;  in __rb_rotate_right()
62 	node->rb_parent = left;  in __rb_rotate_right()
65 void rb_insert_color(rb_node_t * node, rb_root_t * root)  in rb_insert_color()  argument
69 	while ((parent = node->rb_parent) && parent->rb_color == RB_RED)  in rb_insert_color()
82 					node = gparent;  in rb_insert_color()
87 			if (parent->rb_right == node)  in rb_insert_color()
92 				parent = node;  in rb_insert_color()
93 				node = tmp;  in rb_insert_color()
107 					node = gparent;  in rb_insert_color()
112 			if (parent->rb_left == node)  in rb_insert_color()
117 				parent = node;  in rb_insert_color()
118 				node = tmp;  in rb_insert_color()
131 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,  in __rb_erase_color()  argument
136 	while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)  in __rb_erase_color()
138 		if (parent->rb_left == node)  in __rb_erase_color()
154 				node = parent;  in __rb_erase_color()
155 				parent = node->rb_parent;  in __rb_erase_color()
174 				node = root->rb_node;  in __rb_erase_color()
194 				node = parent;  in __rb_erase_color()
195 				parent = node->rb_parent;  in __rb_erase_color()
214 				node = root->rb_node;  in __rb_erase_color()
219 	if (node)  in __rb_erase_color()
220 		node->rb_color = RB_BLACK;  in __rb_erase_color()
223 void rb_erase(rb_node_t * node, rb_root_t * root)  in rb_erase()  argument
228 	if (!node->rb_left)  in rb_erase()
229 		child = node->rb_right;  in rb_erase()
230 	else if (!node->rb_right)  in rb_erase()
231 		child = node->rb_left;  in rb_erase()
234 		rb_node_t * old = node, * left;  in rb_erase()
236 		node = node->rb_right;  in rb_erase()
237 		while ((left = node->rb_left))  in rb_erase()
238 			node = left;  in rb_erase()
239 		child = node->rb_right;  in rb_erase()
240 		parent = node->rb_parent;  in rb_erase()
241 		color = node->rb_color;  in rb_erase()
247 			if (parent->rb_left == node)  in rb_erase()
255 		if (node->rb_parent == old)  in rb_erase()
256 			parent = node;  in rb_erase()
257 		node->rb_parent = old->rb_parent;  in rb_erase()
258 		node->rb_color = old->rb_color;  in rb_erase()
259 		node->rb_right = old->rb_right;  in rb_erase()
260 		node->rb_left = old->rb_left;  in rb_erase()
265 				old->rb_parent->rb_left = node;  in rb_erase()
267 				old->rb_parent->rb_right = node;  in rb_erase()
269 			root->rb_node = node;  in rb_erase()
271 		old->rb_left->rb_parent = node;  in rb_erase()
273 			old->rb_right->rb_parent = node;  in rb_erase()
277 	parent = node->rb_parent;  in rb_erase()
278 	color = node->rb_color;  in rb_erase()
284 		if (parent->rb_left == node)  in rb_erase()
327 rb_node_t *rb_next(rb_node_t *node)  in rb_next()  argument
331 	if (node->rb_right) {  in rb_next()
332 		node = node->rb_right;  in rb_next()
333 		while (node->rb_left)  in rb_next()
334 			node = node->rb_left;  in rb_next()
335 		return node;  in rb_next()
344 	while (node->rb_parent && node == node->rb_parent->rb_right)  in rb_next()
345 		node = node->rb_parent;  in rb_next()
347 	return node->rb_parent;  in rb_next()
351 rb_node_t *rb_prev(rb_node_t *node)  in rb_prev()  argument
355 	if (node->rb_left) {  in rb_prev()
356 		node = node->rb_left;  in rb_prev()
357 		while (node->rb_right)  in rb_prev()
358 			node = node->rb_right;	   in rb_prev()
359 		return node;  in rb_prev()
364 	while (node->rb_parent && node == node->rb_parent->rb_left)  in rb_prev()
365 		node = node->rb_parent;  in rb_prev()
367 	return node->rb_parent;  in rb_prev()