1 #ifndef SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
2 #define SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
3
4 #include <map>
5 #include <set>
6
7 #include <android-base/logging.h>
8
9 namespace android {
10 namespace perfprofd {
11
12 template <typename T, typename U>
GetLeqIterator(T & map,U key)13 decltype(static_cast<T*>(nullptr)->begin()) GetLeqIterator(T& map, U key) {
14 if (map.empty()) {
15 return map.end();
16 }
17 auto it = map.upper_bound(key);
18 if (it == map.begin()) {
19 return map.end();
20 }
21 --it;
22 return it;
23 }
24
25 template <typename SymType, typename ValType>
26 class RangeMap {
27 public:
28 struct AggregatedSymbol {
29 SymType symbol;
30 std::set<ValType> offsets;
AggregatedSymbolAggregatedSymbol31 AggregatedSymbol(const SymType& sym, const ValType& offset) : symbol(sym) {
32 offsets.insert(offset);
33 }
34 };
35
36 public:
Insert(const SymType & sym,const ValType & val)37 void Insert(const SymType& sym, const ValType& val) {
38 auto aggr_it = GetLeqIterator(map_, val);
39 if (aggr_it == map_.end()) {
40 // Maybe we need to extend the first one.
41 if (!map_.empty()) {
42 AggregatedSymbol& first = map_.begin()->second;
43 CHECK_LT(val, map_.begin()->first);
44 if (first.symbol == sym) {
45 ExtendLeft(map_.begin(), val);
46 return;
47 }
48 }
49 // Nope, new entry needed.
50 map_.emplace(val, AggregatedSymbol(sym, val));
51 return;
52 }
53
54 AggregatedSymbol& maybe_match = aggr_it->second;
55
56 if (maybe_match.symbol == sym) {
57 // Same symbol, just insert. This is true for overlap as well as extension.
58 maybe_match.offsets.insert(val);
59 return;
60 }
61
62 // Is there overlap?
63 if (*maybe_match.offsets.rbegin() < val) {
64 // No. See if it can be merged with the next one.
65 ++aggr_it;
66 if (aggr_it != map_.end() && aggr_it->second.symbol == sym) {
67 ExtendLeft(aggr_it, val);
68 return;
69 }
70
71 // Just add a new symbol entry.
72 map_.emplace(val, AggregatedSymbol(sym, val));
73 return;
74 }
75
76 // OK, we have an overlapping non-symbol-equal AggregatedSymbol. Need to break
77 // things up.
78 AggregatedSymbol left(maybe_match.symbol, *maybe_match.offsets.begin());
79 auto offset_it = maybe_match.offsets.begin();
80 for (; *offset_it < val; ++offset_it) {
81 left.offsets.insert(*offset_it);
82 }
83
84 if (*offset_it == val) {
85 // This should not happen.
86 LOG(ERROR) << "Unexpected overlap!";
87 return;
88 }
89
90 AggregatedSymbol right(maybe_match.symbol, *offset_it);
91 for (; offset_it != maybe_match.offsets.end(); ++offset_it) {
92 right.offsets.insert(*offset_it);
93 }
94
95 map_.erase(aggr_it);
96 map_.emplace(*left.offsets.begin(), std::move(left));
97 map_.emplace(val, AggregatedSymbol(sym, val));
98 map_.emplace(*right.offsets.begin(), std::move(right));
99 }
100
101 using RangeMapType = std::map<ValType, AggregatedSymbol>;
102
begin()103 typename RangeMapType::const_iterator begin() const {
104 return map_.begin();
105 }
end()106 typename RangeMapType::const_iterator end() const {
107 return map_.end();
108 }
109
empty()110 bool empty() const {
111 return map_.empty();
112 }
113
114 private:
ExtendLeft(typename RangeMapType::iterator it,const ValType & val)115 void ExtendLeft(typename RangeMapType::iterator it, const ValType& val) {
116 CHECK(val < *it->second.offsets.begin());
117 AggregatedSymbol copy = std::move(it->second);
118 map_.erase(it);
119 copy.offsets.insert(val);
120 map_.emplace(val, std::move(copy));
121 }
122
123 RangeMapType map_;
124 };
125
126 } // namespace perfprofd
127 } // namespace android
128
129 #endif // SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
130