1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14   See Documentation/core-api/rbtree.rst for documentation and samples.
26 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
34 	((node)->__rb_parent_color == (unsigned long)(node))
36 	((node)->__rb_parent_color = (unsigned long)(node))
54 	n = root->rb_node;  in rb_first()
57 	while (n->rb_left)  in rb_first()
58 		n = n->rb_left;  in rb_first()
69 	n = root->rb_node;  in rb_last()
72 	while (n->rb_right)  in rb_last()
73 		n = n->rb_right;  in rb_last()
77 /* Postorder iteration - always visit the parent after its children */
90 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
91 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
99 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node_rcu()
100 	node->rb_left = node->rb_right = NULL;  in rb_link_node_rcu()
111  * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
114  * @pos:	the 'type *' to use as a loop cursor.
123  * Note, however, that it cannot handle other modifications that re-order the
129 	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
134 #define rb_first_cached(root) (root)->rb_leftmost
141 		root->rb_leftmost = node;  in rb_insert_color_cached()
142 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
151 	if (root->rb_leftmost == node)  in rb_erase_cached()
152 		leftmost = root->rb_leftmost = rb_next(node);  in rb_erase_cached()
154 	rb_erase(node, &root->rb_root);  in rb_erase_cached()
163 	if (root->rb_leftmost == victim)  in rb_replace_node_cached()
164 		root->rb_leftmost = new;  in rb_replace_node_cached()
165 	rb_replace_node(victim, new, &root->rb_root);  in rb_replace_node_cached()
172  *	comp(a->key,b) < 0  := less(a,b)
173  *	comp(a->key,b) > 0  := less(b,a)
174  *	comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
181  * on-stack dummy object, which might not be feasible due to object size.
185  * rb_add_cached() - insert @node into the leftmost cached tree @tree
196 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_add_cached()
203 			link = &parent->rb_left;  in rb_add_cached()
205 			link = &parent->rb_right;  in rb_add_cached()
217  * rb_add() - insert @node into @tree
226 	struct rb_node **link = &tree->rb_node;  in rb_add()
232 			link = &parent->rb_left;  in rb_add()
234 			link = &parent->rb_right;  in rb_add()
242  * rb_find_add_cached() - find equivalent @node in @tree, or add @node
243  * @node: node to look-for / insert
255 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_find_add_cached()
264 			link = &parent->rb_left;  in rb_find_add_cached()
266 			link = &parent->rb_right;  in rb_find_add_cached()
279  * rb_find_add() - find equivalent @node in @tree, or add @node
280  * @node: node to look-for / insert
291 	struct rb_node **link = &tree->rb_node;  in rb_find_add()
300 			link = &parent->rb_left;  in rb_find_add()
302 			link = &parent->rb_right;  in rb_find_add()
313  * rb_find_add_rcu() - find equivalent @node in @tree, or add @node
314  * @node: node to look-for / insert
318  * Adds a Store-Release for link_node.
327 	struct rb_node **link = &tree->rb_node;  in rb_find_add_rcu()
336 			link = &parent->rb_left;  in rb_find_add_rcu()
338 			link = &parent->rb_right;  in rb_find_add_rcu()
349  * rb_find() - find @key in tree @tree
360 	struct rb_node *node = tree->rb_node;  in rb_find()
366 			node = node->rb_left;  in rb_find()
368 			node = node->rb_right;  in rb_find()
377  * rb_find_rcu() - find @key in tree @tree
383  * in false-negatives.
391 	struct rb_node *node = tree->rb_node;  in rb_find_rcu()
397 			node = rcu_dereference_raw(node->rb_left);  in rb_find_rcu()
399 			node = rcu_dereference_raw(node->rb_right);  in rb_find_rcu()
408  * rb_find_first() - find the first @key in @tree
419 	struct rb_node *node = tree->rb_node;  in rb_find_first()
428 			node = node->rb_left;  in rb_find_first()
430 			node = node->rb_right;  in rb_find_first()
438  * rb_next_match() - find the next @key in @tree
456  * rb_for_each() - iterates a subtree matching @key