target_pool.cc 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
  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. #include "components/zucchini/target_pool.h"
  5. #include <algorithm>
  6. #include <iterator>
  7. #include <utility>
  8. #include "base/check.h"
  9. #include "components/zucchini/algorithm.h"
  10. #include "components/zucchini/equivalence_map.h"
  11. namespace zucchini {
  12. TargetPool::TargetPool() = default;
  13. TargetPool::TargetPool(std::deque<offset_t>&& targets) {
  14. DCHECK(targets_.empty());
  15. DCHECK(std::is_sorted(targets.begin(), targets.end()));
  16. targets_ = std::move(targets);
  17. }
  18. TargetPool::TargetPool(TargetPool&&) = default;
  19. TargetPool::TargetPool(const TargetPool&) = default;
  20. TargetPool::~TargetPool() = default;
  21. void TargetPool::InsertTargets(const std::vector<offset_t>& targets) {
  22. std::copy(targets.begin(), targets.end(), std::back_inserter(targets_));
  23. SortAndUniquify(&targets_);
  24. }
  25. void TargetPool::InsertTargets(TargetSource* targets) {
  26. for (auto target = targets->GetNext(); target.has_value();
  27. target = targets->GetNext()) {
  28. targets_.push_back(*target);
  29. }
  30. // InsertTargets() can be called many times (number of reference types for the
  31. // pool) in succession. Calling SortAndUniquify() every time enables deduping
  32. // to occur more often. This prioritizes peak memory reduction over running
  33. // time.
  34. SortAndUniquify(&targets_);
  35. }
  36. void TargetPool::InsertTargets(const std::vector<Reference>& references) {
  37. // This can be called many times, so it's better to let std::back_inserter()
  38. // manage |targets_| resize, instead of manually reserving space.
  39. std::transform(references.begin(), references.end(),
  40. std::back_inserter(targets_),
  41. [](const Reference& ref) { return ref.target; });
  42. SortAndUniquify(&targets_);
  43. }
  44. void TargetPool::InsertTargets(ReferenceReader&& references) {
  45. for (auto ref = references.GetNext(); ref.has_value();
  46. ref = references.GetNext()) {
  47. targets_.push_back(ref->target);
  48. }
  49. SortAndUniquify(&targets_);
  50. }
  51. key_t TargetPool::KeyForOffset(offset_t offset) const {
  52. auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
  53. DCHECK(pos != targets_.end() && *pos == offset);
  54. return static_cast<offset_t>(pos - targets_.begin());
  55. }
  56. key_t TargetPool::KeyForNearestOffset(offset_t offset) const {
  57. auto pos = std::lower_bound(targets_.begin(), targets_.end(), offset);
  58. if (pos != targets_.begin()) {
  59. // If distances are equal, prefer lower key.
  60. if (pos == targets_.end() || *pos - offset >= offset - pos[-1])
  61. --pos;
  62. }
  63. return static_cast<offset_t>(pos - targets_.begin());
  64. }
  65. void TargetPool::FilterAndProject(const OffsetMapper& offset_mapper) {
  66. offset_mapper.ForwardProjectAll(&targets_);
  67. std::sort(targets_.begin(), targets_.end());
  68. }
  69. } // namespace zucchini