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