1 /* SPDX-License-Identifier: GPL-2.0-or-later */
11   I know it's not the cleaner way,  but in C (not in C++) to get
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)
41 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
43 	((node)->__rb_parent_color == (unsigned long)(node))
45 	((node)->__rb_parent_color = (unsigned long)(node))
52 /* Find logical next and previous nodes in a tree */
58 /* Postorder iteration - always visit the parent after its children */
69 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
70 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
81  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
93  * Note, however, that it cannot handle other modifications that re-order the
95  * rb_erase() may rebalance the tree, causing us to miss some nodes.
99 	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
110  * Leftmost-cached rbtrees.
127 #define rb_first_cached(root) (root)->rb_leftmost
134 		root->rb_leftmost = node;  in rb_insert_color_cached()
135 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
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()
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()
159  *	comp(a->key,b) < 0  := less(a,b)
160  *	comp(a->key,b) > 0  := less(b,a)
161  *	comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
168  * on-stack dummy object, which might not be feasible due to object size.
172  * rb_add_cached() - insert @node into the leftmost cached tree @tree
174  * @tree: leftmost cached tree to insert @node into
178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_add_cached()  argument
181 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_add_cached()
188 			link = &parent->rb_left;  in rb_add_cached()
190 			link = &parent->rb_right;  in rb_add_cached()
196 	rb_insert_color_cached(node, tree, leftmost);  in rb_add_cached()
200  * rb_add() - insert @node into @tree
202  * @tree: tree to insert @node into
206 rb_add(struct rb_node *node, struct rb_root *tree,  in rb_add()  argument
209 	struct rb_node **link = &tree->rb_node;  in rb_add()
215 			link = &parent->rb_left;  in rb_add()
217 			link = &parent->rb_right;  in rb_add()
221 	rb_insert_color(node, tree);  in rb_add()
225  * rb_find_add() - find equivalent @node in @tree, or add @node
226  * @node: node to look-for / insert
227  * @tree: tree to search / modify
234 rb_find_add(struct rb_node *node, struct rb_root *tree,  in rb_find_add()  argument
237 	struct rb_node **link = &tree->rb_node;  in rb_find_add()
246 			link = &parent->rb_left;  in rb_find_add()
248 			link = &parent->rb_right;  in rb_find_add()
254 	rb_insert_color(node, tree);  in rb_find_add()
259  * rb_find() - find @key in tree @tree
261  * @tree: tree to search
267 rb_find(const void *key, const struct rb_root *tree,  in rb_find()  argument
270 	struct rb_node *node = tree->rb_node;  in rb_find()
276 			node = node->rb_left;  in rb_find()
278 			node = node->rb_right;  in rb_find()
287  * rb_find_first() - find the first @key in @tree
289  * @tree: tree to search
295 rb_find_first(const void *key, const struct rb_root *tree,  in rb_find_first()  argument
298 	struct rb_node *node = tree->rb_node;  in rb_find_first()
307 			node = node->rb_left;  in rb_find_first()
309 			node = node->rb_right;  in rb_find_first()
317  * rb_next_match() - find the next @key in @tree
319  * @tree: tree to search
335  * rb_for_each() - iterates a subtree matching @key
338  * @tree: tree to search
341 #define rb_for_each(node, key, tree, cmp) \  argument
342 	for ((node) = rb_find_first((key), (tree), (cmp)); \