]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2016 Red Hat | |
7 | * | |
8 | * This is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License version 2.1, as published by the Free Software | |
11 | * Foundation. See file COPYING. | |
12 | * | |
13 | */ | |
14 | ||
15 | #ifndef INTERVAL_MAP_H | |
16 | #define INTERVAL_MAP_H | |
17 | ||
18 | #include <map> | |
19 | #include <vector> | |
20 | #include <utility> | |
21 | #include <boost/optional.hpp> | |
22 | #include <iostream> | |
23 | #include "include/interval_set.h" | |
24 | ||
25 | template <typename K, typename V, typename S> | |
26 | /** | |
27 | * interval_map | |
28 | * | |
29 | * Maps intervals to values. Erasing or inserting over an existing | |
30 | * range will use S::operator() to split any overlapping existing | |
31 | * values. | |
32 | * | |
33 | * Surprisingly, boost/icl/interval_map doesn't seem to be appropriate | |
34 | * for this use case. The aggregation concept seems to assume | |
35 | * commutativity, which doesn't work if we want more recent insertions | |
36 | * to overwrite previous ones. | |
37 | */ | |
38 | class interval_map { | |
39 | S s; | |
40 | using map = std::map<K, std::pair<K, V> >; | |
41 | using mapiter = typename std::map<K, std::pair<K, V> >::iterator; | |
42 | using cmapiter = typename std::map<K, std::pair<K, V> >::const_iterator; | |
43 | map m; | |
44 | std::pair<mapiter, mapiter> get_range(K off, K len) { | |
45 | // fst is first iterator with end after off (may be end) | |
46 | auto fst = m.upper_bound(off); | |
47 | if (fst != m.begin()) | |
48 | --fst; | |
49 | if (fst != m.end() && off >= (fst->first + fst->second.first)) | |
50 | ++fst; | |
51 | ||
52 | // lst is first iterator with start after off + len (may be end) | |
53 | auto lst = m.lower_bound(off + len); | |
54 | return std::make_pair(fst, lst); | |
55 | } | |
56 | std::pair<cmapiter, cmapiter> get_range(K off, K len) const { | |
57 | // fst is first iterator with end after off (may be end) | |
58 | auto fst = m.upper_bound(off); | |
59 | if (fst != m.begin()) | |
60 | --fst; | |
61 | if (fst != m.end() && off >= (fst->first + fst->second.first)) | |
62 | ++fst; | |
63 | ||
64 | // lst is first iterator with start after off + len (may be end) | |
65 | auto lst = m.lower_bound(off + len); | |
66 | return std::make_pair(fst, lst); | |
67 | } | |
68 | void try_merge(mapiter niter) { | |
69 | if (niter != m.begin()) { | |
70 | auto prev = niter; | |
71 | prev--; | |
72 | if (prev->first + prev->second.first == niter->first && | |
73 | s.can_merge(prev->second.second, niter->second.second)) { | |
74 | V n = s.merge( | |
75 | std::move(prev->second.second), | |
76 | std::move(niter->second.second)); | |
77 | K off = prev->first; | |
78 | K len = niter->first + niter->second.first - off; | |
79 | niter++; | |
80 | m.erase(prev, niter); | |
81 | auto p = m.insert( | |
82 | std::make_pair( | |
83 | off, | |
84 | std::make_pair(len, std::move(n)))); | |
85 | assert(p.second); | |
86 | niter = p.first; | |
87 | } | |
88 | } | |
89 | auto next = niter; | |
90 | next++; | |
91 | if (next != m.end() && | |
92 | niter->first + niter->second.first == next->first && | |
93 | s.can_merge(niter->second.second, next->second.second)) { | |
94 | V n = s.merge( | |
95 | std::move(niter->second.second), | |
96 | std::move(next->second.second)); | |
97 | K off = niter->first; | |
98 | K len = next->first + next->second.first - off; | |
99 | next++; | |
100 | m.erase(niter, next); | |
101 | auto p = m.insert( | |
102 | std::make_pair( | |
103 | off, | |
104 | std::make_pair(len, std::move(n)))); | |
105 | assert(p.second); | |
106 | } | |
107 | } | |
108 | public: | |
109 | interval_map intersect(K off, K len) const { | |
110 | interval_map ret; | |
111 | auto limits = get_range(off, len); | |
112 | for (auto i = limits.first; i != limits.second; ++i) { | |
113 | K o = i->first; | |
114 | K l = i->second.first; | |
115 | V v = i->second.second; | |
116 | if (o < off) { | |
117 | V p = v; | |
118 | l -= (off - o); | |
119 | v = s.split(off - o, l, p); | |
120 | o = off; | |
121 | } | |
122 | if ((o + l) > (off + len)) { | |
123 | V p = v; | |
124 | l -= (o + l) - (off + len); | |
125 | v = s.split(0, l, p); | |
126 | } | |
127 | ret.insert(o, l, v); | |
128 | } | |
129 | return ret; | |
130 | } | |
131 | void clear() { | |
132 | m.clear(); | |
133 | } | |
134 | void erase(K off, K len) { | |
135 | if (len == 0) | |
136 | return; | |
137 | auto range = get_range(off, len); | |
138 | std::vector< | |
139 | std::pair< | |
140 | K, | |
141 | std::pair<K, V> | |
142 | >> to_insert; | |
143 | for (auto i = range.first; i != range.second; ++i) { | |
144 | if (i->first < off) { | |
145 | to_insert.emplace_back( | |
146 | std::make_pair( | |
147 | i->first, | |
148 | std::make_pair( | |
149 | off - i->first, | |
150 | s.split(0, off - i->first, i->second.second)))); | |
151 | } | |
152 | if ((off + len) < (i->first + i->second.first)) { | |
153 | K nlen = (i->first + i->second.first) - (off + len); | |
154 | to_insert.emplace_back( | |
155 | std::make_pair( | |
156 | off + len, | |
157 | std::make_pair( | |
158 | nlen, | |
159 | s.split(i->second.first - nlen, nlen, i->second.second)))); | |
160 | } | |
161 | } | |
162 | m.erase(range.first, range.second); | |
163 | m.insert(to_insert.begin(), to_insert.end()); | |
164 | } | |
165 | void insert(K off, K len, V &&v) { | |
166 | assert(len > 0); | |
167 | assert(len == s.length(v)); | |
168 | erase(off, len); | |
169 | auto p = m.insert(make_pair(off, std::make_pair(len, std::forward<V>(v)))); | |
170 | assert(p.second); | |
171 | try_merge(p.first); | |
172 | } | |
173 | void insert(interval_map &&other) { | |
174 | for (auto i = other.m.begin(); | |
175 | i != other.m.end(); | |
176 | other.m.erase(i++)) { | |
177 | insert(i->first, i->second.first, std::move(i->second.second)); | |
178 | } | |
179 | } | |
180 | void insert(K off, K len, const V &v) { | |
181 | assert(len > 0); | |
182 | assert(len == s.length(v)); | |
183 | erase(off, len); | |
184 | auto p = m.insert(make_pair(off, std::make_pair(len, v))); | |
185 | assert(p.second); | |
186 | try_merge(p.first); | |
187 | } | |
188 | void insert(const interval_map &other) { | |
189 | for (auto &&i: other) { | |
190 | insert(i.get_off(), i.get_len(), i.get_val()); | |
191 | } | |
192 | } | |
193 | bool empty() const { | |
194 | return m.empty(); | |
195 | } | |
196 | interval_set<K> get_interval_set() const { | |
197 | interval_set<K> ret; | |
198 | for (auto &&i: *this) { | |
199 | ret.insert(i.get_off(), i.get_len()); | |
200 | } | |
201 | return ret; | |
202 | } | |
203 | class const_iterator { | |
204 | cmapiter it; | |
205 | const_iterator(cmapiter &&it) : it(std::move(it)) {} | |
206 | const_iterator(const cmapiter &it) : it(it) {} | |
207 | ||
208 | friend class interval_map; | |
209 | public: | |
210 | const_iterator(const const_iterator &) = default; | |
211 | const_iterator &operator=(const const_iterator &) = default; | |
212 | ||
213 | const_iterator &operator++() { | |
214 | ++it; | |
215 | return *this; | |
216 | } | |
217 | const_iterator operator++(int) { | |
218 | return const_iterator(it++); | |
219 | } | |
220 | const_iterator &operator--() { | |
221 | --it; | |
222 | return *this; | |
223 | } | |
224 | const_iterator operator--(int) { | |
225 | return const_iterator(it--); | |
226 | } | |
227 | bool operator==(const const_iterator &rhs) const { | |
228 | return it == rhs.it; | |
229 | } | |
230 | bool operator!=(const const_iterator &rhs) const { | |
231 | return it != rhs.it; | |
232 | } | |
233 | K get_off() const { | |
234 | return it->first; | |
235 | } | |
236 | K get_len() const { | |
237 | return it->second.first; | |
238 | } | |
239 | const V &get_val() const { | |
240 | return it->second.second; | |
241 | } | |
242 | const_iterator &operator*() { | |
243 | return *this; | |
244 | } | |
245 | }; | |
246 | const_iterator begin() const { | |
247 | return const_iterator(m.begin()); | |
248 | } | |
249 | const_iterator end() const { | |
250 | return const_iterator(m.end()); | |
251 | } | |
252 | std::pair<const_iterator, const_iterator> get_containing_range( | |
253 | K off, | |
254 | K len) const { | |
255 | auto rng = get_range(off, len); | |
256 | return std::make_pair(const_iterator(rng.first), const_iterator(rng.second)); | |
257 | } | |
258 | unsigned ext_count() const { | |
259 | return m.size(); | |
260 | } | |
261 | bool operator==(const interval_map &rhs) const { | |
262 | return m == rhs.m; | |
263 | } | |
264 | ||
265 | std::ostream &print(std::ostream &out) const { | |
266 | bool first = true; | |
267 | out << "{"; | |
268 | for (auto &&i: *this) { | |
269 | if (first) { | |
270 | first = false; | |
271 | } else { | |
272 | out << ","; | |
273 | } | |
274 | out << i.get_off() << "~" << i.get_len() << "(" | |
275 | << s.length(i.get_val()) << ")"; | |
276 | } | |
277 | return out << "}"; | |
278 | } | |
279 | }; | |
280 | ||
281 | template <typename K, typename V, typename S> | |
282 | std::ostream &operator<<(std::ostream &out, const interval_map<K, V, S> &m) { | |
283 | return m.print(out); | |
284 | } | |
285 | ||
286 | #endif |