Merge "simpleperf: refactor SampleTree for reuse."

12 files changed, 1180 insertions, 988 deletions

diff --git a/simpleperf/Android.mk b/simpleperf/Android.mk
index 5a64a3f0..842991e3 100644
--- a/simpleperf/Android.mk
+++ b/simpleperf/Android.mk
@@ -74,7 +74,6 @@ simpleperf_ldlibs_host_linux := -lrt
 # libsimpleperf
 # =========================================================
 libsimpleperf_src_files := \
-  callchain.cpp \
   cmd_dumprecord.cpp \
   cmd_help.cpp \
   cmd_report.cpp \
@@ -87,7 +86,6 @@ libsimpleperf_src_files := \
   read_elf.cpp \
   record.cpp \
   record_file_reader.cpp \
-  sample_tree.cpp \
   thread_tree.cpp \
   utils.cpp \
 
diff --git a/simpleperf/SampleComparator.h b/simpleperf/SampleComparator.h
new file mode 100644
index 00000000..8f9b2e4b
--- /dev/null
+++ b/simpleperf/SampleComparator.h
@@ -0,0 +1,104 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SIMPLE_PERF_SAMPLE_COMPARATOR_H_
+#define SIMPLE_PERF_SAMPLE_COMPARATOR_H_
+
+#include <string.h>
+
+#include <vector>
+
+// The compare functions below are used to compare two samples by their item
+// content.
+
+template <typename T>
+int Compare(const T& a, const T& b) {
+  if (a != b) {
+    return a < b ? -1 : 1;
+  }
+  return 0;
+}
+
+#define BUILD_COMPARE_VALUE_FUNCTION(function_name, compare_part)   \
+  template <typename EntryT>                                        \
+  int function_name(const EntryT* sample1, const EntryT* sample2) { \
+    return Compare(sample1->compare_part, sample2->compare_part);   \
+  }
+
+#define BUILD_COMPARE_VALUE_FUNCTION_REVERSE(function_name, compare_part) \
+  template <typename EntryT>                                              \
+  int function_name(const EntryT* sample1, const EntryT* sample2) {       \
+    return Compare(sample2->compare_part, sample1->compare_part);         \
+  }
+
+#define BUILD_COMPARE_STRING_FUNCTION(function_name, compare_part)  \
+  template <typename EntryT>                                        \
+  int function_name(const EntryT* sample1, const EntryT* sample2) { \
+    return strcmp(sample1->compare_part, sample2->compare_part);    \
+  }
+
+BUILD_COMPARE_VALUE_FUNCTION(ComparePid, thread->pid);
+BUILD_COMPARE_VALUE_FUNCTION(CompareTid, thread->tid);
+BUILD_COMPARE_VALUE_FUNCTION_REVERSE(CompareSampleCount, sample_count);
+BUILD_COMPARE_STRING_FUNCTION(CompareComm, thread_comm);
+BUILD_COMPARE_STRING_FUNCTION(CompareDso, map->dso->Path().c_str());
+BUILD_COMPARE_STRING_FUNCTION(CompareSymbol, symbol->DemangledName());
+BUILD_COMPARE_STRING_FUNCTION(CompareDsoFrom,
+                              branch_from.map->dso->Path().c_str());
+BUILD_COMPARE_STRING_FUNCTION(CompareSymbolFrom,
+                              branch_from.symbol->DemangledName());
+
+template <typename EntryT>
+int CompareTotalPeriod(const EntryT* sample1, const EntryT* sample2) {
+  uint64_t period1 = sample1->period + sample1->accumulated_period;
+  uint64_t period2 = sample2->period + sample2->accumulated_period;
+  return Compare(period2, period1);
+}
+
+// SampleComparator is a class using a collection of compare functions to
+// compare two samples.
+
+template <typename EntryT>
+class SampleComparator {
+ public:
+  typedef int (*compare_sample_func_t)(const EntryT*, const EntryT*);
+
+  void AddCompareFunction(compare_sample_func_t func) {
+    compare_v_.push_back(func);
+  }
+
+  void AddComparator(const SampleComparator<EntryT>& other) {
+    compare_v_.insert(compare_v_.end(), other.compare_v_.begin(),
+                      other.compare_v_.end());
+  }
+
+  bool operator()(const EntryT* sample1, const EntryT* sample2) {
+    for (const auto& func : compare_v_) {
+      int ret = func(sample1, sample2);
+      if (ret != 0) {
+        return ret < 0;
+      }
+    }
+    return false;
+  }
+
+  bool empty() const { return compare_v_.empty(); }
+
+ private:
+  std::vector<compare_sample_func_t> compare_v_;
+};
+
+#endif  // SIMPLE_PERF_SAMPLE_COMPARATOR_H_
diff --git a/simpleperf/SampleDisplayer.h b/simpleperf/SampleDisplayer.h
new file mode 100644
index 00000000..c1a058be
--- /dev/null
+++ b/simpleperf/SampleDisplayer.h
@@ -0,0 +1,223 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SIMPLE_PERF_SAMPLE_DISPLAYER_H_
+#define SIMPLE_PERF_SAMPLE_DISPLAYER_H_
+
+#include <inttypes.h>
+
+#include <string>
+
+#include <android-base/logging.h>
+#include <android-base/stringprintf.h>
+
+// The display functions below are used to show items in a sample.
+
+template <typename EntryT, typename InfoT>
+std::string DisplayAccumulatedOverhead(const EntryT* sample,
+                                       const InfoT* info) {
+  uint64_t period = sample->period + sample->accumulated_period;
+  uint64_t total_period = info->total_period;
+  double percentage = (total_period != 0) ? 100.0 * period / total_period : 0.0;
+  return android::base::StringPrintf("%.2f%%", percentage);
+}
+
+template <typename EntryT, typename InfoT>
+std::string DisplaySelfOverhead(const EntryT* sample, const InfoT* info) {
+  uint64_t period = sample->period;
+  uint64_t total_period = info->total_period;
+  double percentage = (total_period != 0) ? 100.0 * period / total_period : 0.0;
+  return android::base::StringPrintf("%.2f%%", percentage);
+}
+
+#define BUILD_DISPLAY_UINT64_FUNCTION(function_name, display_part)        \
+  template <typename EntryT>                                              \
+  std::string function_name(const EntryT* sample) {                       \
+    return android::base::StringPrintf("%" PRIu64, sample->display_part); \
+  }
+
+BUILD_DISPLAY_UINT64_FUNCTION(DisplaySampleCount, sample_count);
+
+template <typename EntryT>
+std::string DisplayPid(const EntryT* sample) {
+  return android::base::StringPrintf("%d", sample->thread->pid);
+}
+
+template <typename EntryT>
+std::string DisplayTid(const EntryT* sample) {
+  return android::base::StringPrintf("%d", sample->thread->tid);
+}
+
+template <typename EntryT>
+std::string DisplayComm(const EntryT* sample) {
+  return sample->thread_comm;
+}
+
+template <typename EntryT>
+std::string DisplayDso(const EntryT* sample) {
+  return sample->map->dso->Path();
+}
+
+template <typename EntryT>
+std::string DisplaySymbol(const EntryT* sample) {
+  return sample->symbol->DemangledName();
+}
+
+template <typename EntryT>
+std::string DisplayDsoFrom(const EntryT* sample) {
+  return sample->branch_from.map->dso->Path();
+}
+
+template <typename EntryT>
+std::string DisplaySymbolFrom(const EntryT* sample) {
+  return sample->branch_from.symbol->DemangledName();
+}
+
+template <typename CallChainNodeT>
+void DisplayCallGraphEntry(FILE* fp, size_t depth, std::string prefix,
+                           const std::unique_ptr<CallChainNodeT>& node,
+                           uint64_t parent_period, bool last) {
+  if (depth > 20) {
+    LOG(WARNING) << "truncated callgraph at depth " << depth;
+    return;
+  }
+  prefix += "|";
+  fprintf(fp, "%s\n", prefix.c_str());
+  if (last) {
+    prefix.back() = ' ';
+  }
+  std::string percentage_s = "-- ";
+  if (node->period + node->children_period != parent_period) {
+    double percentage =
+        100.0 * (node->period + node->children_period) / parent_period;
+    percentage_s = android::base::StringPrintf("--%.2f%%-- ", percentage);
+  }
+  fprintf(fp, "%s%s%s\n", prefix.c_str(), percentage_s.c_str(),
+          node->chain[0]->symbol->DemangledName());
+  prefix.append(percentage_s.size(), ' ');
+  for (size_t i = 1; i < node->chain.size(); ++i) {
+    fprintf(fp, "%s%s\n", prefix.c_str(),
+            node->chain[i]->symbol->DemangledName());
+  }
+  for (size_t i = 0; i < node->children.size(); ++i) {
+    DisplayCallGraphEntry(fp, depth + 1, prefix, node->children[i],
+                          node->children_period,
+                          (i + 1 == node->children.size()));
+  }
+}
+
+template <typename EntryT>
+void DisplayCallgraph(FILE* fp, const EntryT* sample) {
+  std::string prefix = "       ";
+  fprintf(fp, "%s|\n", prefix.c_str());
+  fprintf(fp, "%s-- %s\n", prefix.c_str(), sample->symbol->DemangledName());
+  prefix.append(3, ' ');
+  for (size_t i = 0; i < sample->callchain.children.size(); ++i) {
+    DisplayCallGraphEntry(fp, 1, prefix, sample->callchain.children[i],
+                          sample->callchain.children_period,
+                          (i + 1 == sample->callchain.children.size()));
+  }
+}
+
+// SampleDisplayer is a class using a collections of display functions to show a
+// sample.
+
+template <typename EntryT, typename InfoT>
+class SampleDisplayer {
+ public:
+  typedef std::string (*display_sample_func_t)(const EntryT*);
+  typedef std::string (*display_sample_with_info_func_t)(const EntryT*,
+                                                         const InfoT*);
+  typedef void (*exclusive_display_sample_func_t)(FILE* fp, const EntryT*);
+
+ private:
+  struct Item {
+    std::string name;
+    size_t width;
+    display_sample_func_t func;
+    display_sample_with_info_func_t func_with_info;
+  };
+
+ public:
+  void SetInfo(const InfoT* info) { info_ = info; }
+
+  void AddDisplayFunction(const std::string& name, display_sample_func_t func) {
+    Item item;
+    item.name = name;
+    item.width = name.size();
+    item.func = func;
+    item.func_with_info = nullptr;
+    display_v_.push_back(item);
+  }
+
+  void AddDisplayFunction(const std::string& name,
+                          display_sample_with_info_func_t func_with_info) {
+    Item item;
+    item.name = name;
+    item.width = name.size();
+    item.func = nullptr;
+    item.func_with_info = func_with_info;
+    display_v_.push_back(item);
+  }
+
+  void AddExclusiveDisplayFunction(exclusive_display_sample_func_t func) {
+    exclusive_display_v_.push_back(func);
+  }
+
+  void AdjustWidth(const EntryT* sample) {
+    for (auto& item : display_v_) {
+      std::string data = (item.func != nullptr)
+                             ? item.func(sample)
+                             : item.func_with_info(sample, info_);
+      item.width = std::max(item.width, data.size());
+    }
+  }
+
+  void PrintNames(FILE* fp) {
+    for (size_t i = 0; i < display_v_.size(); ++i) {
+      auto& item = display_v_[i];
+      if (i != display_v_.size() - 1) {
+        fprintf(fp, "%-*s  ", static_cast<int>(item.width), item.name.c_str());
+      } else {
+        fprintf(fp, "%s\n", item.name.c_str());
+      }
+    }
+  }
+
+  void PrintSample(FILE* fp, const EntryT* sample) {
+    for (size_t i = 0; i < display_v_.size(); ++i) {
+      auto& item = display_v_[i];
+      std::string data = (item.func != nullptr)
+                             ? item.func(sample)
+                             : item.func_with_info(sample, info_);
+      if (i != display_v_.size() - 1) {
+        fprintf(fp, "%-*s  ", static_cast<int>(item.width), data.c_str());
+      } else {
+        fprintf(fp, "%s\n", data.c_str());
+      }
+    }
+    for (auto& func : exclusive_display_v_) {
+      func(fp, sample);
+    }
+  }
+
+ private:
+  const InfoT* info_;
+  std::vector<Item> display_v_;
+  std::vector<exclusive_display_sample_func_t> exclusive_display_v_;
+};
+
+#endif  // SIMPLE_PERF_SAMPLE_DISPLAYER_H_
diff --git a/simpleperf/callchain.cpp b/simpleperf/callchain.cpp
deleted file mode 100644
index 8fdafc43..00000000
--- a/simpleperf/callchain.cpp
+++ /dev/null
@@ -1,128 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "callchain.h"
-
-#include <string.h>
-
-#include <queue>
-
-#include <android-base/logging.h>
-#include "sample_tree.h"
-
-static bool MatchSampleByName(const SampleEntry* sample1, const SampleEntry* sample2) {
-  return strcmp(sample1->symbol->Name(), sample2->symbol->Name()) == 0;
-}
-
-static size_t GetMatchingLengthInNode(const CallChainNode* node,
-                                      const std::vector<SampleEntry*>& chain, size_t chain_start) {
-  size_t i, j;
-  for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); ++i, ++j) {
-    if (!MatchSampleByName(node->chain[i], chain[j])) {
-      break;
-    }
-  }
-  return i;
-}
-
-static CallChainNode* FindMatchingNode(const std::vector<std::unique_ptr<CallChainNode>>& nodes,
-                                       const SampleEntry* sample) {
-  for (auto& node : nodes) {
-    if (MatchSampleByName(node->chain.front(), sample)) {
-      return node.get();
-    }
-  }
-  return nullptr;
-}
-
-static std::unique_ptr<CallChainNode> AllocateNode(const std::vector<SampleEntry*>& chain,
-                                                   size_t chain_start, uint64_t period,
-                                                   uint64_t children_period) {
-  std::unique_ptr<CallChainNode> node(new CallChainNode);
-  for (size_t i = chain_start; i < chain.size(); ++i) {
-    node->chain.push_back(chain[i]);
-  }
-  node->period = period;
-  node->children_period = children_period;
-  return node;
-}
-
-static void SplitNode(CallChainNode* parent, size_t parent_length) {
-  std::unique_ptr<CallChainNode> child =
-      AllocateNode(parent->chain, parent_length, parent->period, parent->children_period);
-  child->children = std::move(parent->children);
-  parent->period = 0;
-  parent->children_period = child->period + child->children_period;
-  parent->chain.resize(parent_length);
-  parent->children.clear();
-  parent->children.push_back(std::move(child));
-}
-
-void CallChainRoot::AddCallChain(const std::vector<SampleEntry*>& callchain, uint64_t period) {
-  children_period += period;
-  CallChainNode* p = FindMatchingNode(children, callchain[0]);
-  if (p == nullptr) {
-    std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, 0, period, 0);
-    children.push_back(std::move(new_node));
-    return;
-  }
-  size_t callchain_pos = 0;
-  while (true) {
-    size_t match_length = GetMatchingLengthInNode(p, callchain, callchain_pos);
-    CHECK_GT(match_length, 0u);
-    callchain_pos += match_length;
-    bool find_child = true;
-    if (match_length < p->chain.size()) {
-      SplitNode(p, match_length);
-      find_child = false;  // No need to find matching node in p->children.
-    }
-    if (callchain_pos == callchain.size()) {
-      p->period += period;
-      return;
-    }
-    p->children_period += period;
-    if (find_child) {
-      CallChainNode* np = FindMatchingNode(p->children, callchain[callchain_pos]);
-      if (np != nullptr) {
-        p = np;
-        continue;
-      }
-    }
-    std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, callchain_pos, period, 0);
-    p->children.push_back(std::move(new_node));
-    break;
-  }
-}
-
-static bool CompareNodeByPeriod(const std::unique_ptr<CallChainNode>& n1,
-                                const std::unique_ptr<CallChainNode>& n2) {
-  uint64_t period1 = n1->period + n1->children_period;
-  uint64_t period2 = n2->period + n2->children_period;
-  return period1 > period2;
-}
-
-void CallChainRoot::SortByPeriod() {
-  std::queue<std::vector<std::unique_ptr<CallChainNode>>*> queue;
-  queue.push(&children);
-  while (!queue.empty()) {
-    std::vector<std::unique_ptr<CallChainNode>>* v = queue.front();
-    queue.pop();
-    std::sort(v->begin(), v->end(), CompareNodeByPeriod);
-    for (auto& node : *v) {
-      queue.push(&node->children);
-    }
-  }
-}
diff --git a/simpleperf/callchain.h b/simpleperf/callchain.h
index 4b8a9d41..54820b14 100644
--- a/simpleperf/callchain.h
+++ b/simpleperf/callchain.h
@@ -17,27 +17,140 @@
 #ifndef SIMPLE_PERF_CALLCHAIN_H_
 #define SIMPLE_PERF_CALLCHAIN_H_
 
+#include <string.h>
+
+#include <algorithm>
 #include <memory>
+#include <queue>
 #include <vector>
 
-struct SampleEntry;
+#include <android-base/logging.h>
 
+template <typename EntryT>
 struct CallChainNode {
   uint64_t period;
   uint64_t children_period;
-  std::vector<SampleEntry*> chain;
+  std::vector<EntryT*> chain;
   std::vector<std::unique_ptr<CallChainNode>> children;
 };
 
+template <typename EntryT>
 struct CallChainRoot {
+  typedef CallChainNode<EntryT> NodeT;
   uint64_t children_period;
-  std::vector<std::unique_ptr<CallChainNode>> children;
+  std::vector<std::unique_ptr<NodeT>> children;
+
+  CallChainRoot() : children_period(0) {}
+
+  void AddCallChain(const std::vector<EntryT*>& callchain, uint64_t period) {
+    children_period += period;
+    NodeT* p = FindMatchingNode(children, callchain[0]);
+    if (p == nullptr) {
+      std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0);
+      children.push_back(std::move(new_node));
+      return;
+    }
+    size_t callchain_pos = 0;
+    while (true) {
+      size_t match_length =
+          GetMatchingLengthInNode(p, callchain, callchain_pos);
+      CHECK_GT(match_length, 0u);
+      callchain_pos += match_length;
+      bool find_child = true;
+      if (match_length < p->chain.size()) {
+        SplitNode(p, match_length);
+        find_child = false;  // No need to find matching node in p->children.
+      }
+      if (callchain_pos == callchain.size()) {
+        p->period += period;
+        return;
+      }
+      p->children_period += period;
+      if (find_child) {
+        NodeT* np = FindMatchingNode(p->children, callchain[callchain_pos]);
+        if (np != nullptr) {
+          p = np;
+          continue;
+        }
+      }
+      std::unique_ptr<NodeT> new_node =
+          AllocateNode(callchain, callchain_pos, period, 0);
+      p->children.push_back(std::move(new_node));
+      break;
+    }
+  }
+
+  void SortByPeriod() {
+    std::queue<std::vector<std::unique_ptr<NodeT>>*> queue;
+    queue.push(&children);
+    while (!queue.empty()) {
+      std::vector<std::unique_ptr<NodeT>>* v = queue.front();
+      queue.pop();
+      std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod);
+      for (auto& node : *v) {
+        if (!node->children.empty()) {
+          queue.push(&node->children);
+        }
+      }
+    }
+  }
+
+ private:
+  NodeT* FindMatchingNode(const std::vector<std::unique_ptr<NodeT>>& nodes,
+                          const EntryT* sample) {
+    for (auto& node : nodes) {
+      if (MatchSampleByName(node->chain.front(), sample)) {
+        return node.get();
+      }
+    }
+    return nullptr;
+  }
+
+  size_t GetMatchingLengthInNode(NodeT* node, const std::vector<EntryT*>& chain,
+                                 size_t chain_start) {
+    size_t i, j;
+    for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size();
+         ++i, ++j) {
+      if (!MatchSampleByName(node->chain[i], chain[j])) {
+        break;
+      }
+    }
+    return i;
+  }
+
+  bool MatchSampleByName(const EntryT* sample1, const EntryT* sample2) {
+    return strcmp(sample1->symbol->Name(), sample2->symbol->Name()) == 0;
+  }
+
+  void SplitNode(NodeT* parent, size_t parent_length) {
+    std::unique_ptr<NodeT> child = AllocateNode(
+        parent->chain, parent_length, parent->period, parent->children_period);
+    child->children = std::move(parent->children);
+    parent->period = 0;
+    parent->children_period = child->period + child->children_period;
+    parent->chain.resize(parent_length);
+    parent->children.clear();
+    parent->children.push_back(std::move(child));
+  }
 
-  CallChainRoot() : children_period(0) {
+  std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain,
+                                      size_t chain_start, uint64_t period,
+                                      uint64_t children_period) {
+    std::unique_ptr<NodeT> node(new NodeT);
+    for (size_t i = chain_start; i < chain.size(); ++i) {
+      node->chain.push_back(chain[i]);
+    }
+    node->period = period;
+    node->children_period = children_period;
+    return node;
   }
 
-  void AddCallChain(const std::vector<SampleEntry*>& callchain, uint64_t period);
-  void SortByPeriod();
+  static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1,
+                                  const std::unique_ptr<NodeT>& n2) {
+    uint64_t period1 = n1->period + n1->children_period;
+    uint64_t period2 = n2->period + n2->children_period;
+    return period1 > period2;
+  }
 };
 
 #endif  // SIMPLE_PERF_CALLCHAIN_H_
diff --git a/simpleperf/cmd_report.cpp b/simpleperf/cmd_report.cpp
index cf41b24e..e2cd39c0 100644
--- a/simpleperf/cmd_report.cpp
+++ b/simpleperf/cmd_report.cpp
@@ -41,276 +41,250 @@
 #include "thread_tree.h"
 #include "utils.h"
 
-class Displayable {
- public:
-  explicit Displayable(const std::string& name) : name_(name), width_(name.size()) {
-  }
-
-  virtual ~Displayable() {
-  }
-
-  const std::string& Name() const {
-    return name_;
-  }
-  size_t Width() const {
-    return width_;
-  }
-
-  virtual std::string Show(const SampleEntry& sample) const = 0;
-  void AdjustWidth(const SampleEntry& sample) {
-    size_t size = Show(sample).size();
-    width_ = std::max(width_, size);
-  }
-
- private:
-  const std::string name_;
-  size_t width_;
-};
-
-class AccumulatedOverheadItem : public Displayable {
- public:
-  explicit AccumulatedOverheadItem(const SampleTree& sample_tree)
-      : Displayable("Children"), sample_tree_(sample_tree) {
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    uint64_t period = sample.period + sample.accumulated_period;
-    uint64_t total_period = sample_tree_.TotalPeriod();
-    double percentage = (total_period != 0) ? 100.0 * period / total_period : 0.0;
-    return android::base::StringPrintf("%.2lf%%", percentage);
-  }
-
- private:
-  const SampleTree& sample_tree_;
-};
-
-class SelfOverheadItem : public Displayable {
- public:
-  explicit SelfOverheadItem(const SampleTree& sample_tree, const std::string& name = "Self")
-      : Displayable(name), sample_tree_(sample_tree) {
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    uint64_t period = sample.period;
-    uint64_t total_period = sample_tree_.TotalPeriod();
-    double percentage = (total_period != 0) ? 100.0 * period / total_period : 0.0;
-    return android::base::StringPrintf("%.2lf%%", percentage);
-  }
-
- private:
-  const SampleTree& sample_tree_;
-};
-
-class SampleCountItem : public Displayable {
- public:
-  SampleCountItem() : Displayable("Sample") {
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    return android::base::StringPrintf("%" PRId64, sample.sample_count);
-  }
-};
-
-class Comparable {
- public:
-  virtual ~Comparable() {
-  }
-
-  virtual int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const = 0;
-};
-
-class PidItem : public Displayable, public Comparable {
- public:
-  PidItem() : Displayable("Pid") {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return sample1.thread->pid - sample2.thread->pid;
-  }
+namespace {
 
-  std::string Show(const SampleEntry& sample) const override {
-    return android::base::StringPrintf("%d", sample.thread->pid);
-  }
-};
-
-class TidItem : public Displayable, public Comparable {
- public:
-  TidItem() : Displayable("Tid") {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return sample1.thread->tid - sample2.thread->tid;
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    return android::base::StringPrintf("%d", sample.thread->tid);
-  }
+static std::set<std::string> branch_sort_keys = {
+    "dso_from", "dso_to", "symbol_from", "symbol_to",
 };
+struct BranchFromEntry {
+  uint64_t ip;
+  const MapEntry* map;
+  const Symbol* symbol;
+  uint64_t flags;
 
-class CommItem : public Displayable, public Comparable {
- public:
-  CommItem() : Displayable("Command") {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return strcmp(sample1.thread_comm, sample2.thread_comm);
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    return sample.thread_comm;
-  }
+  BranchFromEntry() : ip(0), map(nullptr), symbol(nullptr), flags(0) {}
 };
 
-class DsoItem : public Displayable, public Comparable {
- public:
-  explicit DsoItem(const std::string& name = "Shared Object") : Displayable(name) {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return strcmp(sample1.map->dso->Path().c_str(), sample2.map->dso->Path().c_str());
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    return sample.map->dso->Path();
-  }
+struct SampleEntry {
+  uint64_t ip;
+  uint64_t time;
+  uint64_t period;
+  // accumuated when appearing in other sample's callchain
+  uint64_t accumulated_period;
+  uint64_t sample_count;
+  const ThreadEntry* thread;
+  const char* thread_comm;
+  const MapEntry* map;
+  const Symbol* symbol;
+  BranchFromEntry branch_from;
+  // a callchain tree representing all callchains in the sample
+  CallChainRoot<SampleEntry> callchain;
+
+  SampleEntry(uint64_t ip, uint64_t time, uint64_t period,
+              uint64_t accumulated_period, uint64_t sample_count,
+              const ThreadEntry* thread, const MapEntry* map,
+              const Symbol* symbol)
+      : ip(ip),
+        time(time),
+        period(period),
+        accumulated_period(accumulated_period),
+        sample_count(sample_count),
+        thread(thread),
+        thread_comm(thread->comm),
+        map(map),
+        symbol(symbol) {}
+
+  // The data member 'callchain' can only move, not copy.
+  SampleEntry(SampleEntry&&) = default;
+  SampleEntry(SampleEntry&) = delete;
 };
 
-class SymbolItem : public Displayable, public Comparable {
- public:
-  explicit SymbolItem(const std::string& name = "Symbol") : Displayable(name) {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return strcmp(sample1.symbol->DemangledName(), sample2.symbol->DemangledName());
-  }
-
-  std::string Show(const SampleEntry& sample) const override {
-    return sample.symbol->DemangledName();
-  }
+struct SampleTree {
+  std::vector<SampleEntry*> samples;
+  uint64_t total_samples;
+  uint64_t total_period;
 };
 
-class DsoFromItem : public Displayable, public Comparable {
+class ReportCmdSampleTreeBuilder
+    : public SampleTreeBuilder<SampleEntry, uint64_t> {
  public:
-  DsoFromItem() : Displayable("Source Shared Object") {
-  }
-
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return strcmp(sample1.branch_from.map->dso->Path().c_str(),
-                  sample2.branch_from.map->dso->Path().c_str());
+  ReportCmdSampleTreeBuilder(SampleComparator<SampleEntry> sample_comparator,
+                             ThreadTree* thread_tree)
+      : SampleTreeBuilder(sample_comparator),
+        thread_tree_(thread_tree),
+        total_samples_(0),
+        total_period_(0) {}
+
+  void SetFilters(const std::unordered_set<int>& pid_filter,
+                  const std::unordered_set<int>& tid_filter,
+                  const std::unordered_set<std::string>& comm_filter,
+                  const std::unordered_set<std::string>& dso_filter) {
+    pid_filter_ = pid_filter;
+    tid_filter_ = tid_filter;
+    comm_filter_ = comm_filter;
+    dso_filter_ = dso_filter;
+  }
+
+  SampleTree GetSampleTree() const {
+    SampleTree sample_tree;
+    sample_tree.samples = GetSamples();
+    sample_tree.total_samples = total_samples_;
+    sample_tree.total_period = total_period_;
+    return sample_tree;
+  }
+
+ protected:
+  SampleEntry* CreateSample(const SampleRecord& r, bool in_kernel,
+                            uint64_t* acc_info) override {
+    const ThreadEntry* thread =
+        thread_tree_->FindThreadOrNew(r.tid_data.pid, r.tid_data.tid);
+    const MapEntry* map =
+        thread_tree_->FindMap(thread, r.ip_data.ip, in_kernel);
+    const Symbol* symbol = thread_tree_->FindSymbol(map, r.ip_data.ip);
+    *acc_info = r.period_data.period;
+    return InsertSample(std::unique_ptr<SampleEntry>(
+        new SampleEntry(r.ip_data.ip, r.time_data.time, r.period_data.period, 0,
+                        1, thread, map, symbol)));
+  }
+
+  SampleEntry* CreateBranchSample(const SampleRecord& r,
+                                  const BranchStackItemType& item) override {
+    const ThreadEntry* thread =
+        thread_tree_->FindThreadOrNew(r.tid_data.pid, r.tid_data.tid);
+    const MapEntry* from_map = thread_tree_->FindMap(thread, item.from);
+    const Symbol* from_symbol = thread_tree_->FindSymbol(from_map, item.from);
+    const MapEntry* to_map = thread_tree_->FindMap(thread, item.to);
+    const Symbol* to_symbol = thread_tree_->FindSymbol(to_map, item.to);
+    std::unique_ptr<SampleEntry> sample(
+        new SampleEntry(item.to, r.time_data.time, r.period_data.period, 0, 1,
+                        thread, to_map, to_symbol));
+    sample->branch_from.ip = item.from;
+    sample->branch_from.map = from_map;
+    sample->branch_from.symbol = from_symbol;
+    sample->branch_from.flags = item.flags;
+    return InsertSample(std::move(sample));
+  }
+
+  SampleEntry* CreateCallChainSample(const SampleEntry* sample, uint64_t ip,
+                                     bool in_kernel,
+                                     const std::vector<SampleEntry*>& callchain,
+                                     const uint64_t& acc_info) override {
+    const ThreadEntry* thread = sample->thread;
+    const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
+    const Symbol* symbol = thread_tree_->FindSymbol(map, ip);
+    std::unique_ptr<SampleEntry> callchain_sample(
+        new SampleEntry(ip, sample->time, 0, acc_info, 0, thread, map, symbol));
+    return InsertCallChainSample(std::move(callchain_sample), callchain);
+  }
+
+  const ThreadEntry* GetThreadOfSample(SampleEntry* sample) override {
+    return sample->thread;
+  }
+
+  void InsertCallChainForSample(SampleEntry* sample,
+                                const std::vector<SampleEntry*>& callchain,
+                                const uint64_t& acc_info) override {
+    sample->callchain.AddCallChain(callchain, acc_info);
+  }
+
+  bool FilterSample(const SampleEntry* sample) override {
+    if (!pid_filter_.empty() &&
+        pid_filter_.find(sample->thread->pid) == pid_filter_.end()) {
+      return false;
+    }
+    if (!tid_filter_.empty() &&
+        tid_filter_.find(sample->thread->tid) == tid_filter_.end()) {
+      return false;
+    }
+    if (!comm_filter_.empty() &&
+        comm_filter_.find(sample->thread_comm) == comm_filter_.end()) {
+      return false;
+    }
+    if (!dso_filter_.empty() &&
+        dso_filter_.find(sample->map->dso->Path()) == dso_filter_.end()) {
+      return false;
+    }
+    return true;
   }
 
-  std::string Show(const SampleEntry& sample) const override {
-    return sample.branch_from.map->dso->Path();
+  void UpdateSummary(const SampleEntry* sample) override {
+    total_samples_ += sample->sample_count;
+    total_period_ += sample->period;
   }
-};
 
-class DsoToItem : public DsoItem {
- public:
-  DsoToItem() : DsoItem("Target Shared Object") {
+  void MergeSample(SampleEntry* sample1, SampleEntry* sample2) override {
+    sample1->period += sample2->period;
+    sample1->accumulated_period += sample2->accumulated_period;
+    sample1->sample_count += sample2->sample_count;
   }
-};
 
-class SymbolFromItem : public Displayable, public Comparable {
- public:
-  SymbolFromItem() : Displayable("Source Symbol") {
-  }
+ private:
+  ThreadTree* thread_tree_;
 
-  int Compare(const SampleEntry& sample1, const SampleEntry& sample2) const override {
-    return strcmp(sample1.branch_from.symbol->DemangledName(),
-                  sample2.branch_from.symbol->DemangledName());
-  }
+  std::unordered_set<int> pid_filter_;
+  std::unordered_set<int> tid_filter_;
+  std::unordered_set<std::string> comm_filter_;
+  std::unordered_set<std::string> dso_filter_;
 
-  std::string Show(const SampleEntry& sample) const override {
-    return sample.branch_from.symbol->DemangledName();
-  }
+  uint64_t total_samples_;
+  uint64_t total_period_;
 };
 
-class SymbolToItem : public SymbolItem {
- public:
-  SymbolToItem() : SymbolItem("Target Symbol") {
-  }
-};
-
-static std::set<std::string> branch_sort_keys = {
-    "dso_from", "dso_to", "symbol_from", "symbol_to",
-};
+using ReportCmdSampleTreeSorter = SampleTreeSorter<SampleEntry>;
+using ReportCmdSampleTreeDisplayer =
+    SampleTreeDisplayer<SampleEntry, SampleTree>;
 
 class ReportCommand : public Command {
  public:
   ReportCommand()
       : Command(
             "report", "report sampling information in perf.data",
-            "Usage: simpleperf report [options]\n"
-            "    -b            Use the branch-to addresses in sampled take branches instead of\n"
-            "                  the instruction addresses. Only valid for perf.data recorded with\n"
-            "                  -b/-j option.\n"
-            "    --children    Print the overhead accumulated by appearing in the callchain.\n"
-            "    --comms comm1,comm2,...\n"
-            "                  Report only for selected comms.\n"
-            "    --dsos dso1,dso2,...\n"
-            "                  Report only for selected dsos.\n"
-            "    -g [callee|caller]\n"
-            "                  Print call graph. If callee mode is used, the graph shows how\n"
-            "                  functions are called from others. Otherwise, the graph shows how\n"
-            "                  functions call others. Default is callee mode.\n"
-            "    -i <file>     Specify path of record file, default is perf.data.\n"
-            "    -n            Print the sample count for each item.\n"
-            "    --no-demangle        Don't demangle symbol names.\n"
-            "    -o report_file_name  Set report file name, default is stdout.\n"
-            "    --pids pid1,pid2,...\n"
-            "                  Report only for selected pids.\n"
-            "    --sort key1,key2,...\n"
-            "                  Select the keys to sort and print the report. Possible keys\n"
-            "                  include pid, tid, comm, dso, symbol, dso_from, dso_to, symbol_from\n"
-            "                  symbol_to. dso_from, dso_to, symbol_from, symbol_to can only be\n"
-            "                  used with -b option. Default keys are \"comm,pid,tid,dso,symbol\"\n"
-            "    --symfs <dir> Look for files with symbols relative to this directory.\n"
-            "    --tids tid1,tid2,...\n"
-            "                  Report only for selected tids.\n"
-            "    --vmlinux <file>\n"
-            "                  Parse kernel symbols from <file>.\n"),
+            // clang-format off
+"Usage: simpleperf report [options]\n"
+"-b    Use the branch-to addresses in sampled take branches instead of the\n"
+"      instruction addresses. Only valid for perf.data recorded with -b/-j\n"
+"      option.\n"
+"--children    Print the overhead accumulated by appearing in the callchain.\n"
+"--comms comm1,comm2,...   Report only for selected comms.\n"
+"--dsos dso1,dso2,...      Report only for selected dsos.\n"
+"-g [callee|caller]    Print call graph. If callee mode is used, the graph\n"
+"                      shows how functions are called from others. Otherwise,\n"
+"                      the graph shows how functions call others.\n"
+"                      Default is callee mode.\n"
+"-i <file>  Specify path of record file, default is perf.data.\n"
+"-n         Print the sample count for each item.\n"
+"--no-demangle         Don't demangle symbol names.\n"
+"-o report_file_name   Set report file name, default is stdout.\n"
+"--pids pid1,pid2,...  Report only for selected pids.\n"
+"--sort key1,key2,...  Select the keys to sort and print the report.\n"
+"                      Possible keys include pid, tid, comm, dso, symbol,\n"
+"                      dso_from, dso_to, symbol_from, symbol_to.\n"
+"                      dso_from, dso_to, symbol_from, symbol_to can only be\n"
+"                      used with -b option.\n"
+"                      Default keys are \"comm,pid,tid,dso,symbol\"\n"
+"--symfs <dir>         Look for files with symbols relative to this directory.\n"
+"--tids tid1,tid2,...  Report only for selected tids.\n"
+"--vmlinux <file>      Parse kernel symbols from <file>.\n"
+            // clang-format on
+            ),
         record_filename_("perf.data"),
         record_file_arch_(GetBuildArch()),
         use_branch_address_(false),
         system_wide_collection_(false),
         accumulate_callchain_(false),
         print_callgraph_(false),
-        callgraph_show_callee_(true),
-        report_fp_(nullptr) {
-    compare_sample_func_t compare_sample_callback = std::bind(
-        &ReportCommand::CompareSampleEntry, this, std::placeholders::_1, std::placeholders::_2);
-    sample_tree_ =
-        std::unique_ptr<SampleTree>(new SampleTree(&thread_tree_, compare_sample_callback));
-  }
+        callgraph_show_callee_(true) {}
 
   bool Run(const std::vector<std::string>& args);
 
  private:
   bool ParseOptions(const std::vector<std::string>& args);
   bool ReadEventAttrFromRecordFile();
-  void ReadSampleTreeFromRecordFile();
-  void ProcessRecord(std::unique_ptr<Record> record);
-  void ProcessSampleRecord(const SampleRecord& r);
   bool ReadFeaturesFromRecordFile();
-  int CompareSampleEntry(const SampleEntry& sample1, const SampleEntry& sample2);
+  bool ReadSampleTreeFromRecordFile();
+  bool ProcessRecord(std::unique_ptr<Record> record);
   bool PrintReport();
-  void PrintReportContext();
-  void CollectReportWidth();
-  void CollectReportEntryWidth(const SampleEntry& sample);
-  void PrintReportHeader();
-  void PrintReportEntry(const SampleEntry& sample);
-  void PrintCallGraph(const SampleEntry& sample);
-  void PrintCallGraphEntry(size_t depth, std::string prefix, const std::unique_ptr<CallChainNode>& node,
-                           uint64_t parent_period, bool last);
+  void PrintReportContext(FILE* fp);
 
   std::string record_filename_;
   ArchType record_file_arch_;
   std::unique_ptr<RecordFileReader> record_file_reader_;
   std::vector<perf_event_attr> event_attrs_;
-  std::vector<std::unique_ptr<Displayable>> displayable_items_;
-  std::vector<Comparable*> comparable_items_;
   ThreadTree thread_tree_;
-  std::unique_ptr<SampleTree> sample_tree_;
+  SampleTree sample_tree_;
+  std::unique_ptr<ReportCmdSampleTreeBuilder> sample_tree_builder_;
+  std::unique_ptr<ReportCmdSampleTreeSorter> sample_tree_sorter_;
+  std::unique_ptr<ReportCmdSampleTreeDisplayer> sample_tree_displayer_;
   bool use_branch_address_;
   std::string record_cmdline_;
   bool system_wide_collection_;
@@ -319,7 +293,6 @@ class ReportCommand : public Command {
   bool callgraph_show_callee_;
 
   std::string report_filename_;
-  FILE* report_fp_;
 };
 
 bool ReportCommand::Run(const std::vector<std::string>& args) {
@@ -341,7 +314,9 @@ bool ReportCommand::Run(const std::vector<std::string>& args) {
     return false;
   }
   ScopedCurrentArch scoped_arch(record_file_arch_);
-  ReadSampleTreeFromRecordFile();
+  if (!ReadSampleTreeFromRecordFile()) {
+    return false;
+  }
 
   // 3. Show collected information.
   if (!PrintReport()) {
@@ -368,7 +343,8 @@ bool ReportCommand::ParseOptions(const std::vector<std::string>& args) {
     } else if (args[i] == "--children") {
       accumulate_callchain_ = true;
     } else if (args[i] == "--comms" || args[i] == "--dsos") {
-      std::unordered_set<std::string>& filter = (args[i] == "--comms" ? comm_filter : dso_filter);
+      std::unordered_set<std::string>& filter =
+          (args[i] == "--comms" ? comm_filter : dso_filter);
       if (!NextArgumentOrError(args, &i)) {
         return false;
       }
@@ -420,7 +396,8 @@ bool ReportCommand::ParseOptions(const std::vector<std::string>& args) {
         }
         ids.push_back(id);
       }
-      std::unordered_set<int>& filter = (args[i] == "--pids" ? pid_filter : tid_filter);
+      std::unordered_set<int>& filter =
+          (args[i] == "--pids" ? pid_filter : tid_filter);
       filter.insert(ids.begin(), ids.end());
 
     } else if (args[i] == "--sort") {
@@ -453,69 +430,77 @@ bool ReportCommand::ParseOptions(const std::vector<std::string>& args) {
     Dso::SetVmlinux(vmlinux);
   }
 
-  if (!accumulate_callchain_) {
-    displayable_items_.push_back(
-        std::unique_ptr<Displayable>(new SelfOverheadItem(*sample_tree_, "Overhead")));
+  SampleDisplayer<SampleEntry, SampleTree> displayer;
+  SampleComparator<SampleEntry> comparator;
+
+  if (accumulate_callchain_) {
+    displayer.AddDisplayFunction("Children", DisplayAccumulatedOverhead);
+    displayer.AddDisplayFunction("Self", DisplaySelfOverhead);
   } else {
-    displayable_items_.push_back(
-        std::unique_ptr<Displayable>(new AccumulatedOverheadItem(*sample_tree_)));
-    displayable_items_.push_back(std::unique_ptr<Displayable>(new SelfOverheadItem(*sample_tree_)));
+    displayer.AddDisplayFunction("Overhead", DisplaySelfOverhead);
+  }
+  if (print_callgraph_) {
+    displayer.AddExclusiveDisplayFunction(DisplayCallgraph);
   }
   if (print_sample_count) {
-    displayable_items_.push_back(std::unique_ptr<Displayable>(new SampleCountItem));
+    displayer.AddDisplayFunction("Sample", DisplaySampleCount);
   }
+
   for (auto& key : sort_keys) {
-    if (!use_branch_address_ && branch_sort_keys.find(key) != branch_sort_keys.end()) {
+    if (!use_branch_address_ &&
+        branch_sort_keys.find(key) != branch_sort_keys.end()) {
       LOG(ERROR) << "sort key '" << key << "' can only be used with -b option.";
       return false;
     }
     if (key == "pid") {
-      PidItem* item = new PidItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(ComparePid);
+      displayer.AddDisplayFunction("Pid", DisplayPid);
     } else if (key == "tid") {
-      TidItem* item = new TidItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareTid);
+      displayer.AddDisplayFunction("Tid", DisplayTid);
     } else if (key == "comm") {
-      CommItem* item = new CommItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareComm);
+      displayer.AddDisplayFunction("Command", DisplayComm);
     } else if (key == "dso") {
-      DsoItem* item = new DsoItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareDso);
+      displayer.AddDisplayFunction("Shared Object", DisplayDso);
     } else if (key == "symbol") {
-      SymbolItem* item = new SymbolItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareSymbol);
+      displayer.AddDisplayFunction("Symbol", DisplaySymbol);
     } else if (key == "dso_from") {
-      DsoFromItem* item = new DsoFromItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareDsoFrom);
+      displayer.AddDisplayFunction("Source Shared Object", DisplayDsoFrom);
     } else if (key == "dso_to") {
-      DsoToItem* item = new DsoToItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareDso);
+      displayer.AddDisplayFunction("Target Shared Object", DisplayDso);
     } else if (key == "symbol_from") {
-      SymbolFromItem* item = new SymbolFromItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareSymbolFrom);
+      displayer.AddDisplayFunction("Source Symbol", DisplaySymbolFrom);
     } else if (key == "symbol_to") {
-      SymbolToItem* item = new SymbolToItem;
-      displayable_items_.push_back(std::unique_ptr<Displayable>(item));
-      comparable_items_.push_back(item);
+      comparator.AddCompareFunction(CompareSymbol);
+      displayer.AddDisplayFunction("Target Symbol", DisplaySymbol);
     } else {
       LOG(ERROR) << "Unknown sort key: " << key;
       return false;
     }
   }
-  sample_tree_->SetFilters(pid_filter, tid_filter, comm_filter, dso_filter);
+
+  sample_tree_builder_.reset(
+      new ReportCmdSampleTreeBuilder(comparator, &thread_tree_));
+  sample_tree_builder_->SetFilters(pid_filter, tid_filter, comm_filter,
+                                   dso_filter);
+
+  SampleComparator<SampleEntry> sort_comparator;
+  sort_comparator.AddCompareFunction(CompareTotalPeriod);
+  sort_comparator.AddComparator(comparator);
+  sample_tree_sorter_.reset(new ReportCmdSampleTreeSorter(sort_comparator));
+  sample_tree_displayer_.reset(new ReportCmdSampleTreeDisplayer(displayer));
   return true;
 }
 
 bool ReportCommand::ReadEventAttrFromRecordFile() {
-  const std::vector<PerfFileFormat::FileAttr>& file_attrs = record_file_reader_->AttrSection();
+  const std::vector<PerfFileFormat::FileAttr>& file_attrs =
+      record_file_reader_->AttrSection();
   for (const auto& attr : file_attrs) {
     event_attrs_.push_back(attr.attr);
   }
@@ -528,127 +513,25 @@ bool ReportCommand::ReadEventAttrFromRecordFile() {
       }
     }
     if (!has_branch_stack) {
-      LOG(ERROR) << record_filename_ << " is not recorded with branch stack sampling option.";
+      LOG(ERROR) << record_filename_
+                 << " is not recorded with branch stack sampling option.";
       return false;
     }
   }
   return true;
 }
 
-void ReportCommand::ReadSampleTreeFromRecordFile() {
-  thread_tree_.AddThread(0, 0, "swapper");
-  record_file_reader_->ReadDataSection([this](std::unique_ptr<Record> record) {
-    ProcessRecord(std::move(record));
-    return true;
-  });
-}
-
-void ReportCommand::ProcessRecord(std::unique_ptr<Record> record) {
-  BuildThreadTree(*record, &thread_tree_);
-  if (record->header.type == PERF_RECORD_SAMPLE) {
-    ProcessSampleRecord(*static_cast<const SampleRecord*>(record.get()));
-  }
-}
-
-void ReportCommand::ProcessSampleRecord(const SampleRecord& r) {
-  if (use_branch_address_ && (r.sample_type & PERF_SAMPLE_BRANCH_STACK)) {
-    for (auto& item : r.branch_stack_data.stack) {
-      if (item.from != 0 && item.to != 0) {
-        sample_tree_->AddBranchSample(r.tid_data.pid, r.tid_data.tid, item.from, item.to,
-                                      item.flags, r.time_data.time, r.period_data.period);
-      }
-    }
-  } else {
-    bool in_kernel = (r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL;
-    SampleEntry* sample = sample_tree_->AddSample(r.tid_data.pid, r.tid_data.tid, r.ip_data.ip,
-                                                  r.time_data.time, r.period_data.period, in_kernel);
-    if (sample == nullptr) {
-      return;
-    }
-    if (accumulate_callchain_) {
-      std::vector<uint64_t> ips;
-      if (r.sample_type & PERF_SAMPLE_CALLCHAIN) {
-        ips.insert(ips.end(), r.callchain_data.ips.begin(), r.callchain_data.ips.end());
-      }
-      // Use stack_user_data.data.size() instead of stack_user_data.dyn_size, to make up for
-      // the missing kernel patch in N9. See b/22612370.
-      if ((r.sample_type & PERF_SAMPLE_REGS_USER) && (r.regs_user_data.reg_mask != 0) &&
-          (r.sample_type & PERF_SAMPLE_STACK_USER) && (!r.stack_user_data.data.empty())) {
-        RegSet regs = CreateRegSet(r.regs_user_data.reg_mask, r.regs_user_data.regs);
-        std::vector<char> stack(r.stack_user_data.data.begin(),
-                                r.stack_user_data.data.begin() + r.stack_user_data.data.size());
-        ArchType arch = GetArchForAbi(ScopedCurrentArch::GetCurrentArch(), r.regs_user_data.abi);
-        // Normally do strict arch check when unwinding stack. But allow unwinding 32-bit processes
-        // on 64-bit devices for system wide profiling.
-        bool strict_arch_check = !system_wide_collection_;
-        std::vector<uint64_t> unwind_ips =
-            UnwindCallChain(arch, *sample->thread, regs, stack, strict_arch_check);
-        if (!unwind_ips.empty()) {
-          ips.push_back(PERF_CONTEXT_USER);
-          ips.insert(ips.end(), unwind_ips.begin(), unwind_ips.end());
-        }
-      }
-
-      std::vector<SampleEntry*> callchain;
-      callchain.push_back(sample);
-
-      bool first_ip = true;
-      for (auto& ip : ips) {
-        if (ip >= PERF_CONTEXT_MAX) {
-          switch (ip) {
-            case PERF_CONTEXT_KERNEL:
-              in_kernel = true;
-              break;
-            case PERF_CONTEXT_USER:
-              in_kernel = false;
-              break;
-            default:
-              LOG(ERROR) << "Unexpected perf_context in callchain: " << ip;
-          }
-        } else {
-          if (first_ip) {
-            first_ip = false;
-            // Remove duplication with sampled ip.
-            if (ip == r.ip_data.ip) {
-              continue;
-            }
-          }
-          SampleEntry* sample =
-              sample_tree_->AddCallChainSample(r.tid_data.pid, r.tid_data.tid, ip, r.time_data.time,
-                                               r.period_data.period, in_kernel, callchain);
-          callchain.push_back(sample);
-        }
-      }
-
-      if (print_callgraph_) {
-        std::set<SampleEntry*> added_set;
-        if (!callgraph_show_callee_) {
-          std::reverse(callchain.begin(), callchain.end());
-        }
-        while (callchain.size() >= 2) {
-          SampleEntry* sample = callchain[0];
-          callchain.erase(callchain.begin());
-          // Add only once for recursive calls on callchain.
-          if (added_set.find(sample) != added_set.end()) {
-            continue;
-          }
-          added_set.insert(sample);
-          sample_tree_->InsertCallChainForSample(sample, callchain, r.period_data.period);
-        }
-      }
-    }
-  }
-}
-
 bool ReportCommand::ReadFeaturesFromRecordFile() {
-  std::vector<BuildIdRecord> records = record_file_reader_->ReadBuildIdFeature();
+  std::vector<BuildIdRecord> records =
+      record_file_reader_->ReadBuildIdFeature();
   std::vector<std::pair<std::string, BuildId>> build_ids;
   for (auto& r : records) {
     build_ids.push_back(std::make_pair(r.filename, r.build_id));
   }
   Dso::SetBuildIds(build_ids);
 
-  std::string arch = record_file_reader_->ReadFeatureString(PerfFileFormat::FEAT_ARCH);
+  std::string arch =
+      record_file_reader_->ReadFeatureString(PerfFileFormat::FEAT_ARCH);
   if (!arch.empty()) {
     record_file_arch_ = GetArchType(arch);
     if (record_file_arch_ == ARCH_UNSUPPORTED) {
@@ -659,15 +542,16 @@ bool ReportCommand::ReadFeaturesFromRecordFile() {
   std::vector<std::string> cmdline = record_file_reader_->ReadCmdlineFeature();
   if (!cmdline.empty()) {
     record_cmdline_ = android::base::Join(cmdline, ' ');
-    // TODO: the code to detect system wide collection option is fragile, remove it once we can
-    // do cross unwinding.
+    // TODO: the code to detect system wide collection option is fragile, remove
+    // it once we can do cross unwinding.
     for (size_t i = 0; i < cmdline.size(); i++) {
       std::string& s = cmdline[i];
       if (s == "-a") {
         system_wide_collection_ = true;
         break;
-      } else if (s == "--call-graph" || s == "--cpu" || s == "-e" || s == "-f" || s == "-F" ||
-                 s == "-j" || s == "-m" || s == "-o" || s == "-p" || s == "-t") {
+      } else if (s == "--call-graph" || s == "--cpu" || s == "-e" ||
+                 s == "-f" || s == "-F" || s == "-j" || s == "-m" ||
+                 s == "-o" || s == "-p" || s == "-t") {
         i++;
       } else if (!s.empty() && s[0] != '-') {
         break;
@@ -677,44 +561,60 @@ bool ReportCommand::ReadFeaturesFromRecordFile() {
   return true;
 }
 
-int ReportCommand::CompareSampleEntry(const SampleEntry& sample1, const SampleEntry& sample2) {
-  for (auto& item : comparable_items_) {
-    int result = item->Compare(sample1, sample2);
-    if (result != 0) {
-      return result;
-    }
+bool ReportCommand::ReadSampleTreeFromRecordFile() {
+  thread_tree_.AddThread(0, 0, "swapper");
+  sample_tree_builder_->SetBranchSampleOption(use_branch_address_);
+  // Normally do strict arch check when unwinding stack. But allow unwinding
+  // 32-bit processes on 64-bit devices for system wide profiling.
+  bool strict_unwind_arch_check = !system_wide_collection_;
+  sample_tree_builder_->SetCallChainSampleOptions(
+      accumulate_callchain_, print_callgraph_, !callgraph_show_callee_,
+      strict_unwind_arch_check);
+  if (!record_file_reader_->ReadDataSection(
+          [this](std::unique_ptr<Record> record) {
+            return ProcessRecord(std::move(record));
+          })) {
+    return false;
+  }
+  sample_tree_ = sample_tree_builder_->GetSampleTree();
+  sample_tree_sorter_->Sort(sample_tree_.samples, print_callgraph_);
+  return true;
+}
+
+bool ReportCommand::ProcessRecord(std::unique_ptr<Record> record) {
+  BuildThreadTree(*record, &thread_tree_);
+  if (record->header.type == PERF_RECORD_SAMPLE) {
+    sample_tree_builder_->ProcessSampleRecord(
+        *static_cast<const SampleRecord*>(record.get()));
   }
-  return 0;
+  return true;
 }
 
 bool ReportCommand::PrintReport() {
   std::unique_ptr<FILE, decltype(&fclose)> file_handler(nullptr, fclose);
-  if (report_filename_.empty()) {
-    report_fp_ = stdout;
-  } else {
-    report_fp_ = fopen(report_filename_.c_str(), "w");
-    if (report_fp_ == nullptr) {
+  FILE* report_fp = stdout;
+  if (!report_filename_.empty()) {
+    report_fp = fopen(report_filename_.c_str(), "w");
+    if (report_fp == nullptr) {
       PLOG(ERROR) << "failed to open file " << report_filename_;
       return false;
     }
-    file_handler.reset(report_fp_);
-  }
-  PrintReportContext();
-  CollectReportWidth();
-  PrintReportHeader();
-  sample_tree_->VisitAllSamples(
-      std::bind(&ReportCommand::PrintReportEntry, this, std::placeholders::_1));
-  fflush(report_fp_);
-  if (ferror(report_fp_) != 0) {
+    file_handler.reset(report_fp);
+  }
+  PrintReportContext(report_fp);
+  sample_tree_displayer_->DisplaySamples(report_fp, sample_tree_.samples,
+                                         &sample_tree_);
+  fflush(report_fp);
+  if (ferror(report_fp) != 0) {
     PLOG(ERROR) << "print report failed";
     return false;
   }
   return true;
 }
 
-void ReportCommand::PrintReportContext() {
+void ReportCommand::PrintReportContext(FILE* report_fp) {
   if (!record_cmdline_.empty()) {
-    fprintf(report_fp_, "Cmdline: %s\n", record_cmdline_.c_str());
+    fprintf(report_fp, "Cmdline: %s\n", record_cmdline_.c_str());
   }
   for (const auto& attr : event_attrs_) {
     const EventType* event_type = FindEventTypeByConfig(attr.type, attr.config);
@@ -722,88 +622,16 @@ void ReportCommand::PrintReportContext() {
     if (event_type != nullptr) {
       name = event_type->name;
     }
-    fprintf(report_fp_, "Event: %s (type %u, config %llu)\n", name.c_str(), attr.type, attr.config);
+    fprintf(report_fp, "Event: %s (type %u, config %llu)\n", name.c_str(),
+            attr.type, attr.config);
   }
-  fprintf(report_fp_, "Samples: %" PRIu64 "\n", sample_tree_->TotalSamples());
-  fprintf(report_fp_, "Event count: %" PRIu64 "\n\n", sample_tree_->TotalPeriod());
+  fprintf(report_fp, "Samples: %" PRIu64 "\n", sample_tree_.total_samples);
+  fprintf(report_fp, "Event count: %" PRIu64 "\n\n", sample_tree_.total_period);
 }
 
-void ReportCommand::CollectReportWidth() {
-  sample_tree_->VisitAllSamples(
-      std::bind(&ReportCommand::CollectReportEntryWidth, this, std::placeholders::_1));
-}
-
-void ReportCommand::CollectReportEntryWidth(const SampleEntry& sample) {
-  for (auto& item : displayable_items_) {
-    item->AdjustWidth(sample);
-  }
-}
-
-void ReportCommand::PrintReportHeader() {
-  for (size_t i = 0; i < displayable_items_.size(); ++i) {
-    auto& item = displayable_items_[i];
-    if (i != displayable_items_.size() - 1) {
-      fprintf(report_fp_, "%-*s  ", static_cast<int>(item->Width()), item->Name().c_str());
-    } else {
-      fprintf(report_fp_, "%s\n", item->Name().c_str());
-    }
-  }
-}
-
-void ReportCommand::PrintReportEntry(const SampleEntry& sample) {
-  for (size_t i = 0; i < displayable_items_.size(); ++i) {
-    auto& item = displayable_items_[i];
-    if (i != displayable_items_.size() - 1) {
-      fprintf(report_fp_, "%-*s  ", static_cast<int>(item->Width()), item->Show(sample).c_str());
-    } else {
-      fprintf(report_fp_, "%s\n", item->Show(sample).c_str());
-    }
-  }
-  if (print_callgraph_) {
-    PrintCallGraph(sample);
-  }
-}
-
-void ReportCommand::PrintCallGraph(const SampleEntry& sample) {
-  std::string prefix = "       ";
-  fprintf(report_fp_, "%s|\n", prefix.c_str());
-  fprintf(report_fp_, "%s-- %s\n", prefix.c_str(), sample.symbol->DemangledName());
-  prefix.append(3, ' ');
-  for (size_t i = 0; i < sample.callchain.children.size(); ++i) {
-    PrintCallGraphEntry(1, prefix, sample.callchain.children[i], sample.callchain.children_period,
-                        (i + 1 == sample.callchain.children.size()));
-  }
-}
-
-void ReportCommand::PrintCallGraphEntry(size_t depth, std::string prefix,
-                                        const std::unique_ptr<CallChainNode>& node,
-                                        uint64_t parent_period, bool last) {
-  if (depth > 20) {
-    LOG(WARNING) << "truncated callgraph at depth " << depth;
-    return;
-  }
-  prefix += "|";
-  fprintf(report_fp_, "%s\n", prefix.c_str());
-  if (last) {
-    prefix.back() = ' ';
-  }
-  std::string percentage_s = "-- ";
-  if (node->period + node->children_period != parent_period) {
-    double percentage = 100.0 * (node->period + node->children_period) / parent_period;
-    percentage_s = android::base::StringPrintf("--%.2lf%%-- ", percentage);
-  }
-  fprintf(report_fp_, "%s%s%s\n", prefix.c_str(), percentage_s.c_str(), node->chain[0]->symbol->DemangledName());
-  prefix.append(percentage_s.size(), ' ');
-  for (size_t i = 1; i < node->chain.size(); ++i) {
-    fprintf(report_fp_, "%s%s\n", prefix.c_str(), node->chain[i]->symbol->DemangledName());
-  }
-
-  for (size_t i = 0; i < node->children.size(); ++i) {
-    PrintCallGraphEntry(depth + 1, prefix, node->children[i], node->children_period,
-                        (i + 1 == node->children.size()));
-  }
-}
+}  // namespace
 
 void RegisterReportCommand() {
-  RegisterCommand("report", [] { return std::unique_ptr<Command>(new ReportCommand()); });
+  RegisterCommand("report",
+                  [] { return std::unique_ptr<Command>(new ReportCommand()); });
 }
diff --git a/simpleperf/record.h b/simpleperf/record.h
index 8b17bc10..85dcbc70 100644
--- a/simpleperf/record.h
+++ b/simpleperf/record.h
@@ -81,12 +81,13 @@ struct PerfSampleRawType {
   std::vector<char> data;
 };
 
+struct BranchStackItemType {
+  uint64_t from;
+  uint64_t to;
+  uint64_t flags;
+};
+
 struct PerfSampleBranchStackType {
-  struct BranchStackItemType {
-    uint64_t from;
-    uint64_t to;
-    uint64_t flags;
-  };
   std::vector<BranchStackItemType> stack;
 };
 
@@ -152,6 +153,10 @@ struct Record {
     return header.type;
   }
 
+  bool InKernel() const {
+    return (header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL;
+  }
+
   void Dump(size_t indent = 0) const;
   virtual std::vector<char> BinaryFormat() const = 0;
   virtual uint64_t Timestamp() const;
diff --git a/simpleperf/sample_tree.cpp b/simpleperf/sample_tree.cpp
deleted file mode 100644
index a34107b1..00000000
--- a/simpleperf/sample_tree.cpp
+++ /dev/null
@@ -1,161 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "sample_tree.h"
-
-#include <android-base/logging.h>
-
-#include "environment.h"
-
-void SampleTree::SetFilters(const std::unordered_set<int>& pid_filter,
-                            const std::unordered_set<int>& tid_filter,
-                            const std::unordered_set<std::string>& comm_filter,
-                            const std::unordered_set<std::string>& dso_filter) {
-  pid_filter_ = pid_filter;
-  tid_filter_ = tid_filter;
-  comm_filter_ = comm_filter;
-  dso_filter_ = dso_filter;
-}
-
-SampleEntry* SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
-                                   bool in_kernel) {
-  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
-  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
-  const Symbol* symbol = thread_tree_->FindSymbol(map, ip);
-
-  SampleEntry value(ip, time, period, 0, 1, thread, map, symbol);
-
-  if (IsFilteredOut(value)) {
-    return nullptr;
-  }
-  return InsertSample(value);
-}
-
-void SampleTree::AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip,
-                                 uint64_t branch_flags, uint64_t time, uint64_t period) {
-  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
-  const MapEntry* from_map = thread_tree_->FindMap(thread, from_ip, false);
-  if (from_map == thread_tree_->UnknownMap()) {
-    from_map = thread_tree_->FindMap(thread, from_ip, true);
-  }
-  const Symbol* from_symbol = thread_tree_->FindSymbol(from_map, from_ip);
-  const MapEntry* to_map = thread_tree_->FindMap(thread, to_ip, false);
-  if (to_map == thread_tree_->UnknownMap()) {
-    to_map = thread_tree_->FindMap(thread, to_ip, true);
-  }
-  const Symbol* to_symbol = thread_tree_->FindSymbol(to_map, to_ip);
-
-  SampleEntry value(to_ip, time, period, 0, 1, thread, to_map, to_symbol);
-  value.branch_from.ip = from_ip;
-  value.branch_from.map = from_map;
-  value.branch_from.symbol = from_symbol;
-  value.branch_from.flags = branch_flags;
-
-  if (IsFilteredOut(value)) {
-    return;
-  }
-  InsertSample(value);
-}
-
-SampleEntry* SampleTree::AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time,
-                                            uint64_t period, bool in_kernel,
-                                            const std::vector<SampleEntry*>& callchain) {
-  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
-  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
-  const Symbol* symbol = thread_tree_->FindSymbol(map, ip);
-
-  SampleEntry value(ip, time, 0, period, 0, thread, map, symbol);
-
-  if (IsFilteredOut(value)) {
-    // Store in callchain_sample_tree_ for use in other SampleEntry's callchain.
-    auto it = callchain_sample_tree_.find(&value);
-    if (it != callchain_sample_tree_.end()) {
-      return *it;
-    }
-    SampleEntry* sample = AllocateSample(value);
-    callchain_sample_tree_.insert(sample);
-    return sample;
-  }
-
-  auto it = sample_tree_.find(&value);
-  if (it != sample_tree_.end()) {
-    SampleEntry* sample = *it;
-    // Process only once for recursive function call.
-    if (std::find(callchain.begin(), callchain.end(), sample) != callchain.end()) {
-      return sample;
-    }
-  }
-  return InsertSample(value);
-}
-
-bool SampleTree::IsFilteredOut(const SampleEntry& value) {
-  if (!pid_filter_.empty() && pid_filter_.find(value.thread->pid) == pid_filter_.end()) {
-    return true;
-  }
-  if (!tid_filter_.empty() && tid_filter_.find(value.thread->tid) == tid_filter_.end()) {
-    return true;
-  }
-  if (!comm_filter_.empty() && comm_filter_.find(value.thread_comm) == comm_filter_.end()) {
-    return true;
-  }
-  if (!dso_filter_.empty() && dso_filter_.find(value.map->dso->Path()) == dso_filter_.end()) {
-    return true;
-  }
-  return false;
-}
-
-SampleEntry* SampleTree::InsertSample(SampleEntry& value) {
-  SampleEntry* result;
-  auto it = sample_tree_.find(&value);
-  if (it == sample_tree_.end()) {
-    result = AllocateSample(value);
-    auto pair = sample_tree_.insert(result);
-    CHECK(pair.second);
-  } else {
-    result = *it;
-    result->period += value.period;
-    result->accumulated_period += value.accumulated_period;
-    result->sample_count += value.sample_count;
-  }
-  total_samples_ += value.sample_count;
-  total_period_ += value.period;
-  return result;
-}
-
-SampleEntry* SampleTree::AllocateSample(SampleEntry& value) {
-  SampleEntry* sample = new SampleEntry(std::move(value));
-  sample_storage_.push_back(std::unique_ptr<SampleEntry>(sample));
-  return sample;
-}
-
-void SampleTree::InsertCallChainForSample(SampleEntry* sample,
-                                          const std::vector<SampleEntry*>& callchain,
-                                          uint64_t period) {
-  sample->callchain.AddCallChain(callchain, period);
-}
-
-void SampleTree::VisitAllSamples(std::function<void(const SampleEntry&)> callback) {
-  if (sorted_sample_tree_.size() != sample_tree_.size()) {
-    sorted_sample_tree_.clear();
-    for (auto& sample : sample_tree_) {
-      sample->callchain.SortByPeriod();
-      sorted_sample_tree_.insert(sample);
-    }
-  }
-  for (auto& sample : sorted_sample_tree_) {
-    callback(*sample);
-  }
-}
diff --git a/simpleperf/sample_tree.h b/simpleperf/sample_tree.h
index 6eb73722..c35a91a2 100644
--- a/simpleperf/sample_tree.h
+++ b/simpleperf/sample_tree.h
@@ -17,146 +17,299 @@
 #ifndef SIMPLE_PERF_SAMPLE_TREE_H_
 #define SIMPLE_PERF_SAMPLE_TREE_H_
 
-#include <limits.h>
-#include <functional>
-#include <set>
-#include <string>
-#include <unordered_map>
-#include <unordered_set>
-#include <vector>
-
 #include "callchain.h"
+#include "dwarf_unwind.h"
+#include "perf_regs.h"
+#include "record.h"
+#include "SampleComparator.h"
+#include "SampleDisplayer.h"
 #include "thread_tree.h"
 
-struct BranchFromEntry {
-  uint64_t ip;
-  const MapEntry* map;
-  const Symbol* symbol;
-  uint64_t flags;
+// A SampleTree is a collection of samples. A profiling report is mainly about
+// constructing a SampleTree and display it. There are three steps involved:
+// build the tree, sort the tree, and display it. For example, if we want to
+// show how many cpu-cycles are spent in different functions, we should do as
+// follows:
+// 1. Build a SampleTree from SampleRecords with each sample containing
+//    (cpu-cycles, function name). When building the tree, we should merge
+//    samples containing the same function name.
+// 2. Sort the SampleTree by cpu-cycles in the sample. As we want to display the
+//    samples in a decreasing order of cpu-cycles, we should sort it like this.
+// 3. Display the SampleTree, each sample prints its (cpu-cycles, function name)
+//    pair.
+//
+// We represent the three steps with three template classes.
+// 1. A SampleTree is built by SampleTreeBuilder. The comparator passed in
+//    SampleTreeBuilder's constructor decides the property of samples should be
+//    merged together.
+// 2. After a SampleTree is built and got from SampleTreeBuilder, it should be
+//    sorted by SampleTreeSorter. The sort result decides the order to show
+//    samples.
+// 3. At last, the sorted SampleTree is passed to SampleTreeDisplayer, which
+//    displays each sample in the SampleTree.
+
+template <typename EntryT, typename AccumulateInfoT>
+class SampleTreeBuilder {
+ public:
+  SampleTreeBuilder(SampleComparator<EntryT> comparator)
+      : sample_set_(comparator),
+        callchain_sample_set_(comparator),
+        use_branch_address_(false),
+        accumulate_callchain_(false),
+        build_callchain_(false),
+        use_caller_as_callchain_root_(false),
+        strict_unwind_arch_check_(false) {}
+
+  virtual ~SampleTreeBuilder() {}
 
-  BranchFromEntry() : ip(0), map(nullptr), symbol(nullptr), flags(0) {
+  void SetBranchSampleOption(bool use_branch_address) {
+    use_branch_address_ = use_branch_address;
   }
-};
 
-struct SampleEntry {
-  uint64_t ip;
-  uint64_t time;
-  uint64_t period;
-  uint64_t accumulated_period;  // Accumulated when appearing in other samples' callchain.
-  uint64_t sample_count;
-  const ThreadEntry* thread;
-  const char* thread_comm;  // It refers to the thread comm when the sample happens.
-  const MapEntry* map;
-  const Symbol* symbol;
-  BranchFromEntry branch_from;
-  CallChainRoot callchain;  // A callchain tree representing all callchains in the sample records.
-
-  SampleEntry(uint64_t ip, uint64_t time, uint64_t period, uint64_t accumulated_period,
-              uint64_t sample_count, const ThreadEntry* thread, const MapEntry* map,
-              const Symbol* symbol)
-      : ip(ip),
-        time(time),
-        period(period),
-        accumulated_period(accumulated_period),
-        sample_count(sample_count),
-        thread(thread),
-        thread_comm(thread->comm),
-        map(map),
-        symbol(symbol) {
+  void SetCallChainSampleOptions(bool accumulate_callchain,
+                                 bool build_callchain,
+                                 bool use_caller_as_callchain_root,
+                                 bool strict_unwind_arch_check) {
+    accumulate_callchain_ = accumulate_callchain;
+    build_callchain_ = build_callchain;
+    use_caller_as_callchain_root_ = use_caller_as_callchain_root;
+    strict_unwind_arch_check_ = strict_unwind_arch_check;
   }
 
-  // The data member 'callchain' can only move, not copy.
-  SampleEntry(SampleEntry&&) = default;
-  SampleEntry(SampleEntry&) = delete;
-};
+  void ProcessSampleRecord(const SampleRecord& r) {
+    if (use_branch_address_ && (r.sample_type & PERF_SAMPLE_BRANCH_STACK)) {
+      for (auto& item : r.branch_stack_data.stack) {
+        if (item.from != 0 && item.to != 0) {
+          CreateBranchSample(r, item);
+        }
+      }
+      return;
+    }
+    bool in_kernel = r.InKernel();
+    AccumulateInfoT acc_info;
+    EntryT* sample = CreateSample(r, in_kernel, &acc_info);
+    if (sample == nullptr) {
+      return;
+    }
+    if (accumulate_callchain_) {
+      std::vector<uint64_t> ips;
+      if (r.sample_type & PERF_SAMPLE_CALLCHAIN) {
+        ips.insert(ips.end(), r.callchain_data.ips.begin(),
+                   r.callchain_data.ips.end());
+      }
+      const ThreadEntry* thread = GetThreadOfSample(sample);
+      // Use stack_user_data.data.size() instead of stack_user_data.dyn_size, to
+      // make up for the missing kernel patch in N9. See b/22612370.
+      if (thread != nullptr && (r.sample_type & PERF_SAMPLE_REGS_USER) &&
+          (r.regs_user_data.reg_mask != 0) &&
+          (r.sample_type & PERF_SAMPLE_STACK_USER) &&
+          (!r.stack_user_data.data.empty())) {
+        RegSet regs =
+            CreateRegSet(r.regs_user_data.reg_mask, r.regs_user_data.regs);
+        std::vector<char> stack(
+            r.stack_user_data.data.begin(),
+            r.stack_user_data.data.begin() + r.stack_user_data.data.size());
+        ArchType arch = GetArchForAbi(ScopedCurrentArch::GetCurrentArch(),
+                                      r.regs_user_data.abi);
+        std::vector<uint64_t> unwind_ips = UnwindCallChain(
+            arch, *thread, regs, stack, strict_unwind_arch_check_);
+        if (!unwind_ips.empty()) {
+          ips.push_back(PERF_CONTEXT_USER);
+          ips.insert(ips.end(), unwind_ips.begin(), unwind_ips.end());
+        }
+      }
 
-typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t;
+      std::vector<EntryT*> callchain;
+      callchain.push_back(sample);
 
-class SampleTree {
- public:
-  SampleTree(ThreadTree* thread_tree, compare_sample_func_t sample_compare_function)
-      : thread_tree_(thread_tree),
-        sample_comparator_(sample_compare_function),
-        sample_tree_(sample_comparator_),
-        callchain_sample_tree_(sample_comparator_),
-        sorted_sample_comparator_(sample_compare_function),
-        sorted_sample_tree_(sorted_sample_comparator_),
-        total_samples_(0),
-        total_period_(0) {
-  }
+      bool first_ip = true;
+      for (auto& ip : ips) {
+        if (ip >= PERF_CONTEXT_MAX) {
+          switch (ip) {
+            case PERF_CONTEXT_KERNEL:
+              in_kernel = true;
+              break;
+            case PERF_CONTEXT_USER:
+              in_kernel = false;
+              break;
+            default:
+              LOG(DEBUG) << "Unexpected perf_context in callchain: " << ip;
+          }
+        } else {
+          if (first_ip) {
+            first_ip = false;
+            // Remove duplication with sampled ip.
+            if (ip == r.ip_data.ip) {
+              continue;
+            }
+          }
+          EntryT* callchain_sample =
+              CreateCallChainSample(sample, ip, in_kernel, callchain, acc_info);
+          if (callchain_sample == nullptr) {
+            break;
+          }
+          callchain.push_back(callchain_sample);
+        }
+      }
 
-  void SetFilters(const std::unordered_set<int>& pid_filter,
-                  const std::unordered_set<int>& tid_filter,
-                  const std::unordered_set<std::string>& comm_filter,
-                  const std::unordered_set<std::string>& dso_filter);
-
-  SampleEntry* AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
-                         bool in_kernel);
-  void AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip, uint64_t branch_flags,
-                       uint64_t time, uint64_t period);
-  SampleEntry* AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
-                                  bool in_kernel, const std::vector<SampleEntry*>& callchain);
-  void InsertCallChainForSample(SampleEntry* sample, const std::vector<SampleEntry*>& callchain,
-                                uint64_t period);
-  void VisitAllSamples(std::function<void(const SampleEntry&)> callback);
-
-  uint64_t TotalSamples() const {
-    return total_samples_;
+      if (build_callchain_) {
+        std::set<EntryT*> added_set;
+        if (use_caller_as_callchain_root_) {
+          std::reverse(callchain.begin(), callchain.end());
+        }
+        while (callchain.size() >= 2) {
+          EntryT* sample = callchain[0];
+          callchain.erase(callchain.begin());
+          // Add only once for recursive calls on callchain.
+          if (added_set.find(sample) != added_set.end()) {
+            continue;
+          }
+          added_set.insert(sample);
+          InsertCallChainForSample(sample, callchain, acc_info);
+        }
+      }
+    }
   }
 
-  uint64_t TotalPeriod() const {
-    return total_period_;
+  std::vector<EntryT*> GetSamples() const {
+    std::vector<EntryT*> result;
+    for (auto& entry : sample_set_) {
+      result.push_back(entry);
+    }
+    return result;
   }
 
- private:
-  bool IsFilteredOut(const SampleEntry& value);
-  SampleEntry* InsertSample(SampleEntry& value);
-  SampleEntry* AllocateSample(SampleEntry& value);
+ protected:
+  virtual EntryT* CreateSample(const SampleRecord& r, bool in_kernel,
+                               AccumulateInfoT* acc_info) = 0;
+  virtual EntryT* CreateBranchSample(const SampleRecord& r,
+                                     const BranchStackItemType& item) = 0;
+  virtual EntryT* CreateCallChainSample(const EntryT* sample, uint64_t ip,
+                                        bool in_kernel,
+                                        const std::vector<EntryT*>& callchain,
+                                        const AccumulateInfoT& acc_info) = 0;
+  virtual const ThreadEntry* GetThreadOfSample(EntryT*) = 0;
+  virtual void InsertCallChainForSample(EntryT* sample,
+                                        const std::vector<EntryT*>& callchain,
+                                        const AccumulateInfoT& acc_info) = 0;
+  virtual bool FilterSample(const EntryT*) { return true; }
 
-  struct SampleComparator {
-    bool operator()(SampleEntry* sample1, SampleEntry* sample2) const {
-      return compare_function(*sample1, *sample2) < 0;
+  virtual void UpdateSummary(const EntryT*) {}
+
+  virtual void MergeSample(EntryT* sample1, EntryT* sample2) = 0;
+
+  EntryT* InsertSample(std::unique_ptr<EntryT> sample) {
+    if (sample == nullptr || !FilterSample(sample.get())) {
+      return nullptr;
     }
-    SampleComparator(compare_sample_func_t compare_function) : compare_function(compare_function) {
+    UpdateSummary(sample.get());
+    EntryT* result;
+    auto it = sample_set_.find(sample.get());
+    if (it == sample_set_.end()) {
+      result = sample.get();
+      sample_set_.insert(sample.get());
+      sample_storage_.push_back(std::move(sample));
+    } else {
+      result = *it;
+      MergeSample(*it, sample.get());
     }
+    return result;
+  }
 
-    compare_sample_func_t compare_function;
-  };
+  EntryT* InsertCallChainSample(std::unique_ptr<EntryT> sample,
+                                const std::vector<EntryT*>& callchain) {
+    if (sample == nullptr) {
+      return nullptr;
+    }
+    if (!FilterSample(sample.get())) {
+      // Store in callchain_sample_set_ for use in other EntryT's callchain.
+      auto it = callchain_sample_set_.find(sample.get());
+      if (it != callchain_sample_set_.end()) {
+        return *it;
+      }
+      EntryT* result = sample.get();
+      callchain_sample_set_.insert(sample.get());
+      sample_storage_.push_back(std::move(sample));
+      return result;
+    }
+
+    auto it = sample_set_.find(sample.get());
+    if (it != sample_set_.end()) {
+      EntryT* sample = *it;
+      // Process only once for recursive function call.
+      if (std::find(callchain.begin(), callchain.end(), sample) !=
+          callchain.end()) {
+        return sample;
+      }
+    }
+    return InsertSample(std::move(sample));
+  }
+
+  std::set<EntryT*, SampleComparator<EntryT>> sample_set_;
+
+ private:
+  // If a CallChainSample is filtered out, it is stored in callchain_sample_set_
+  // and only used in other EntryT's callchain.
+  std::set<EntryT*, SampleComparator<EntryT>> callchain_sample_set_;
+  std::vector<std::unique_ptr<EntryT>> sample_storage_;
+
+  bool use_branch_address_;
+  bool accumulate_callchain_;
+  bool build_callchain_;
+  bool use_caller_as_callchain_root_;
+  bool strict_unwind_arch_check_;
+};
+
+template <typename EntryT>
+class SampleTreeSorter {
+ public:
+  SampleTreeSorter(SampleComparator<EntryT> comparator)
+      : comparator_(comparator) {}
+
+  virtual ~SampleTreeSorter() {}
 
-  struct SortedSampleComparator {
-    bool operator()(SampleEntry* sample1, SampleEntry* sample2) const {
-      uint64_t period1 = sample1->period + sample1->accumulated_period;
-      uint64_t period2 = sample2->period + sample2->accumulated_period;
-      if (period1 != period2) {
-        return period1 > period2;
+  void Sort(std::vector<EntryT*>& v, bool sort_callchain) {
+    if (sort_callchain) {
+      for (auto& sample : v) {
+        SortCallChain(sample);
       }
-      return compare_function(*sample1, *sample2) < 0;
     }
-    SortedSampleComparator(compare_sample_func_t compare_function)
-        : compare_function(compare_function) {
+    if (!comparator_.empty()) {
+      std::sort(v.begin(), v.end(), [this](const EntryT* s1, const EntryT* s2) {
+        return comparator_(s1, s2);
+      });
     }
+  }
 
-    compare_sample_func_t compare_function;
-  };
+ protected:
+  void SortCallChain(EntryT* sample) { sample->callchain.SortByPeriod(); }
 
-  ThreadTree* thread_tree_;
-  SampleComparator sample_comparator_;
-  std::set<SampleEntry*, SampleComparator> sample_tree_;
-  // If a CallChainSample is filtered out, it is stored in callchain_sample_tree_ and only used
-  // in other SampleEntry's callchain.
-  std::set<SampleEntry*, SampleComparator> callchain_sample_tree_;
+ private:
+  SampleComparator<EntryT> comparator_;
+};
 
-  SortedSampleComparator sorted_sample_comparator_;
-  std::set<SampleEntry*, SortedSampleComparator> sorted_sample_tree_;
-  std::vector<std::unique_ptr<SampleEntry>> sample_storage_;
+template <typename EntryT, typename InfoT>
+class SampleTreeDisplayer {
+ public:
+  SampleTreeDisplayer(SampleDisplayer<EntryT, InfoT> displayer)
+      : displayer_(displayer) {}
 
-  std::unordered_set<int> pid_filter_;
-  std::unordered_set<int> tid_filter_;
-  std::unordered_set<std::string> comm_filter_;
-  std::unordered_set<std::string> dso_filter_;
+  virtual ~SampleTreeDisplayer() {}
 
-  uint64_t total_samples_;
-  uint64_t total_period_;
+  void DisplaySamples(FILE* fp, const std::vector<EntryT*>& samples,
+                      const InfoT* info) {
+    displayer_.SetInfo(info);
+    for (const auto& sample : samples) {
+      displayer_.AdjustWidth(sample);
+    }
+    displayer_.PrintNames(fp);
+    for (const auto& sample : samples) {
+      displayer_.PrintSample(fp, sample);
+    }
+  }
+
+ private:
+  SampleDisplayer<EntryT, InfoT> displayer_;
 };
 
 #endif  // SIMPLE_PERF_SAMPLE_TREE_H_
diff --git a/simpleperf/sample_tree_test.cpp b/simpleperf/sample_tree_test.cpp
index 434ee713..a88ecf98 100644
--- a/simpleperf/sample_tree_test.cpp
+++ b/simpleperf/sample_tree_test.cpp
@@ -17,64 +17,105 @@
 #include <gtest/gtest.h>
 
 #include "sample_tree.h"
+#include "thread_tree.h"
 
-struct ExpectedSampleInMap {
+namespace {
+
+struct SampleEntry {
   int pid;
   int tid;
-  const char* comm;
+  const char* thread_comm;
   std::string dso_name;
   uint64_t map_start_addr;
   size_t sample_count;
+
+  SampleEntry(int pid, int tid, const char* thread_comm,
+              const std::string& dso_name, uint64_t map_start_addr,
+              size_t sample_count = 1u)
+      : pid(pid),
+        tid(tid),
+        thread_comm(thread_comm),
+        dso_name(dso_name),
+        map_start_addr(map_start_addr),
+        sample_count(sample_count) {}
 };
 
-static void SampleMatchExpectation(const SampleEntry& sample, const ExpectedSampleInMap& expected,
-                                   bool* has_error) {
-  *has_error = true;
-  ASSERT_TRUE(sample.thread != nullptr);
-  ASSERT_EQ(expected.pid, sample.thread->pid);
-  ASSERT_EQ(expected.tid, sample.thread->tid);
-  ASSERT_STREQ(expected.comm, sample.thread_comm);
-  ASSERT_TRUE(sample.map != nullptr);
-  ASSERT_EQ(expected.dso_name, sample.map->dso->Path());
-  ASSERT_EQ(expected.map_start_addr, sample.map->start_addr);
-  ASSERT_EQ(expected.sample_count, sample.sample_count);
-  *has_error = false;
-}
+BUILD_COMPARE_VALUE_FUNCTION(TestComparePid, pid);
+BUILD_COMPARE_VALUE_FUNCTION(TestCompareTid, tid);
+BUILD_COMPARE_STRING_FUNCTION(TestCompareDsoName, dso_name.c_str());
+BUILD_COMPARE_VALUE_FUNCTION(TestCompareMapStartAddr, map_start_addr);
+
+class TestSampleComparator : public SampleComparator<SampleEntry> {
+ public:
+  TestSampleComparator() {
+    AddCompareFunction(TestComparePid);
+    AddCompareFunction(TestCompareTid);
+    AddCompareFunction(CompareComm);
+    AddCompareFunction(TestCompareDsoName);
+    AddCompareFunction(TestCompareMapStartAddr);
+  }
+};
 
-static void CheckSampleCallback(const SampleEntry& sample,
-                                std::vector<ExpectedSampleInMap>& expected_samples, size_t* pos) {
-  ASSERT_LT(*pos, expected_samples.size());
-  bool has_error;
-  SampleMatchExpectation(sample, expected_samples[*pos], &has_error);
-  ASSERT_FALSE(has_error) << "Error matching sample at pos " << *pos;
-  ++*pos;
-}
+class TestSampleTreeBuilder : public SampleTreeBuilder<SampleEntry, int> {
+ public:
+  TestSampleTreeBuilder(ThreadTree* thread_tree)
+      : SampleTreeBuilder(TestSampleComparator()), thread_tree_(thread_tree) {}
 
-static int CompareSampleFunction(const SampleEntry& sample1, const SampleEntry& sample2) {
-  if (sample1.thread->pid != sample2.thread->pid) {
-    return sample1.thread->pid - sample2.thread->pid;
+  void AddSample(int pid, int tid, uint64_t ip, bool in_kernel) {
+    const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
+    const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
+    InsertSample(std::unique_ptr<SampleEntry>(new SampleEntry(
+        pid, tid, thread->comm, map->dso->Path(), map->start_addr)));
   }
-  if (sample1.thread->tid != sample2.thread->tid) {
-    return sample1.thread->tid - sample2.thread->tid;
+
+ protected:
+  SampleEntry* CreateSample(const SampleRecord&, bool, int*) override {
+    return nullptr;
   }
-  if (strcmp(sample1.thread_comm, sample2.thread_comm) != 0) {
-    return strcmp(sample1.thread_comm, sample2.thread_comm);
+  SampleEntry* CreateBranchSample(const SampleRecord&,
+                                  const BranchStackItemType&) override {
+    return nullptr;
+  };
+  SampleEntry* CreateCallChainSample(const SampleEntry*, uint64_t, bool,
+                                     const std::vector<SampleEntry*>&,
+                                     const int&) override {
+    return nullptr;
   }
-  if (sample1.map->dso->Path() != sample2.map->dso->Path()) {
-    return sample1.map->dso->Path() > sample2.map->dso->Path() ? 1 : -1;
+  const ThreadEntry* GetThreadOfSample(SampleEntry*) override {
+    return nullptr;
   }
-  if (sample1.map->start_addr != sample2.map->start_addr) {
-    return sample1.map->start_addr - sample2.map->start_addr;
+  void InsertCallChainForSample(SampleEntry*, const std::vector<SampleEntry*>&,
+                                const int&) override {}
+  void MergeSample(SampleEntry* sample1, SampleEntry* sample2) override {
+    sample1->sample_count += sample2->sample_count;
   }
-  return 0;
+
+ private:
+  ThreadTree* thread_tree_;
+};
+
+static void SampleMatchExpectation(const SampleEntry& sample,
+                                   const SampleEntry& expected,
+                                   bool* has_error) {
+  *has_error = true;
+  ASSERT_EQ(expected.pid, sample.pid);
+  ASSERT_EQ(expected.tid, sample.tid);
+  ASSERT_STREQ(expected.thread_comm, sample.thread_comm);
+  ASSERT_EQ(expected.dso_name, sample.dso_name);
+  ASSERT_EQ(expected.map_start_addr, sample.map_start_addr);
+  ASSERT_EQ(expected.sample_count, sample.sample_count);
+  *has_error = false;
 }
 
-void VisitSampleTree(SampleTree* sample_tree,
-                     const std::vector<ExpectedSampleInMap>& expected_samples) {
-  size_t pos = 0;
-  sample_tree->VisitAllSamples(
-      std::bind(&CheckSampleCallback, std::placeholders::_1, expected_samples, &pos));
-  ASSERT_EQ(expected_samples.size(), pos);
+static void CheckSamples(const std::vector<SampleEntry*>& samples,
+                         const std::vector<SampleEntry>& expected_samples) {
+  ASSERT_EQ(samples.size(), expected_samples.size());
+  for (size_t i = 0; i < samples.size(); ++i) {
+    bool has_error;
+    SampleMatchExpectation(*samples[i], expected_samples[i], &has_error);
+    ASSERT_FALSE(has_error) << "Error matching sample at pos " << i;
+  }
+}
 }
 
 class SampleTreeTest : public testing::Test {
@@ -88,102 +129,107 @@ class SampleTreeTest : public testing::Test {
     thread_tree.AddThreadMap(1, 11, 1, 10, 0, 0, "process1_thread11");
     thread_tree.AddThreadMap(2, 2, 1, 20, 0, 0, "process2_thread2");
     thread_tree.AddKernelMap(10, 20, 0, 0, "kernel");
-    sample_tree = std::unique_ptr<SampleTree>(new SampleTree(&thread_tree, CompareSampleFunction));
+    sample_tree_builder.reset(new TestSampleTreeBuilder(&thread_tree));
   }
 
-  void VisitSampleTree(const std::vector<ExpectedSampleInMap>& expected_samples) {
-    ::VisitSampleTree(sample_tree.get(), expected_samples);
+  void CheckSamples(const std::vector<SampleEntry>& expected_samples) {
+    ::CheckSamples(sample_tree_builder->GetSamples(), expected_samples);
   }
 
   ThreadTree thread_tree;
-  std::unique_ptr<SampleTree> sample_tree;
+  std::unique_ptr<TestSampleTreeBuilder> sample_tree_builder;
 };
 
 TEST_F(SampleTreeTest, ip_in_map) {
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  sample_tree->AddSample(1, 1, 2, 0, 0, false);
-  sample_tree->AddSample(1, 1, 5, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "process1_thread1", 1, 3},
+  sample_tree_builder->AddSample(1, 1, 1, false);
+  sample_tree_builder->AddSample(1, 1, 2, false);
+  sample_tree_builder->AddSample(1, 1, 5, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "process1_thread1", 1, 3),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, different_pid) {
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  sample_tree->AddSample(2, 2, 1, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "process1_thread1", 1, 1}, {2, 2, "p2t2", "process2_thread2", 1, 1},
+  sample_tree_builder->AddSample(1, 1, 1, false);
+  sample_tree_builder->AddSample(2, 2, 1, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "process1_thread1", 1, 1),
+      SampleEntry(2, 2, "p2t2", "process2_thread2", 1, 1),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, different_tid) {
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  sample_tree->AddSample(1, 11, 1, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "process1_thread1", 1, 1}, {1, 11, "p1t11", "process1_thread11", 1, 1},
+  sample_tree_builder->AddSample(1, 1, 1, false);
+  sample_tree_builder->AddSample(1, 11, 1, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "process1_thread1", 1, 1),
+      SampleEntry(1, 11, "p1t11", "process1_thread11", 1, 1),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, different_comm) {
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
+  sample_tree_builder->AddSample(1, 1, 1, false);
   thread_tree.AddThread(1, 1, "p1t1_comm2");
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "process1_thread1", 1, 1}, {1, 1, "p1t1_comm2", "process1_thread1", 1, 1},
+  sample_tree_builder->AddSample(1, 1, 1, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "process1_thread1", 1, 1),
+      SampleEntry(1, 1, "p1t1_comm2", "process1_thread1", 1, 1),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, different_map) {
-  sample_tree->AddSample(1, 1, 1, 0, 0, false);
-  sample_tree->AddSample(1, 1, 6, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "process1_thread1", 1, 1}, {1, 1, "p1t1", "process1_thread1_map2", 6, 1},
+  sample_tree_builder->AddSample(1, 1, 1, false);
+  sample_tree_builder->AddSample(1, 1, 6, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "process1_thread1", 1, 1),
+      SampleEntry(1, 1, "p1t1", "process1_thread1_map2", 6, 1),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, unmapped_sample) {
-  sample_tree->AddSample(1, 1, 0, 0, 0, false);
-  sample_tree->AddSample(1, 1, 31, 0, 0, false);
-  sample_tree->AddSample(1, 1, 70, 0, 0, false);
+  sample_tree_builder->AddSample(1, 1, 0, false);
+  sample_tree_builder->AddSample(1, 1, 31, false);
+  sample_tree_builder->AddSample(1, 1, 70, false);
   // Match the unknown map.
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "unknown", 0, 3},
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "unknown", 0, 3),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST_F(SampleTreeTest, map_kernel) {
-  sample_tree->AddSample(1, 1, 10, 0, 0, true);
-  sample_tree->AddSample(1, 1, 10, 0, 0, false);
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "p1t1", "kernel", 10, 1}, {1, 1, "p1t1", "process1_thread1_map2", 6, 1},
+  sample_tree_builder->AddSample(1, 1, 10, true);
+  sample_tree_builder->AddSample(1, 1, 10, false);
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "p1t1", "kernel", 10, 1),
+      SampleEntry(1, 1, "p1t1", "process1_thread1_map2", 6, 1),
   };
-  VisitSampleTree(expected_samples);
+  CheckSamples(expected_samples);
 }
 
 TEST(sample_tree, overlapped_map) {
   ThreadTree thread_tree;
-  SampleTree sample_tree(&thread_tree, CompareSampleFunction);
+  TestSampleTreeBuilder sample_tree_builder(&thread_tree);
   thread_tree.AddThread(1, 1, "thread1");
   thread_tree.AddThreadMap(1, 1, 1, 10, 0, 0, "map1");  // Add map 1.
-  sample_tree.AddSample(1, 1, 5, 0, 0, false);          // Hit map 1.
+  sample_tree_builder.AddSample(1, 1, 5, false);        // Hit map 1.
   thread_tree.AddThreadMap(1, 1, 5, 20, 0, 0, "map2");  // Add map 2.
-  sample_tree.AddSample(1, 1, 6, 0, 0, false);          // Hit map 2.
-  sample_tree.AddSample(1, 1, 4, 0, 0, false);          // Hit map 1.
+  sample_tree_builder.AddSample(1, 1, 6, false);        // Hit map 2.
+  sample_tree_builder.AddSample(1, 1, 4, false);        // Hit map 1.
   thread_tree.AddThreadMap(1, 1, 2, 7, 0, 0, "map3");   // Add map 3.
-  sample_tree.AddSample(1, 1, 7, 0, 0, false);          // Hit map 3.
-  sample_tree.AddSample(1, 1, 10, 0, 0, false);         // Hit map 2.
-
-  std::vector<ExpectedSampleInMap> expected_samples = {
-      {1, 1, "thread1", "map1", 1, 2},
-      {1, 1, "thread1", "map2", 5, 1},
-      {1, 1, "thread1", "map2", 9, 1},
-      {1, 1, "thread1", "map3", 2, 1},
+  sample_tree_builder.AddSample(1, 1, 7, false);        // Hit map 3.
+  sample_tree_builder.AddSample(1, 1, 10, false);       // Hit map 2.
+
+  std::vector<SampleEntry> expected_samples = {
+      SampleEntry(1, 1, "thread1", "map1", 1, 2),
+      SampleEntry(1, 1, "thread1", "map2", 5, 1),
+      SampleEntry(1, 1, "thread1", "map2", 9, 1),
+      SampleEntry(1, 1, "thread1", "map3", 2, 1),
   };
-  VisitSampleTree(&sample_tree, expected_samples);
+  CheckSamples(sample_tree_builder.GetSamples(), expected_samples);
 }
diff --git a/simpleperf/thread_tree.cpp b/simpleperf/thread_tree.cpp
index daf3ff52..d9714042 100644
--- a/simpleperf/thread_tree.cpp
+++ b/simpleperf/thread_tree.cpp
@@ -185,6 +185,15 @@ const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool
   return result != nullptr ? result : &unknown_map_;
 }
 
+const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip) {
+  MapEntry* result = FindMapByAddr(thread->maps, ip);
+  if (result != nullptr) {
+    return result;
+  }
+  result = FindMapByAddr(kernel_map_tree_, ip);
+  return result != nullptr ? result : &unknown_map_;
+}
+
 const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
   uint64_t vaddr_in_file;
   if (map->dso == kernel_dso_.get()) {
diff --git a/simpleperf/thread_tree.h b/simpleperf/thread_tree.h
index de10138a..6dc7dd7e 100644
--- a/simpleperf/thread_tree.h
+++ b/simpleperf/thread_tree.h
@@ -72,6 +72,8 @@ class ThreadTree {
   void AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
                     uint64_t time, const std::string& filename);
   const MapEntry* FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel);
+  // Find map for an ip address when we don't know whether it is in kernel.
+  const MapEntry* FindMap(const ThreadEntry* thread, uint64_t ip);
   const Symbol* FindSymbol(const MapEntry* map, uint64_t ip);
   const MapEntry* UnknownMap() const {
     return &unknown_map_;