1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#ifndef __TOOLS_LINUX_PERF_RBTREE_H
30#define __TOOLS_LINUX_PERF_RBTREE_H
31
32#include <linux/kernel.h>
33#include <linux/stddef.h>
34
35struct rb_node {
36 unsigned long __rb_parent_color;
37 struct rb_node *rb_right;
38 struct rb_node *rb_left;
39} __attribute__((aligned(sizeof(long))));
40
41
42struct rb_root {
43 struct rb_node *rb_node;
44};
45
46#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
47
48#define RB_ROOT (struct rb_root) { NULL, }
49#define rb_entry(ptr, type, member) container_of(ptr, type, member)
50
51#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
52
53
54#define RB_EMPTY_NODE(node) \
55 ((node)->__rb_parent_color == (unsigned long)(node))
56#define RB_CLEAR_NODE(node) \
57 ((node)->__rb_parent_color = (unsigned long)(node))
58
59
60extern void rb_insert_color(struct rb_node *, struct rb_root *);
61extern void rb_erase(struct rb_node *, struct rb_root *);
62
63
64
65extern struct rb_node *rb_next(const struct rb_node *);
66extern struct rb_node *rb_prev(const struct rb_node *);
67extern struct rb_node *rb_first(const struct rb_root *);
68extern struct rb_node *rb_last(const struct rb_root *);
69
70
71extern struct rb_node *rb_first_postorder(const struct rb_root *);
72extern struct rb_node *rb_next_postorder(const struct rb_node *);
73
74
75extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
76 struct rb_root *root);
77
78static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
79 struct rb_node **rb_link)
80{
81 node->__rb_parent_color = (unsigned long)parent;
82 node->rb_left = node->rb_right = NULL;
83
84 *rb_link = node;
85}
86
87#define rb_entry_safe(ptr, type, member) \
88 ({ typeof(ptr) ____ptr = (ptr); \
89 ____ptr ? rb_entry(____ptr, type, member) : NULL; \
90 })
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
110 for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
111 pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
112 typeof(*pos), field); 1; }); \
113 pos = n)
114
115static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)
116{
117 rb_erase(n, root);
118 RB_CLEAR_NODE(n);
119}
120
121
122
123
124
125
126
127
128
129
130
131struct rb_root_cached {
132 struct rb_root rb_root;
133 struct rb_node *rb_leftmost;
134};
135
136#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
137
138
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
150static inline void rb_erase_cached(struct rb_node *node,
151 struct rb_root_cached *root)
152{
153 if (root->rb_leftmost == node)
154 root->rb_leftmost = rb_next(node);
155 rb_erase(node, &root->rb_root);
156}
157
158static inline void rb_replace_node_cached(struct rb_node *victim,
159 struct rb_node *new,
160 struct rb_root_cached *root)
161{
162 if (root->rb_leftmost == victim)
163 root->rb_leftmost = new;
164 rb_replace_node(victim, new, &root->rb_root);
165}
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189static __always_inline void
190rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
191 bool (*less)(struct rb_node *, const struct rb_node *))
192{
193 struct rb_node **link = &tree->rb_root.rb_node;
194 struct rb_node *parent = NULL;
195 bool leftmost = true;
196
197 while (*link) {
198 parent = *link;
199 if (less(node, parent)) {
200 link = &parent->rb_left;
201 } else {
202 link = &parent->rb_right;
203 leftmost = false;
204 }
205 }
206
207 rb_link_node(node, parent, link);
208 rb_insert_color_cached(node, tree, leftmost);
209}
210
211
212
213
214
215
216
217static __always_inline void
218rb_add(struct rb_node *node, struct rb_root *tree,
219 bool (*less)(struct rb_node *, const struct rb_node *))
220{
221 struct rb_node **link = &tree->rb_node;
222 struct rb_node *parent = NULL;
223
224 while (*link) {
225 parent = *link;
226 if (less(node, parent))
227 link = &parent->rb_left;
228 else
229 link = &parent->rb_right;
230 }
231
232 rb_link_node(node, parent, link);
233 rb_insert_color(node, tree);
234}
235
236
237
238
239
240
241
242
243
244
245static __always_inline struct rb_node *
246rb_find_add(struct rb_node *node, struct rb_root *tree,
247 int (*cmp)(struct rb_node *, const struct rb_node *))
248{
249 struct rb_node **link = &tree->rb_node;
250 struct rb_node *parent = NULL;
251 int c;
252
253 while (*link) {
254 parent = *link;
255 c = cmp(node, parent);
256
257 if (c < 0)
258 link = &parent->rb_left;
259 else if (c > 0)
260 link = &parent->rb_right;
261 else
262 return parent;
263 }
264
265 rb_link_node(node, parent, link);
266 rb_insert_color(node, tree);
267 return NULL;
268}
269
270
271
272
273
274
275
276
277
278static __always_inline struct rb_node *
279rb_find(const void *key, const struct rb_root *tree,
280 int (*cmp)(const void *key, const struct rb_node *))
281{
282 struct rb_node *node = tree->rb_node;
283
284 while (node) {
285 int c = cmp(key, node);
286
287 if (c < 0)
288 node = node->rb_left;
289 else if (c > 0)
290 node = node->rb_right;
291 else
292 return node;
293 }
294
295 return NULL;
296}
297
298
299
300
301
302
303
304
305
306static __always_inline struct rb_node *
307rb_find_first(const void *key, const struct rb_root *tree,
308 int (*cmp)(const void *key, const struct rb_node *))
309{
310 struct rb_node *node = tree->rb_node;
311 struct rb_node *match = NULL;
312
313 while (node) {
314 int c = cmp(key, node);
315
316 if (c <= 0) {
317 if (!c)
318 match = node;
319 node = node->rb_left;
320 } else if (c > 0) {
321 node = node->rb_right;
322 }
323 }
324
325 return match;
326}
327
328
329
330
331
332
333
334
335
336static __always_inline struct rb_node *
337rb_next_match(const void *key, struct rb_node *node,
338 int (*cmp)(const void *key, const struct rb_node *))
339{
340 node = rb_next(node);
341 if (node && cmp(key, node))
342 node = NULL;
343 return node;
344}
345
346
347
348
349
350
351
352
353#define rb_for_each(node, key, tree, cmp) \
354 for ((node) = rb_find_first((key), (tree), (cmp)); \
355 (node); (node) = rb_next_match((key), (node), (cmp)))
356
357#endif
358