Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
1/* SPDX-License-Identifier: GPL-2.0-or-later */
2/*
3 Red Black Trees
4 (C) 1999 Andrea Arcangeli <andrea@suse.de>
5
6
7 linux/include/linux/rbtree.h
8
9 To use rbtrees you'll have to implement your own insert and search cores.
10 This will avoid us to use callbacks and to drop drammatically performances.
11 I know it's not the cleaner way, but in C (not in C++) to get
12 performances and genericity...
13
14 See Documentation/core-api/rbtree.rst for documentation and samples.
15*/
16
17#ifndef _LINUX_RBTREE_H
18#define _LINUX_RBTREE_H
19
20#include <linux/container_of.h>
21#include <linux/rbtree_types.h>
22
23#include <linux/stddef.h>
24#include <linux/rcupdate.h>
25
26#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
27
28#define rb_entry(ptr, type, member) container_of(ptr, type, member)
29
30#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
31
32/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
33#define RB_EMPTY_NODE(node) \
34 ((node)->__rb_parent_color == (unsigned long)(node))
35#define RB_CLEAR_NODE(node) \
36 ((node)->__rb_parent_color = (unsigned long)(node))
37
38#define RB_EMPTY_LINKED_NODE(lnode) RB_EMPTY_NODE(&(lnode)->node)
39#define RB_CLEAR_LINKED_NODE(lnode) ({ \
40 RB_CLEAR_NODE(&(lnode)->node); \
41 (lnode)->prev = (lnode)->next = NULL; \
42})
43
44extern void rb_insert_color(struct rb_node *, struct rb_root *);
45extern void rb_erase(struct rb_node *, struct rb_root *);
46extern bool rb_erase_linked(struct rb_node_linked *, struct rb_root_linked *);
47
48/* Find logical next and previous nodes in a tree */
49extern struct rb_node *rb_next(const struct rb_node *);
50extern struct rb_node *rb_prev(const struct rb_node *);
51
52/*
53 * This function returns the first node (in sort order) of the tree.
54 */
55static inline struct rb_node *rb_first(const struct rb_root *root)
56{
57 struct rb_node *n;
58
59 n = root->rb_node;
60 if (!n)
61 return NULL;
62 while (n->rb_left)
63 n = n->rb_left;
64 return n;
65}
66
67/*
68 * This function returns the last node (in sort order) of the tree.
69 */
70static inline struct rb_node *rb_last(const struct rb_root *root)
71{
72 struct rb_node *n;
73
74 n = root->rb_node;
75 if (!n)
76 return NULL;
77 while (n->rb_right)
78 n = n->rb_right;
79 return n;
80}
81
82/* Postorder iteration - always visit the parent after its children */
83extern struct rb_node *rb_first_postorder(const struct rb_root *);
84extern struct rb_node *rb_next_postorder(const struct rb_node *);
85
86/* Fast replacement of a single node without remove/rebalance/add/rebalance */
87extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
88 struct rb_root *root);
89extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
90 struct rb_root *root);
91
92static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
93 struct rb_node **rb_link)
94{
95 node->__rb_parent_color = (unsigned long)parent;
96 node->rb_left = node->rb_right = NULL;
97
98 *rb_link = node;
99}
100
101static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
102 struct rb_node **rb_link)
103{
104 node->__rb_parent_color = (unsigned long)parent;
105 node->rb_left = node->rb_right = NULL;
106
107 rcu_assign_pointer(*rb_link, node);
108}
109
110#define rb_entry_safe(ptr, type, member) \
111 ({ typeof(ptr) ____ptr = (ptr); \
112 ____ptr ? rb_entry(____ptr, type, member) : NULL; \
113 })
114
115/**
116 * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
117 * given type allowing the backing memory of @pos to be invalidated
118 *
119 * @pos: the 'type *' to use as a loop cursor.
120 * @n: another 'type *' to use as temporary storage
121 * @root: 'rb_root *' of the rbtree.
122 * @field: the name of the rb_node field within 'type'.
123 *
124 * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
125 * list_for_each_entry_safe() and allows the iteration to continue independent
126 * of changes to @pos by the body of the loop.
127 *
128 * Note, however, that it cannot handle other modifications that re-order the
129 * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
130 * rb_erase() may rebalance the tree, causing us to miss some nodes.
131 */
132#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
133 for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
134 pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
135 typeof(*pos), field); 1; }); \
136 pos = n)
137
138/* Same as rb_first(), but O(1) */
139#define rb_first_cached(root) (root)->rb_leftmost
140
141static inline void rb_insert_color_cached(struct rb_node *node,
142 struct rb_root_cached *root,
143 bool leftmost)
144{
145 if (leftmost)
146 root->rb_leftmost = node;
147 rb_insert_color(node, &root->rb_root);
148}
149
150
151static inline struct rb_node *
152rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
153{
154 struct rb_node *leftmost = NULL;
155
156 if (root->rb_leftmost == node)
157 leftmost = root->rb_leftmost = rb_next(node);
158
159 rb_erase(node, &root->rb_root);
160
161 return leftmost;
162}
163
164static inline void rb_replace_node_cached(struct rb_node *victim,
165 struct rb_node *new,
166 struct rb_root_cached *root)
167{
168 if (root->rb_leftmost == victim)
169 root->rb_leftmost = new;
170 rb_replace_node(victim, new, &root->rb_root);
171}
172
173/*
174 * The below helper functions use 2 operators with 3 different
175 * calling conventions. The operators are related like:
176 *
177 * comp(a->key,b) < 0 := less(a,b)
178 * comp(a->key,b) > 0 := less(b,a)
179 * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
180 *
181 * If these operators define a partial order on the elements we make no
182 * guarantee on which of the elements matching the key is found. See
183 * rb_find().
184 *
185 * The reason for this is to allow the find() interface without requiring an
186 * on-stack dummy object, which might not be feasible due to object size.
187 */
188
189/**
190 * rb_add_cached() - insert @node into the leftmost cached tree @tree
191 * @node: node to insert
192 * @tree: leftmost cached tree to insert @node into
193 * @less: operator defining the (partial) node order
194 *
195 * Returns @node when it is the new leftmost, or NULL.
196 */
197static __always_inline struct rb_node *
198rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
199 bool (*less)(struct rb_node *, const struct rb_node *))
200{
201 struct rb_node **link = &tree->rb_root.rb_node;
202 struct rb_node *parent = NULL;
203 bool leftmost = true;
204
205 while (*link) {
206 parent = *link;
207 if (less(node, parent)) {
208 link = &parent->rb_left;
209 } else {
210 link = &parent->rb_right;
211 leftmost = false;
212 }
213 }
214
215 rb_link_node(node, parent, link);
216 rb_insert_color_cached(node, tree, leftmost);
217
218 return leftmost ? node : NULL;
219}
220
221static __always_inline void
222__rb_add(struct rb_node *node, struct rb_root *tree,
223 bool (*less)(struct rb_node *, const struct rb_node *),
224 void (*linkop)(struct rb_node *, struct rb_node *, struct rb_node **))
225{
226 struct rb_node **link = &tree->rb_node;
227 struct rb_node *parent = NULL;
228
229 while (*link) {
230 parent = *link;
231 if (less(node, parent))
232 link = &parent->rb_left;
233 else
234 link = &parent->rb_right;
235 }
236
237 linkop(node, parent, link);
238 rb_link_node(node, parent, link);
239 rb_insert_color(node, tree);
240}
241
242#define __node_2_linked_node(_n) \
243 rb_entry((_n), struct rb_node_linked, node)
244
245static inline void
246rb_link_linked_node(struct rb_node *node, struct rb_node *parent, struct rb_node **link)
247{
248 if (!parent)
249 return;
250
251 struct rb_node_linked *nnew = __node_2_linked_node(node);
252 struct rb_node_linked *npar = __node_2_linked_node(parent);
253
254 if (link == &parent->rb_left) {
255 nnew->prev = npar->prev;
256 nnew->next = npar;
257 npar->prev = nnew;
258 if (nnew->prev)
259 nnew->prev->next = nnew;
260 } else {
261 nnew->next = npar->next;
262 nnew->prev = npar;
263 npar->next = nnew;
264 if (nnew->next)
265 nnew->next->prev = nnew;
266 }
267}
268
269/**
270 * rb_add_linked() - insert @node into the leftmost linked tree @tree
271 * @node: node to insert
272 * @tree: linked tree to insert @node into
273 * @less: operator defining the (partial) node order
274 *
275 * Returns @true when @node is the new leftmost, @false otherwise.
276 */
277static __always_inline bool
278rb_add_linked(struct rb_node_linked *node, struct rb_root_linked *tree,
279 bool (*less)(struct rb_node *, const struct rb_node *))
280{
281 __rb_add(&node->node, &tree->rb_root, less, rb_link_linked_node);
282 if (!node->prev)
283 tree->rb_leftmost = node;
284 return !node->prev;
285}
286
287/* Empty linkop function which is optimized away by the compiler */
288static __always_inline void
289rb_link_noop(struct rb_node *n, struct rb_node *p, struct rb_node **l) { }
290
291/**
292 * rb_add() - insert @node into @tree
293 * @node: node to insert
294 * @tree: tree to insert @node into
295 * @less: operator defining the (partial) node order
296 */
297static __always_inline void
298rb_add(struct rb_node *node, struct rb_root *tree,
299 bool (*less)(struct rb_node *, const struct rb_node *))
300{
301 __rb_add(node, tree, less, rb_link_noop);
302}
303
304/**
305 * rb_find_add_cached() - find equivalent @node in @tree, or add @node
306 * @node: node to look-for / insert
307 * @tree: tree to search / modify
308 * @cmp: operator defining the node order
309 *
310 * Returns the rb_node matching @node, or NULL when no match is found and @node
311 * is inserted.
312 */
313static __always_inline struct rb_node *
314rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
315 int (*cmp)(const struct rb_node *new, const struct rb_node *exist))
316{
317 bool leftmost = true;
318 struct rb_node **link = &tree->rb_root.rb_node;
319 struct rb_node *parent = NULL;
320 int c;
321
322 while (*link) {
323 parent = *link;
324 c = cmp(node, parent);
325
326 if (c < 0) {
327 link = &parent->rb_left;
328 } else if (c > 0) {
329 link = &parent->rb_right;
330 leftmost = false;
331 } else {
332 return parent;
333 }
334 }
335
336 rb_link_node(node, parent, link);
337 rb_insert_color_cached(node, tree, leftmost);
338 return NULL;
339}
340
341/**
342 * rb_find_add() - find equivalent @node in @tree, or add @node
343 * @node: node to look-for / insert
344 * @tree: tree to search / modify
345 * @cmp: operator defining the node order
346 *
347 * Returns the rb_node matching @node, or NULL when no match is found and @node
348 * is inserted.
349 */
350static __always_inline struct rb_node *
351rb_find_add(struct rb_node *node, struct rb_root *tree,
352 int (*cmp)(struct rb_node *, const struct rb_node *))
353{
354 struct rb_node **link = &tree->rb_node;
355 struct rb_node *parent = NULL;
356 int c;
357
358 while (*link) {
359 parent = *link;
360 c = cmp(node, parent);
361
362 if (c < 0)
363 link = &parent->rb_left;
364 else if (c > 0)
365 link = &parent->rb_right;
366 else
367 return parent;
368 }
369
370 rb_link_node(node, parent, link);
371 rb_insert_color(node, tree);
372 return NULL;
373}
374
375/**
376 * rb_find_add_rcu() - find equivalent @node in @tree, or add @node
377 * @node: node to look-for / insert
378 * @tree: tree to search / modify
379 * @cmp: operator defining the node order
380 *
381 * Adds a Store-Release for link_node.
382 *
383 * Returns the rb_node matching @node, or NULL when no match is found and @node
384 * is inserted.
385 */
386static __always_inline struct rb_node *
387rb_find_add_rcu(struct rb_node *node, struct rb_root *tree,
388 int (*cmp)(struct rb_node *, const struct rb_node *))
389{
390 struct rb_node **link = &tree->rb_node;
391 struct rb_node *parent = NULL;
392 int c;
393
394 while (*link) {
395 parent = *link;
396 c = cmp(node, parent);
397
398 if (c < 0)
399 link = &parent->rb_left;
400 else if (c > 0)
401 link = &parent->rb_right;
402 else
403 return parent;
404 }
405
406 rb_link_node_rcu(node, parent, link);
407 rb_insert_color(node, tree);
408 return NULL;
409}
410
411/**
412 * rb_find() - find @key in tree @tree
413 * @key: key to match
414 * @tree: tree to search
415 * @cmp: operator defining the node order
416 *
417 * Returns the rb_node matching @key or NULL.
418 */
419static __always_inline struct rb_node *
420rb_find(const void *key, const struct rb_root *tree,
421 int (*cmp)(const void *key, const struct rb_node *))
422{
423 struct rb_node *node = tree->rb_node;
424
425 while (node) {
426 int c = cmp(key, node);
427
428 if (c < 0)
429 node = node->rb_left;
430 else if (c > 0)
431 node = node->rb_right;
432 else
433 return node;
434 }
435
436 return NULL;
437}
438
439/**
440 * rb_find_rcu() - find @key in tree @tree
441 * @key: key to match
442 * @tree: tree to search
443 * @cmp: operator defining the node order
444 *
445 * Notably, tree descent vs concurrent tree rotations is unsound and can result
446 * in false-negatives.
447 *
448 * Returns the rb_node matching @key or NULL.
449 */
450static __always_inline struct rb_node *
451rb_find_rcu(const void *key, const struct rb_root *tree,
452 int (*cmp)(const void *key, const struct rb_node *))
453{
454 struct rb_node *node = tree->rb_node;
455
456 while (node) {
457 int c = cmp(key, node);
458
459 if (c < 0)
460 node = rcu_dereference_raw(node->rb_left);
461 else if (c > 0)
462 node = rcu_dereference_raw(node->rb_right);
463 else
464 return node;
465 }
466
467 return NULL;
468}
469
470/**
471 * rb_find_first() - find the first @key in @tree
472 * @key: key to match
473 * @tree: tree to search
474 * @cmp: operator defining node order
475 *
476 * Returns the leftmost node matching @key, or NULL.
477 */
478static __always_inline struct rb_node *
479rb_find_first(const void *key, const struct rb_root *tree,
480 int (*cmp)(const void *key, const struct rb_node *))
481{
482 struct rb_node *node = tree->rb_node;
483 struct rb_node *match = NULL;
484
485 while (node) {
486 int c = cmp(key, node);
487
488 if (c <= 0) {
489 if (!c)
490 match = node;
491 node = node->rb_left;
492 } else if (c > 0) {
493 node = node->rb_right;
494 }
495 }
496
497 return match;
498}
499
500/**
501 * rb_next_match() - find the next @key in @tree
502 * @key: key to match
503 * @tree: tree to search
504 * @cmp: operator defining node order
505 *
506 * Returns the next node matching @key, or NULL.
507 */
508static __always_inline struct rb_node *
509rb_next_match(const void *key, struct rb_node *node,
510 int (*cmp)(const void *key, const struct rb_node *))
511{
512 node = rb_next(node);
513 if (node && cmp(key, node))
514 node = NULL;
515 return node;
516}
517
518/**
519 * rb_for_each() - iterates a subtree matching @key
520 * @node: iterator
521 * @key: key to match
522 * @tree: tree to search
523 * @cmp: operator defining node order
524 */
525#define rb_for_each(node, key, tree, cmp) \
526 for ((node) = rb_find_first((key), (tree), (cmp)); \
527 (node); (node) = rb_next_match((key), (node), (cmp)))
528
529#endif /* _LINUX_RBTREE_H */