Home
last modified time | relevance | path

Searched refs:rb_node (Results 1 – 25 of 70) sorted by relevance

123

/tools/include/linux/
Drbtree.h23 struct rb_node { struct
25 struct rb_node *rb_right; argument
26 struct rb_node *rb_left; argument
31 struct rb_node *rb_node; member
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)
48 extern void rb_insert_color(struct rb_node *, struct rb_root *);
49 extern void rb_erase(struct rb_node *, struct rb_root *);
53 extern struct rb_node *rb_next(const struct rb_node *);
54 extern struct rb_node *rb_prev(const struct rb_node *);
[all …]
Drbtree_augmented.h30 void (*propagate)(struct rb_node *node, struct rb_node *stop);
31 void (*copy)(struct rb_node *old, struct rb_node *new);
32 void (*rotate)(struct rb_node *old, struct rb_node *new);
35 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
36 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
49 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented()
56 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached()
79 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \
89 RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
96 RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
[all …]
/tools/perf/util/
Dintlist.c13 static struct rb_node *intlist__node_new(struct rblist *rblist __maybe_unused, in intlist__node_new()
17 struct rb_node *rc = NULL; in intlist__node_new()
23 rc = &node->rb_node; in intlist__node_new()
35 struct rb_node *rb_node) in intlist__node_delete() argument
37 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_delete()
42 static int intlist__node_cmp(struct rb_node *rb_node, const void *entry) in intlist__node_cmp() argument
45 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_cmp()
57 rblist__remove_node(&ilist->rblist, &node->rb_node); in intlist__remove()
64 struct rb_node *rb_node; in __intlist__findnew() local
70 rb_node = rblist__findnew(&ilist->rblist, (void *)((long)i)); in __intlist__findnew()
[all …]
Drblist.c15 struct rb_node **p = &rblist->entries.rb_root.rb_node; in rblist__add_node()
16 struct rb_node *parent = NULL, *new_node; in rblist__add_node()
46 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) in rblist__remove_node() argument
48 rb_erase_cached(rb_node, &rblist->entries); in rblist__remove_node()
50 rblist->node_delete(rblist, rb_node); in rblist__remove_node()
53 static struct rb_node *__rblist__findnew(struct rblist *rblist, in __rblist__findnew()
57 struct rb_node **p = &rblist->entries.rb_root.rb_node; in __rblist__findnew()
58 struct rb_node *parent = NULL, *new_node = NULL; in __rblist__findnew()
90 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) in rblist__find()
95 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) in rblist__findnew()
[all …]
Dstrlist.c15 struct rb_node *strlist__node_new(struct rblist *rblist, const void *entry) in strlist__node_new()
18 struct rb_node *rc = NULL; in strlist__node_new()
29 rc = &snode->rb_node; in strlist__node_new()
47 void strlist__node_delete(struct rblist *rblist, struct rb_node *rb_node) in strlist__node_delete() argument
50 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_delete()
55 static int strlist__node_cmp(struct rb_node *rb_node, const void *entry) in strlist__node_cmp() argument
58 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_cmp()
97 rblist__remove_node(&slist->rblist, &snode->rb_node); in strlist__remove()
103 struct rb_node *rb_node = rblist__find(&slist->rblist, entry); in strlist__find() local
105 if (rb_node) in strlist__find()
[all …]
Drblist.h26 int (*node_cmp)(struct rb_node *rbn, const void *entry);
27 struct rb_node *(*node_new)(struct rblist *rlist, const void *new_entry);
28 void (*node_delete)(struct rblist *rblist, struct rb_node *rb_node);
35 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node);
36 struct rb_node *rblist__find(struct rblist *rblist, const void *entry);
37 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry);
38 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx);
Drb_resort.h57 struct rb_node rb_node; \
60 static void __name##_sorted__init_entry(struct rb_node *nd, \
63 static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb) \
66 a = rb_entry(nda, struct __name##_sorted_entry, rb_node); \
67 b = rb_entry(ndb, struct __name##_sorted_entry, rb_node); \
77 struct rb_node *sorted_nd) \
79 struct rb_node **p = &sorted->entries.rb_node, *parent = NULL; \
94 struct rb_node *nd; \
99 __name##_sorted__insert(sorted, &snd->rb_node); \
120 static void __name##_sorted__init_entry(struct rb_node *nd, \
[all …]
Dmem2node.c11 struct rb_node rb_node; member
19 struct rb_node **p = &root->rb_node; in phys_entry__insert()
20 struct rb_node *parent = NULL; in phys_entry__insert()
25 e = rb_entry(parent, struct phys_entry, rb_node); in phys_entry__insert()
33 rb_link_node(&entry->rb_node, parent, p); in phys_entry__insert()
34 rb_insert_color(&entry->rb_node, root); in phys_entry__insert()
43 RB_CLEAR_NODE(&entry->rb_node); in phys_entry__init()
119 struct rb_node **p, *parent = NULL; in mem2node__node()
122 p = &map->root.rb_node; in mem2node__node()
125 entry = rb_entry(parent, struct phys_entry, rb_node); in mem2node__node()
Denv.c21 struct rb_node *parent = NULL; in perf_env__insert_bpf_prog_info()
22 struct rb_node **p; in perf_env__insert_bpf_prog_info()
25 p = &env->bpf_progs.infos.rb_node; in perf_env__insert_bpf_prog_info()
29 node = rb_entry(parent, struct bpf_prog_info_node, rb_node); in perf_env__insert_bpf_prog_info()
40 rb_link_node(&info_node->rb_node, parent, p); in perf_env__insert_bpf_prog_info()
41 rb_insert_color(&info_node->rb_node, &env->bpf_progs.infos); in perf_env__insert_bpf_prog_info()
51 struct rb_node *n; in perf_env__find_bpf_prog_info()
54 n = env->bpf_progs.infos.rb_node; in perf_env__find_bpf_prog_info()
57 node = rb_entry(n, struct bpf_prog_info_node, rb_node); in perf_env__find_bpf_prog_info()
74 struct rb_node *parent = NULL; in perf_env__insert_btf()
[all …]
Dstrlist.h11 struct rb_node rb_node; member
60 struct rb_node *rn = rb_first_cached(&slist->rblist.entries); in strlist__first()
61 return rn ? rb_entry(rn, struct str_node, rb_node) : NULL; in strlist__first()
65 struct rb_node *rn; in strlist__next()
68 rn = rb_next(&sn->rb_node); in strlist__next()
69 return rn ? rb_entry(rn, struct str_node, rb_node) : NULL; in strlist__next()
Dintlist.h11 struct rb_node rb_node; member
48 struct rb_node *rn = rb_first_cached(&ilist->rblist.entries); in intlist__first()
49 return rn ? rb_entry(rn, struct int_node, rb_node) : NULL; in intlist__first()
53 struct rb_node *rn; in intlist__next()
56 rn = rb_next(&in->rb_node); in intlist__next()
57 return rn ? rb_entry(rn, struct int_node, rb_node) : NULL; in intlist__next()
Dcomm.c14 struct rb_node rb_node; member
34 rb_erase(&cs->rb_node, &comm_str_root); in comm_str__put()
63 struct rb_node **p = &root->rb_node; in __comm_str__findnew()
64 struct rb_node *parent = NULL; in __comm_str__findnew()
70 iter = rb_entry(parent, struct comm_str, rb_node); in __comm_str__findnew()
91 rb_link_node(&new->rb_node, parent, p); in __comm_str__findnew()
92 rb_insert_color(&new->rb_node, root); in __comm_str__findnew()
Dsrcline.c597 struct rb_node rb_node; member
602 struct rb_node **p = &tree->rb_root.rb_node; in srcline__tree_insert()
603 struct rb_node *parent = NULL; in srcline__tree_insert()
618 i = rb_entry(parent, struct srcline_node, rb_node); in srcline__tree_insert()
626 rb_link_node(&node->rb_node, parent, p); in srcline__tree_insert()
627 rb_insert_color_cached(&node->rb_node, tree, leftmost); in srcline__tree_insert()
632 struct rb_node *n = tree->rb_root.rb_node; in srcline__tree_find()
636 rb_node); in srcline__tree_find()
652 struct rb_node *next = rb_first_cached(tree); in srcline__tree_delete()
655 pos = rb_entry(next, struct srcline_node, rb_node); in srcline__tree_delete()
[all …]
Dblock-range.c19 struct rb_node *rb; in block_range__debug()
35 struct rb_node **p = &block_ranges.root.rb_node; in block_range__find()
36 struct rb_node *parent = NULL; in block_range__find()
54 static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node) in rb_link_left_of_node()
56 struct rb_node **p = &node->rb_left; in rb_link_left_of_node()
64 static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node) in rb_link_right_of_node()
66 struct rb_node **p = &node->rb_right; in rb_link_right_of_node()
83 struct rb_node **p = &block_ranges.root.rb_node; in block_range__create()
84 struct rb_node *n, *parent = NULL; in block_range__create()
Dbpf-event.h23 struct rb_node rb_node; member
27 struct rb_node rb_node; member
Dcall-path.c22 RB_CLEAR_NODE(&cp->rb_node); in call_path__init()
81 struct rb_node **p; in call_path__findnew()
82 struct rb_node *node_parent = NULL; in call_path__findnew()
92 p = &parent->children.rb_node; in call_path__findnew()
95 cp = rb_entry(node_parent, struct call_path, rb_node); in call_path__findnew()
110 rb_link_node(&cp->rb_node, node_parent, p); in call_path__findnew()
111 rb_insert_color(&cp->rb_node, &parent->children); in call_path__findnew()
Dmap.c142 RB_CLEAR_NODE(&map->rb_node); in map__init()
291 BUG_ON(!RB_EMPTY_NODE(&map->rb_node)); in map__exit()
310 struct rb_node *nd = rb_first_cached(symbols); in map__fixup_start()
312 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_start()
320 struct rb_node *nd = rb_last(&symbols->rb_root); in map__fixup_end()
322 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_end()
396 RB_CLEAR_NODE(&map->rb_node); in map__clone()
598 struct rb_node *next = rb_first(root); in __maps__purge()
601 struct map *pos = rb_entry(next, struct map, rb_node); in __maps__purge()
603 next = rb_next(&pos->rb_node); in __maps__purge()
[all …]
Dsymbol.c187 struct rb_node *nd; in symbols__fixup_duplicate()
196 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
198 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
199 next = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
208 rb_erase_cached(&next->rb_node, symbols); in symbols__fixup_duplicate()
212 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
213 rb_erase_cached(&curr->rb_node, symbols); in symbols__fixup_duplicate()
221 struct rb_node *nd, *prevnd = rb_first_cached(symbols); in symbols__fixup_end()
227 curr = rb_entry(prevnd, struct symbol, rb_node); in symbols__fixup_end()
231 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_end()
[all …]
Dhist.c226 struct rb_node *next = rb_first_cached(&hists->entries); in hists__output_recalc_col_len()
233 n = rb_entry(next, struct hist_entry, rb_node); in hists__output_recalc_col_len()
236 next = rb_next(&n->rb_node); in hists__output_recalc_col_len()
321 struct rb_node *node = rb_first_cached(&he->hroot_out); in hists__decay_entry()
323 child = rb_entry(node, struct hist_entry, rb_node); in hists__decay_entry()
351 rb_erase_cached(&he->rb_node, root_out); in hists__delete_entry()
362 struct rb_node *next = rb_first_cached(&hists->entries); in hists__decay_entries()
366 n = rb_entry(next, struct hist_entry, rb_node); in hists__decay_entries()
367 next = rb_next(&n->rb_node); in hists__decay_entries()
378 struct rb_node *next = rb_first_cached(&hists->entries); in hists__delete_entries()
[all …]
Ddsos.c44 struct rb_node **p = &root->rb_node; in __dsos__findnew_link_by_longname()
45 struct rb_node *parent = NULL; in __dsos__findnew_link_by_longname()
53 struct dso *this = rb_entry(*p, struct dso, rb_node); in __dsos__findnew_link_by_longname()
83 rb_link_node(&dso->rb_node, parent, p); in __dsos__findnew_link_by_longname()
84 rb_insert_color(&dso->rb_node, root); in __dsos__findnew_link_by_longname()
Dmetricgroup.c30 struct rb_node *nd; in metricgroup__lookup()
50 static int metric_event_cmp(struct rb_node *rb_node, const void *entry) in metric_event_cmp() argument
52 struct metric_event *a = container_of(rb_node, in metric_event_cmp()
64 static struct rb_node *metric_event_new(struct rblist *rblist __maybe_unused, in metric_event_new()
222 struct rb_node nd;
227 static int mep_cmp(struct rb_node *rb_node, const void *entry) in mep_cmp() argument
229 struct mep *a = container_of(rb_node, struct mep, nd); in mep_cmp()
235 static struct rb_node *mep_new(struct rblist *rl __maybe_unused, in mep_new()
259 struct rb_node *nd; in mep_lookup()
274 struct rb_node *nd) in mep_delete()
[all …]
/tools/lib/
Drbtree.c59 static inline void rb_set_black(struct rb_node *rb) in rb_set_black()
64 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent()
66 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent()
75 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents()
78 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents()
85 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert()
86 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert()
88 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color()
228 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color()
[all …]
/tools/perf/tests/
Dhists_output.c97 struct rb_node *node; in del_hist_entries()
109 he = rb_entry(node, struct hist_entry, rb_node); in del_hist_entries()
131 struct rb_node *node; in test1()
167 he = rb_entry(node, struct hist_entry, rb_node); in test1()
173 he = rb_entry(node, struct hist_entry, rb_node); in test1()
179 he = rb_entry(node, struct hist_entry, rb_node); in test1()
185 he = rb_entry(node, struct hist_entry, rb_node); in test1()
191 he = rb_entry(node, struct hist_entry, rb_node); in test1()
197 he = rb_entry(node, struct hist_entry, rb_node); in test1()
203 he = rb_entry(node, struct hist_entry, rb_node); in test1()
[all …]
/tools/perf/ui/browsers/
Dmap.c27 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map_browser__write()
45 return ((void *)browser) - sizeof(struct rb_node) - sizeof(u32); in symbol__browser_index()
67 browser->b.top = &sym->rb_node; in map_browser__search()
116 struct rb_node *nd; in map__browse()
121 struct symbol *pos = rb_entry(nd, struct symbol, rb_node); in map__browse()
/tools/perf/ui/stdio/
Dhist.c112 struct rb_node *node, *next; in __callchain__fprintf_graph()
129 child = rb_entry(node, struct callchain_node, rb_node); in __callchain__fprintf_graph()
205 static bool need_percent_display(struct rb_node *node, u64 parent_samples) in need_percent_display()
212 cnode = rb_entry(node, struct callchain_node, rb_node); in need_percent_display()
224 struct rb_node *node; in callchain__fprintf_graph()
231 cnode = rb_entry(node, struct callchain_node, rb_node); in callchain__fprintf_graph()
310 struct rb_node *rb_node = rb_first(tree); in callchain__fprintf_flat() local
312 while (rb_node) { in callchain__fprintf_flat()
313 chain = rb_entry(rb_node, struct callchain_node, rb_node); in callchain__fprintf_flat()
323 rb_node = rb_next(rb_node); in callchain__fprintf_flat()
[all …]

123