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_cached() - 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_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()
233 c = cmp(node, parent); in rb_find_add_cached()
236 link = &parent->rb_left; in rb_find_add_cached()
238 link = &parent->rb_right; in rb_find_add_cached()
245 rb_link_node(node, parent, link); 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
252 * @node: node to look-for / insert
254 * @cmp: operator defining the node order
256 * Returns the rb_node matching @node, or NULL when no match is found and @node
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()
269 c = cmp(node, parent); in rb_find_add()
272 link = &parent->rb_left; in rb_find_add()
274 link = &parent->rb_right; in rb_find_add()
279 rb_link_node(node, parent, link); 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
286 * @node: node to look-for / insert
288 * @cmp: operator defining the node order
290 * Adds a Store-Release for link_node.
292 * Returns the rb_node matching @node, or NULL when no match is found and @node
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()
305 c = cmp(node, parent); in rb_find_add_rcu()
308 link = &parent->rb_left; in rb_find_add_rcu()
310 link = &parent->rb_right; in rb_find_add_rcu()
315 rb_link_node_rcu(node, parent, link); in rb_find_add_rcu()
316 rb_insert_color(node, tree); in rb_find_add_rcu()
321 * rb_find() - find @key in tree @tree
324 * @cmp: operator defining the node order
332 struct rb_node *node = tree->rb_node; in rb_find() local
334 while (node) { in rb_find()
335 int c = cmp(key, node); in rb_find()
338 node = node->rb_left; in rb_find()
340 node = node->rb_right; in rb_find()
342 return node; in rb_find()
349 * rb_find_rcu() - find @key in tree @tree
352 * @cmp: operator defining the node order
355 * in false-negatives.
363 struct rb_node *node = tree->rb_node; in rb_find_rcu() local
365 while (node) { in rb_find_rcu()
366 int c = cmp(key, node); in rb_find_rcu()
369 node = rcu_dereference_raw(node->rb_left); in rb_find_rcu()
371 node = rcu_dereference_raw(node->rb_right); in rb_find_rcu()
373 return node; in rb_find_rcu()
380 * rb_find_first() - find the first @key in @tree
383 * @cmp: operator defining node order
385 * Returns the leftmost node matching @key, or NULL.
391 struct rb_node *node = tree->rb_node; in rb_find_first() local
394 while (node) { in rb_find_first()
395 int c = cmp(key, node); in rb_find_first()
399 match = node; in rb_find_first()
400 node = node->rb_left; in rb_find_first()
402 node = node->rb_right; in rb_find_first()
410 * rb_next_match() - find the next @key in @tree
413 * @cmp: operator defining node order
415 * Returns the next node matching @key, or NULL.
418 rb_next_match(const void *key, struct rb_node *node, in rb_next_match() argument
421 node = rb_next(node); in rb_next_match()
422 if (node && cmp(key, node)) in rb_next_match()
423 node = NULL; in rb_next_match()
424 return node; in rb_next_match()
428 * rb_for_each() - iterates a subtree matching @key
429 * @node: iterator
432 * @cmp: operator defining node order
434 #define rb_for_each(node, key, tree, cmp) \ argument
435 for ((node) = rb_find_first((key), (tree), (cmp)); \
436 (node); (node) = rb_next_match((key), (node), (cmp)))