1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "components/zucchini/target_pool.h"
6
7 #include <algorithm>
8 #include <iterator>
9 #include <utility>
10
11 #include "base/check.h"
12 #include "components/zucchini/algorithm.h"
13 #include "components/zucchini/equivalence_map.h"
14
15 namespace zucchini {
16
17 TargetPool::TargetPool() = default;
18
TargetPool(std::deque<offset_t> && targets)19 TargetPool::TargetPool(std::deque<offset_t>&& targets) {
20 DCHECK(targets_.empty());
21 DCHECK(std::is_sorted(targets.begin(), targets.end()));
22 targets_ = std::move(targets);
23 }
24
25 TargetPool::TargetPool(TargetPool&&) = default;
26 TargetPool::TargetPool(const TargetPool&) = default;
27 TargetPool::~TargetPool() = default;
28
InsertTargets(const std::vector<offset_t> & targets)29 void TargetPool::InsertTargets(const std::vector<offset_t>& targets) {
30 std::copy(targets.begin(), targets.end(), std::back_inserter(targets_));
31 SortAndUniquify(&targets_);
32 }
33
InsertTargets(TargetSource * targets)34 void TargetPool::InsertTargets(TargetSource* targets) {
35 for (auto target = targets->GetNext(); target.has_value();
36 target = targets->GetNext()) {
37 targets_.push_back(*target);
38 }
39 // InsertTargets() can be called many times (number of reference types for the
40 // pool) in succession. Calling SortAndUniquify() every time enables deduping
41 // to occur more often. This prioritizes peak memory reduction over running
42 // time.
43 SortAndUniquify(&targets_);
44 }
45
InsertTargets(const std::vector<Reference> & references)46 void TargetPool::InsertTargets(const std::vector<Reference>& references) {
47 // This can be called many times, so it's better to let std::back_inserter()
48 // manage |targets_| resize, instead of manually reserving space.
49 std::transform(references.begin(), references.end(),
50 std::back_inserter(targets_),
51 [](const Reference& ref) { return ref.target; });
52 SortAndUniquify(&targets_);
53 }
54
InsertTargets(ReferenceReader && references)55 void TargetPool::InsertTargets(ReferenceReader&& references) {
56 for (auto ref = references.GetNext(); ref.has_value();
57 ref = references.GetNext()) {
58 targets_.push_back(ref->target);
59 }
60 SortAndUniquify(&targets_);
61 }
62
KeyForOffset(offset_t offset) const63 key_t TargetPool::KeyForOffset(offset_t offset) const {
64 auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
65 DCHECK(pos != targets_.end() && *pos == offset);
66 return static_cast<offset_t>(pos - targets_.begin());
67 }
68
KeyForNearestOffset(offset_t offset) const69 key_t TargetPool::KeyForNearestOffset(offset_t offset) const {
70 auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
71 if (pos != targets_.begin()) {
72 // If distances are equal, prefer lower key.
73 if (pos == targets_.end() || *pos - offset >= offset - pos[-1])
74 --pos;
75 }
76 return static_cast<offset_t>(pos - targets_.begin());
77 }
78
FilterAndProject(const OffsetMapper & offset_mapper)79 void TargetPool::FilterAndProject(const OffsetMapper& offset_mapper) {
80 offset_mapper.ForwardProjectAll(&targets_);
81 std::sort(targets_.begin(), targets_.end());
82 }
83
84 } // namespace zucchini
85