Lines Matching +full:root +full:- +full:node
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) argument
33 #define RB_EMPTY_NODE(node) \ argument
34 ((node)->__rb_parent_color == (unsigned long)(node))
35 #define RB_CLEAR_NODE(node) \ argument
36 ((node)->__rb_parent_color = (unsigned long)(node))
49 /* Postorder iteration - always visit the parent after its children */
53 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
55 struct rb_root *root);
57 struct rb_root *root);
59 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, in rb_link_node() argument
62 node->__rb_parent_color = (unsigned long)parent; in rb_link_node()
63 node->rb_left = node->rb_right = NULL; in rb_link_node()
65 *rb_link = node; in rb_link_node()
68 static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent, in rb_link_node_rcu() argument
71 node->__rb_parent_color = (unsigned long)parent; in rb_link_node_rcu()
72 node->rb_left = node->rb_right = NULL; in rb_link_node_rcu()
74 rcu_assign_pointer(*rb_link, node); in rb_link_node_rcu()
83 * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
88 * @root: 'rb_root *' of the rbtree.
95 * Note, however, that it cannot handle other modifications that re-order the
99 #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ argument
100 for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
101 pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
106 #define rb_first_cached(root) (root)->rb_leftmost argument
108 static inline void rb_insert_color_cached(struct rb_node *node, in rb_insert_color_cached() argument
109 struct rb_root_cached *root, in rb_insert_color_cached() argument
113 root->rb_leftmost = node; in rb_insert_color_cached()
114 rb_insert_color(node, &root->rb_root); in rb_insert_color_cached()
119 rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) in rb_erase_cached() argument
123 if (root->rb_leftmost == node) in rb_erase_cached()
124 leftmost = root->rb_leftmost = rb_next(node); in rb_erase_cached()
126 rb_erase(node, &root->rb_root); in rb_erase_cached()
133 struct rb_root_cached *root) in rb_replace_node_cached() argument
135 if (root->rb_leftmost == victim) in rb_replace_node_cached()
136 root->rb_leftmost = new; in rb_replace_node_cached()
137 rb_replace_node(victim, new, &root->rb_root); in rb_replace_node_cached()
144 * comp(a->key,b) < 0 := less(a,b)
145 * comp(a->key,b) > 0 := less(b,a)
146 * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
153 * on-stack dummy object, which might not be feasible due to object size.
157 * rb_add_cached() - insert @node into the leftmost cached tree @tree
158 * @node: node to insert
159 * @tree: leftmost cached tree to insert @node into
160 * @less: operator defining the (partial) node order
162 * Returns @node when it is the new leftmost, or NULL.
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()
174 if (less(node, parent)) { in rb_add_cached()
175 link = &parent->rb_left; in rb_add_cached()
177 link = &parent->rb_right; in rb_add_cached()
182 rb_link_node(node, parent, link); in rb_add_cached()
183 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
185 return leftmost ? node : NULL; in rb_add_cached()
189 * rb_add() - insert @node into @tree
190 * @node: node to insert
191 * @tree: tree to insert @node into
192 * @less: operator defining the (partial) node order
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()
203 if (less(node, parent)) in rb_add()
204 link = &parent->rb_left; in rb_add()
206 link = &parent->rb_right; in rb_add()
209 rb_link_node(node, parent, link); in rb_add()
210 rb_insert_color(node, tree); in rb_add()
214 * rb_find_add() - find equivalent @node in @tree, or add @node
215 * @node: node to look-for / insert
217 * @cmp: operator defining the node order
219 * Returns the rb_node matching @node, or NULL when no match is found and @node
223 rb_find_add(struct rb_node *node, struct rb_root *tree, in rb_find_add() argument
226 struct rb_node **link = &tree->rb_node; in rb_find_add()
232 c = cmp(node, parent); in rb_find_add()
235 link = &parent->rb_left; in rb_find_add()
237 link = &parent->rb_right; in rb_find_add()
242 rb_link_node(node, parent, link); in rb_find_add()
243 rb_insert_color(node, tree); in rb_find_add()
248 * rb_find_add_rcu() - find equivalent @node in @tree, or add @node
249 * @node: node to look-for / insert
251 * @cmp: operator defining the node order
253 * Adds a Store-Release for link_node.
255 * Returns the rb_node matching @node, or NULL when no match is found and @node
259 rb_find_add_rcu(struct rb_node *node, struct rb_root *tree, in rb_find_add_rcu() argument
262 struct rb_node **link = &tree->rb_node; in rb_find_add_rcu()
268 c = cmp(node, parent); in rb_find_add_rcu()
271 link = &parent->rb_left; in rb_find_add_rcu()
273 link = &parent->rb_right; in rb_find_add_rcu()
278 rb_link_node_rcu(node, parent, link); in rb_find_add_rcu()
279 rb_insert_color(node, tree); in rb_find_add_rcu()
284 * rb_find() - find @key in tree @tree
287 * @cmp: operator defining the node order
295 struct rb_node *node = tree->rb_node; in rb_find() local
297 while (node) { in rb_find()
298 int c = cmp(key, node); in rb_find()
301 node = node->rb_left; in rb_find()
303 node = node->rb_right; in rb_find()
305 return node; in rb_find()
312 * rb_find_rcu() - find @key in tree @tree
315 * @cmp: operator defining the node order
318 * in false-negatives.
326 struct rb_node *node = tree->rb_node; in rb_find_rcu() local
328 while (node) { in rb_find_rcu()
329 int c = cmp(key, node); in rb_find_rcu()
332 node = rcu_dereference_raw(node->rb_left); in rb_find_rcu()
334 node = rcu_dereference_raw(node->rb_right); in rb_find_rcu()
336 return node; in rb_find_rcu()
343 * rb_find_first() - find the first @key in @tree
346 * @cmp: operator defining node order
348 * Returns the leftmost node matching @key, or NULL.
354 struct rb_node *node = tree->rb_node; in rb_find_first() local
357 while (node) { in rb_find_first()
358 int c = cmp(key, node); in rb_find_first()
362 match = node; in rb_find_first()
363 node = node->rb_left; in rb_find_first()
365 node = node->rb_right; in rb_find_first()
373 * rb_next_match() - find the next @key in @tree
376 * @cmp: operator defining node order
378 * Returns the next node matching @key, or NULL.
381 rb_next_match(const void *key, struct rb_node *node, in rb_next_match() argument
384 node = rb_next(node); in rb_next_match()
385 if (node && cmp(key, node)) in rb_next_match()
386 node = NULL; in rb_next_match()
387 return node; in rb_next_match()
391 * rb_for_each() - iterates a subtree matching @key
392 * @node: iterator
395 * @cmp: operator defining node order
397 #define rb_for_each(node, key, tree, cmp) \ argument
398 for ((node) = rb_find_first((key), (tree), (cmp)); \
399 (node); (node) = rb_next_match((key), (node), (cmp)))