43 /* Find logical next and previous nodes in a tree */
97  * rb_erase() may rebalance the tree, causing us to miss some nodes.
157  * rb_add_cached() - insert @node into the leftmost cached tree @tree
159  * @tree: leftmost cached tree to insert @node into
165 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_add_cached()  argument
168 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_add_cached()
183 	rb_insert_color_cached(node, tree, leftmost);  in rb_add_cached()
189  * rb_add() - insert @node into @tree
191  * @tree: tree to insert @node into
195 rb_add(struct rb_node *node, struct rb_root *tree,  in rb_add()  argument
198 	struct rb_node **link = &tree->rb_node;  in rb_add()
210 	rb_insert_color(node, tree);  in rb_add()
214  * rb_find_add_cached() - find equivalent @node in @tree, or add @node
216  * @tree: tree to search / modify
223 rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_find_add_cached()  argument
227 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_find_add_cached()
246 	rb_insert_color_cached(node, tree, leftmost);  in rb_find_add_cached()
251  * rb_find_add() - find equivalent @node in @tree, or add @node
253  * @tree: tree to search / modify
260 rb_find_add(struct rb_node *node, struct rb_root *tree,  in rb_find_add()  argument
263 	struct rb_node **link = &tree->rb_node;  in rb_find_add()
280 	rb_insert_color(node, tree);  in rb_find_add()
285  * rb_find_add_rcu() - find equivalent @node in @tree, or add @node
287  * @tree: tree to search / modify
296 rb_find_add_rcu(struct rb_node *node, struct rb_root *tree,  in rb_find_add_rcu()  argument
299 	struct rb_node **link = &tree->rb_node;  in rb_find_add_rcu()
316 	rb_insert_color(node, tree);  in rb_find_add_rcu()
321  * rb_find() - find @key in tree @tree
323  * @tree: tree to search
329 rb_find(const void *key, const struct rb_root *tree,  in rb_find()  argument
332 	struct rb_node *node = tree->rb_node;  in rb_find()
349  * rb_find_rcu() - find @key in tree @tree
351  * @tree: tree to search
354  * Notably, tree descent vs concurrent tree rotations is unsound and can result
360 rb_find_rcu(const void *key, const struct rb_root *tree,  in rb_find_rcu()  argument
363 	struct rb_node *node = tree->rb_node;  in rb_find_rcu()
380  * rb_find_first() - find the first @key in @tree
382  * @tree: tree to search
388 rb_find_first(const void *key, const struct rb_root *tree,  in rb_find_first()  argument
391 	struct rb_node *node = tree->rb_node;  in rb_find_first()
410  * rb_next_match() - find the next @key in @tree
412  * @tree: tree to search
431  * @tree: tree to search
434 #define rb_for_each(node, key, tree, cmp) \  argument
435 	for ((node) = rb_find_first((key), (tree), (cmp)); \