Home | History | Annotate | Download | only in perfprofd 
      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