perf hists: Introduce hists__link_hierarchy()

The hists__link_hierarchy() is to support hierarchy reports with an
event group.  When it matches the leader event and the other members
(using hists__match_hierarchy()), it also needs to link unmatched member
entries with a dummy leader event so that it can show up in the output.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20160913074552.13284-3-namhyung@kernel.org
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>

1 files changed, 95 insertions, 0 deletions

diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index be3f5ce31303..702ba3a8ead6 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -2149,6 +2149,50 @@ out:
         return he;
 }
 
+static struct hist_entry *add_dummy_hierarchy_entry(struct hists *hists,
+                                                    struct rb_root *root,
+                                                    struct hist_entry *pair)
+{
+        struct rb_node **p;
+        struct rb_node *parent = NULL;
+        struct hist_entry *he;
+        struct perf_hpp_fmt *fmt;
+
+        p = &root->rb_node;
+        while (*p != NULL) {
+                int64_t cmp = 0;
+
+                parent = *p;
+                he = rb_entry(parent, struct hist_entry, rb_node_in);
+
+                perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
+                        cmp = fmt->collapse(fmt, he, pair);
+                        if (cmp)
+                                break;
+                }
+                if (!cmp)
+                        goto out;
+
+                if (cmp < 0)
+                        p = &parent->rb_left;
+                else
+                        p = &parent->rb_right;
+        }
+
+        he = hist_entry__new(pair, true);
+        if (he) {
+                rb_link_node(&he->rb_node_in, parent, p);
+                rb_insert_color(&he->rb_node_in, root);
+
+                he->dummy = true;
+                he->hists = hists;
+                memset(&he->stat, 0, sizeof(he->stat));
+                hists__inc_stats(hists, he);
+        }
+out:
+        return he;
+}
+
 static struct hist_entry *hists__find_entry(struct hists *hists,
                                             struct hist_entry *he)
 {
@@ -2248,6 +2292,50 @@ void hists__match(struct hists *leader, struct hists *other)
         }
 }
 
+static int hists__link_hierarchy(struct hists *leader_hists,
+                                 struct hist_entry *parent,
+                                 struct rb_root *leader_root,
+                                 struct rb_root *other_root)
+{
+        struct rb_node *nd;
+        struct hist_entry *pos, *leader;
+
+        for (nd = rb_first(other_root); nd; nd = rb_next(nd)) {
+                pos = rb_entry(nd, struct hist_entry, rb_node_in);
+
+                if (hist_entry__has_pairs(pos)) {
+                        bool found = false;
+
+                        list_for_each_entry(leader, &pos->pairs.head, pairs.node) {
+                                if (leader->hists == leader_hists) {
+                                        found = true;
+                                        break;
+                                }
+                        }
+                        if (!found)
+                                return -1;
+                } else {
+                        leader = add_dummy_hierarchy_entry(leader_hists,
+                                                           leader_root, pos);
+                        if (leader == NULL)
+                                return -1;
+
+                        /* do not point parent in the pos */
+                        leader->parent_he = parent;
+
+                        hist_entry__add_pair(pos, leader);
+                }
+
+                if (!pos->leaf) {
+                        if (hists__link_hierarchy(leader_hists, leader,
+                                                  &leader->hroot_in,
+                                                  &pos->hroot_in) < 0)
+                                return -1;
+                }
+        }
+        return 0;
+}
+
 /*
  * Look for entries in the other hists that are not present in the leader, if
  * we find them, just add a dummy entry on the leader hists, with period=0,
@@ -2259,6 +2347,13 @@ int hists__link(struct hists *leader, struct hists *other)
         struct rb_node *nd;
         struct hist_entry *pos, *pair;
 
+        if (symbol_conf.report_hierarchy) {
+                /* hierarchy report always collapses entries */
+                return hists__link_hierarchy(leader, NULL,
+                                             &leader->entries_collapsed,
+                                             &other->entries_collapsed);
+        }
+
         if (hists__has(other, need_collapse))
                 root = &other->entries_collapsed;
         else