perfprofd/map_utils.h

#ifndef SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_
#define SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_

#include <map>
#include <set>

#include <android-base/logging.h>

namespace android {
namespace perfprofd {

template <typename T, typename U>
decltype(static_cast<T*>(nullptr)->begin()) GetLeqIterator(T& map, U key) {
  if (map.empty()) {
    return map.end();
  }
  auto it = map.upper_bound(key);
  if (it == map.begin()) {
    return map.end();
  }
  --it;
  return it;
}

template <typename SymType, typename ValType>
class RangeMap {
 public:
  struct AggregatedSymbol {
    SymType symbol;
    std::set<ValType> offsets;
    AggregatedSymbol(const SymType& sym, const ValType& offset) : symbol(sym) {
      offsets.insert(offset);
    }
  };

 public:
  void Insert(const SymType& sym, const ValType& val) {
    auto aggr_it = GetLeqIterator(map_, val);
    if (aggr_it == map_.end()) {
      // Maybe we need to extend the first one.
      if (!map_.empty()) {
        AggregatedSymbol& first = map_.begin()->second;
        CHECK_LT(val, map_.begin()->first);
        if (first.symbol == sym) {
          ExtendLeft(map_.begin(), val);
          return;
        }
      }
      // Nope, new entry needed.
      map_.emplace(val, AggregatedSymbol(sym, val));
      return;
    }

    AggregatedSymbol& maybe_match = aggr_it->second;

    if (maybe_match.symbol == sym) {
      // Same symbol, just insert. This is true for overlap as well as extension.
      maybe_match.offsets.insert(val);
      return;
    }

    // Is there overlap?
    if (*maybe_match.offsets.rbegin() < val) {
      // No. See if it can be merged with the next one.
      ++aggr_it;
      if (aggr_it != map_.end() && aggr_it->second.symbol == sym) {
        ExtendLeft(aggr_it, val);
        return;
      }

      // Just add a new symbol entry.
      map_.emplace(val, AggregatedSymbol(sym, val));
      return;
    }

    // OK, we have an overlapping non-symbol-equal AggregatedSymbol. Need to break
    // things up.
    AggregatedSymbol left(maybe_match.symbol, *maybe_match.offsets.begin());
    auto offset_it = maybe_match.offsets.begin();
    for (; *offset_it < val; ++offset_it) {
      left.offsets.insert(*offset_it);
    }

    if (*offset_it == val) {
      // This should not happen.
      LOG(ERROR) << "Unexpected overlap!";
      return;
    }

    AggregatedSymbol right(maybe_match.symbol, *offset_it);
    for (; offset_it != maybe_match.offsets.end(); ++offset_it) {
      right.offsets.insert(*offset_it);
    }

    map_.erase(aggr_it);
    map_.emplace(*left.offsets.begin(), std::move(left));
    map_.emplace(val, AggregatedSymbol(sym, val));
    map_.emplace(*right.offsets.begin(), std::move(right));
  }

  using RangeMapType = std::map<ValType, AggregatedSymbol>;

  typename RangeMapType::const_iterator begin() const {
    return map_.begin();
  }
  typename RangeMapType::const_iterator end() const {
    return map_.end();
  }

  bool empty() const {
    return map_.empty();
  }

 private:
  void ExtendLeft(typename RangeMapType::iterator it, const ValType& val) {
    CHECK(val < *it->second.offsets.begin());
    AggregatedSymbol copy = std::move(it->second);
    map_.erase(it);
    copy.offsets.insert(val);
    map_.emplace(val, std::move(copy));
  }

  RangeMapType map_;
};

}  // namespace perfprofd
}  // namespace android

#endif  // SYSTEM_EXTRAS_PERFPROFD_MAP_UTILS_H_