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 "courgette/consecutive_range_visitor.h" | |
11 | |
12 namespace courgette { | |
13 | |
14 LabelManager::RvaVisitor::~RvaVisitor() { } | |
15 | |
16 LabelManager::LabelManager() { } | |
17 | |
18 LabelManager::~LabelManager() { } | |
19 | |
20 // We wish to minimize peak memory usage here. Analysis: Let | |
21 // m = number of (RVA) elements in |rva_visitor|, | |
22 // n = number of distinct (RVA) elements in |rva_visitor|. | |
23 // The final storage is n * sizeof(Label) bytes. During computation we uniquify | |
24 // m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using | |
25 // std::map or std::unordered_map would consume additionally 32 * n bytes. | |
26 // Meanwhile, our std::vector implementation consumes additionally 4 * m bytes | |
27 // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of | |
28 // extra contiguous memory during computation. Assuming memory fragmentation | |
29 // would not be an issue, this is much better than using std::map. | |
30 void LabelManager::Read(RvaVisitor* rva_visitor) { | |
31 // Write all values in |rva_visitor| to |rvas|. | |
32 size_t num_rva = rva_visitor->Remaining(); | |
33 std::vector<RVA> rvas(num_rva); | |
34 for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next()) | |
35 rvas[i] = rva_visitor->Get(); | |
36 | |
37 // Sort |rvas|, then count the number of distinct values. | |
38 using CRV = ConsecutiveRangeVisitor<std::vector<RVA>::iterator>; | |
39 std::sort(rvas.begin(), rvas.end()); | |
40 size_t num_distinct_rva = 0; | |
41 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) | |
42 ++num_distinct_rva; | |
43 | |
44 // Reserve space for |labels_|, populate with sorted RVA and repeats. | |
45 DCHECK(labels_.empty()); | |
46 labels_.reserve(num_distinct_rva); | |
47 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) { | |
48 labels_.push_back(Label(*it.cur())); | |
49 labels_.back().count_ = it.repeat(); | |
50 } | |
51 } | |
52 | |
53 void LabelManager::RemoveUnderusedLabels(int count_threshold) { | |
54 if (count_threshold <= 0) | |
55 return; | |
56 for (Label& label : labels_) { | |
57 if (label.count_ < count_threshold) | |
58 label.count_ = 0; // Use this as marker for removal. | |
59 } | |
60 labels_.erase(std::remove_if(labels_.begin(), | |
61 labels_.end(), | |
62 [](const Label& l) { return l.count_ == 0; }), | |
grt (UTC plus 2)
2015/12/03 15:19:09
can you do the mark-n-remove in one pass like so:
huangs
2015/12/03 19:29:06
Ah nice! Using temp variable for the lambda.
grt (UTC plus 2)
2015/12/04 19:33:41
i think keeping the lambda inline is closer to wha
huangs
2015/12/04 21:25:36
Oops missed this. Ran "git cl format", too.
| |
63 labels_.end()); | |
64 // Not shrinking |labels_|, since this may cause reallocation. | |
65 } | |
66 | |
67 // Uses binary search to find |rva|. | |
68 Label* LabelManager::Find(RVA rva) { | |
69 auto it = std::lower_bound(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 |