| /* |
| * 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_ |