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