1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14   See Documentation/core-api/rbtree.rst for documentation and samples.
34 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
39 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)  argument
42 #define RB_EMPTY_NODE(node)  \  argument
43 	((node)->__rb_parent_color == (unsigned long)(node))
44 #define RB_CLEAR_NODE(node)  \  argument
45 	((node)->__rb_parent_color = (unsigned long)(node))
58 /* Postorder iteration - always visit the parent after its children */
62 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
64 			    struct rb_root *root);
66 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,  in rb_link_node()  argument
69 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
70 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
72 	*rb_link = node;  in rb_link_node()
81  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
86  * @root:	'rb_root *' of the rbtree.
93  * Note, however, that it cannot handle other modifications that re-order the
97 #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \  argument
98 	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
99 	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
103 static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)  in rb_erase_init()  argument
105 	rb_erase(n, root);  in rb_erase_init()
110  * Leftmost-cached rbtrees.
112  * We do not cache the rightmost node based on footprint
127 #define rb_first_cached(root) (root)->rb_leftmost  argument
129 static inline void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()  argument
130 					  struct rb_root_cached *root,  in rb_insert_color_cached()  argument
134 		root->rb_leftmost = node;  in rb_insert_color_cached()
135 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
138 static inline void rb_erase_cached(struct rb_node *node,  in rb_erase_cached()  argument
139 				   struct rb_root_cached *root)  in rb_erase_cached()  argument
141 	if (root->rb_leftmost == node)  in rb_erase_cached()
142 		root->rb_leftmost = rb_next(node);  in rb_erase_cached()
143 	rb_erase(node, &root->rb_root);  in rb_erase_cached()
148 					  struct rb_root_cached *root)  in rb_replace_node_cached()  argument
150 	if (root->rb_leftmost == victim)  in rb_replace_node_cached()
151 		root->rb_leftmost = new;  in rb_replace_node_cached()
152 	rb_replace_node(victim, new, &root->rb_root);  in rb_replace_node_cached()