diff --git a/simpleperf/Android.mk b/simpleperf/Android.mk
index b7213d7..d2c5276 100644
--- a/simpleperf/Android.mk
+++ b/simpleperf/Android.mk
@@ -31,6 +31,7 @@
   cmd_help.cpp \
   cmd_list.cpp \
   cmd_record.cpp \
+  cmd_report.cpp \
   cmd_stat.cpp \
   command.cpp \
   environment.cpp \
@@ -41,6 +42,7 @@
   read_elf.cpp \
   record.cpp \
   record_file.cpp \
+  sample_tree.cpp \
   utils.cpp \
   workload.cpp \
 
@@ -102,6 +104,7 @@
   cmd_dumprecord_test.cpp \
   cmd_list_test.cpp \
   cmd_record_test.cpp \
+  cmd_report_test.cpp \
   cmd_stat_test.cpp \
   command_test.cpp \
   cpu_offline_test.cpp \
@@ -109,6 +112,7 @@
   gtest_main.cpp \
   record_file_test.cpp \
   record_test.cpp \
+  sample_tree_test.cpp \
   workload_test.cpp \
 
 include $(CLEAR_VARS)
diff --git a/simpleperf/cmd_dumprecord.cpp b/simpleperf/cmd_dumprecord.cpp
index e4594b6..9245d18 100644
--- a/simpleperf/cmd_dumprecord.cpp
+++ b/simpleperf/cmd_dumprecord.cpp
@@ -185,8 +185,8 @@
       while (p < end) {
         const perf_event_header* header = reinterpret_cast<const perf_event_header*>(p);
         CHECK_LE(p + header->size, end);
-        CHECK_EQ(PERF_RECORD_BUILD_ID, header->type);
         BuildIdRecord record(header);
+        record.header.type = PERF_RECORD_BUILD_ID;  // Set type explicitly as perf doesn't set it.
         record.Dump(1);
         p += header->size;
       }
diff --git a/simpleperf/cmd_report.cpp b/simpleperf/cmd_report.cpp
new file mode 100644
index 0000000..7b41bf7
--- /dev/null
+++ b/simpleperf/cmd_report.cpp
@@ -0,0 +1,295 @@
+/*
+ * 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 <inttypes.h>
+#include <functional>
+#include <map>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/stringprintf.h>
+#include <base/strings.h>
+
+#include "command.h"
+#include "environment.h"
+#include "event_attr.h"
+#include "event_type.h"
+#include "record.h"
+#include "record_file.h"
+#include "sample_tree.h"
+
+typedef int (*compare_sample_entry_t)(const SampleEntry& sample1, const SampleEntry& sample2);
+typedef void (*print_sample_entry_header_t)();
+typedef void (*print_sample_entry_t)(const SampleEntry& sample);
+
+struct ReportItem {
+  compare_sample_entry_t compare_function;
+  print_sample_entry_header_t print_header_function;
+  print_sample_entry_t print_function;
+};
+
+static int ComparePid(const SampleEntry& sample1, const SampleEntry& sample2) {
+  return sample1.process_entry->pid - sample2.process_entry->pid;
+}
+
+static void PrintHeaderPid() {
+  printf("%8s", "Pid");
+}
+
+static void PrintPid(const SampleEntry& sample) {
+  printf("%8d", sample.process_entry->pid);
+}
+
+static ReportItem report_pid_item = {
+    .compare_function = ComparePid,
+    .print_header_function = PrintHeaderPid,
+    .print_function = PrintPid,
+};
+
+static int CompareComm(const SampleEntry& sample1, const SampleEntry& sample2) {
+  return strcmp(sample1.process_entry->comm.c_str(), sample2.process_entry->comm.c_str());
+}
+
+static void PrintHeaderComm() {
+  printf("%20s", "Command");
+}
+
+static void PrintComm(const SampleEntry& sample) {
+  printf("%20s", sample.process_entry->comm.c_str());
+}
+
+static ReportItem report_comm_item = {
+    .compare_function = CompareComm,
+    .print_header_function = PrintHeaderComm,
+    .print_function = PrintComm,
+};
+
+static int CompareDso(const SampleEntry& sample1, const SampleEntry& sample2) {
+  return strcmp(sample1.map_entry->filename.c_str(), sample2.map_entry->filename.c_str());
+}
+
+static void PrintHeaderDso() {
+  printf("%20s", "Shared Object");
+}
+
+static void PrintDso(const SampleEntry& sample) {
+  std::string filename = sample.map_entry->filename;
+  if (filename == DEFAULT_KERNEL_MMAP_NAME) {
+    filename = "[kernel.kallsyms]";
+  } else if (filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP) {
+    filename = "[unknown]";
+  }
+  printf("%20s", filename.c_str());
+}
+
+static ReportItem report_dso_item = {
+    .compare_function = CompareDso,
+    .print_header_function = PrintHeaderDso,
+    .print_function = PrintDso,
+};
+
+static std::unordered_map<std::string, ReportItem*> report_item_map = {
+    {"comm", &report_comm_item}, {"pid", &report_pid_item}, {"dso", &report_dso_item},
+};
+
+class ReportCommand : public Command {
+ public:
+  ReportCommand()
+      : Command("report", "report sampling information in perf.data",
+                "Usage: simpleperf report [options]\n"
+                "    -i <file>     specify path of record file, default is perf.data\n"
+                "    --sort key1,key2,... Select the keys to sort and print the report.\n"
+                "                         Possible keys include pid, comm, dso.\n"
+                "                         Default keys are \"comm,pid,dso\"\n"),
+        record_filename_("perf.data") {
+  }
+
+  bool Run(const std::vector<std::string>& args);
+
+ private:
+  bool ParseOptions(const std::vector<std::string>& args);
+  bool ReadEventAttrFromRecordFile();
+  void ReadSampleTreeFromRecordFile();
+  int CompareSampleEntry(const SampleEntry& sample1, const SampleEntry& sample2);
+  void PrintReport();
+  void PrintReportContext();
+  void PrintReportHeader();
+  void PrintReportEntry(const SampleEntry& sample);
+
+  std::string record_filename_;
+  std::unique_ptr<RecordFileReader> record_file_reader_;
+  perf_event_attr event_attr_;
+  std::vector<ReportItem*> report_items_;
+  std::unique_ptr<SampleTree> sample_tree_;
+};
+
+bool ReportCommand::Run(const std::vector<std::string>& args) {
+  // 1. Parse options.
+  if (!ParseOptions(args)) {
+    return false;
+  }
+
+  // 2. Read record file and build SampleTree.
+  record_file_reader_ = RecordFileReader::CreateInstance(record_filename_);
+  if (record_file_reader_ == nullptr) {
+    return false;
+  }
+  if (!ReadEventAttrFromRecordFile()) {
+    return false;
+  }
+  ReadSampleTreeFromRecordFile();
+
+  // 3. Read symbol table from elf files.
+
+  // 4. Show collected information.
+  PrintReport();
+
+  return true;
+}
+
+bool ReportCommand::ParseOptions(const std::vector<std::string>& args) {
+  for (size_t i = 0; i < args.size(); ++i) {
+    if (args[i] == "-i") {
+      if (!NextArgumentOrError(args, &i)) {
+        return false;
+      }
+      record_filename_ = args[i];
+    } else if (args[i] == "--sort") {
+      if (!NextArgumentOrError(args, &i)) {
+        return false;
+      }
+      std::vector<std::string> sort_keys = android::base::Split(args[i], ",");
+      for (auto& key : sort_keys) {
+        auto it = report_item_map.find(key);
+        if (it != report_item_map.end()) {
+          report_items_.push_back(it->second);
+        } else {
+          LOG(ERROR) << "Unknown sort key: " << key;
+          return false;
+        }
+      }
+    } else {
+      ReportUnknownOption(args, i);
+      return false;
+    }
+  }
+
+  if (report_items_.empty()) {
+    report_items_.push_back(report_item_map["comm"]);
+    report_items_.push_back(report_item_map["pid"]);
+    report_items_.push_back(report_item_map["dso"]);
+  }
+  return true;
+}
+
+bool ReportCommand::ReadEventAttrFromRecordFile() {
+  std::vector<const PerfFileFormat::FileAttr*> attrs = record_file_reader_->AttrSection();
+  if (attrs.size() != 1) {
+    LOG(ERROR) << "record file contains " << attrs.size() << " attrs";
+    return false;
+  }
+  event_attr_ = attrs[0]->attr;
+  return true;
+}
+
+void ReportCommand::ReadSampleTreeFromRecordFile() {
+  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(compare_sample_callback));
+  sample_tree_->AddProcess(0, "swapper");
+
+  std::vector<std::unique_ptr<const Record>> records = record_file_reader_->DataSection();
+  for (auto& record : records) {
+    if (record->header.type == PERF_RECORD_MMAP) {
+      const MmapRecord& r = *static_cast<const MmapRecord*>(record.get());
+      if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
+        sample_tree_->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff,
+                                   r.sample_id.time_data.time, r.filename);
+      } else {
+        sample_tree_->AddUserMap(r.data.pid, r.data.addr, r.data.len, r.data.pgoff,
+                                 r.sample_id.time_data.time, r.filename);
+      }
+    } else if (record->header.type == PERF_RECORD_SAMPLE) {
+      const SampleRecord& r = *static_cast<const SampleRecord*>(record.get());
+      sample_tree_->AddSample(r.tid_data.pid, r.tid_data.tid, r.ip_data.ip, r.time_data.time,
+                              r.period_data.period);
+    } else if (record->header.type == PERF_RECORD_COMM) {
+      const CommRecord& r = *static_cast<const CommRecord*>(record.get());
+      sample_tree_->AddProcess(r.data.pid, r.comm);
+    }
+  }
+}
+
+int ReportCommand::CompareSampleEntry(const SampleEntry& sample1, const SampleEntry& sample2) {
+  for (auto& item : report_items_) {
+    int result = item->compare_function(sample1, sample2);
+    if (result != 0) {
+      return result;
+    }
+  }
+  return 0;
+}
+
+void ReportCommand::PrintReport() {
+  PrintReportContext();
+  PrintReportHeader();
+  sample_tree_->VisitAllSamples(
+      std::bind(&ReportCommand::PrintReportEntry, this, std::placeholders::_1));
+  fflush(stdout);
+}
+
+void ReportCommand::PrintReportContext() {
+  const EventType* event_type =
+      EventTypeFactory::FindEventTypeByConfig(event_attr_.type, event_attr_.config);
+  std::string event_type_name;
+  if (event_type != nullptr) {
+    event_type_name = event_type->name;
+  } else {
+    event_type_name =
+        android::base::StringPrintf("(type %u, config %llu)", event_attr_.type, event_attr_.config);
+  }
+  printf("Samples: %" PRIu64 " of event '%s'\n", sample_tree_->TotalSamples(),
+         event_type_name.c_str());
+  printf("Event count: %" PRIu64 "\n\n", sample_tree_->TotalPeriod());
+}
+
+void ReportCommand::PrintReportHeader() {
+  printf("%8s", "Overhead");
+  for (ReportItem* item : report_items_) {
+    printf(" ");
+    item->print_header_function();
+  }
+  printf("\n");
+}
+
+void ReportCommand::PrintReportEntry(const SampleEntry& sample) {
+  double percentage = 0.0;
+  if (sample_tree_->TotalPeriod() != 0) {
+    percentage = 100.0 * sample.period / sample_tree_->TotalPeriod();
+  }
+  printf("%7.2lf%%", percentage);
+  for (ReportItem* item : report_items_) {
+    printf(" ");
+    item->print_function(sample);
+  }
+  printf("\n");
+}
+
+__attribute__((constructor)) static void RegisterReportCommand() {
+  RegisterCommand("report", [] { return std::unique_ptr<Command>(new ReportCommand()); });
+}
diff --git a/simpleperf/cmd_report_test.cpp b/simpleperf/cmd_report_test.cpp
new file mode 100644
index 0000000..34d156c
--- /dev/null
+++ b/simpleperf/cmd_report_test.cpp
@@ -0,0 +1,51 @@
+/*
+ * 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 <gtest/gtest.h>
+
+#include "command.h"
+
+static std::unique_ptr<Command> RecordCmd() {
+  return CreateCommandInstance("record");
+}
+
+static std::unique_ptr<Command> ReportCmd() {
+  return CreateCommandInstance("report");
+}
+
+class ReportCommandTest : public ::testing::Test {
+ protected:
+  static void SetUpTestCase() {
+    ASSERT_TRUE(RecordCmd()->Run({"-a", "sleep", "1"}));
+    ASSERT_TRUE(RecordCmd()->Run({"-a", "-o", "perf2.data", "sleep", "1"}));
+  }
+};
+
+TEST_F(ReportCommandTest, no_options) {
+  ASSERT_TRUE(ReportCmd()->Run({}));
+}
+
+TEST_F(ReportCommandTest, input_file_option) {
+  ASSERT_TRUE(ReportCmd()->Run({"-i", "perf2.data"}));
+}
+
+TEST_F(ReportCommandTest, sort_option_pid) {
+  ASSERT_TRUE(ReportCmd()->Run({"--sort", "pid"}));
+}
+
+TEST_F(ReportCommandTest, sort_option_all) {
+  ASSERT_TRUE(ReportCmd()->Run({"--sort", "comm,pid,dso"}));
+}
diff --git a/simpleperf/event_attr.cpp b/simpleperf/event_attr.cpp
index 79ed4b8..5e02215 100644
--- a/simpleperf/event_attr.cpp
+++ b/simpleperf/event_attr.cpp
@@ -100,7 +100,7 @@
     event_name = event_type->name;
   }
 
-  PrintIndented(indent, "event_attr: for event %s\n", event_name.c_str());
+  PrintIndented(indent, "event_attr: for event type %s\n", event_name.c_str());
 
   PrintIndented(indent + 1, "type %u, size %u, config %llu\n", attr.type, attr.size, attr.config);
 
diff --git a/simpleperf/sample_tree.cpp b/simpleperf/sample_tree.cpp
new file mode 100644
index 0000000..9c792f2
--- /dev/null
+++ b/simpleperf/sample_tree.cpp
@@ -0,0 +1,154 @@
+/*
+ * 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 <base/logging.h>
+
+bool SampleTree::MapComparator::operator()(const MapEntry& map1, const MapEntry& map2) {
+  if (map1.pid != map2.pid) {
+    return map1.pid < map2.pid;
+  }
+  if (map1.start_addr != map2.start_addr) {
+    return map1.start_addr < map2.start_addr;
+  }
+  if (map1.len != map2.len) {
+    return map1.len < map2.len;
+  }
+  if (map1.time != map2.time) {
+    return map1.time < map2.time;
+  }
+  return false;
+}
+
+void SampleTree::AddProcess(int pid, const std::string& comm) {
+  ProcessEntry process = {
+      .pid = pid, .comm = comm,
+  };
+  process_tree_[pid] = process;
+}
+
+void SampleTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
+                              const std::string& filename) {
+  MapEntry map = {
+      .pid = -1,
+      .start_addr = start_addr,
+      .len = len,
+      .pgoff = pgoff,
+      .time = time,
+      .filename = filename,
+  };
+  kernel_map_tree_.insert(map);
+}
+
+void SampleTree::AddUserMap(int pid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
+                            uint64_t time, const std::string& filename) {
+  MapEntry map = {
+      .pid = pid,
+      .start_addr = start_addr,
+      .len = len,
+      .pgoff = pgoff,
+      .time = time,
+      .filename = filename,
+  };
+  user_map_tree_.insert(map);
+}
+
+const ProcessEntry* SampleTree::FindProcessEntryOrNew(int pid) {
+  auto it = process_tree_.find(pid);
+  if (it == process_tree_.end()) {
+    ProcessEntry new_entry = {
+        .pid = pid, .comm = "unknown",
+    };
+    auto pair = process_tree_.insert(std::make_pair(pid, new_entry));
+    it = pair.first;
+  }
+  return &it->second;
+}
+
+static bool IsIpInMap(int pid, uint64_t ip, const MapEntry& map) {
+  return (pid == map.pid && map.start_addr <= ip && map.start_addr + map.len > ip);
+}
+
+const MapEntry* SampleTree::FindMapEntryOrNew(int pid, uint64_t ip) {
+  // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
+  MapEntry find_map = {
+      .pid = pid,
+      .start_addr = ip,
+      .len = static_cast<uint64_t>(-1),
+      .time = static_cast<uint64_t>(-1),
+  };
+  auto it = user_map_tree_.upper_bound(find_map);
+  if (it != user_map_tree_.begin() && IsIpInMap(pid, ip, *--it)) {
+    return &*it;
+  }
+  find_map.pid = -1;
+  it = kernel_map_tree_.upper_bound(find_map);
+  if (it != kernel_map_tree_.begin() && IsIpInMap(-1, ip, *--it)) {
+    return &*it;
+  }
+  auto unknown_it = unknown_maps_.find(pid);
+  if (unknown_it == unknown_maps_.end()) {
+    MapEntry unknown_map = {
+        .pid = pid,
+        .start_addr = 0,
+        .len = static_cast<uint64_t>(-1),
+        .pgoff = 0,
+        .time = 0,
+        .filename = "unknown",
+    };
+    auto pair = unknown_maps_.insert(std::make_pair(pid, unknown_map));
+    unknown_it = pair.first;
+  }
+  return &unknown_it->second;
+}
+
+void SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period) {
+  const ProcessEntry* process_entry = FindProcessEntryOrNew(pid);
+  const MapEntry* map_entry = FindMapEntryOrNew(pid, ip);
+
+  SampleEntry find_sample = {
+      .tid = tid,
+      .ip = ip,
+      .time = time,
+      .period = period,
+      .sample_count = 1,
+      .process_entry = process_entry,
+      .map_entry = map_entry,
+  };
+  auto it = sample_tree_.find(find_sample);
+  if (it == sample_tree_.end()) {
+    sample_tree_.insert(find_sample);
+  } else {
+    SampleEntry* sample_entry = const_cast<SampleEntry*>(&*it);
+    sample_entry->period += period;
+    sample_entry->sample_count++;
+  }
+  total_samples_++;
+  total_period_ += 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_) {
+      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
new file mode 100644
index 0000000..ba144ba
--- /dev/null
+++ b/simpleperf/sample_tree.h
@@ -0,0 +1,125 @@
+/*
+ * 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.
+ */
+
+#ifndef SIMPLE_PERF_SAMPLE_TREE_H_
+#define SIMPLE_PERF_SAMPLE_TREE_H_
+
+#include <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+struct ProcessEntry {
+  int pid;
+  std::string comm;
+};
+
+struct MapEntry {
+  int pid;  // pid = -1 for kernel map entries.
+  uint64_t start_addr;
+  uint64_t len;
+  uint64_t pgoff;
+  uint64_t time;  // Map creation time.
+  std::string filename;
+};
+
+struct SampleEntry {
+  int tid;
+  uint64_t ip;
+  uint64_t time;
+  uint64_t period;
+  uint64_t sample_count;
+  const ProcessEntry* process_entry;
+  const MapEntry* map_entry;
+};
+
+typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t;
+
+class SampleTree {
+ public:
+  SampleTree(compare_sample_func_t sample_compare_function)
+      : sample_comparator_(sample_compare_function),
+        sample_tree_(sample_comparator_),
+        sorted_sample_comparator_(sample_compare_function),
+        sorted_sample_tree_(sorted_sample_comparator_),
+        total_samples_(0),
+        total_period_(0) {
+  }
+
+  void AddProcess(int pid, const std::string& comm);
+  void AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
+                    const std::string& filename);
+  void AddUserMap(int pid, uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
+                  const std::string& filename);
+  void AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period);
+  void VisitAllSamples(std::function<void(const SampleEntry&)> callback);
+
+  uint64_t TotalSamples() const {
+    return total_samples_;
+  }
+
+  uint64_t TotalPeriod() const {
+    return total_period_;
+  }
+
+ private:
+  const ProcessEntry* FindProcessEntryOrNew(int pid);
+  const MapEntry* FindMapEntryOrNew(int pid, uint64_t ip);
+
+  struct MapComparator {
+    bool operator()(const MapEntry& map1, const MapEntry& map2);
+  };
+
+  struct SampleComparator {
+    bool operator()(const SampleEntry& sample1, const SampleEntry& sample2) {
+      return compare_function(sample1, sample2) < 0;
+    }
+    SampleComparator(compare_sample_func_t compare_function) : compare_function(compare_function) {
+    }
+
+    compare_sample_func_t compare_function;
+  };
+
+  struct SortedSampleComparator {
+    bool operator()(const SampleEntry& sample1, const SampleEntry& sample2) {
+      if (sample1.period != sample2.period) {
+        return sample1.period > sample2.period;
+      }
+      return compare_function(sample1, sample2) < 0;
+    }
+    SortedSampleComparator(compare_sample_func_t compare_function)
+        : compare_function(compare_function) {
+    }
+
+    compare_sample_func_t compare_function;
+  };
+
+  std::unordered_map<int, ProcessEntry> process_tree_;
+
+  std::set<MapEntry, MapComparator> kernel_map_tree_;
+  std::set<MapEntry, MapComparator> user_map_tree_;
+  std::unordered_map<int, MapEntry> unknown_maps_;
+
+  SampleComparator sample_comparator_;
+  std::set<SampleEntry, SampleComparator> sample_tree_;
+  SortedSampleComparator sorted_sample_comparator_;
+  std::set<SampleEntry, SortedSampleComparator> sorted_sample_tree_;
+
+  uint64_t total_samples_;
+  uint64_t total_period_;
+};
+
+#endif  // SIMPLE_PERF_SAMPLE_TREE_H_
diff --git a/simpleperf/sample_tree_test.cpp b/simpleperf/sample_tree_test.cpp
new file mode 100644
index 0000000..09a7a2c
--- /dev/null
+++ b/simpleperf/sample_tree_test.cpp
@@ -0,0 +1,142 @@
+/*
+ * 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 <gtest/gtest.h>
+
+struct ExpectedSampleInMap {
+  int pid;
+  int tid;
+  int map_pid;
+  uint64_t map_start_addr;
+  size_t sample_count;
+};
+
+static void SampleMatchExpectation(const SampleEntry& sample, const ExpectedSampleInMap& expected,
+                                   bool* has_error) {
+  *has_error = true;
+  ASSERT_TRUE(sample.process_entry != nullptr);
+  ASSERT_EQ(expected.pid, sample.process_entry->pid);
+  ASSERT_EQ(expected.tid, sample.tid);
+  ASSERT_TRUE(sample.map_entry != nullptr);
+  ASSERT_EQ(expected.map_pid, sample.map_entry->pid);
+  ASSERT_EQ(expected.map_start_addr, sample.map_entry->start_addr);
+  ASSERT_EQ(expected.sample_count, sample.sample_count);
+  *has_error = false;
+}
+
+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;
+}
+
+static int CompareSampleFunction(const SampleEntry& sample1, const SampleEntry& sample2) {
+  if (sample1.process_entry->pid != sample2.process_entry->pid) {
+    return sample1.process_entry->pid - sample2.process_entry->pid;
+  }
+  if (sample1.tid != sample2.tid) {
+    return sample1.tid - sample2.tid;
+  }
+  if (sample1.map_entry->pid != sample2.map_entry->pid) {
+    return sample1.map_entry->pid - sample2.map_entry->pid;
+  }
+  if (sample1.map_entry->start_addr != sample2.map_entry->start_addr) {
+    return sample1.map_entry->start_addr - sample2.map_entry->start_addr;
+  }
+  return 0;
+}
+
+class SampleTreeTest : public testing::Test {
+ protected:
+  virtual void SetUp() {
+    sample_tree = std::unique_ptr<SampleTree>(new SampleTree(CompareSampleFunction));
+    sample_tree->AddUserMap(1, 1, 10, 0, 0, "");
+    sample_tree->AddUserMap(1, 11, 10, 0, 0, "");
+    sample_tree->AddUserMap(2, 1, 20, 0, 0, "");
+    sample_tree->AddKernelMap(11, 20, 0, 0, "");
+  }
+
+  void VisitSampleTree(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);
+  }
+
+  std::unique_ptr<SampleTree> sample_tree;
+};
+
+TEST_F(SampleTreeTest, ip_in_map) {
+  sample_tree->AddSample(1, 1, 1, 0, 0);
+  sample_tree->AddSample(1, 1, 5, 0, 0);
+  sample_tree->AddSample(1, 1, 10, 0, 0);
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 1, 3},
+  };
+  VisitSampleTree(expected_samples);
+}
+
+TEST_F(SampleTreeTest, different_pid) {
+  sample_tree->AddSample(1, 1, 1, 0, 0);
+  sample_tree->AddSample(2, 2, 1, 0, 0);
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 1, 1}, {2, 2, 2, 1, 1},
+  };
+  VisitSampleTree(expected_samples);
+}
+
+TEST_F(SampleTreeTest, different_tid) {
+  sample_tree->AddSample(1, 1, 1, 0, 0);
+  sample_tree->AddSample(1, 11, 1, 0, 0);
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 1, 1}, {1, 11, 1, 1, 1},
+  };
+  VisitSampleTree(expected_samples);
+}
+
+TEST_F(SampleTreeTest, different_map) {
+  sample_tree->AddSample(1, 1, 1, 0, 0);
+  sample_tree->AddSample(1, 1, 11, 0, 0);
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 1, 1}, {1, 1, 1, 11, 1},
+  };
+  VisitSampleTree(expected_samples);
+}
+
+TEST_F(SampleTreeTest, unmapped_sample) {
+  sample_tree->AddSample(1, 1, 0, 0, 0);
+  sample_tree->AddSample(1, 1, 31, 0, 0);
+  sample_tree->AddSample(1, 1, 70, 0, 0);
+  // Match the unknown map.
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, 1, 0, 3},
+  };
+  VisitSampleTree(expected_samples);
+}
+
+TEST_F(SampleTreeTest, map_kernel) {
+  sample_tree->AddSample(1, 1, 11, 0, 0);
+  sample_tree->AddSample(1, 1, 21, 0, 0);
+  std::vector<ExpectedSampleInMap> expected_samples = {
+      {1, 1, -1, 11, 1}, {1, 1, 1, 11, 1},
+  };
+  VisitSampleTree(expected_samples);
+}