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>
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;
31     AggregatedSymbol(const SymType& sym, const ValType& offset) : symbol(sym) {
32       offsets.insert(offset);
33     }
34   };
35 
36  public:
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 
103   typename RangeMapType::const_iterator begin() const {
104     return map_.begin();
105   }
106   typename RangeMapType::const_iterator end() const {
107     return map_.end();
108   }
109 
110   bool empty() const {
111     return map_.empty();
112   }
113 
114  private:
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