targets_affinity.cc 4.1 KB

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