71 static inline void rb_set_black(struct rb_node *rb)  in rb_set_black()
76 static inline struct rb_node *rb_red_parent(struct rb_node *red)  in rb_red_parent()
78 	return (struct rb_node *)red->__rb_parent_color;  in rb_red_parent()
87 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,  in __rb_rotate_set_parents()
90 	struct rb_node *parent = rb_parent(old);  in __rb_rotate_set_parents()
97 __rb_insert(struct rb_node *node, struct rb_root *root,  in __rb_insert()
98 	    bool newleft, struct rb_node **leftmost,  in __rb_insert()
99 	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))  in __rb_insert()
101 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;  in __rb_insert()
243 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,  in ____rb_erase_color()
244 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))  in ____rb_erase_color()
246 	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;  in ____rb_erase_color()
426 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,  in __rb_erase_color()
427 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))  in __rb_erase_color()
440 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}  in dummy_propagate()
441 static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}  in dummy_copy()
442 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}  in dummy_rotate()
450 void rb_insert_color(struct rb_node *node, struct rb_root *root)  in rb_insert_color()
456 void rb_erase(struct rb_node *node, struct rb_root *root)  in rb_erase()
458 	struct rb_node *rebalance;  in rb_erase()
466 void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()
474 void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)  in rb_erase_cached()
476 	struct rb_node *rebalance;  in rb_erase_cached()
491 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,  in __rb_insert_augmented()
492 			   bool newleft, struct rb_node **leftmost,  in __rb_insert_augmented()
493 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))  in __rb_insert_augmented()
502 struct rb_node *rb_first(const struct rb_root *root)  in rb_first()
504 	struct rb_node	*n;  in rb_first()
506 	n = root->rb_node;  in rb_first()
515 struct rb_node *rb_last(const struct rb_root *root)  in rb_last()
517 	struct rb_node	*n;  in rb_last()
519 	n = root->rb_node;  in rb_last()
528 struct rb_node *rb_next(const struct rb_node *node)  in rb_next()
530 	struct rb_node *parent;  in rb_next()
543 		return (struct rb_node *)node;  in rb_next()
560 struct rb_node *rb_prev(const struct rb_node *node)  in rb_prev()
562 	struct rb_node *parent;  in rb_prev()
575 		return (struct rb_node *)node;  in rb_prev()
589 void rb_replace_node(struct rb_node *victim, struct rb_node *new,  in rb_replace_node()
592 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node()
606 void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,  in rb_replace_node_cached()
616 void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,  in rb_replace_node_rcu()
619 	struct rb_node *parent = rb_parent(victim);  in rb_replace_node_rcu()
638 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)  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()
652 	const struct rb_node *parent;  in rb_next_postorder()
665 		return (struct rb_node *)parent;  in rb_next_postorder()
669 struct rb_node *rb_first_postorder(const struct rb_root *root)  in rb_first_postorder()
671 	if (!root->rb_node)  in rb_first_postorder()
674 	return rb_left_deepest_node(root->rb_node);  in rb_first_postorder()