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 namespace { | |
15 | |
16 bool CompareLabelByRva(const Label& label1, const Label& label2) { | |
17 return label1.rva_ < label2.rva_; | |
18 } | |
19 | |
20 bool LabelHasZeroCount(const Label& label) { | |
21 return label.count_ == 0; | |
22 } | |
23 | |
24 } // namespace | |
25 | |
26 LabelManager::RvaVisitor::~RvaVisitor() { } | |
27 | |
28 LabelManager::LabelManager() { } | |
29 | |
30 LabelManager::~LabelManager() { } | |
31 | |
32 // We wish to minimize peak memory usage here. Analysis: Let | |
33 // m = number of (RVA) elements in |rva_visitor|, | |
34 // n = number of distinct (RVA) elements in |rva_visitor|. | |
35 // The final storage is n * sizeof(Label) bytes. During computation we uniquify | |
36 // m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using | |
37 // std::map or std::unordered_map would consume additionally 32 * n bytes. | |
38 // Meanwhile, our std::vector implementation consumes additionally 4 * m bytes | |
39 // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of | |
40 // extra contiguous memory during computation. Assuming memory fragmentation | |
41 // would not be an issue, this is much better than using std::map. | |
42 void LabelManager::Read(RvaVisitor* rva_visitor) { | |
43 // Write all values in |rva_visitor| to |rvas|. | |
44 size_t num_rva = rva_visitor->Remaining(); | |
45 std::vector<RVA> rvas(num_rva); | |
46 for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next()) | |
47 rvas[i] = rva_visitor->Get(); | |
48 | |
49 // Sort |rvas|, then count the number of distinct values. | |
50 typedef ConsecutiveRangeVisitor<std::vector<RVA>::iterator> CRV; | |
grt (UTC plus 2)
2015/12/02 19:03:41
nit:
using CRV = ConsecutiveRangeVisitor<std::ve
huangs
2015/12/02 20:51:02
Done.
| |
51 std::sort(rvas.begin(), rvas.end()); | |
52 size_t num_distinct_rva = 0; | |
53 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) | |
54 ++num_distinct_rva; | |
55 | |
56 // Reserve space for |labels_|, populate with sorted RVA and repeats. | |
57 DCHECK(labels_.empty()); | |
grt (UTC plus 2)
2015/12/02 19:03:40
have you tried using a std::deque rather than a st
huangs
2015/12/02 20:51:02
Per discussion, the std::vector implementation is
| |
58 labels_.reserve(num_distinct_rva); | |
59 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) { | |
60 labels_.push_back(Label(*it.cur())); | |
61 labels_.back().count_ = it.repeat(); | |
62 } | |
63 } | |
64 | |
65 void LabelManager::RemoveUnderusedLabels(int count_threshold) { | |
66 Label marker; | |
grt (UTC plus 2)
2015/12/02 19:03:40
unused
huangs
2015/12/02 20:51:02
Removed.
| |
67 if (count_threshold <= 0) | |
68 return; | |
69 for (Label& label : labels_) { | |
70 if (label.count_ < count_threshold) | |
71 label.count_ = 0; // Use this as marker for removal. | |
72 } | |
73 auto it = std::remove_if(labels_.begin(), labels_.end(), LabelHasZeroCount); | |
grt (UTC plus 2)
2015/12/02 19:03:40
lambda:
[](const Label& l) { return l.count_ == 0;
huangs
2015/12/02 20:51:02
Woot! Done.
| |
74 if (it != labels_.end()) { | |
75 labels_.erase(it, labels_.end()); | |
76 // Not calling labels_.shrink_to_fit(), since this may cause reallocation. | |
grt (UTC plus 2)
2015/12/02 19:03:41
shrink_to_fit can't be used in any case since it h
huangs
2015/12/02 20:51:02
Done, making comment more generic.
| |
77 } | |
78 } | |
79 | |
80 // Uses binary search to find |rva|. | |
81 Label* LabelManager::Find(RVA rva) { | |
82 auto it = std::lower_bound(labels_.begin(), labels_.end(), Label(rva), | |
83 CompareLabelByRva); | |
grt (UTC plus 2)
2015/12/02 19:03:41
this is a perfect use of a lambda:
[](const Label&
huangs
2015/12/02 20:51:02
Done.
| |
84 return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it); | |
85 } | |
86 | |
87 } // namespace courgette | |
OLD | NEW |