4 files changed, 125 insertions, 46 deletions

diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c
index fd20670ce98..1478dc64bf1 100644
--- a/tools/perf/builtin-annotate.c
+++ b/tools/perf/builtin-annotate.c
@@ -285,7 +285,7 @@ static int hist_entry__tty_annotate(struct hist_entry *he)
         LIST_HEAD(head);
         struct objdump_line *pos, *n;
 
-        if (hist_entry__annotate(he, &head) < 0)
+        if (hist_entry__annotate(he, &head, 0) < 0)
                 return -1;
 
         if (full_paths)
diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c
index 62ec9b0e4b9..be22ae6ef05 100644
--- a/tools/perf/util/hist.c
+++ b/tools/perf/util/hist.c
@@ -983,9 +983,9 @@ int hist_entry__inc_addr_samples(struct hist_entry *self, u64 ip)
         return 0;
 }
 
-static struct objdump_line *objdump_line__new(s64 offset, char *line)
+static struct objdump_line *objdump_line__new(s64 offset, char *line, size_t privsize)
 {
-        struct objdump_line *self = malloc(sizeof(*self));
+        struct objdump_line *self = malloc(sizeof(*self) + privsize);
 
         if (self != NULL) {
                 self->offset = offset;
@@ -1017,7 +1017,7 @@ struct objdump_line *objdump__get_next_ip_line(struct list_head *head,
 }
 
 static int hist_entry__parse_objdump_line(struct hist_entry *self, FILE *file,
-                                          struct list_head *head)
+                                          struct list_head *head, size_t privsize)
 {
         struct symbol *sym = self->ms.sym;
         struct objdump_line *objdump_line;
@@ -1068,7 +1068,7 @@ static int hist_entry__parse_objdump_line(struct hist_entry *self, FILE *file,
                         offset = -1;
         }
 
-        objdump_line = objdump_line__new(offset, line);
+        objdump_line = objdump_line__new(offset, line, privsize);
         if (objdump_line == NULL) {
                 free(line);
                 return -1;
@@ -1078,7 +1078,8 @@ static int hist_entry__parse_objdump_line(struct hist_entry *self, FILE *file,
         return 0;
 }
 
-int hist_entry__annotate(struct hist_entry *self, struct list_head *head)
+int hist_entry__annotate(struct hist_entry *self, struct list_head *head,
+                         size_t privsize)
 {
         struct symbol *sym = self->ms.sym;
         struct map *map = self->ms.map;
@@ -1143,7 +1144,7 @@ fallback:
                 goto out_free_filename;
 
         while (!feof(file))
-                if (hist_entry__parse_objdump_line(self, file, head) < 0)
+                if (hist_entry__parse_objdump_line(self, file, head, privsize) < 0)
                         break;
 
         pclose(file);
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h
index 65a48db46a2..587d375d343 100644
--- a/tools/perf/util/hist.h
+++ b/tools/perf/util/hist.h
@@ -101,7 +101,8 @@ size_t hists__fprintf(struct hists *self, struct hists *pair,
                       bool show_displacement, FILE *fp);
 
 int hist_entry__inc_addr_samples(struct hist_entry *self, u64 ip);
-int hist_entry__annotate(struct hist_entry *self, struct list_head *head);
+int hist_entry__annotate(struct hist_entry *self, struct list_head *head,
+                         size_t privsize);
 
 void hists__filter_by_dso(struct hists *self, const struct dso *dso);
 void hists__filter_by_thread(struct hists *self, const struct thread *thread);
diff --git a/tools/perf/util/ui/browsers/annotate.c b/tools/perf/util/ui/browsers/annotate.c
index 5b01df633f9..763592b09d7 100644
--- a/tools/perf/util/ui/browsers/annotate.c
+++ b/tools/perf/util/ui/browsers/annotate.c
@@ -14,6 +14,23 @@ static void ui__error_window(const char *fmt, ...)
         va_end(ap);
 }
 
+struct annotate_browser {
+        struct ui_browser b;
+        struct rb_root    entries;
+};
+
+struct objdump_line_rb_node {
+        struct rb_node  rb_node;
+        double          percent;
+        u32             idx;
+};
+
+static inline
+struct objdump_line_rb_node *objdump_line__rb(struct objdump_line *self)
+{
+        return (struct objdump_line_rb_node *)(self + 1);
+}
+
 static void annotate_browser__write(struct ui_browser *self, void *entry, int row)
 {
         struct objdump_line *ol = rb_entry(entry, struct objdump_line, node);
@@ -21,17 +38,41 @@ static void annotate_browser__write(struct ui_browser *self, void *entry, int ro
         int width = self->width;
 
         if (ol->offset != -1) {
-                struct hist_entry *he = self->priv;
-                struct symbol *sym = he->ms.sym;
-                int len = he->ms.sym->end - he->ms.sym->start;
+                struct objdump_line_rb_node *olrb = objdump_line__rb(ol);
+                int color = ui_browser__percent_color(olrb->percent, current_entry);
+                SLsmg_set_color(color);
+                slsmg_printf(" %7.2f ", olrb->percent);
+                if (!current_entry)
+                        SLsmg_set_color(HE_COLORSET_CODE);
+        } else {
+                int color = ui_browser__percent_color(0, current_entry);
+                SLsmg_set_color(color);
+                slsmg_write_nstring(" ", 9);
+        }
+
+        SLsmg_write_char(':');
+        slsmg_write_nstring(" ", 8);
+        if (!*ol->line)
+                slsmg_write_nstring(" ", width - 18);
+        else
+                slsmg_write_nstring(ol->line, width - 18);
+}
+
+static double objdump_line__calc_percent(struct objdump_line *self,
+                                         struct list_head *head,
+                                         struct symbol *sym)
+{
+        double percent = 0.0;
+
+        if (self->offset != -1) {
+                int len = sym->end - sym->start;
                 unsigned int hits = 0;
-                double percent = 0.0;
-                int color;
                 struct sym_priv *priv = symbol__priv(sym);
                 struct sym_ext *sym_ext = priv->ext;
                 struct sym_hist *h = priv->hist;
-                s64 offset = ol->offset;
-                struct objdump_line *next = objdump__get_next_ip_line(self->entries, ol);
+                s64 offset = self->offset;
+                struct objdump_line *next = objdump__get_next_ip_line(head, self);
+
 
                 while (offset < (s64)len &&
                        (next == NULL || offset < next->offset)) {
@@ -45,37 +86,45 @@ static void annotate_browser__write(struct ui_browser *self, void *entry, int ro
 
                 if (sym_ext == NULL && h->sum)
                         percent = 100.0 * hits / h->sum;
-
-                color = ui_browser__percent_color(percent, current_entry);
-                SLsmg_set_color(color);
-                slsmg_printf(" %7.2f ", percent);
-                if (!current_entry)
-                        SLsmg_set_color(HE_COLORSET_CODE);
-        } else {
-                int color = ui_browser__percent_color(0, current_entry);
-                SLsmg_set_color(color);
-                slsmg_write_nstring(" ", 9);
         }
 
-        SLsmg_write_char(':');
-        slsmg_write_nstring(" ", 8);
-        if (!*ol->line)
-                slsmg_write_nstring(" ", width - 18);
-        else
-                slsmg_write_nstring(ol->line, width - 18);
+        return percent;
+}
+
+static void objdump__insert_line(struct rb_root *self,
+                                 struct objdump_line_rb_node *line)
+{
+        struct rb_node **p = &self->rb_node;
+        struct rb_node *parent = NULL;
+        struct objdump_line_rb_node *l;
+
+        while (*p != NULL) {
+                parent = *p;
+                l = rb_entry(parent, struct objdump_line_rb_node, rb_node);
+                if (line->percent < l->percent)
+                        p = &(*p)->rb_left;
+                else
+                        p = &(*p)->rb_right;
+        }
+        rb_link_node(&line->rb_node, parent, p);
+        rb_insert_color(&line->rb_node, self);
 }
 
 int hist_entry__tui_annotate(struct hist_entry *self)
 {
         struct newtExitStruct es;
         struct objdump_line *pos, *n;
+        struct objdump_line_rb_node *rbpos;
+        struct rb_node *nd;
         LIST_HEAD(head);
-        struct ui_browser browser = {
-                .entries = &head,
-                .refresh = ui_browser__list_head_refresh,
-                .seek    = ui_browser__list_head_seek,
-                .write   = annotate_browser__write,
-                .priv    = self,
+        struct annotate_browser browser = {
+                .b = {
+                        .entries = &head,
+                        .refresh = ui_browser__list_head_refresh,
+                        .seek    = ui_browser__list_head_seek,
+                        .write   = annotate_browser__write,
+                        .priv    = self,
+                },
         };
         int ret;
 
@@ -85,7 +134,7 @@ int hist_entry__tui_annotate(struct hist_entry *self)
         if (self->ms.map->dso->annotate_warned)
                 return -1;
 
-        if (hist_entry__annotate(self, &head) < 0) {
+        if (hist_entry__annotate(self, &head, sizeof(*rbpos)) < 0) {
                 ui__error_window(ui_helpline__last_msg);
                 return -1;
         }
@@ -94,16 +143,44 @@ int hist_entry__tui_annotate(struct hist_entry *self)
 
         list_for_each_entry(pos, &head, node) {
                 size_t line_len = strlen(pos->line);
-                if (browser.width < line_len)
-                        browser.width = line_len;
-                ++browser.nr_entries;
+                if (browser.b.width < line_len)
+                        browser.b.width = line_len;
+                rbpos = objdump_line__rb(pos);
+                rbpos->idx = browser.b.nr_entries++;
+                rbpos->percent = objdump_line__calc_percent(pos, &head, self->ms.sym);
+                if (rbpos->percent < 0.01)
+                        continue;
+                objdump__insert_line(&browser.entries, rbpos);
+        }
+
+        /*
+         * Position the browser at the hottest line.
+         */
+        nd = rb_last(&browser.entries);
+        if (nd != NULL) {
+                unsigned back;
+
+                ui_browser__refresh_dimensions(&browser.b);
+                back = browser.b.height / 2;
+                rbpos = rb_entry(nd, struct objdump_line_rb_node, rb_node);
+                pos = ((struct objdump_line *)rbpos) - 1;
+                browser.b.top_idx = browser.b.index = rbpos->idx;
+
+                while (browser.b.top_idx != 0 && back != 0) {
+                        pos = list_entry(pos->node.prev, struct objdump_line, node);
+
+                        --browser.b.top_idx;
+                        --back;
+                }
+
+                browser.b.top = pos;
         }
 
-        browser.width += 18; /* Percentage */
-        ui_browser__show(&browser, self->ms.sym->name);
-        newtFormAddHotKey(browser.form, ' ');
-        ret = ui_browser__run(&browser, &es);
-        newtFormDestroy(browser.form);
+        browser.b.width += 18; /* Percentage */
+        ui_browser__show(&browser.b, self->ms.sym->name);
+        newtFormAddHotKey(browser.b.form, ' ');
+        ret = ui_browser__run(&browser.b, &es);
+        newtFormDestroy(browser.b.form);
         newtPopWindow();
         list_for_each_entry_safe(pos, n, &head, node) {
                 list_del(&pos->node);