64 __rb_insert(struct rb_node *node, struct rb_root *root,  in __rb_insert()  argument
67 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()
78 			rb_set_parent_color(node, NULL, RB_BLACK);  in __rb_insert()
103 				node = gparent;  in __rb_insert()
104 				parent = rb_parent(node);  in __rb_insert()
105 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
110 			if (node == tmp) {  in __rb_insert()
123 				parent->rb_right = tmp = node->rb_left;  in __rb_insert()
124 				node->rb_left = parent;  in __rb_insert()
128 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
129 				augment_rotate(parent, node);  in __rb_insert()
130 				parent = node;  in __rb_insert()
131 				tmp = node->rb_right;  in __rb_insert()
156 				node = gparent;  in __rb_insert()
157 				parent = rb_parent(node);  in __rb_insert()
158 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
163 			if (node == tmp) {  in __rb_insert()
165 				parent->rb_left = tmp = node->rb_right;  in __rb_insert()
166 				node->rb_right = parent;  in __rb_insert()
170 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
171 				augment_rotate(parent, node);  in __rb_insert()
172 				parent = node;  in __rb_insert()
173 				tmp = node->rb_left;  in __rb_insert()
196 	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;  in ____rb_erase_color()  local
207 		if (node != sibling) {	/* node == parent->rb_left */  in ____rb_erase_color()
250 						node = parent;  in ____rb_erase_color()
251 						parent = rb_parent(node);  in ____rb_erase_color()
322 						node = parent;  in ____rb_erase_color()
323 						parent = rb_parent(node);  in ____rb_erase_color()
369 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}  in dummy_propagate()  argument
377 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()  argument
379 	__rb_insert(node, root, dummy_rotate);  in rb_insert_color()
383 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()  argument
386 	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);  in rb_erase()
399 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,  in __rb_insert_augmented()  argument
402 	__rb_insert(node, root, augment_rotate);  in __rb_insert_augmented()
435 struct rb_node *rb_next(const struct rb_node *node)  in rb_next()  argument
439 	if (RB_EMPTY_NODE(node))  in rb_next()
446 	if (node->rb_right) {  in rb_next()
447 		node = node->rb_right;   in rb_next()
448 		while (node->rb_left)  in rb_next()
449 			node=node->rb_left;  in rb_next()
450 		return (struct rb_node *)node;  in rb_next()
460 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
461 		node = parent;  in rb_next()
467 struct rb_node *rb_prev(const struct rb_node *node)  in rb_prev()  argument
471 	if (RB_EMPTY_NODE(node))  in rb_prev()
478 	if (node->rb_left) {  in rb_prev()
479 		node = node->rb_left;   in rb_prev()
480 		while (node->rb_right)  in rb_prev()
481 			node=node->rb_right;  in rb_prev()
482 		return (struct rb_node *)node;  in rb_prev()
489 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
490 		node = parent;  in rb_prev()
513 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)  in rb_left_deepest_node()  argument
516 		if (node->rb_left)  in rb_left_deepest_node()
517 			node = node->rb_left;  in rb_left_deepest_node()
518 		else if (node->rb_right)  in rb_left_deepest_node()
519 			node = node->rb_right;  in rb_left_deepest_node()
521 			return (struct rb_node *)node;  in rb_left_deepest_node()
525 struct rb_node *rb_next_postorder(const struct rb_node *node)  in rb_next_postorder()  argument
528 	if (!node)  in rb_next_postorder()
530 	parent = rb_parent(node);  in rb_next_postorder()
533 	if (parent && node == parent->rb_left && parent->rb_right) {  in rb_next_postorder()