1 files changed, 84 insertions, 0 deletions
diff --git a/target_pool.cc b/target_pool.cc
new file mode 100644
index 0000000..0c1e0a5
--- /dev/null
+++ b/target_pool.cc
@@ -0,0 +1,84 @@
+// Copyright 2017 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 "components/zucchini/target_pool.h"
+
+#include <algorithm>
+#include <iterator>
+#include <utility>
+
+#include "base/logging.h"
+#include "components/zucchini/algorithm.h"
+#include "components/zucchini/equivalence_map.h"
+
+namespace zucchini {
+
+TargetPool::TargetPool() = default;
+
+TargetPool::TargetPool(std::vector<offset_t>&& targets) {
+  DCHECK(targets_.empty());
+  DCHECK(std::is_sorted(targets.begin(), targets.end()));
+  targets_ = std::move(targets);
+}
+
+TargetPool::TargetPool(TargetPool&&) = default;
+TargetPool::TargetPool(const TargetPool&) = default;
+TargetPool::~TargetPool() = default;
+
+void TargetPool::InsertTargets(const std::vector<offset_t>& targets) {
+  std::copy(targets.begin(), targets.end(), std::back_inserter(targets_));
+  SortAndUniquify(&targets_);
+}
+
+void TargetPool::InsertTargets(TargetSource* targets) {
+  for (auto target = targets->GetNext(); target.has_value();
+       target = targets->GetNext()) {
+    targets_.push_back(*target);
+  }
+  // InsertTargets() can be called many times (number of reference types for the
+  // pool) in succession. Calling SortAndUniquify() every time enables deduping
+  // to occur more often. This prioritizes peak memory reduction over running
+  // time.
+  SortAndUniquify(&targets_);
+}
+
+void TargetPool::InsertTargets(const std::vector<Reference>& references) {
+  // This can be called many times, so it's better to let std::back_inserter()
+  // manage |targets_| resize, instead of manually reserving space.
+  std::transform(references.begin(), references.end(),
+                 std::back_inserter(targets_),
+                 [](const Reference& ref) { return ref.target; });
+  SortAndUniquify(&targets_);
+}
+
+void TargetPool::InsertTargets(ReferenceReader&& references) {
+  for (auto ref = references.GetNext(); ref.has_value();
+       ref = references.GetNext()) {
+    targets_.push_back(ref->target);
+  }
+  SortAndUniquify(&targets_);
+}
+
+key_t TargetPool::KeyForOffset(offset_t offset) const {
+  auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
+  DCHECK(pos != targets_.end() && *pos == offset);
+  return static_cast<offset_t>(pos - targets_.begin());
+}
+
+key_t TargetPool::KeyForNearestOffset(offset_t offset) const {
+  auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
+  if (pos != targets_.begin()) {
+    // If distances are equal, prefer lower key.
+    if (pos == targets_.end() || *pos - offset >= offset - pos[-1])
+      --pos;
+  }
+  return static_cast<offset_t>(pos - targets_.begin());
+}
+
+void TargetPool::FilterAndProject(const OffsetMapper& offset_mapper) {
+  offset_mapper.ForwardProjectAll(&targets_);
+  std::sort(targets_.begin(), targets_.end());
+}
+
+}  // namespace zucchini