1 // Copyright 2016 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/targets_affinity.h"
6
7 #include <algorithm>
8
9 #include "base/check_op.h"
10 #include "components/zucchini/equivalence_map.h"
11
12 namespace zucchini {
13
14 namespace {
15
16 constexpr uint32_t kNoLabel = 0;
17 }
18
19 TargetsAffinity::TargetsAffinity() = default;
20 TargetsAffinity::~TargetsAffinity() = default;
21
InferFromSimilarities(const EquivalenceMap & equivalences,const std::deque<offset_t> & old_targets,const std::deque<offset_t> & new_targets)22 void TargetsAffinity::InferFromSimilarities(
23 const EquivalenceMap& equivalences,
24 const std::deque<offset_t>& old_targets,
25 const std::deque<offset_t>& new_targets) {
26 forward_association_.assign(old_targets.size(), {});
27 backward_association_.assign(new_targets.size(), {});
28
29 if (old_targets.empty() || new_targets.empty())
30 return;
31
32 key_t new_key = 0;
33 for (auto candidate : equivalences) { // Sorted by |dst_offset|.
34 DCHECK_GT(candidate.similarity, 0.0);
35 while (new_key < new_targets.size() &&
36 new_targets[new_key] < candidate.eq.dst_offset) {
37 ++new_key;
38 }
39
40 // Visit each new target covered by |candidate.eq| and find / update its
41 // associated old target.
42 for (; new_key < new_targets.size() &&
43 new_targets[new_key] < candidate.eq.dst_end();
44 ++new_key) {
45 if (backward_association_[new_key].affinity >= candidate.similarity)
46 continue;
47
48 DCHECK_GE(new_targets[new_key], candidate.eq.dst_offset);
49 offset_t old_target = new_targets[new_key] - candidate.eq.dst_offset +
50 candidate.eq.src_offset;
51 auto old_it =
52 std::lower_bound(old_targets.begin(), old_targets.end(), old_target);
53 // If new target can be mapped via |candidate.eq| to an old target, then
54 // attempt to associate them. Multiple new targets can compete for the
55 // same old target. The heuristic here makes selections to maximize
56 // |candidate.similarity|, and if a tie occurs, minimize new target offset
57 // (by first-come, first-served).
58 if (old_it != old_targets.end() && *old_it == old_target) {
59 key_t old_key = static_cast<key_t>(old_it - old_targets.begin());
60 if (candidate.similarity > forward_association_[old_key].affinity) {
61 // Reset other associations.
62 if (forward_association_[old_key].affinity > 0.0)
63 backward_association_[forward_association_[old_key].other] = {};
64 if (backward_association_[new_key].affinity > 0.0)
65 forward_association_[backward_association_[new_key].other] = {};
66 // Assign new association.
67 forward_association_[old_key] = {new_key, candidate.similarity};
68 backward_association_[new_key] = {old_key, candidate.similarity};
69 }
70 }
71 }
72 }
73 }
74
AssignLabels(double min_affinity,std::vector<uint32_t> * old_labels,std::vector<uint32_t> * new_labels)75 uint32_t TargetsAffinity::AssignLabels(double min_affinity,
76 std::vector<uint32_t>* old_labels,
77 std::vector<uint32_t>* new_labels) {
78 old_labels->assign(forward_association_.size(), kNoLabel);
79 new_labels->assign(backward_association_.size(), kNoLabel);
80
81 uint32_t label = kNoLabel + 1;
82 for (key_t old_key = 0; old_key < forward_association_.size(); ++old_key) {
83 Association association = forward_association_[old_key];
84 if (association.affinity >= min_affinity) {
85 (*old_labels)[old_key] = label;
86 DCHECK_EQ(0U, (*new_labels)[association.other]);
87 (*new_labels)[association.other] = label;
88 ++label;
89 }
90 }
91 return label;
92 }
93
AffinityBetween(key_t old_key,key_t new_key) const94 double TargetsAffinity::AffinityBetween(key_t old_key, key_t new_key) const {
95 DCHECK_LT(old_key, forward_association_.size());
96 DCHECK_LT(new_key, backward_association_.size());
97 if (forward_association_[old_key].affinity > 0.0 &&
98 forward_association_[old_key].other == new_key) {
99 DCHECK_EQ(backward_association_[new_key].other, old_key);
100 DCHECK_EQ(forward_association_[old_key].affinity,
101 backward_association_[new_key].affinity);
102 return forward_association_[old_key].affinity;
103 }
104 return -std::max(forward_association_[old_key].affinity,
105 backward_association_[new_key].affinity);
106 }
107
108 } // namespace zucchini
109