src/intervalmap.h

/*
 * Copyright (c) 2016, Google Inc.
 * All rights reserved.
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef PERFTOOLS_INTERVALMAP_H_
#define PERFTOOLS_INTERVALMAP_H_

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>

#include "int_compat.h"

namespace perftools {

template <class V>
class IntervalMap {
 public:
  IntervalMap();

  // Set [start, limit) to value. If this interval overlaps one currently in the
  // map, the overlapping section will be overwritten by the new interval.
  void Set(uint64 start, uint64 limit, const V& value);

  // Finds the value associated with the interval containing key. Returns false
  // if no interval contains key.
  bool Lookup(uint64 key, V* value) const;

  // Find the interval containing key, or the next interval containing
  // something greater than key. Returns false if one is not found, otherwise
  // it sets start, limit, and value to the corresponding values from the
  // interval.
  bool FindNext(uint64 key, uint64* start, uint64* limit, V* value) const;

  // Remove all entries from the map.
  void Clear();

  // Clears everything in the interval map from [clear_start,
  // clear_limit). This may cut off sections or entire intervals in
  // the map. This will invalidate iterators to intervals which have a
  // start value residing in [clear_start, clear_limit).
  void ClearInterval(uint64 clear_start, uint64 clear_limit);

  uint64 Size() const;

 private:
  struct Value {
    uint64 limit;
    V value;
  };

  using MapIter = typename std::map<uint64, Value>::iterator;
  using ConstMapIter = typename std::map<uint64, Value>::const_iterator;

  // For an interval to be valid, start must be strictly less than limit.
  void AssertValidInterval(uint64 start, uint64 limit) const;

  // Returns an iterator pointing to the interval containing the given key, or
  // end() if one was not found.
  ConstMapIter GetContainingInterval(uint64 point) const {
    auto bound = interval_start_.upper_bound(point);
    if (!Decrement(&bound)) {
      return interval_start_.end();
    }
    if (bound->second.limit <= point) {
      return interval_start_.end();
    }
    return bound;
  }

  MapIter GetContainingInterval(uint64 point) {
    auto bound = interval_start_.upper_bound(point);
    if (!Decrement(&bound)) {
      return interval_start_.end();
    }
    if (bound->second.limit <= point) {
      return interval_start_.end();
    }
    return bound;
  }

  // Decrements the provided iterator to interval_start_, or returns false if
  // iter == begin().
  bool Decrement(ConstMapIter* iter) const;
  bool Decrement(MapIter* iter);

  // Removes everything in the interval map from [remove_start,
  // remove_limit). This may cut off sections or entire intervals in
  // the map. This will invalidate iterators to intervals which have a
  // start value residing in [remove_start, remove_limit).
  void RemoveInterval(uint64 remove_start, uint64 remove_limit);

  void Insert(uint64 start, uint64 limit, const V& value);

  // Split an interval into two intervals, [iter.start, point) and
  // [point, iter.limit). If point is not within (iter.start, point) or iter is
  // end(), it is a noop.
  void SplitInterval(MapIter iter, uint64 point);

  // Map from the start of the interval to the limit of the interval and the
  // corresponding value.
  std::map<uint64, Value> interval_start_;
};

template <class V>
IntervalMap<V>::IntervalMap() {}

template <class V>
void IntervalMap<V>::Set(uint64 start, uint64 limit, const V& value) {
  AssertValidInterval(start, limit);
  RemoveInterval(start, limit);
  Insert(start, limit, value);
}

template <class V>
bool IntervalMap<V>::Lookup(uint64 key, V* value) const {
  const auto contain = GetContainingInterval(key);
  if (contain == interval_start_.end()) {
    return false;
  }
  *value = contain->second.value;
  return true;
}

template <class V>
bool IntervalMap<V>::FindNext(uint64 key, uint64* start, uint64* limit,
                              V* value) const {
  auto iter = interval_start_.upper_bound(key);
  if (iter == interval_start_.end()) {
    return false;
  }
  *start = iter->first;
  *limit = iter->second.limit;
  *value = iter->second.value;
  return true;
}

template <class V>
void IntervalMap<V>::Clear() {
  interval_start_.clear();
}

template <class V>
void IntervalMap<V>::ClearInterval(uint64 clear_start, uint64 clear_limit) {
  AssertValidInterval(clear_start, clear_limit);
  RemoveInterval(clear_start, clear_limit);
}

template <class V>
uint64 IntervalMap<V>::Size() const {
  return interval_start_.size();
}

template <class V>
void IntervalMap<V>::RemoveInterval(uint64 remove_start, uint64 remove_limit) {
  if (remove_start >= remove_limit) {
    return;
  }
  // It starts by splitting intervals that will only be partly cleared into two,
  // where one of those will be fully cleared and the other will not be cleared.
  SplitInterval(GetContainingInterval(remove_limit), remove_limit);
  SplitInterval(GetContainingInterval(remove_start), remove_start);

  auto remove_interval_start = interval_start_.lower_bound(remove_start);
  auto remove_interval_end = interval_start_.lower_bound(remove_limit);
  // Note that if there are no intervals to be cleared, then
  // clear_interval_start == clear_interval_end and the erase will be a noop.
  interval_start_.erase(remove_interval_start, remove_interval_end);
}

template <class V>
void IntervalMap<V>::SplitInterval(MapIter iter, uint64 point) {
  if (iter == interval_start_.end() || point <= iter->first ||
      point >= iter->second.limit) {
    return;
  }
  const auto larger_limit = iter->second.limit;
  iter->second.limit = point;
  Insert(point, larger_limit, iter->second.value);
}

template <class V>
bool IntervalMap<V>::Decrement(ConstMapIter* iter) const {
  if ((*iter) == interval_start_.begin()) {
    return false;
  }
  --(*iter);
  return true;
}

template <class V>
bool IntervalMap<V>::Decrement(MapIter* iter) {
  if ((*iter) == interval_start_.begin()) {
    return false;
  }
  --(*iter);
  return true;
}

template <class V>
void IntervalMap<V>::Insert(uint64 start, uint64 limit, const V& value) {
  interval_start_.emplace(std::pair<uint64, Value>{start, {limit, value}});
}

template <class V>
void IntervalMap<V>::AssertValidInterval(uint64 start, uint64 limit) const {
  if (start >= limit) {
    std::cerr << "Invalid interval. Start may not be >= limit." << std::endl
              << "Start: " << start << std::endl
              << "Limit: " << limit << std::endl;
    abort();
  }
}

}  // namespace perftools

#endif  // PERFTOOLS_INTERVALMAP_H_