97 __rb_insert(struct rb_node *node, struct rb_root *root,  in __rb_insert()  argument
101 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()
104 		*leftmost = node;  in __rb_insert()
116 			rb_set_parent_color(node, NULL, RB_BLACK);  in __rb_insert()
149 				node = gparent;  in __rb_insert()
150 				parent = rb_parent(node);  in __rb_insert()
151 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
156 			if (node == tmp) {  in __rb_insert()
170 				tmp = node->rb_left;  in __rb_insert()
172 				WRITE_ONCE(node->rb_left, parent);  in __rb_insert()
176 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
177 				augment_rotate(parent, node);  in __rb_insert()
178 				parent = node;  in __rb_insert()
179 				tmp = node->rb_right;  in __rb_insert()
205 				node = gparent;  in __rb_insert()
206 				parent = rb_parent(node);  in __rb_insert()
207 				rb_set_parent_color(node, parent, RB_RED);  in __rb_insert()
212 			if (node == tmp) {  in __rb_insert()
214 				tmp = node->rb_right;  in __rb_insert()
216 				WRITE_ONCE(node->rb_right, parent);  in __rb_insert()
220 				rb_set_parent_color(parent, node, RB_RED);  in __rb_insert()
221 				augment_rotate(parent, node);  in __rb_insert()
222 				parent = node;  in __rb_insert()
223 				tmp = node->rb_left;  in __rb_insert()
246 	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;  in ____rb_erase_color()  local
257 		if (node != sibling) {	/* node == parent->rb_left */  in ____rb_erase_color()
301 						node = parent;  in ____rb_erase_color()
302 						parent = rb_parent(node);  in ____rb_erase_color()
391 						node = parent;  in ____rb_erase_color()
392 						parent = rb_parent(node);  in ____rb_erase_color()
440 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}  in dummy_propagate()  argument
450 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()  argument
452 	__rb_insert(node, root, false, NULL, dummy_rotate);  in rb_insert_color()
456 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()  argument
459 	rebalance = __rb_erase_augmented(node, root,  in rb_erase()
466 void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()  argument
469 	__rb_insert(node, &root->rb_root, leftmost,  in rb_insert_color_cached()
474 void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)  in rb_erase_cached()  argument
477 	rebalance = __rb_erase_augmented(node, &root->rb_root,  in rb_erase_cached()
491 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,  in __rb_insert_augmented()  argument
495 	__rb_insert(node, root, newleft, leftmost, augment_rotate);  in __rb_insert_augmented()
528 struct rb_node *rb_next(const struct rb_node *node)  in rb_next()  argument
532 	if (RB_EMPTY_NODE(node))  in rb_next()
539 	if (node->rb_right) {  in rb_next()
540 		node = node->rb_right;  in rb_next()
541 		while (node->rb_left)  in rb_next()
542 			node=node->rb_left;  in rb_next()
543 		return (struct rb_node *)node;  in rb_next()
553 	while ((parent = rb_parent(node)) && node == parent->rb_right)  in rb_next()
554 		node = parent;  in rb_next()
560 struct rb_node *rb_prev(const struct rb_node *node)  in rb_prev()  argument
564 	if (RB_EMPTY_NODE(node))  in rb_prev()
571 	if (node->rb_left) {  in rb_prev()
572 		node = node->rb_left;  in rb_prev()
573 		while (node->rb_right)  in rb_prev()
574 			node=node->rb_right;  in rb_prev()
575 		return (struct rb_node *)node;  in rb_prev()
582 	while ((parent = rb_parent(node)) && node == parent->rb_left)  in rb_prev()
583 		node = parent;  in rb_prev()
638 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)  in rb_left_deepest_node()  argument
641 		if (node->rb_left)  in rb_left_deepest_node()
642 			node = node->rb_left;  in rb_left_deepest_node()
643 		else if (node->rb_right)  in rb_left_deepest_node()
644 			node = node->rb_right;  in rb_left_deepest_node()
646 			return (struct rb_node *)node;  in rb_left_deepest_node()
650 struct rb_node *rb_next_postorder(const struct rb_node *node)  in rb_next_postorder()  argument
653 	if (!node)  in rb_next_postorder()
655 	parent = rb_parent(node);  in rb_next_postorder()
658 	if (parent && node == parent->rb_left && parent->rb_right) {  in rb_next_postorder()