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.
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) argument
42 #define RB_EMPTY_NODE(node) \ argument
43 ((node)->__rb_parent_color == (unsigned long)(node))
44 #define RB_CLEAR_NODE(node) \ argument
45 ((node)->__rb_parent_color = (unsigned long)(node))
58 /* Postorder iteration - always visit the parent after its children */
62 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
64 struct rb_root *root);
66 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, in rb_link_node() argument
69 node->__rb_parent_color = (unsigned long)parent; in rb_link_node()
70 node->rb_left = node->rb_right = NULL; in rb_link_node()
72 *rb_link = node; in rb_link_node()
81 * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
86 * @root: 'rb_root *' of the rbtree.
93 * Note, however, that it cannot handle other modifications that re-order the
97 #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ argument
98 for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
99 pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
103 static inline void rb_erase_init(struct rb_node *n, struct rb_root *root) in rb_erase_init() argument
105 rb_erase(n, root); in rb_erase_init()
110 * Leftmost-cached rbtrees.
112 * We do not cache the rightmost node based on footprint
127 #define rb_first_cached(root) (root)->rb_leftmost argument
129 static inline void rb_insert_color_cached(struct rb_node *node, in rb_insert_color_cached() argument
130 struct rb_root_cached *root, in rb_insert_color_cached() argument
134 root->rb_leftmost = node; in rb_insert_color_cached()
135 rb_insert_color(node, &root->rb_root); in rb_insert_color_cached()
138 static inline void rb_erase_cached(struct rb_node *node, in rb_erase_cached() argument
139 struct rb_root_cached *root) in rb_erase_cached() argument
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()
148 struct rb_root_cached *root) in rb_replace_node_cached() argument
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
173 * @node: node to insert
174 * @tree: leftmost cached tree to insert @node into
175 * @less: operator defining the (partial) node order
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()
187 if (less(node, parent)) { in rb_add_cached()
188 link = &parent->rb_left; in rb_add_cached()
190 link = &parent->rb_right; in rb_add_cached()
195 rb_link_node(node, parent, link); in rb_add_cached()
196 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
200 * rb_add() - insert @node into @tree
201 * @node: node to insert
202 * @tree: tree to insert @node into
203 * @less: operator defining the (partial) node order
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()
214 if (less(node, parent)) in rb_add()
215 link = &parent->rb_left; in rb_add()
217 link = &parent->rb_right; in rb_add()
220 rb_link_node(node, parent, link); 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
228 * @cmp: operator defining the node order
230 * Returns the rb_node matching @node, or NULL when no match is found and @node
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()
243 c = cmp(node, parent); in rb_find_add()
246 link = &parent->rb_left; in rb_find_add()
248 link = &parent->rb_right; in rb_find_add()
253 rb_link_node(node, parent, link); in rb_find_add()
254 rb_insert_color(node, tree); in rb_find_add()
259 * rb_find() - find @key in tree @tree
262 * @cmp: operator defining the node order
270 struct rb_node *node = tree->rb_node; in rb_find() local
272 while (node) { in rb_find()
273 int c = cmp(key, node); in rb_find()
276 node = node->rb_left; in rb_find()
278 node = node->rb_right; in rb_find()
280 return node; in rb_find()
287 * rb_find_first() - find the first @key in @tree
290 * @cmp: operator defining node order
292 * Returns the leftmost node matching @key, or NULL.
298 struct rb_node *node = tree->rb_node; in rb_find_first() local
301 while (node) { in rb_find_first()
302 int c = cmp(key, node); in rb_find_first()
306 match = 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
320 * @cmp: operator defining node order
322 * Returns the next node matching @key, or NULL.
325 rb_next_match(const void *key, struct rb_node *node, in rb_next_match() argument
328 node = rb_next(node); in rb_next_match()
329 if (node && cmp(key, node)) in rb_next_match()
330 node = NULL; in rb_next_match()
331 return node; in rb_next_match()
335 * rb_for_each() - iterates a subtree matching @key
336 * @node: iterator
339 * @cmp: operator defining node order
341 #define rb_for_each(node, key, tree, cmp) \ argument
342 for ((node) = rb_find_first((key), (tree), (cmp)); \
343 (node); (node) = rb_next_match((key), (node), (cmp)))