perf session: Move the hist_entries rb tree to perf_session
[linux-2.6.git] / tools / perf / util / hist.c
1 #include "hist.h"
2 #include "session.h"
3 #include "sort.h"
4
5 struct callchain_param  callchain_param = {
6         .mode   = CHAIN_GRAPH_REL,
7         .min_percent = 0.5
8 };
9
10 /*
11  * histogram, sorted on item, collects counts
12  */
13
14 struct hist_entry *__perf_session__add_hist_entry(struct perf_session *self,
15                                                   struct addr_location *al,
16                                                   struct symbol *sym_parent,
17                                                   u64 count, bool *hit)
18 {
19         struct rb_node **p = &self->hists.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, &self->hists);
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 perf_session__collapse_resort(struct perf_session *self)
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(&self->hists);
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, &self->hists);
149                 collapse__insert_entry(&tmp, n);
150         }
151
152         self->hists = tmp;
153 }
154
155 /*
156  * reverse the map, sort on count.
157  */
158
159 static void perf_session__insert_output_hist_entry(struct perf_session *self,
160                                                    struct rb_root *root,
161                                                    struct hist_entry *he,
162                                                    u64 min_callchain_hits)
163 {
164         struct rb_node **p = &root->rb_node;
165         struct rb_node *parent = NULL;
166         struct hist_entry *iter;
167
168         if (self->use_callchain)
169                 callchain_param.sort(&he->sorted_chain, &he->callchain,
170                                       min_callchain_hits, &callchain_param);
171
172         while (*p != NULL) {
173                 parent = *p;
174                 iter = rb_entry(parent, struct hist_entry, rb_node);
175
176                 if (he->count > iter->count)
177                         p = &(*p)->rb_left;
178                 else
179                         p = &(*p)->rb_right;
180         }
181
182         rb_link_node(&he->rb_node, parent, p);
183         rb_insert_color(&he->rb_node, root);
184 }
185
186 void perf_session__output_resort(struct perf_session *self, u64 total_samples)
187 {
188         struct rb_root tmp;
189         struct rb_node *next;
190         struct hist_entry *n;
191         u64 min_callchain_hits;
192
193         min_callchain_hits =
194                 total_samples * (callchain_param.min_percent / 100);
195
196         tmp = RB_ROOT;
197         next = rb_first(&self->hists);
198
199         while (next) {
200                 n = rb_entry(next, struct hist_entry, rb_node);
201                 next = rb_next(&n->rb_node);
202
203                 rb_erase(&n->rb_node, &self->hists);
204                 perf_session__insert_output_hist_entry(self, &tmp, n,
205                                                        min_callchain_hits);
206         }
207
208         self->hists = tmp;
209 }