diff options
Diffstat (limited to 'tools/perf/util/callchain.c')
-rw-r--r-- | tools/perf/util/callchain.c | 51 |
1 files changed, 42 insertions, 9 deletions
diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c index 3c4a91fea622..a9873aafcd92 100644 --- a/tools/perf/util/callchain.c +++ b/tools/perf/util/callchain.c | |||
@@ -19,9 +19,9 @@ | |||
19 | #define chain_for_each_child(child, parent) \ | 19 | #define chain_for_each_child(child, parent) \ |
20 | list_for_each_entry(child, &parent->children, brothers) | 20 | list_for_each_entry(child, &parent->children, brothers) |
21 | 21 | ||
22 | |||
23 | static void | 22 | static void |
24 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) | 23 | rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, |
24 | enum chain_mode mode) | ||
25 | { | 25 | { |
26 | struct rb_node **p = &root->rb_node; | 26 | struct rb_node **p = &root->rb_node; |
27 | struct rb_node *parent = NULL; | 27 | struct rb_node *parent = NULL; |
@@ -31,10 +31,22 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) | |||
31 | parent = *p; | 31 | parent = *p; |
32 | rnode = rb_entry(parent, struct callchain_node, rb_node); | 32 | rnode = rb_entry(parent, struct callchain_node, rb_node); |
33 | 33 | ||
34 | if (rnode->hit < chain->hit) | 34 | switch (mode) { |
35 | p = &(*p)->rb_left; | 35 | case FLAT: |
36 | else | 36 | if (rnode->hit < chain->hit) |
37 | p = &(*p)->rb_right; | 37 | p = &(*p)->rb_left; |
38 | else | ||
39 | p = &(*p)->rb_right; | ||
40 | break; | ||
41 | case GRAPH: | ||
42 | if (rnode->cumul_hit < chain->cumul_hit) | ||
43 | p = &(*p)->rb_left; | ||
44 | else | ||
45 | p = &(*p)->rb_right; | ||
46 | break; | ||
47 | default: | ||
48 | break; | ||
49 | } | ||
38 | } | 50 | } |
39 | 51 | ||
40 | rb_link_node(&chain->rb_node, parent, p); | 52 | rb_link_node(&chain->rb_node, parent, p); |
@@ -45,15 +57,36 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) | |||
45 | * Once we get every callchains from the stream, we can now | 57 | * Once we get every callchains from the stream, we can now |
46 | * sort them by hit | 58 | * sort them by hit |
47 | */ | 59 | */ |
48 | void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node) | 60 | void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node) |
49 | { | 61 | { |
50 | struct callchain_node *child; | 62 | struct callchain_node *child; |
51 | 63 | ||
52 | chain_for_each_child(child, node) | 64 | chain_for_each_child(child, node) |
53 | sort_chain_to_rbtree(rb_root, child); | 65 | sort_chain_flat(rb_root, child); |
54 | 66 | ||
55 | if (node->hit) | 67 | if (node->hit) |
56 | rb_insert_callchain(rb_root, node); | 68 | rb_insert_callchain(rb_root, node, FLAT); |
69 | } | ||
70 | |||
71 | static void __sort_chain_graph(struct callchain_node *node) | ||
72 | { | ||
73 | struct callchain_node *child; | ||
74 | |||
75 | node->rb_root = RB_ROOT; | ||
76 | node->cumul_hit = node->hit; | ||
77 | |||
78 | chain_for_each_child(child, node) { | ||
79 | __sort_chain_graph(child); | ||
80 | rb_insert_callchain(&node->rb_root, child, GRAPH); | ||
81 | node->cumul_hit += child->cumul_hit; | ||
82 | } | ||
83 | } | ||
84 | |||
85 | void | ||
86 | sort_chain_graph(struct rb_root *rb_root, struct callchain_node *chain_root) | ||
87 | { | ||
88 | __sort_chain_graph(chain_root); | ||
89 | rb_root->rb_node = chain_root->rb_root.rb_node; | ||
57 | } | 90 | } |
58 | 91 | ||
59 | /* | 92 | /* |