1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14   See Documentation/core-api/rbtree.rst for documentation and samples.
35 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
40 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)  argument
43 #define RB_EMPTY_NODE(node)  \  argument
44 	((node)->__rb_parent_color == (unsigned long)(node))
45 #define RB_CLEAR_NODE(node)  \  argument
46 	((node)->__rb_parent_color = (unsigned long)(node))
59 /* Postorder iteration - always visit the parent after its children */
63 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
65 			    struct rb_root *root);
67 				struct rb_root *root);
69 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,  in rb_link_node()  argument
72 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
73 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
75 	*rb_link = node;  in rb_link_node()
78 static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,  in rb_link_node_rcu()  argument
81 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node_rcu()
82 	node->rb_left = node->rb_right = NULL;  in rb_link_node_rcu()
84 	rcu_assign_pointer(*rb_link, node);  in rb_link_node_rcu()
93  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
98  * @root:	'rb_root *' of the rbtree.
105  * Note, however, that it cannot handle other modifications that re-order the
109 #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \  argument
110 	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
111 	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
116  * Leftmost-cached rbtrees.
118  * We do not cache the rightmost node based on footprint
133 #define rb_first_cached(root) (root)->rb_leftmost  argument
135 static inline void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()  argument
136 					  struct rb_root_cached *root,  in rb_insert_color_cached()  argument
140 		root->rb_leftmost = node;  in rb_insert_color_cached()
141 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
144 static inline void rb_erase_cached(struct rb_node *node,  in rb_erase_cached()  argument
145 				   struct rb_root_cached *root)  in rb_erase_cached()  argument
147 	if (root->rb_leftmost == node)  in rb_erase_cached()
148 		root->rb_leftmost = rb_next(node);  in rb_erase_cached()
149 	rb_erase(node, &root->rb_root);  in rb_erase_cached()
154 					  struct rb_root_cached *root)  in rb_replace_node_cached()  argument
156 	if (root->rb_leftmost == victim)  in rb_replace_node_cached()
157 		root->rb_leftmost = new;  in rb_replace_node_cached()
158 	rb_replace_node(victim, new, &root->rb_root);  in rb_replace_node_cached()