diff options
Diffstat (limited to 'targets_affinity.cc')
-rw-r--r-- | targets_affinity.cc | 108 |
1 files changed, 108 insertions, 0 deletions
diff --git a/targets_affinity.cc b/targets_affinity.cc new file mode 100644 index 0000000..11903a9 --- /dev/null +++ b/targets_affinity.cc @@ -0,0 +1,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/logging.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::vector<offset_t>& old_targets, + const std::vector<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 |