1 /*
2 * Copyright (c) 2016, Google Inc.
3 * All rights reserved.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #ifndef PERFTOOLS_INTERVALMAP_H_
9 #define PERFTOOLS_INTERVALMAP_H_
10
11 #include <cstdlib>
12 #include <iostream>
13 #include <iterator>
14 #include <map>
15 #include <sstream>
16
17 #include "int_compat.h"
18
19 namespace perftools {
20
21 template <class V>
22 class IntervalMap {
23 public:
24 IntervalMap();
25
26 // Set [start, limit) to value. If this interval overlaps one currently in the
27 // map, the overlapping section will be overwritten by the new interval.
28 void Set(uint64 start, uint64 limit, const V& value);
29
30 // Finds the value associated with the interval containing key. Returns false
31 // if no interval contains key.
32 bool Lookup(uint64 key, V* value) const;
33
34 // Find the interval containing key, or the next interval containing
35 // something greater than key. Returns false if one is not found, otherwise
36 // it sets start, limit, and value to the corresponding values from the
37 // interval.
38 bool FindNext(uint64 key, uint64* start, uint64* limit, V* value) const;
39
40 // Remove all entries from the map.
41 void Clear();
42
43 // Clears everything in the interval map from [clear_start,
44 // clear_limit). This may cut off sections or entire intervals in
45 // the map. This will invalidate iterators to intervals which have a
46 // start value residing in [clear_start, clear_limit).
47 void ClearInterval(uint64 clear_start, uint64 clear_limit);
48
49 uint64 Size() const;
50
51 private:
52 struct Value {
53 uint64 limit;
54 V value;
55 };
56
57 using MapIter = typename std::map<uint64, Value>::iterator;
58 using ConstMapIter = typename std::map<uint64, Value>::const_iterator;
59
60 // For an interval to be valid, start must be strictly less than limit.
61 void AssertValidInterval(uint64 start, uint64 limit) const;
62
63 // Returns an iterator pointing to the interval containing the given key, or
64 // end() if one was not found.
GetContainingInterval(uint64 point)65 ConstMapIter GetContainingInterval(uint64 point) const {
66 auto bound = interval_start_.upper_bound(point);
67 if (!Decrement(&bound)) {
68 return interval_start_.end();
69 }
70 if (bound->second.limit <= point) {
71 return interval_start_.end();
72 }
73 return bound;
74 }
75
GetContainingInterval(uint64 point)76 MapIter GetContainingInterval(uint64 point) {
77 auto bound = interval_start_.upper_bound(point);
78 if (!Decrement(&bound)) {
79 return interval_start_.end();
80 }
81 if (bound->second.limit <= point) {
82 return interval_start_.end();
83 }
84 return bound;
85 }
86
87 // Decrements the provided iterator to interval_start_, or returns false if
88 // iter == begin().
89 bool Decrement(ConstMapIter* iter) const;
90 bool Decrement(MapIter* iter);
91
92 // Removes everything in the interval map from [remove_start,
93 // remove_limit). This may cut off sections or entire intervals in
94 // the map. This will invalidate iterators to intervals which have a
95 // start value residing in [remove_start, remove_limit).
96 void RemoveInterval(uint64 remove_start, uint64 remove_limit);
97
98 void Insert(uint64 start, uint64 limit, const V& value);
99
100 // Split an interval into two intervals, [iter.start, point) and
101 // [point, iter.limit). If point is not within (iter.start, point) or iter is
102 // end(), it is a noop.
103 void SplitInterval(MapIter iter, uint64 point);
104
105 // Map from the start of the interval to the limit of the interval and the
106 // corresponding value.
107 std::map<uint64, Value> interval_start_;
108 };
109
110 template <class V>
IntervalMap()111 IntervalMap<V>::IntervalMap() {}
112
113 template <class V>
Set(uint64 start,uint64 limit,const V & value)114 void IntervalMap<V>::Set(uint64 start, uint64 limit, const V& value) {
115 AssertValidInterval(start, limit);
116 RemoveInterval(start, limit);
117 Insert(start, limit, value);
118 }
119
120 template <class V>
Lookup(uint64 key,V * value)121 bool IntervalMap<V>::Lookup(uint64 key, V* value) const {
122 const auto contain = GetContainingInterval(key);
123 if (contain == interval_start_.end()) {
124 return false;
125 }
126 *value = contain->second.value;
127 return true;
128 }
129
130 template <class V>
FindNext(uint64 key,uint64 * start,uint64 * limit,V * value)131 bool IntervalMap<V>::FindNext(uint64 key, uint64* start, uint64* limit,
132 V* value) const {
133 auto iter = interval_start_.upper_bound(key);
134 if (iter == interval_start_.end()) {
135 return false;
136 }
137 *start = iter->first;
138 *limit = iter->second.limit;
139 *value = iter->second.value;
140 return true;
141 }
142
143 template <class V>
Clear()144 void IntervalMap<V>::Clear() {
145 interval_start_.clear();
146 }
147
148 template <class V>
ClearInterval(uint64 clear_start,uint64 clear_limit)149 void IntervalMap<V>::ClearInterval(uint64 clear_start, uint64 clear_limit) {
150 AssertValidInterval(clear_start, clear_limit);
151 RemoveInterval(clear_start, clear_limit);
152 }
153
154 template <class V>
Size()155 uint64 IntervalMap<V>::Size() const {
156 return interval_start_.size();
157 }
158
159 template <class V>
RemoveInterval(uint64 remove_start,uint64 remove_limit)160 void IntervalMap<V>::RemoveInterval(uint64 remove_start, uint64 remove_limit) {
161 if (remove_start >= remove_limit) {
162 return;
163 }
164 // It starts by splitting intervals that will only be partly cleared into two,
165 // where one of those will be fully cleared and the other will not be cleared.
166 SplitInterval(GetContainingInterval(remove_limit), remove_limit);
167 SplitInterval(GetContainingInterval(remove_start), remove_start);
168
169 auto remove_interval_start = interval_start_.lower_bound(remove_start);
170 auto remove_interval_end = interval_start_.lower_bound(remove_limit);
171 // Note that if there are no intervals to be cleared, then
172 // clear_interval_start == clear_interval_end and the erase will be a noop.
173 interval_start_.erase(remove_interval_start, remove_interval_end);
174 }
175
176 template <class V>
SplitInterval(MapIter iter,uint64 point)177 void IntervalMap<V>::SplitInterval(MapIter iter, uint64 point) {
178 if (iter == interval_start_.end() || point <= iter->first ||
179 point >= iter->second.limit) {
180 return;
181 }
182 const auto larger_limit = iter->second.limit;
183 iter->second.limit = point;
184 Insert(point, larger_limit, iter->second.value);
185 }
186
187 template <class V>
Decrement(ConstMapIter * iter)188 bool IntervalMap<V>::Decrement(ConstMapIter* iter) const {
189 if ((*iter) == interval_start_.begin()) {
190 return false;
191 }
192 --(*iter);
193 return true;
194 }
195
196 template <class V>
Decrement(MapIter * iter)197 bool IntervalMap<V>::Decrement(MapIter* iter) {
198 if ((*iter) == interval_start_.begin()) {
199 return false;
200 }
201 --(*iter);
202 return true;
203 }
204
205 template <class V>
Insert(uint64 start,uint64 limit,const V & value)206 void IntervalMap<V>::Insert(uint64 start, uint64 limit, const V& value) {
207 interval_start_.emplace(std::pair<uint64, Value>{start, {limit, value}});
208 }
209
210 template <class V>
AssertValidInterval(uint64 start,uint64 limit)211 void IntervalMap<V>::AssertValidInterval(uint64 start, uint64 limit) const {
212 if (start >= limit) {
213 std::cerr << "Invalid interval. Start may not be >= limit." << std::endl
214 << "Start: " << start << std::endl
215 << "Limit: " << limit << std::endl;
216 abort();
217 }
218 }
219
220 } // namespace perftools
221
222 #endif // PERFTOOLS_INTERVALMAP_H_
223