4 struct rb_root collapse_hists;
5 struct rb_root output_hists;
8 struct callchain_param callchain_param = {
9 .mode = CHAIN_GRAPH_REL,
14 * histogram, sorted on item, collects counts
17 struct hist_entry *__hist_entry__add(struct thread *thread, struct map *map,
19 struct symbol *sym_parent,
20 u64 ip, u64 count, char level, bool *hit)
22 struct rb_node **p = &hist.rb_node;
23 struct rb_node *parent = NULL;
24 struct hist_entry *he;
25 struct hist_entry entry = {
38 he = rb_entry(parent, struct hist_entry, rb_node);
40 cmp = hist_entry__cmp(&entry, he);
53 he = malloc(sizeof(*he));
57 rb_link_node(&he->rb_node, parent, p);
58 rb_insert_color(&he->rb_node, &hist);
64 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
66 struct sort_entry *se;
69 list_for_each_entry(se, &hist_entry__sort_list, list) {
70 cmp = se->cmp(left, right);
79 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
81 struct sort_entry *se;
84 list_for_each_entry(se, &hist_entry__sort_list, list) {
85 int64_t (*f)(struct hist_entry *, struct hist_entry *);
87 f = se->collapse ?: se->cmp;
97 void hist_entry__free(struct hist_entry *he)
103 * collapse the histogram
106 void collapse__insert_entry(struct hist_entry *he)
108 struct rb_node **p = &collapse_hists.rb_node;
109 struct rb_node *parent = NULL;
110 struct hist_entry *iter;
115 iter = rb_entry(parent, struct hist_entry, rb_node);
117 cmp = hist_entry__collapse(iter, he);
120 iter->count += he->count;
121 hist_entry__free(he);
131 rb_link_node(&he->rb_node, parent, p);
132 rb_insert_color(&he->rb_node, &collapse_hists);
135 void collapse__resort(void)
137 struct rb_node *next;
138 struct hist_entry *n;
140 if (!sort__need_collapse)
143 next = rb_first(&hist);
145 n = rb_entry(next, struct hist_entry, rb_node);
146 next = rb_next(&n->rb_node);
148 rb_erase(&n->rb_node, &hist);
149 collapse__insert_entry(n);
154 * reverse the map, sort on count.
157 void output__insert_entry(struct hist_entry *he, u64 min_callchain_hits)
159 struct rb_node **p = &output_hists.rb_node;
160 struct rb_node *parent = NULL;
161 struct hist_entry *iter;
164 callchain_param.sort(&he->sorted_chain, &he->callchain,
165 min_callchain_hits, &callchain_param);
169 iter = rb_entry(parent, struct hist_entry, rb_node);
171 if (he->count > iter->count)
177 rb_link_node(&he->rb_node, parent, p);
178 rb_insert_color(&he->rb_node, &output_hists);
181 void output__resort(u64 total_samples)
183 struct rb_node *next;
184 struct hist_entry *n;
185 struct rb_root *tree = &hist;
186 u64 min_callchain_hits;
189 total_samples * (callchain_param.min_percent / 100);
191 if (sort__need_collapse)
192 tree = &collapse_hists;
194 next = rb_first(tree);
197 n = rb_entry(next, struct hist_entry, rb_node);
198 next = rb_next(&n->rb_node);
200 rb_erase(&n->rb_node, tree);
201 output__insert_entry(n, min_callchain_hits);