blob: b183aaac45ee7df1c0240a7af24ec0a323c9cf31 [file] [log] [blame]
Raul Silvera0c3c35e2016-09-21 13:14:55 -07001/*
2 * Copyright (c) 2016, Google Inc.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google Inc. nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL Google Inc. BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28#ifndef PERFTOOLS_INTERVALMAP_H_
29#define PERFTOOLS_INTERVALMAP_H_
30
31#include <cstdlib>
32#include <iostream>
33#include <iterator>
34#include <map>
35#include <sstream>
36
37#include "int_compat.h"
38
39namespace perftools {
40
41template <class V>
42class IntervalMap {
43 public:
44 IntervalMap();
45
46 // Set [start, limit) to value. If this interval overlaps one currently in the
47 // map, the overlapping section will be overwritten by the new interval.
Alexey Alexandrove18bc452016-11-04 14:55:48 -070048 void Set(uint64 start, uint64 limit, const V& value);
Raul Silvera0c3c35e2016-09-21 13:14:55 -070049
50 // Finds the value associated with the interval containing key. Returns false
51 // if no interval contains key.
Alexey Alexandrove18bc452016-11-04 14:55:48 -070052 bool Lookup(uint64 key, V* value) const;
Raul Silvera0c3c35e2016-09-21 13:14:55 -070053
54 // Find the interval containing key, or the next interval containing
55 // something greater than key. Returns false if one is not found, otherwise
56 // it sets start, limit, and value to the corresponding values from the
57 // interval.
Alexey Alexandrove18bc452016-11-04 14:55:48 -070058 bool FindNext(uint64 key, uint64* start, uint64* limit, V* value) const;
Raul Silvera0c3c35e2016-09-21 13:14:55 -070059
60 // Remove all entries from the map.
61 void Clear();
62
Alexey Alexandrove18bc452016-11-04 14:55:48 -070063 // Clears everything in the interval map from [clear_start,
64 // clear_limit). This may cut off sections or entire intervals in
65 // the map. This will invalidate iterators to intervals which have a
66 // start value residing in [clear_start, clear_limit).
67 void ClearInterval(uint64 clear_start, uint64 clear_limit);
68
Raul Silvera0c3c35e2016-09-21 13:14:55 -070069 uint64 Size() const;
70
71 private:
72 struct Value {
73 uint64 limit;
74 V value;
75 };
76
77 using MapIter = typename std::map<uint64, Value>::iterator;
78 using ConstMapIter = typename std::map<uint64, Value>::const_iterator;
79
80 // For an interval to be valid, start must be strictly less than limit.
81 void AssertValidInterval(uint64 start, uint64 limit) const;
82
83 // Returns an iterator pointing to the interval containing the given key, or
84 // end() if one was not found.
85 ConstMapIter GetContainingInterval(uint64 point) const {
86 auto bound = interval_start_.upper_bound(point);
87 if (!Decrement(&bound)) {
88 return interval_start_.end();
89 }
90 if (bound->second.limit <= point) {
91 return interval_start_.end();
92 }
93 return bound;
94 }
95
96 MapIter GetContainingInterval(uint64 point) {
97 auto bound = interval_start_.upper_bound(point);
98 if (!Decrement(&bound)) {
99 return interval_start_.end();
100 }
101 if (bound->second.limit <= point) {
102 return interval_start_.end();
103 }
104 return bound;
105 }
106
107 // Decrements the provided iterator to interval_start_, or returns false if
108 // iter == begin().
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700109 bool Decrement(ConstMapIter* iter) const;
110 bool Decrement(MapIter* iter);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700111
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700112 // Removes everything in the interval map from [remove_start,
113 // remove_limit). This may cut off sections or entire intervals in
114 // the map. This will invalidate iterators to intervals which have a
115 // start value residing in [remove_start, remove_limit).
116 void RemoveInterval(uint64 remove_start, uint64 remove_limit);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700117
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700118 void Insert(uint64 start, uint64 limit, const V& value);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700119
120 // Split an interval into two intervals, [iter.start, point) and
121 // [point, iter.limit). If point is not within (iter.start, point) or iter is
122 // end(), it is a noop.
123 void SplitInterval(MapIter iter, uint64 point);
124
125 // Map from the start of the interval to the limit of the interval and the
126 // corresponding value.
127 std::map<uint64, Value> interval_start_;
128};
129
130template <class V>
131IntervalMap<V>::IntervalMap() {}
132
133template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700134void IntervalMap<V>::Set(uint64 start, uint64 limit, const V& value) {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700135 AssertValidInterval(start, limit);
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700136 RemoveInterval(start, limit);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700137 Insert(start, limit, value);
138}
139
140template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700141bool IntervalMap<V>::Lookup(uint64 key, V* value) const {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700142 const auto contain = GetContainingInterval(key);
143 if (contain == interval_start_.end()) {
144 return false;
145 }
146 *value = contain->second.value;
147 return true;
148}
149
150template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700151bool IntervalMap<V>::FindNext(uint64 key, uint64* start, uint64* limit,
152 V* value) const {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700153 auto iter = interval_start_.upper_bound(key);
154 if (iter == interval_start_.end()) {
155 return false;
156 }
157 *start = iter->first;
158 *limit = iter->second.limit;
159 *value = iter->second.value;
160 return true;
161}
162
163template <class V>
164void IntervalMap<V>::Clear() {
165 interval_start_.clear();
166}
167
168template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700169void IntervalMap<V>::ClearInterval(uint64 clear_start, uint64 clear_limit) {
170 AssertValidInterval(clear_start, clear_limit);
171 RemoveInterval(clear_start, clear_limit);
172}
173
174template <class V>
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700175uint64 IntervalMap<V>::Size() const {
176 return interval_start_.size();
177}
178
179template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700180void IntervalMap<V>::RemoveInterval(uint64 remove_start, uint64 remove_limit) {
181 if (remove_start >= remove_limit) {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700182 return;
183 }
184 // It starts by splitting intervals that will only be partly cleared into two,
185 // where one of those will be fully cleared and the other will not be cleared.
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700186 SplitInterval(GetContainingInterval(remove_limit), remove_limit);
187 SplitInterval(GetContainingInterval(remove_start), remove_start);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700188
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700189 auto remove_interval_start = interval_start_.lower_bound(remove_start);
190 auto remove_interval_end = interval_start_.lower_bound(remove_limit);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700191 // Note that if there are no intervals to be cleared, then
192 // clear_interval_start == clear_interval_end and the erase will be a noop.
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700193 interval_start_.erase(remove_interval_start, remove_interval_end);
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700194}
195
196template <class V>
197void IntervalMap<V>::SplitInterval(MapIter iter, uint64 point) {
198 if (iter == interval_start_.end() || point <= iter->first ||
199 point >= iter->second.limit) {
200 return;
201 }
202 const auto larger_limit = iter->second.limit;
203 iter->second.limit = point;
204 Insert(point, larger_limit, iter->second.value);
205}
206
207template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700208bool IntervalMap<V>::Decrement(ConstMapIter* iter) const {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700209 if ((*iter) == interval_start_.begin()) {
210 return false;
211 }
212 --(*iter);
213 return true;
214}
215
216template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700217bool IntervalMap<V>::Decrement(MapIter* iter) {
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700218 if ((*iter) == interval_start_.begin()) {
219 return false;
220 }
221 --(*iter);
222 return true;
223}
224
225template <class V>
Alexey Alexandrove18bc452016-11-04 14:55:48 -0700226void IntervalMap<V>::Insert(uint64 start, uint64 limit, const V& value) {
227 interval_start_.emplace(std::pair<uint64, Value>{start, {limit, value}});
Raul Silvera0c3c35e2016-09-21 13:14:55 -0700228}
229
230template <class V>
231void IntervalMap<V>::AssertValidInterval(uint64 start, uint64 limit) const {
232 if (start >= limit) {
233 std::cerr << "Invalid interval. Start may not be >= limit." << std::endl
234 << "Start: " << start << std::endl
235 << "Limit: " << limit << std::endl;
236 abort();
237 }
238}
239
240} // namespace perftools
241
242#endif // PERFTOOLS_INTERVALMAP_H_