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