| /tools/include/linux/ |
| D | rbtree.h | 35 struct rb_node { struct
37 struct rb_node *rb_right; argument
38 struct rb_node *rb_left; argument
43 struct rb_node *rb_node; member
47 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
52 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
61 extern void rb_insert_color(struct rb_node *, struct rb_root *);
62 extern void rb_erase(struct rb_node *, struct rb_root *);
66 extern struct rb_node *rb_next(const struct rb_node *);
67 extern struct rb_node *rb_prev(const struct rb_node *);
[all …]
|
| D | rbtree_augmented.h | 42 void (*propagate)(struct rb_node *node, struct rb_node *stop);
43 void (*copy)(struct rb_node *old, struct rb_node *new);
44 void (*rotate)(struct rb_node *old, struct rb_node *new);
47 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
48 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
60 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented()
69 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
81 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
88 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
103 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
[all …]
|
| /tools/perf/util/ |
| D | intlist.c | 14 static struct rb_node *intlist__node_new(struct rblist *rblist __maybe_unused, in intlist__node_new()
18 struct rb_node *rc = NULL; in intlist__node_new()
24 rc = &node->rb_node; in intlist__node_new()
36 struct rb_node *rb_node) in intlist__node_delete() argument
38 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_delete()
43 static int intlist__node_cmp(struct rb_node *rb_node, const void *entry) in intlist__node_cmp() argument
46 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_cmp()
58 rblist__remove_node(&ilist->rblist, &node->rb_node); in intlist__remove()
65 struct rb_node *rb_node; in __intlist__findnew() local
71 rb_node = rblist__findnew(&ilist->rblist, (void *)((long)i)); in __intlist__findnew()
[all …]
|
| D | rblist.h | 26 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);
34 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node);
35 struct rb_node *rblist__find(struct rblist *rblist, const void *entry);
36 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry);
37 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx);
|
| D | rblist.c | 16 struct rb_node **p = &rblist->entries.rb_node; in rblist__add_node()
17 struct rb_node *parent = NULL, *new_node; in rblist__add_node()
44 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) in rblist__remove_node() argument
46 rb_erase(rb_node, &rblist->entries); in rblist__remove_node()
48 rblist->node_delete(rblist, rb_node); in rblist__remove_node()
51 static struct rb_node *__rblist__findnew(struct rblist *rblist, in __rblist__findnew()
55 struct rb_node **p = &rblist->entries.rb_node; in __rblist__findnew()
56 struct rb_node *parent = NULL, *new_node = NULL; in __rblist__findnew()
84 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) in rblist__find()
89 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) in rblist__findnew()
[all …]
|
| D | strlist.c | 16 struct rb_node *strlist__node_new(struct rblist *rblist, const void *entry) in strlist__node_new()
19 struct rb_node *rc = NULL; in strlist__node_new()
30 rc = &snode->rb_node; in strlist__node_new()
48 void strlist__node_delete(struct rblist *rblist, struct rb_node *rb_node) in strlist__node_delete() argument
51 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_delete()
56 static int strlist__node_cmp(struct rb_node *rb_node, const void *entry) in strlist__node_cmp() argument
59 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_cmp()
98 rblist__remove_node(&slist->rblist, &snode->rb_node); in strlist__remove()
104 struct rb_node *rb_node = rblist__find(&slist->rblist, entry); in strlist__find() local
106 if (rb_node) in strlist__find()
[all …]
|
| D | rb_resort.h | 57 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 …]
|
| D | intlist.h | 11 struct rb_node rb_node; member
48 struct rb_node *rn = rb_first(&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()
|
| D | strlist.h | 11 struct rb_node rb_node; member
60 struct rb_node *rn = rb_first(&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()
|
| D | comm.c | 12 struct rb_node rb_node; member
30 rb_erase(&cs->rb_node, &comm_str_root); in comm_str__put()
57 struct rb_node **p = &root->rb_node; in comm_str__findnew()
58 struct rb_node *parent = NULL; in comm_str__findnew()
64 iter = rb_entry(parent, struct comm_str, rb_node); in comm_str__findnew()
85 rb_link_node(&new->rb_node, parent, p); in comm_str__findnew()
86 rb_insert_color(&new->rb_node, root); in comm_str__findnew()
|
| D | block-range.c | 17 struct rb_node *rb; in block_range__debug()
33 struct rb_node **p = &block_ranges.root.rb_node; in block_range__find()
34 struct rb_node *parent = NULL; in block_range__find()
52 static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node) in rb_link_left_of_node()
54 struct rb_node **p = &node->rb_left; in rb_link_left_of_node()
62 static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node) in rb_link_right_of_node()
64 struct rb_node **p = &node->rb_right; in rb_link_right_of_node()
81 struct rb_node **p = &block_ranges.root.rb_node; in block_range__create()
82 struct rb_node *n, *parent = NULL; in block_range__create()
|
| D | call-path.c | 30 RB_CLEAR_NODE(&cp->rb_node); in call_path__init()
89 struct rb_node **p; in call_path__findnew()
90 struct rb_node *node_parent = NULL; in call_path__findnew()
100 p = &parent->children.rb_node; in call_path__findnew()
103 cp = rb_entry(node_parent, struct call_path, rb_node); in call_path__findnew()
118 rb_link_node(&cp->rb_node, node_parent, p); in call_path__findnew()
119 rb_insert_color(&cp->rb_node, &parent->children); in call_path__findnew()
|
| D | symbol.c | 180 struct rb_node *nd; in symbols__fixup_duplicate()
189 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
191 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
192 next = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
201 rb_erase(&next->rb_node, symbols); in symbols__fixup_duplicate()
205 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
206 rb_erase(&curr->rb_node, symbols); in symbols__fixup_duplicate()
214 struct rb_node *nd, *prevnd = rb_first(symbols); in symbols__fixup_end()
220 curr = rb_entry(prevnd, struct symbol, rb_node); in symbols__fixup_end()
224 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_end()
[all …]
|
| D | map.c | 144 RB_CLEAR_NODE(&map->rb_node); in map__init()
265 BUG_ON(!RB_EMPTY_NODE(&map->rb_node)); in map__exit()
284 struct rb_node *nd = rb_first(symbols); in map__fixup_start()
286 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_start()
294 struct rb_node *nd = rb_last(symbols); in map__fixup_end()
296 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_end()
372 RB_CLEAR_NODE(&map->rb_node); in map__clone()
509 struct rb_node *next = rb_first(root); in __maps__purge()
512 struct map *pos = rb_entry(next, struct map, rb_node); in __maps__purge()
514 next = rb_next(&pos->rb_node); in __maps__purge()
[all …]
|
| D | hist.c | 210 struct rb_node *next = rb_first(&hists->entries); in hists__output_recalc_col_len()
217 n = rb_entry(next, struct hist_entry, rb_node); in hists__output_recalc_col_len()
220 next = rb_next(&n->rb_node); in hists__output_recalc_col_len()
297 struct rb_node *node = rb_first(&he->hroot_out); in hists__decay_entry()
299 child = rb_entry(node, struct hist_entry, rb_node); in hists__decay_entry()
327 rb_erase(&he->rb_node, root_out); in hists__delete_entry()
338 struct rb_node *next = rb_first(&hists->entries); in hists__decay_entries()
342 n = rb_entry(next, struct hist_entry, rb_node); in hists__decay_entries()
343 next = rb_next(&n->rb_node); in hists__decay_entries()
354 struct rb_node *next = rb_first(&hists->entries); in hists__delete_entries()
[all …]
|
| D | call-path.h | 43 struct rb_node rb_node; member
|
| D | dso.c | 713 struct rb_node *next = rb_first(root); in dso_cache__free()
719 cache = rb_entry(next, struct dso_cache, rb_node); in dso_cache__free()
720 next = rb_next(&cache->rb_node); in dso_cache__free()
721 rb_erase(&cache->rb_node, root); in dso_cache__free()
730 struct rb_node * const *p = &root->rb_node; in dso_cache__find()
731 const struct rb_node *parent = NULL; in dso_cache__find()
738 cache = rb_entry(parent, struct dso_cache, rb_node); in dso_cache__find()
756 struct rb_node **p = &root->rb_node; in dso_cache__insert()
757 struct rb_node *parent = NULL; in dso_cache__insert()
766 cache = rb_entry(parent, struct dso_cache, rb_node); in dso_cache__insert()
[all …]
|
| D | machine.c | 41 RB_CLEAR_NODE(&machine->rb_node); in machine__init()
127 RB_CLEAR_NODE(&pos->rb_node); in dsos__purge()
144 struct rb_node *nd; in machine__delete_threads()
149 struct thread *t = rb_entry(nd, struct thread, rb_node); in machine__delete_threads()
194 struct rb_node **p = &machines->guests.rb_node; in machines__add()
195 struct rb_node *parent = NULL; in machines__add()
208 pos = rb_entry(parent, struct machine, rb_node); in machines__add()
215 rb_link_node(&machine->rb_node, parent, p); in machines__add()
216 rb_insert_color(&machine->rb_node, &machines->guests); in machines__add()
223 struct rb_node *nd; in machines__set_comm_exec()
[all …]
|
| D | block-range.h | 19 struct rb_node node;
36 struct rb_node *n = rb_next(&br->node); in block_range__next()
|
| D | callchain.c | 368 struct rb_node **p = &root->rb_node; in rb_insert_callchain()
369 struct rb_node *parent = NULL; in rb_insert_callchain()
377 rnode = rb_entry(parent, struct callchain_node, rb_node); in rb_insert_callchain()
401 rb_link_node(&chain->rb_node, parent, p); in rb_insert_callchain()
402 rb_insert_color(&chain->rb_node, root); in rb_insert_callchain()
409 struct rb_node *n; in __sort_chain_flat()
439 struct rb_node *n; in __sort_chain_graph_abs()
461 rb_root->rb_node = chain_root->node.rb_root.rb_node; in sort_chain_graph_abs()
467 struct rb_node *n; in __sort_chain_graph_rel()
491 rb_root->rb_node = chain_root->node.rb_root.rb_node; in sort_chain_graph_rel()
[all …]
|
| /tools/lib/ |
| D | rbtree.c | 46 static inline void rb_set_black(struct rb_node *rb) in rb_set_black()
51 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent()
53 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent()
62 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents()
65 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents()
72 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert()
73 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert()
75 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
201 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color()
202 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color()
[all …]
|
| /tools/perf/tests/ |
| D | hists_output.c | 96 struct rb_node *node; in del_hist_entries()
108 he = rb_entry(node, struct hist_entry, rb_node); in del_hist_entries()
130 struct rb_node *node; in test1()
166 he = rb_entry(node, struct hist_entry, rb_node); in test1()
172 he = rb_entry(node, struct hist_entry, rb_node); in test1()
178 he = rb_entry(node, struct hist_entry, rb_node); in test1()
184 he = rb_entry(node, struct hist_entry, rb_node); in test1()
190 he = rb_entry(node, struct hist_entry, rb_node); in test1()
196 he = rb_entry(node, struct hist_entry, rb_node); in test1()
202 he = rb_entry(node, struct hist_entry, rb_node); in test1()
[all …]
|
| /tools/perf/ui/browsers/ |
| D | map.c | 25 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map_browser__write()
43 return ((void *)browser) - sizeof(struct rb_node) - sizeof(u32); in symbol__browser_index()
65 browser->b.top = &sym->rb_node; in map_browser__search()
114 struct rb_node *nd; in map__browse()
119 struct symbol *pos = rb_entry(nd, struct symbol, rb_node); in map__browse()
|
| /tools/perf/ui/stdio/ |
| D | hist.c | 166 struct rb_node *node, *next; in __callchain__fprintf_graph()
183 child = rb_entry(node, struct callchain_node, rb_node); in __callchain__fprintf_graph()
259 static bool need_percent_display(struct rb_node *node, u64 parent_samples) in need_percent_display()
266 cnode = rb_entry(node, struct callchain_node, rb_node); in need_percent_display()
278 struct rb_node *node; in callchain__fprintf_graph()
285 cnode = rb_entry(node, struct callchain_node, rb_node); in callchain__fprintf_graph()
371 struct rb_node *rb_node = rb_first(tree); in callchain__fprintf_flat() local
373 while (rb_node) { in callchain__fprintf_flat()
374 chain = rb_entry(rb_node, struct callchain_node, rb_node); in callchain__fprintf_flat()
384 rb_node = rb_next(rb_node); in callchain__fprintf_flat()
[all …]
|
| /tools/perf/ |
| D | builtin-kmem.c | 65 struct rb_node node;
83 struct rb_node **node = &root_alloc_stat.rb_node; in insert_alloc_stat()
84 struct rb_node *parent = NULL; in insert_alloc_stat()
128 struct rb_node **node = &root_caller_stat.rb_node; in insert_caller_stat()
129 struct rb_node *parent = NULL; in insert_caller_stat()
210 struct rb_node *node = root->rb_node; in search_alloc_stat()
276 struct rb_node node;
333 struct rb_node *node; in build_alloc_func_list()
439 struct rb_node **node = &page_live_tree.rb_node; in __page_stat__findnew_page()
440 struct rb_node *parent = NULL; in __page_stat__findnew_page()
[all …]
|