[Courgette] Initial Implementation of LabelManager.

courgette/label_manager_unittest.cc

Index: courgette/label_manager_unittest.cc
diff --git a/courgette/label_manager_unittest.cc b/courgette/label_manager_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..bc19aa9d9f94e99f16eac278fc8419cde8268643
--- /dev/null
+++ b/courgette/label_manager_unittest.cc
@@ -0,0 +1,144 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "courgette/label_manager.h"
+
+#include <iterator>
+#include <map>
+#include <utility>
+#include <vector>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace courgette {
+
+namespace {
+
+// Test version of LabelManager: Expose data to test implementation.
+class TestLabelManager : public LabelManager {
+ public:
+  const size_t LabelCount() const { return labels_.size(); };
+};
+
+void CheckLabelManagerContent(TestLabelManager* label_manager,
+                              const std::map<RVA, size_t>& expected) {
+  EXPECT_EQ(expected.size(), label_manager->LabelCount());
+  for (auto rva_and_count : expected) {

[grt (UTC plus 2), 2015/12/04 19:33:41]

const auto& rva_and_count

[huangs, 2015/12/04 20:01:13]

Done.

+    Label* label = label_manager->Find(rva_and_count.first);
+    EXPECT_TRUE(label != nullptr);
+    EXPECT_EQ(rva_and_count.first, label->rva_);
+    EXPECT_EQ(rva_and_count.second, label->count_);
+  }
+}
+
+}  // namespace
+
+// Test version of RvaVisitor: Just wrap std::vector<RVA>.
+class TestRvaVisitor : public LabelManager::RvaVisitor {
+ public:
+  explicit TestRvaVisitor(const std::vector<RVA>& rva_list)
+      : rva_list_(rva_list), it_(rva_list.begin()) {}
+
+  ~TestRvaVisitor() override {}
+
+  size_t Remaining() const override {
+    return std::distance(it_, rva_list_.end());
+  }
+
+  RVA Get() const override{ return *it_; }

[grt (UTC plus 2), 2015/12/04 19:33:41]

nit: space after "override"

[huangs, 2015/12/04 20:01:13]

Done.

+
+  void Next() override { ++it_; }
+
+ private:
+  const std::vector<RVA>& rva_list_;

[grt (UTC plus 2), 2015/12/04 19:33:41]

holding a ref to an external object is a bit dangerous. how about taking the
begin/end pair of iterators in the ctor?

[huangs, 2015/12/04 20:01:13]

Done.

+  std::vector<RVA>::const_iterator it_;
+};
+
+TEST(LabelManagerTest, Basic) {
+  const RVA test_targets_raw[] = {

[grt (UTC plus 2), 2015/12/04 19:33:41]

static const RVA kTestTargetsRaw[]

[huangs, 2015/12/04 20:01:13]

Done, also applied below.

+    0x04000010,
+    0x04000030,
+    0x04000020,
+    0x04000010,  // Redundant
+    0xFEEDF00D,
+    0x04000030,  // Redundant
+    0xFEEDF00D,  // Redundant
+    0x00000110,
+    0x04000010,  // Redundant
+    0xABCD1234
+  };
+  std::vector<RVA> test_targets(std::begin(test_targets_raw),
+                                std::end(test_targets_raw));
+  TestRvaVisitor visitor(test_targets);
+
+  // Preallocate targets, then populate.
+  TestLabelManager label_manager;
+  label_manager.Read(&visitor);
+
+  const std::pair<RVA, size_t> expected1_raw[] = {
+    {0x00000110, 1U},
+    {0x04000010, 3U},
+    {0x04000020, 1U},
+    {0x04000030, 2U},
+    {0xABCD1234, 1U},
+    {0xFEEDF00D, 2U}
+  };
+  std::map<RVA, size_t> expected1(std::begin(expected1_raw),
+                                  std::end(expected1_raw));
+
+  CheckLabelManagerContent(&label_manager, expected1);
+
+  // Expect to *not* find labels for various RVAs that were never added.
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x00000000)));
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x0400000F)));
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x04000011)));
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x5F3759DF)));
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFEEDFFF0)));
+  EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFFFFFFFF)));
+
+  // Remove Labels with |count_| < 2.
+  label_manager.RemoveUnderusedLabels(2U);
+  const std::pair<RVA, size_t> expected2_raw[] = {
+    {0x04000010, 3U},
+    {0x04000030, 2U},
+    {0xFEEDF00D, 2U}
+  };
+  std::map<RVA, size_t> expected2(std::begin(expected2_raw),
+                                  std::end(expected2_raw));
+  CheckLabelManagerContent(&label_manager, expected2);
+}
+
+TEST(LabelManagerTest, Single) {
+  const RVA kRva = 12U;
+  for (int dup = 1; dup < 8; ++dup) {
+    // Test data: |dup| copies of kRva.
+    std::vector<RVA> test_targets(dup, kRva);
+    TestRvaVisitor visitor(test_targets);
+    TestLabelManager label_manager;
+    label_manager.Read(&visitor);
+    EXPECT_EQ(1U, label_manager.LabelCount());  // Deduped to 1 Label.
+
+    Label* label = label_manager.Find(kRva);
+    EXPECT_NE(nullptr, label);
+    EXPECT_EQ(kRva, label->rva_);
+    EXPECT_EQ(dup, label->count_);
+
+    for (RVA rva = 0U; rva < 16U; ++rva) {
+      if (rva != kRva)
+        EXPECT_EQ(nullptr, label_manager.Find(rva));
+    }
+  }
+}
+
+TEST(LabelManagerTest, Empty) {
+  std::vector<RVA> empty_test_targets;
+  TestRvaVisitor visitor(empty_test_targets);
+  TestLabelManager label_manager;
+  label_manager.Read(&visitor);
+  EXPECT_EQ(0U, label_manager.LabelCount());
+  for (RVA rva = 0U; rva < 16U; ++rva)
+    EXPECT_EQ(nullptr, label_manager.Find(rva));
+}
+
+}  // namespace courgette