11a59d1b8SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */
21da177e4SLinus Torvalds /*
31da177e4SLinus Torvalds Red Black Trees
41da177e4SLinus Torvalds (C) 1999 Andrea Arcangeli <andrea@suse.de>
51da177e4SLinus Torvalds
61da177e4SLinus Torvalds
71da177e4SLinus Torvalds linux/include/linux/rbtree.h
81da177e4SLinus Torvalds
91da177e4SLinus Torvalds To use rbtrees you'll have to implement your own insert and search cores.
101da177e4SLinus Torvalds This will avoid us to use callbacks and to drop drammatically performances.
111da177e4SLinus Torvalds I know it's not the cleaner way, but in C (not in C++) to get
121da177e4SLinus Torvalds performances and genericity...
131da177e4SLinus Torvalds
1414bbe3e3SMatthew Wilcox (Oracle) See Documentation/core-api/rbtree.rst for documentation and samples.
151da177e4SLinus Torvalds */
161da177e4SLinus Torvalds
171da177e4SLinus Torvalds #ifndef _LINUX_RBTREE_H
181da177e4SLinus Torvalds #define _LINUX_RBTREE_H
191da177e4SLinus Torvalds
20*4815a360SAndy Shevchenko #include <linux/container_of.h>
21089050caSSebastian Andrzej Siewior #include <linux/rbtree_types.h>
22089050caSSebastian Andrzej Siewior
231da177e4SLinus Torvalds #include <linux/stddef.h>
24d72da4a4SPeter Zijlstra #include <linux/rcupdate.h>
251da177e4SLinus Torvalds
26bf7ad8eeSMichel Lespinasse #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
2755a98102SDavid Woodhouse
281da177e4SLinus Torvalds #define rb_entry(ptr, type, member) container_of(ptr, type, member)
291da177e4SLinus Torvalds
30a460beceSDavidlohr Bueso #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
31dd67d051SJens Axboe
327647f14fSJohn de la Garza /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
33bf7ad8eeSMichel Lespinasse #define RB_EMPTY_NODE(node) \
34bf7ad8eeSMichel Lespinasse ((node)->__rb_parent_color == (unsigned long)(node))
35bf7ad8eeSMichel Lespinasse #define RB_CLEAR_NODE(node) \
36bf7ad8eeSMichel Lespinasse ((node)->__rb_parent_color = (unsigned long)(node))
374c199a93SMichel Lespinasse
3888d19cf3SJohn Stultz
391da177e4SLinus Torvalds extern void rb_insert_color(struct rb_node *, struct rb_root *);
401da177e4SLinus Torvalds extern void rb_erase(struct rb_node *, struct rb_root *);
411da177e4SLinus Torvalds
4214b94af0SMichel Lespinasse
431da177e4SLinus Torvalds /* Find logical next and previous nodes in a tree */
44f4b477c4SArtem Bityutskiy extern struct rb_node *rb_next(const struct rb_node *);
45f4b477c4SArtem Bityutskiy extern struct rb_node *rb_prev(const struct rb_node *);
46f4b477c4SArtem Bityutskiy extern struct rb_node *rb_first(const struct rb_root *);
47f4b477c4SArtem Bityutskiy extern struct rb_node *rb_last(const struct rb_root *);
481da177e4SLinus Torvalds
499dee5c51SCody P Schafer /* Postorder iteration - always visit the parent after its children */
509dee5c51SCody P Schafer extern struct rb_node *rb_first_postorder(const struct rb_root *);
519dee5c51SCody P Schafer extern struct rb_node *rb_next_postorder(const struct rb_node *);
529dee5c51SCody P Schafer
531da177e4SLinus Torvalds /* Fast replacement of a single node without remove/rebalance/add/rebalance */
541da177e4SLinus Torvalds extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
551da177e4SLinus Torvalds struct rb_root *root);
56c1adf200SDavid Howells extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
57c1adf200SDavid Howells struct rb_root *root);
581da177e4SLinus Torvalds
rb_link_node(struct rb_node * node,struct rb_node * parent,struct rb_node ** rb_link)591da177e4SLinus Torvalds static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
601da177e4SLinus Torvalds struct rb_node **rb_link)
611da177e4SLinus Torvalds {
62bf7ad8eeSMichel Lespinasse node->__rb_parent_color = (unsigned long)parent;
631da177e4SLinus Torvalds node->rb_left = node->rb_right = NULL;
641da177e4SLinus Torvalds
651da177e4SLinus Torvalds *rb_link = node;
661da177e4SLinus Torvalds }
671da177e4SLinus Torvalds
rb_link_node_rcu(struct rb_node * node,struct rb_node * parent,struct rb_node ** rb_link)68d72da4a4SPeter Zijlstra static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
69d72da4a4SPeter Zijlstra struct rb_node **rb_link)
70d72da4a4SPeter Zijlstra {
71d72da4a4SPeter Zijlstra node->__rb_parent_color = (unsigned long)parent;
72d72da4a4SPeter Zijlstra node->rb_left = node->rb_right = NULL;
73d72da4a4SPeter Zijlstra
74d72da4a4SPeter Zijlstra rcu_assign_pointer(*rb_link, node);
75d72da4a4SPeter Zijlstra }
76d72da4a4SPeter Zijlstra
771310a5a9SJan Kara #define rb_entry_safe(ptr, type, member) \
781310a5a9SJan Kara ({ typeof(ptr) ____ptr = (ptr); \
791310a5a9SJan Kara ____ptr ? rb_entry(____ptr, type, member) : NULL; \
801310a5a9SJan Kara })
811310a5a9SJan Kara
822b529089SCody P Schafer /**
838de1ee7eSCody P Schafer * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
848de1ee7eSCody P Schafer * given type allowing the backing memory of @pos to be invalidated
852b529089SCody P Schafer *
862b529089SCody P Schafer * @pos: the 'type *' to use as a loop cursor.
872b529089SCody P Schafer * @n: another 'type *' to use as temporary storage
882b529089SCody P Schafer * @root: 'rb_root *' of the rbtree.
892b529089SCody P Schafer * @field: the name of the rb_node field within 'type'.
908de1ee7eSCody P Schafer *
918de1ee7eSCody P Schafer * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
928de1ee7eSCody P Schafer * list_for_each_entry_safe() and allows the iteration to continue independent
938de1ee7eSCody P Schafer * of changes to @pos by the body of the loop.
948de1ee7eSCody P Schafer *
958de1ee7eSCody P Schafer * Note, however, that it cannot handle other modifications that re-order the
968de1ee7eSCody P Schafer * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
978de1ee7eSCody P Schafer * rb_erase() may rebalance the tree, causing us to miss some nodes.
982b529089SCody P Schafer */
992b529089SCody P Schafer #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
1001310a5a9SJan Kara for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
1011310a5a9SJan Kara pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
1021310a5a9SJan Kara typeof(*pos), field); 1; }); \
1031310a5a9SJan Kara pos = n)
1042b529089SCody P Schafer
1059f973cb3SMichel Lespinasse /* Same as rb_first(), but O(1) */
1069f973cb3SMichel Lespinasse #define rb_first_cached(root) (root)->rb_leftmost
1079f973cb3SMichel Lespinasse
rb_insert_color_cached(struct rb_node * node,struct rb_root_cached * root,bool leftmost)1089f973cb3SMichel Lespinasse static inline void rb_insert_color_cached(struct rb_node *node,
1099f973cb3SMichel Lespinasse struct rb_root_cached *root,
1109f973cb3SMichel Lespinasse bool leftmost)
1119f973cb3SMichel Lespinasse {
1129f973cb3SMichel Lespinasse if (leftmost)
1139f973cb3SMichel Lespinasse root->rb_leftmost = node;
1149f973cb3SMichel Lespinasse rb_insert_color(node, &root->rb_root);
1159f973cb3SMichel Lespinasse }
1169f973cb3SMichel Lespinasse
1178ecca394SPeter Zijlstra
1188ecca394SPeter Zijlstra static inline struct rb_node *
rb_erase_cached(struct rb_node * node,struct rb_root_cached * root)1198ecca394SPeter Zijlstra rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
1209f973cb3SMichel Lespinasse {
1218ecca394SPeter Zijlstra struct rb_node *leftmost = NULL;
1228ecca394SPeter Zijlstra
1239f973cb3SMichel Lespinasse if (root->rb_leftmost == node)
1248ecca394SPeter Zijlstra leftmost = root->rb_leftmost = rb_next(node);
1258ecca394SPeter Zijlstra
1269f973cb3SMichel Lespinasse rb_erase(node, &root->rb_root);
1278ecca394SPeter Zijlstra
1288ecca394SPeter Zijlstra return leftmost;
1299f973cb3SMichel Lespinasse }
1309f973cb3SMichel Lespinasse
rb_replace_node_cached(struct rb_node * victim,struct rb_node * new,struct rb_root_cached * root)1319f973cb3SMichel Lespinasse static inline void rb_replace_node_cached(struct rb_node *victim,
1329f973cb3SMichel Lespinasse struct rb_node *new,
1339f973cb3SMichel Lespinasse struct rb_root_cached *root)
1349f973cb3SMichel Lespinasse {
1359f973cb3SMichel Lespinasse if (root->rb_leftmost == victim)
1369f973cb3SMichel Lespinasse root->rb_leftmost = new;
1379f973cb3SMichel Lespinasse rb_replace_node(victim, new, &root->rb_root);
1389f973cb3SMichel Lespinasse }
1399f973cb3SMichel Lespinasse
1402d24dd57SPeter Zijlstra /*
1412d24dd57SPeter Zijlstra * The below helper functions use 2 operators with 3 different
1422d24dd57SPeter Zijlstra * calling conventions. The operators are related like:
1432d24dd57SPeter Zijlstra *
1442d24dd57SPeter Zijlstra * comp(a->key,b) < 0 := less(a,b)
1452d24dd57SPeter Zijlstra * comp(a->key,b) > 0 := less(b,a)
1462d24dd57SPeter Zijlstra * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
1472d24dd57SPeter Zijlstra *
1482d24dd57SPeter Zijlstra * If these operators define a partial order on the elements we make no
1492d24dd57SPeter Zijlstra * guarantee on which of the elements matching the key is found. See
1502d24dd57SPeter Zijlstra * rb_find().
1512d24dd57SPeter Zijlstra *
1522d24dd57SPeter Zijlstra * The reason for this is to allow the find() interface without requiring an
1532d24dd57SPeter Zijlstra * on-stack dummy object, which might not be feasible due to object size.
1542d24dd57SPeter Zijlstra */
1552d24dd57SPeter Zijlstra
1562d24dd57SPeter Zijlstra /**
1572d24dd57SPeter Zijlstra * rb_add_cached() - insert @node into the leftmost cached tree @tree
1582d24dd57SPeter Zijlstra * @node: node to insert
1592d24dd57SPeter Zijlstra * @tree: leftmost cached tree to insert @node into
1602d24dd57SPeter Zijlstra * @less: operator defining the (partial) node order
1618ecca394SPeter Zijlstra *
1628ecca394SPeter Zijlstra * Returns @node when it is the new leftmost, or NULL.
1632d24dd57SPeter Zijlstra */
1648ecca394SPeter Zijlstra static __always_inline struct rb_node *
rb_add_cached(struct rb_node * node,struct rb_root_cached * tree,bool (* less)(struct rb_node *,const struct rb_node *))1652d24dd57SPeter Zijlstra rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
1662d24dd57SPeter Zijlstra bool (*less)(struct rb_node *, const struct rb_node *))
1672d24dd57SPeter Zijlstra {
1682d24dd57SPeter Zijlstra struct rb_node **link = &tree->rb_root.rb_node;
1692d24dd57SPeter Zijlstra struct rb_node *parent = NULL;
1702d24dd57SPeter Zijlstra bool leftmost = true;
1712d24dd57SPeter Zijlstra
1722d24dd57SPeter Zijlstra while (*link) {
1732d24dd57SPeter Zijlstra parent = *link;
1742d24dd57SPeter Zijlstra if (less(node, parent)) {
1752d24dd57SPeter Zijlstra link = &parent->rb_left;
1762d24dd57SPeter Zijlstra } else {
1772d24dd57SPeter Zijlstra link = &parent->rb_right;
1782d24dd57SPeter Zijlstra leftmost = false;
1792d24dd57SPeter Zijlstra }
1802d24dd57SPeter Zijlstra }
1812d24dd57SPeter Zijlstra
1822d24dd57SPeter Zijlstra rb_link_node(node, parent, link);
1832d24dd57SPeter Zijlstra rb_insert_color_cached(node, tree, leftmost);
1848ecca394SPeter Zijlstra
1858ecca394SPeter Zijlstra return leftmost ? node : NULL;
1862d24dd57SPeter Zijlstra }
1872d24dd57SPeter Zijlstra
1882d24dd57SPeter Zijlstra /**
1892d24dd57SPeter Zijlstra * rb_add() - insert @node into @tree
1902d24dd57SPeter Zijlstra * @node: node to insert
1912d24dd57SPeter Zijlstra * @tree: tree to insert @node into
1922d24dd57SPeter Zijlstra * @less: operator defining the (partial) node order
1932d24dd57SPeter Zijlstra */
1942d24dd57SPeter Zijlstra static __always_inline void
rb_add(struct rb_node * node,struct rb_root * tree,bool (* less)(struct rb_node *,const struct rb_node *))1952d24dd57SPeter Zijlstra rb_add(struct rb_node *node, struct rb_root *tree,
1962d24dd57SPeter Zijlstra bool (*less)(struct rb_node *, const struct rb_node *))
1972d24dd57SPeter Zijlstra {
1982d24dd57SPeter Zijlstra struct rb_node **link = &tree->rb_node;
1992d24dd57SPeter Zijlstra struct rb_node *parent = NULL;
2002d24dd57SPeter Zijlstra
2012d24dd57SPeter Zijlstra while (*link) {
2022d24dd57SPeter Zijlstra parent = *link;
2032d24dd57SPeter Zijlstra if (less(node, parent))
2042d24dd57SPeter Zijlstra link = &parent->rb_left;
2052d24dd57SPeter Zijlstra else
2062d24dd57SPeter Zijlstra link = &parent->rb_right;
2072d24dd57SPeter Zijlstra }
2082d24dd57SPeter Zijlstra
2092d24dd57SPeter Zijlstra rb_link_node(node, parent, link);
2102d24dd57SPeter Zijlstra rb_insert_color(node, tree);
2112d24dd57SPeter Zijlstra }
2122d24dd57SPeter Zijlstra
2132d24dd57SPeter Zijlstra /**
2142d24dd57SPeter Zijlstra * rb_find_add() - find equivalent @node in @tree, or add @node
2152d24dd57SPeter Zijlstra * @node: node to look-for / insert
2162d24dd57SPeter Zijlstra * @tree: tree to search / modify
2172d24dd57SPeter Zijlstra * @cmp: operator defining the node order
2182d24dd57SPeter Zijlstra *
2192d24dd57SPeter Zijlstra * Returns the rb_node matching @node, or NULL when no match is found and @node
2202d24dd57SPeter Zijlstra * is inserted.
2212d24dd57SPeter Zijlstra */
2222d24dd57SPeter Zijlstra static __always_inline struct rb_node *
rb_find_add(struct rb_node * node,struct rb_root * tree,int (* cmp)(struct rb_node *,const struct rb_node *))2232d24dd57SPeter Zijlstra rb_find_add(struct rb_node *node, struct rb_root *tree,
2242d24dd57SPeter Zijlstra int (*cmp)(struct rb_node *, const struct rb_node *))
2252d24dd57SPeter Zijlstra {
2262d24dd57SPeter Zijlstra struct rb_node **link = &tree->rb_node;
2272d24dd57SPeter Zijlstra struct rb_node *parent = NULL;
2282d24dd57SPeter Zijlstra int c;
2292d24dd57SPeter Zijlstra
2302d24dd57SPeter Zijlstra while (*link) {
2312d24dd57SPeter Zijlstra parent = *link;
2322d24dd57SPeter Zijlstra c = cmp(node, parent);
2332d24dd57SPeter Zijlstra
2342d24dd57SPeter Zijlstra if (c < 0)
2352d24dd57SPeter Zijlstra link = &parent->rb_left;
2362d24dd57SPeter Zijlstra else if (c > 0)
2372d24dd57SPeter Zijlstra link = &parent->rb_right;
2382d24dd57SPeter Zijlstra else
2392d24dd57SPeter Zijlstra return parent;
2402d24dd57SPeter Zijlstra }
2412d24dd57SPeter Zijlstra
2422d24dd57SPeter Zijlstra rb_link_node(node, parent, link);
2432d24dd57SPeter Zijlstra rb_insert_color(node, tree);
2442d24dd57SPeter Zijlstra return NULL;
2452d24dd57SPeter Zijlstra }
2462d24dd57SPeter Zijlstra
2472d24dd57SPeter Zijlstra /**
2482d24dd57SPeter Zijlstra * rb_find() - find @key in tree @tree
2492d24dd57SPeter Zijlstra * @key: key to match
2502d24dd57SPeter Zijlstra * @tree: tree to search
2512d24dd57SPeter Zijlstra * @cmp: operator defining the node order
2522d24dd57SPeter Zijlstra *
2532d24dd57SPeter Zijlstra * Returns the rb_node matching @key or NULL.
2542d24dd57SPeter Zijlstra */
2552d24dd57SPeter Zijlstra static __always_inline struct rb_node *
rb_find(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *))2562d24dd57SPeter Zijlstra rb_find(const void *key, const struct rb_root *tree,
2572d24dd57SPeter Zijlstra int (*cmp)(const void *key, const struct rb_node *))
2582d24dd57SPeter Zijlstra {
2592d24dd57SPeter Zijlstra struct rb_node *node = tree->rb_node;
2602d24dd57SPeter Zijlstra
2612d24dd57SPeter Zijlstra while (node) {
2622d24dd57SPeter Zijlstra int c = cmp(key, node);
2632d24dd57SPeter Zijlstra
2642d24dd57SPeter Zijlstra if (c < 0)
2652d24dd57SPeter Zijlstra node = node->rb_left;
2662d24dd57SPeter Zijlstra else if (c > 0)
2672d24dd57SPeter Zijlstra node = node->rb_right;
2682d24dd57SPeter Zijlstra else
2692d24dd57SPeter Zijlstra return node;
2702d24dd57SPeter Zijlstra }
2712d24dd57SPeter Zijlstra
2722d24dd57SPeter Zijlstra return NULL;
2732d24dd57SPeter Zijlstra }
2742d24dd57SPeter Zijlstra
2752d24dd57SPeter Zijlstra /**
2762d24dd57SPeter Zijlstra * rb_find_first() - find the first @key in @tree
2772d24dd57SPeter Zijlstra * @key: key to match
2782d24dd57SPeter Zijlstra * @tree: tree to search
2792d24dd57SPeter Zijlstra * @cmp: operator defining node order
2802d24dd57SPeter Zijlstra *
2812d24dd57SPeter Zijlstra * Returns the leftmost node matching @key, or NULL.
2822d24dd57SPeter Zijlstra */
2832d24dd57SPeter Zijlstra static __always_inline struct rb_node *
rb_find_first(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *))2842d24dd57SPeter Zijlstra rb_find_first(const void *key, const struct rb_root *tree,
2852d24dd57SPeter Zijlstra int (*cmp)(const void *key, const struct rb_node *))
2862d24dd57SPeter Zijlstra {
2872d24dd57SPeter Zijlstra struct rb_node *node = tree->rb_node;
2882d24dd57SPeter Zijlstra struct rb_node *match = NULL;
2892d24dd57SPeter Zijlstra
2902d24dd57SPeter Zijlstra while (node) {
2912d24dd57SPeter Zijlstra int c = cmp(key, node);
2922d24dd57SPeter Zijlstra
2932d24dd57SPeter Zijlstra if (c <= 0) {
2942d24dd57SPeter Zijlstra if (!c)
2952d24dd57SPeter Zijlstra match = node;
2962d24dd57SPeter Zijlstra node = node->rb_left;
2972d24dd57SPeter Zijlstra } else if (c > 0) {
2982d24dd57SPeter Zijlstra node = node->rb_right;
2992d24dd57SPeter Zijlstra }
3002d24dd57SPeter Zijlstra }
3012d24dd57SPeter Zijlstra
3022d24dd57SPeter Zijlstra return match;
3032d24dd57SPeter Zijlstra }
3042d24dd57SPeter Zijlstra
3052d24dd57SPeter Zijlstra /**
3062d24dd57SPeter Zijlstra * rb_next_match() - find the next @key in @tree
3072d24dd57SPeter Zijlstra * @key: key to match
3082d24dd57SPeter Zijlstra * @tree: tree to search
3092d24dd57SPeter Zijlstra * @cmp: operator defining node order
3102d24dd57SPeter Zijlstra *
3112d24dd57SPeter Zijlstra * Returns the next node matching @key, or NULL.
3122d24dd57SPeter Zijlstra */
3132d24dd57SPeter Zijlstra static __always_inline struct rb_node *
rb_next_match(const void * key,struct rb_node * node,int (* cmp)(const void * key,const struct rb_node *))3142d24dd57SPeter Zijlstra rb_next_match(const void *key, struct rb_node *node,
3152d24dd57SPeter Zijlstra int (*cmp)(const void *key, const struct rb_node *))
3162d24dd57SPeter Zijlstra {
3172d24dd57SPeter Zijlstra node = rb_next(node);
3182d24dd57SPeter Zijlstra if (node && cmp(key, node))
3192d24dd57SPeter Zijlstra node = NULL;
3202d24dd57SPeter Zijlstra return node;
3212d24dd57SPeter Zijlstra }
3222d24dd57SPeter Zijlstra
3232d24dd57SPeter Zijlstra /**
3242d24dd57SPeter Zijlstra * rb_for_each() - iterates a subtree matching @key
3252d24dd57SPeter Zijlstra * @node: iterator
3262d24dd57SPeter Zijlstra * @key: key to match
3272d24dd57SPeter Zijlstra * @tree: tree to search
3282d24dd57SPeter Zijlstra * @cmp: operator defining node order
3292d24dd57SPeter Zijlstra */
3302d24dd57SPeter Zijlstra #define rb_for_each(node, key, tree, cmp) \
3312d24dd57SPeter Zijlstra for ((node) = rb_find_first((key), (tree), (cmp)); \
3322d24dd57SPeter Zijlstra (node); (node) = rb_next_match((key), (node), (cmp)))
3332d24dd57SPeter Zijlstra
3341da177e4SLinus Torvalds #endif /* _LINUX_RBTREE_H */
335