Blame view
include/linux/rbtree.h
5.1 KB
1a59d1b8e treewide: Replace... |
1 |
/* SPDX-License-Identifier: GPL-2.0-or-later */ |
1da177e4c Linux-2.6.12-rc2 |
2 3 4 5 |
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> |
1da177e4c Linux-2.6.12-rc2 |
6 7 8 9 10 11 12 |
linux/include/linux/rbtree.h To use rbtrees you'll have to implement your own insert and search cores. This will avoid us to use callbacks and to drop drammatically performances. I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... |
14bbe3e33 docs: Add rbtree ... |
13 |
See Documentation/core-api/rbtree.rst for documentation and samples. |
1da177e4c Linux-2.6.12-rc2 |
14 15 16 17 18 19 20 |
*/ #ifndef _LINUX_RBTREE_H #define _LINUX_RBTREE_H #include <linux/kernel.h> #include <linux/stddef.h> |
d72da4a4d rbtree: Make lock... |
21 |
#include <linux/rcupdate.h> |
1da177e4c Linux-2.6.12-rc2 |
22 |
|
bf7ad8eea rbtree: move some... |
23 24 |
struct rb_node { unsigned long __rb_parent_color; |
1da177e4c Linux-2.6.12-rc2 |
25 26 |
struct rb_node *rb_right; struct rb_node *rb_left; |
e977145ae [RBTREE] Add expl... |
27 28 |
} __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */ |
1da177e4c Linux-2.6.12-rc2 |
29 |
|
bf7ad8eea rbtree: move some... |
30 |
struct rb_root { |
1da177e4c Linux-2.6.12-rc2 |
31 32 |
struct rb_node *rb_node; }; |
bf7ad8eea rbtree: move some... |
33 |
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) |
55a981027 [RBTREE] Merge co... |
34 |
|
b945d6b25 rbtree: Undo augm... |
35 |
#define RB_ROOT (struct rb_root) { NULL, } |
1da177e4c Linux-2.6.12-rc2 |
36 |
#define rb_entry(ptr, type, member) container_of(ptr, type, member) |
a460bece0 rbtree: use READ_... |
37 |
#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) |
4c199a93a rbtree: empty nod... |
38 |
|
7647f14fe lib/rbtree.c: fix... |
39 |
/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */ |
bf7ad8eea rbtree: move some... |
40 41 42 43 |
#define RB_EMPTY_NODE(node) \ ((node)->__rb_parent_color == (unsigned long)(node)) #define RB_CLEAR_NODE(node) \ ((node)->__rb_parent_color = (unsigned long)(node)) |
dd67d0515 [PATCH] rbtree: s... |
44 |
|
88d19cf37 timers: Add rb_in... |
45 |
|
1da177e4c Linux-2.6.12-rc2 |
46 47 |
extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); |
14b94af0b rbtree: faster au... |
48 |
|
1da177e4c Linux-2.6.12-rc2 |
49 |
/* Find logical next and previous nodes in a tree */ |
f4b477c47 rbtree: add const... |
50 51 52 53 |
extern struct rb_node *rb_next(const struct rb_node *); extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); |
1da177e4c Linux-2.6.12-rc2 |
54 |
|
9dee5c515 rbtree: add posto... |
55 56 57 |
/* Postorder iteration - always visit the parent after its children */ extern struct rb_node *rb_first_postorder(const struct rb_root *); extern struct rb_node *rb_next_postorder(const struct rb_node *); |
1da177e4c Linux-2.6.12-rc2 |
58 |
/* Fast replacement of a single node without remove/rebalance/add/rebalance */ |
d72da4a4d rbtree: Make lock... |
59 |
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, |
1da177e4c Linux-2.6.12-rc2 |
60 |
struct rb_root *root); |
c1adf2005 Introduce rb_repl... |
61 62 |
extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root); |
1da177e4c Linux-2.6.12-rc2 |
63 |
|
d72da4a4d rbtree: Make lock... |
64 65 |
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) |
1da177e4c Linux-2.6.12-rc2 |
66 |
{ |
bf7ad8eea rbtree: move some... |
67 |
node->__rb_parent_color = (unsigned long)parent; |
1da177e4c Linux-2.6.12-rc2 |
68 69 70 71 |
node->rb_left = node->rb_right = NULL; *rb_link = node; } |
d72da4a4d rbtree: Make lock... |
72 73 74 75 76 77 78 79 |
static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; rcu_assign_pointer(*rb_link, node); } |
1310a5a99 rbtree: fix rbtre... |
80 81 82 83 |
#define rb_entry_safe(ptr, type, member) \ ({ typeof(ptr) ____ptr = (ptr); \ ____ptr ? rb_entry(____ptr, type, member) : NULL; \ }) |
2b5290892 rbtree: add rbtre... |
84 |
/** |
8de1ee7eb rbtree: clarify d... |
85 86 |
* rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of * given type allowing the backing memory of @pos to be invalidated |
2b5290892 rbtree: add rbtre... |
87 88 89 90 91 |
* * @pos: the 'type *' to use as a loop cursor. * @n: another 'type *' to use as temporary storage * @root: 'rb_root *' of the rbtree. * @field: the name of the rb_node field within 'type'. |
8de1ee7eb rbtree: clarify d... |
92 93 94 95 96 97 98 99 |
* * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as * list_for_each_entry_safe() and allows the iteration to continue independent * of changes to @pos by the body of the loop. * * Note, however, that it cannot handle other modifications that re-order the * rbtree it is iterating over. This includes calling rb_erase() on @pos, as * rb_erase() may rebalance the tree, causing us to miss some nodes. |
2b5290892 rbtree: add rbtre... |
100 101 |
*/ #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ |
1310a5a99 rbtree: fix rbtre... |
102 103 104 105 |
for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ typeof(*pos), field); 1; }); \ pos = n) |
2b5290892 rbtree: add rbtre... |
106 |
|
9f973cb38 lib/rbtree: avoid... |
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
/* * Leftmost-cached rbtrees. * * We do not cache the rightmost node based on footprint * size vs number of potential users that could benefit * from O(1) rb_last(). Just not worth it, users that want * this feature can always implement the logic explicitly. * Furthermore, users that want to cache both pointers may * find it a bit asymmetric, but that's ok. */ struct rb_root_cached { struct rb_root rb_root; struct rb_node *rb_leftmost; }; #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } /* Same as rb_first(), but O(1) */ #define rb_first_cached(root) (root)->rb_leftmost static inline void rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root, bool leftmost) { if (leftmost) root->rb_leftmost = node; rb_insert_color(node, &root->rb_root); } static inline void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) { if (root->rb_leftmost == node) root->rb_leftmost = rb_next(node); rb_erase(node, &root->rb_root); } static inline void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, struct rb_root_cached *root) { if (root->rb_leftmost == victim) root->rb_leftmost = new; rb_replace_node(victim, new, &root->rb_root); } |
1da177e4c Linux-2.6.12-rc2 |
152 |
#endif /* _LINUX_RBTREE_H */ |