b40e37ded4bf11672bfaf406dbbab7f80e460b06
[linux-2.6.git] / tools / perf / util / hist.c
1 #include "hist.h"
2
3 struct rb_root hist;
4 int callchain;
5
6 struct callchain_param  callchain_param = {
7         .mode   = CHAIN_GRAPH_REL,
8         .min_percent = 0.5
9 };
10
11 /*
12  * histogram, sorted on item, collects counts
13  */
14
15 struct hist_entry *__hist_entry__add(struct addr_location *al,
16                                      struct symbol *sym_parent,
17                                      u64 count, bool *hit)
18 {
19         struct rb_node **p = &hist.rb_node;
20         struct rb_node *parent = NULL;
21         struct hist_entry *he;
22         struct hist_entry entry = {
23                 .thread = al->thread,
24                 .map    = al->map,
25                 .sym    = al->sym,
26                 .ip     = al->addr,
27                 .level  = al->level,
28                 .count  = count,
29                 .parent = sym_parent,
30         };
31         int cmp;
32
33         while (*p != NULL) {
34                 parent = *p;
35                 he = rb_entry(parent, struct hist_entry, rb_node);
36
37                 cmp = hist_entry__cmp(&entry, he);
38
39                 if (!cmp) {
40                         *hit = true;
41                         return he;
42                 }
43
44                 if (cmp < 0)
45                         p = &(*p)->rb_left;
46                 else
47                         p = &(*p)->rb_right;
48         }
49
50         he = malloc(sizeof(*he));
51         if (!he)
52                 return NULL;
53         *he = entry;
54         rb_link_node(&he->rb_node, parent, p);
55         rb_insert_color(&he->rb_node, &hist);
56         *hit = false;
57         return he;
58 }
59
60 int64_t
61 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
62 {
63         struct sort_entry *se;
64         int64_t cmp = 0;
65
66         list_for_each_entry(se, &hist_entry__sort_list, list) {
67                 cmp = se->cmp(left, right);
68                 if (cmp)
69                         break;
70         }
71
72         return cmp;
73 }
74
75 int64_t
76 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
77 {
78         struct sort_entry *se;
79         int64_t cmp = 0;
80
81         list_for_each_entry(se, &hist_entry__sort_list, list) {
82                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
83
84                 f = se->collapse ?: se->cmp;
85
86                 cmp = f(left, right);
87                 if (cmp)
88                         break;
89         }
90
91         return cmp;
92 }
93
94 void hist_entry__free(struct hist_entry *he)
95 {
96         free(he);
97 }
98
99 /*
100  * collapse the histogram
101  */
102
103 static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
104 {
105         struct rb_node **p = &root->rb_node;
106         struct rb_node *parent = NULL;
107         struct hist_entry *iter;
108         int64_t cmp;
109
110         while (*p != NULL) {
111                 parent = *p;
112                 iter = rb_entry(parent, struct hist_entry, rb_node);
113
114                 cmp = hist_entry__collapse(iter, he);
115
116                 if (!cmp) {
117                         iter->count += he->count;
118                         hist_entry__free(he);
119                         return;
120                 }
121
122                 if (cmp < 0)
123                         p = &(*p)->rb_left;
124                 else
125                         p = &(*p)->rb_right;
126         }
127
128         rb_link_node(&he->rb_node, parent, p);
129         rb_insert_color(&he->rb_node, root);
130 }
131
132 void collapse__resort(void)
133 {
134         struct rb_root tmp;
135         struct rb_node *next;
136         struct hist_entry *n;
137
138         if (!sort__need_collapse)
139                 return;
140
141         tmp = RB_ROOT;
142         next = rb_first(&hist);
143
144         while (next) {
145                 n = rb_entry(next, struct hist_entry, rb_node);
146                 next = rb_next(&n->rb_node);
147
148                 rb_erase(&n->rb_node, &hist);
149                 collapse__insert_entry(&tmp, n);
150         }
151
152         hist = tmp;
153 }
154
155 /*
156  * reverse the map, sort on count.
157  */
158
159 static void output__insert_entry(struct rb_root *root, struct hist_entry *he,
160                                  u64 min_callchain_hits)
161 {
162         struct rb_node **p = &root->rb_node;
163         struct rb_node *parent = NULL;
164         struct hist_entry *iter;
165
166         if (callchain)
167                 callchain_param.sort(&he->sorted_chain, &he->callchain,
168                                       min_callchain_hits, &callchain_param);
169
170         while (*p != NULL) {
171                 parent = *p;
172                 iter = rb_entry(parent, struct hist_entry, rb_node);
173
174                 if (he->count > iter->count)
175                         p = &(*p)->rb_left;
176                 else
177                         p = &(*p)->rb_right;
178         }
179
180         rb_link_node(&he->rb_node, parent, p);
181         rb_insert_color(&he->rb_node, root);
182 }
183
184 void output__resort(u64 total_samples)
185 {
186         struct rb_root tmp;
187         struct rb_node *next;
188         struct hist_entry *n;
189         u64 min_callchain_hits;
190
191         min_callchain_hits =
192                 total_samples * (callchain_param.min_percent / 100);
193
194         tmp = RB_ROOT;
195         next = rb_first(&hist);
196
197         while (next) {
198                 n = rb_entry(next, struct hist_entry, rb_node);
199                 next = rb_next(&n->rb_node);
200
201                 rb_erase(&n->rb_node, &hist);
202                 output__insert_entry(&tmp, n, min_callchain_hits);
203         }
204
205         hist = tmp;
206 }