OLD | NEW |
(Empty) | |
| 1 // Copyright 2015 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 "courgette/label_manager.h" |
| 6 |
| 7 #include <algorithm> |
| 8 |
| 9 #include "base/logging.h" |
| 10 #include "base/numerics/safe_math.h" |
| 11 #include "courgette/consecutive_range_visitor.h" |
| 12 |
| 13 namespace courgette { |
| 14 |
| 15 LabelManager::RvaVisitor::~RvaVisitor() {} |
| 16 |
| 17 LabelManager::LabelManager() {} |
| 18 |
| 19 LabelManager::~LabelManager() {} |
| 20 |
| 21 // We wish to minimize peak memory usage here. Analysis: Let |
| 22 // m = number of (RVA) elements in |rva_visitor|, |
| 23 // n = number of distinct (RVA) elements in |rva_visitor|. |
| 24 // The final storage is n * sizeof(Label) bytes. During computation we uniquify |
| 25 // m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using |
| 26 // std::map or std::unordered_map would consume additionally 32 * n bytes. |
| 27 // Meanwhile, our std::vector implementation consumes additionally 4 * m bytes |
| 28 // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of |
| 29 // extra contiguous memory during computation. Assuming memory fragmentation |
| 30 // would not be an issue, this is much better than using std::map. |
| 31 void LabelManager::Read(RvaVisitor* rva_visitor) { |
| 32 // Write all values in |rva_visitor| to |rvas|. |
| 33 size_t num_rva = rva_visitor->Remaining(); |
| 34 std::vector<RVA> rvas(num_rva); |
| 35 for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next()) |
| 36 rvas[i] = rva_visitor->Get(); |
| 37 |
| 38 // Sort |rvas|, then count the number of distinct values. |
| 39 using CRV = ConsecutiveRangeVisitor<std::vector<RVA>::iterator>; |
| 40 std::sort(rvas.begin(), rvas.end()); |
| 41 size_t num_distinct_rva = 0; |
| 42 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) |
| 43 ++num_distinct_rva; |
| 44 |
| 45 // Reserve space for |labels_|, populate with sorted RVA and repeats. |
| 46 DCHECK(labels_.empty()); |
| 47 labels_.reserve(num_distinct_rva); |
| 48 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) { |
| 49 labels_.push_back(Label(*it.cur())); |
| 50 base::CheckedNumeric<uint32> count = it.repeat(); |
| 51 labels_.back().count_ = count.ValueOrDie(); |
| 52 } |
| 53 } |
| 54 |
| 55 void LabelManager::RemoveUnderusedLabels(int32 count_threshold) { |
| 56 if (count_threshold <= 0) |
| 57 return; |
| 58 labels_.erase(std::remove_if(labels_.begin(), labels_.end(), |
| 59 [count_threshold](const Label& label) { |
| 60 return label.count_ < count_threshold; |
| 61 }), |
| 62 labels_.end()); |
| 63 // Not shrinking |labels_|, since this may cause reallocation. |
| 64 } |
| 65 |
| 66 // Uses binary search to find |rva|. |
| 67 Label* LabelManager::Find(RVA rva) { |
| 68 auto it = std::lower_bound( |
| 69 labels_.begin(), labels_.end(), Label(rva), |
| 70 [](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; }); |
| 71 return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it); |
| 72 } |
| 73 |
| 74 } // namespace courgette |
OLD | NEW |