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 addr_location *al,
18 struct symbol *sym_parent,
21 struct rb_node **p = &hist.rb_node;
22 struct rb_node *parent = NULL;
23 struct hist_entry *he;
24 struct hist_entry entry = {
37 he = rb_entry(parent, struct hist_entry, rb_node);
39 cmp = hist_entry__cmp(&entry, he);
52 he = malloc(sizeof(*he));
56 rb_link_node(&he->rb_node, parent, p);
57 rb_insert_color(&he->rb_node, &hist);
63 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
65 struct sort_entry *se;
68 list_for_each_entry(se, &hist_entry__sort_list, list) {
69 cmp = se->cmp(left, right);
78 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
80 struct sort_entry *se;
83 list_for_each_entry(se, &hist_entry__sort_list, list) {
84 int64_t (*f)(struct hist_entry *, struct hist_entry *);
86 f = se->collapse ?: se->cmp;
96 void hist_entry__free(struct hist_entry *he)
102 * collapse the histogram
105 void collapse__insert_entry(struct hist_entry *he)
107 struct rb_node **p = &collapse_hists.rb_node;
108 struct rb_node *parent = NULL;
109 struct hist_entry *iter;
114 iter = rb_entry(parent, struct hist_entry, rb_node);
116 cmp = hist_entry__collapse(iter, he);
119 iter->count += he->count;
120 hist_entry__free(he);
130 rb_link_node(&he->rb_node, parent, p);
131 rb_insert_color(&he->rb_node, &collapse_hists);
134 void collapse__resort(void)
136 struct rb_node *next;
137 struct hist_entry *n;
139 if (!sort__need_collapse)
142 next = rb_first(&hist);
144 n = rb_entry(next, struct hist_entry, rb_node);
145 next = rb_next(&n->rb_node);
147 rb_erase(&n->rb_node, &hist);
148 collapse__insert_entry(n);
153 * reverse the map, sort on count.
156 void output__insert_entry(struct hist_entry *he, u64 min_callchain_hits)
158 struct rb_node **p = &output_hists.rb_node;
159 struct rb_node *parent = NULL;
160 struct hist_entry *iter;
163 callchain_param.sort(&he->sorted_chain, &he->callchain,
164 min_callchain_hits, &callchain_param);
168 iter = rb_entry(parent, struct hist_entry, rb_node);
170 if (he->count > iter->count)
176 rb_link_node(&he->rb_node, parent, p);
177 rb_insert_color(&he->rb_node, &output_hists);
180 void output__resort(u64 total_samples)
182 struct rb_node *next;
183 struct hist_entry *n;
184 struct rb_root *tree = &hist;
185 u64 min_callchain_hits;
188 total_samples * (callchain_param.min_percent / 100);
190 if (sort__need_collapse)
191 tree = &collapse_hists;
193 next = rb_first(tree);
196 n = rb_entry(next, struct hist_entry, rb_node);
197 next = rb_next(&n->rb_node);
199 rb_erase(&n->rb_node, tree);
200 output__insert_entry(n, min_callchain_hits);