]>
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) 2004-2006 Sage Weil <sage@newdream.net> | |
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 | ||
16 | #ifndef CEPH_INTERVAL_SET_H | |
17 | #define CEPH_INTERVAL_SET_H | |
18 | ||
19 | #include <iterator> | |
20 | #include <map> | |
21 | #include <ostream> | |
22 | ||
23 | #include "encoding.h" | |
24 | ||
94b18763 FG |
25 | /* |
26 | * *** NOTE *** | |
27 | * | |
28 | * This class is written to work with a variety of map-like containers, | |
29 | * *include* ones that invalidate iterators when they are modified (e.g., | |
30 | * flat_map and btree_map). | |
31 | */ | |
32 | ||
7c673cae FG |
33 | #ifndef MIN |
34 | # define MIN(a,b) ((a)<=(b) ? (a):(b)) | |
35 | #endif | |
36 | #ifndef MAX | |
37 | # define MAX(a,b) ((a)>=(b) ? (a):(b)) | |
38 | #endif | |
39 | ||
40 | ||
94b18763 | 41 | template<typename T, typename Map = std::map<T,T>> |
7c673cae FG |
42 | class interval_set { |
43 | public: | |
44 | ||
45 | class const_iterator; | |
46 | ||
47 | class iterator : public std::iterator <std::forward_iterator_tag, T> | |
48 | { | |
49 | public: | |
94b18763 | 50 | explicit iterator(typename Map::iterator iter) |
7c673cae FG |
51 | : _iter(iter) |
52 | { } | |
53 | ||
54 | // For the copy constructor and assignment operator, the compiler-generated functions, which | |
55 | // perform simple bitwise copying, should be fine. | |
56 | ||
57 | bool operator==(const iterator& rhs) const { | |
58 | return (_iter == rhs._iter); | |
59 | } | |
60 | ||
61 | bool operator!=(const iterator& rhs) const { | |
62 | return (_iter != rhs._iter); | |
63 | } | |
64 | ||
65 | // Dereference this iterator to get a pair. | |
66 | std::pair < T, T > &operator*() { | |
67 | return *_iter; | |
68 | } | |
69 | ||
70 | // Return the interval start. | |
71 | T get_start() const { | |
72 | return _iter->first; | |
73 | } | |
74 | ||
75 | // Return the interval length. | |
76 | T get_len() const { | |
77 | return _iter->second; | |
78 | } | |
79 | ||
80 | // Set the interval length. | |
81 | void set_len(T len) { | |
82 | _iter->second = len; | |
83 | } | |
84 | ||
85 | // Preincrement | |
86 | iterator &operator++() | |
87 | { | |
88 | ++_iter; | |
89 | return *this; | |
90 | } | |
91 | ||
92 | // Postincrement | |
93 | iterator operator++(int) | |
94 | { | |
95 | iterator prev(_iter); | |
96 | ++_iter; | |
97 | return prev; | |
98 | } | |
99 | ||
94b18763 | 100 | friend class interval_set<T,Map>::const_iterator; |
7c673cae FG |
101 | |
102 | protected: | |
94b18763 FG |
103 | typename Map::iterator _iter; |
104 | friend class interval_set<T,Map>; | |
7c673cae FG |
105 | }; |
106 | ||
107 | class const_iterator : public std::iterator <std::forward_iterator_tag, T> | |
108 | { | |
109 | public: | |
94b18763 | 110 | explicit const_iterator(typename Map::const_iterator iter) |
7c673cae FG |
111 | : _iter(iter) |
112 | { } | |
113 | ||
114 | const_iterator(const iterator &i) | |
115 | : _iter(i._iter) | |
116 | { } | |
117 | ||
118 | // For the copy constructor and assignment operator, the compiler-generated functions, which | |
119 | // perform simple bitwise copying, should be fine. | |
120 | ||
121 | bool operator==(const const_iterator& rhs) const { | |
122 | return (_iter == rhs._iter); | |
123 | } | |
124 | ||
125 | bool operator!=(const const_iterator& rhs) const { | |
126 | return (_iter != rhs._iter); | |
127 | } | |
128 | ||
129 | // Dereference this iterator to get a pair. | |
130 | std::pair < T, T > operator*() const { | |
131 | return *_iter; | |
132 | } | |
133 | ||
134 | // Return the interval start. | |
135 | T get_start() const { | |
136 | return _iter->first; | |
137 | } | |
138 | ||
139 | // Return the interval length. | |
140 | T get_len() const { | |
141 | return _iter->second; | |
142 | } | |
143 | ||
144 | // Preincrement | |
145 | const_iterator &operator++() | |
146 | { | |
147 | ++_iter; | |
148 | return *this; | |
149 | } | |
150 | ||
151 | // Postincrement | |
152 | const_iterator operator++(int) | |
153 | { | |
154 | const_iterator prev(_iter); | |
155 | ++_iter; | |
156 | return prev; | |
157 | } | |
158 | ||
159 | protected: | |
94b18763 | 160 | typename Map::const_iterator _iter; |
7c673cae FG |
161 | }; |
162 | ||
163 | interval_set() : _size(0) {} | |
94b18763 | 164 | interval_set(Map& other) { |
7c673cae FG |
165 | m.swap(other); |
166 | _size = 0; | |
167 | for (auto& i : m) { | |
168 | _size += i.second; | |
169 | } | |
170 | } | |
171 | ||
172 | int num_intervals() const | |
173 | { | |
174 | return m.size(); | |
175 | } | |
176 | ||
94b18763 FG |
177 | typename interval_set<T,Map>::iterator begin() { |
178 | return typename interval_set<T,Map>::iterator(m.begin()); | |
7c673cae FG |
179 | } |
180 | ||
94b18763 FG |
181 | typename interval_set<T,Map>::iterator lower_bound(T start) { |
182 | return typename interval_set<T,Map>::iterator(find_inc_m(start)); | |
7c673cae FG |
183 | } |
184 | ||
94b18763 FG |
185 | typename interval_set<T,Map>::iterator end() { |
186 | return typename interval_set<T,Map>::iterator(m.end()); | |
7c673cae FG |
187 | } |
188 | ||
94b18763 FG |
189 | typename interval_set<T,Map>::const_iterator begin() const { |
190 | return typename interval_set<T,Map>::const_iterator(m.begin()); | |
7c673cae FG |
191 | } |
192 | ||
94b18763 FG |
193 | typename interval_set<T,Map>::const_iterator lower_bound(T start) const { |
194 | return typename interval_set<T,Map>::const_iterator(find_inc(start)); | |
7c673cae FG |
195 | } |
196 | ||
94b18763 FG |
197 | typename interval_set<T,Map>::const_iterator end() const { |
198 | return typename interval_set<T,Map>::const_iterator(m.end()); | |
7c673cae FG |
199 | } |
200 | ||
201 | // helpers | |
202 | private: | |
94b18763 FG |
203 | typename Map::const_iterator find_inc(T start) const { |
204 | typename Map::const_iterator p = m.lower_bound(start); // p->first >= start | |
7c673cae FG |
205 | if (p != m.begin() && |
206 | (p == m.end() || p->first > start)) { | |
207 | p--; // might overlap? | |
208 | if (p->first + p->second <= start) | |
209 | p++; // it doesn't. | |
210 | } | |
211 | return p; | |
212 | } | |
213 | ||
94b18763 FG |
214 | typename Map::iterator find_inc_m(T start) { |
215 | typename Map::iterator p = m.lower_bound(start); | |
7c673cae FG |
216 | if (p != m.begin() && |
217 | (p == m.end() || p->first > start)) { | |
218 | p--; // might overlap? | |
219 | if (p->first + p->second <= start) | |
220 | p++; // it doesn't. | |
221 | } | |
222 | return p; | |
223 | } | |
224 | ||
94b18763 FG |
225 | typename Map::const_iterator find_adj(T start) const { |
226 | typename Map::const_iterator p = m.lower_bound(start); | |
7c673cae FG |
227 | if (p != m.begin() && |
228 | (p == m.end() || p->first > start)) { | |
229 | p--; // might touch? | |
230 | if (p->first + p->second < start) | |
231 | p++; // it doesn't. | |
232 | } | |
233 | return p; | |
234 | } | |
235 | ||
94b18763 FG |
236 | typename Map::iterator find_adj_m(T start) { |
237 | typename Map::iterator p = m.lower_bound(start); | |
7c673cae FG |
238 | if (p != m.begin() && |
239 | (p == m.end() || p->first > start)) { | |
240 | p--; // might touch? | |
241 | if (p->first + p->second < start) | |
242 | p++; // it doesn't. | |
243 | } | |
244 | return p; | |
245 | } | |
94b18763 FG |
246 | |
247 | void intersection_size_asym(const interval_set &s, const interval_set &l) { | |
248 | typename decltype(m)::const_iterator ps = s.m.begin(), pl; | |
249 | assert(ps != s.m.end()); | |
250 | T offset = ps->first, prev_offset; | |
251 | bool first = true; | |
252 | typename decltype(m)::iterator mi = m.begin(); | |
253 | ||
254 | while (1) { | |
255 | if (first) | |
256 | first = false; | |
257 | else | |
258 | assert(offset > prev_offset); | |
259 | pl = l.find_inc(offset); | |
260 | prev_offset = offset; | |
261 | if (pl == l.m.end()) | |
262 | break; | |
263 | while (ps != s.m.end() && ps->first + ps->second <= pl->first) | |
264 | ++ps; | |
265 | if (ps == s.m.end()) | |
266 | break; | |
267 | offset = pl->first + pl->second; | |
268 | if (offset <= ps->first) { | |
269 | offset = ps->first; | |
270 | continue; | |
271 | } | |
272 | ||
273 | if (*ps == *pl) { | |
274 | do { | |
275 | mi = m.insert(mi, *ps); | |
276 | _size += ps->second; | |
277 | ++ps; | |
278 | ++pl; | |
279 | } while (ps != s.m.end() && pl != l.m.end() && *ps == *pl); | |
280 | if (ps == s.m.end()) | |
281 | break; | |
282 | offset = ps->first; | |
283 | continue; | |
284 | } | |
285 | ||
286 | T start = std::max<T>(ps->first, pl->first); | |
287 | T en = std::min<T>(ps->first + ps->second, offset); | |
288 | assert(en > start); | |
289 | typename decltype(m)::value_type i{start, en - start}; | |
290 | mi = m.insert(mi, i); | |
291 | _size += i.second; | |
292 | if (ps->first + ps->second <= offset) { | |
293 | ++ps; | |
294 | if (ps == s.m.end()) | |
295 | break; | |
296 | offset = ps->first; | |
297 | } | |
298 | } | |
299 | } | |
300 | ||
301 | bool subset_size_sym(const interval_set &b) const { | |
302 | auto pa = m.begin(), pb = b.m.begin(); | |
303 | const auto a_end = m.end(), b_end = b.m.end(); | |
304 | ||
305 | while (pa != a_end && pb != b_end) { | |
306 | while (pb->first + pb->second <= pa->first) { | |
307 | ++pb; | |
308 | if (pb == b_end) | |
309 | return false; | |
310 | } | |
311 | ||
312 | if (*pa == *pb) { | |
313 | do { | |
314 | ++pa; | |
315 | ++pb; | |
316 | } while (pa != a_end && pb != b_end && *pa == *pb); | |
317 | continue; | |
318 | } | |
319 | ||
320 | // interval begins before other | |
321 | if (pa->first < pb->first) | |
322 | return false; | |
323 | // interval is longer than other | |
324 | if (pa->first + pa->second > pb->first + pb->second) | |
325 | return false; | |
326 | ||
327 | ++pa; | |
328 | } | |
329 | ||
330 | return pa == a_end; | |
331 | } | |
7c673cae FG |
332 | |
333 | public: | |
334 | bool operator==(const interval_set& other) const { | |
335 | return _size == other._size && m == other.m; | |
336 | } | |
337 | ||
338 | int64_t size() const { | |
339 | return _size; | |
340 | } | |
341 | ||
342 | void bound_encode(size_t& p) const { | |
94b18763 | 343 | denc_traits<Map>::bound_encode(m, p); |
7c673cae FG |
344 | } |
345 | void encode(bufferlist::contiguous_appender& p) const { | |
31f18b77 | 346 | denc(m, p); |
7c673cae FG |
347 | } |
348 | void decode(bufferptr::iterator& p) { | |
31f18b77 | 349 | denc(m, p); |
7c673cae | 350 | _size = 0; |
31f18b77 FG |
351 | for (const auto& i : m) { |
352 | _size += i.second; | |
353 | } | |
354 | } | |
355 | void decode(bufferlist::iterator& p) { | |
356 | denc(m, p); | |
357 | _size = 0; | |
358 | for (const auto& i : m) { | |
359 | _size += i.second; | |
360 | } | |
7c673cae FG |
361 | } |
362 | ||
363 | void encode_nohead(bufferlist::contiguous_appender& p) const { | |
94b18763 | 364 | denc_traits<Map>::encode_nohead(m, p); |
7c673cae FG |
365 | } |
366 | void decode_nohead(int n, bufferptr::iterator& p) { | |
94b18763 | 367 | denc_traits<Map>::decode_nohead(n, m, p); |
7c673cae | 368 | _size = 0; |
31f18b77 FG |
369 | for (const auto& i : m) { |
370 | _size += i.second; | |
371 | } | |
7c673cae FG |
372 | } |
373 | ||
374 | void clear() { | |
375 | m.clear(); | |
376 | _size = 0; | |
377 | } | |
378 | ||
379 | bool contains(T i, T *pstart=0, T *plen=0) const { | |
94b18763 | 380 | typename Map::const_iterator p = find_inc(i); |
7c673cae FG |
381 | if (p == m.end()) return false; |
382 | if (p->first > i) return false; | |
383 | if (p->first+p->second <= i) return false; | |
384 | assert(p->first <= i && p->first+p->second > i); | |
385 | if (pstart) | |
386 | *pstart = p->first; | |
387 | if (plen) | |
388 | *plen = p->second; | |
389 | return true; | |
390 | } | |
391 | bool contains(T start, T len) const { | |
94b18763 | 392 | typename Map::const_iterator p = find_inc(start); |
7c673cae FG |
393 | if (p == m.end()) return false; |
394 | if (p->first > start) return false; | |
395 | if (p->first+p->second <= start) return false; | |
396 | assert(p->first <= start && p->first+p->second > start); | |
397 | if (p->first+p->second < start+len) return false; | |
398 | return true; | |
399 | } | |
400 | bool intersects(T start, T len) const { | |
401 | interval_set a; | |
402 | a.insert(start, len); | |
403 | interval_set i; | |
404 | i.intersection_of( *this, a ); | |
405 | if (i.empty()) return false; | |
406 | return true; | |
407 | } | |
408 | ||
409 | // outer range of set | |
410 | bool empty() const { | |
411 | return m.empty(); | |
412 | } | |
413 | T range_start() const { | |
414 | assert(!empty()); | |
94b18763 | 415 | typename Map::const_iterator p = m.begin(); |
7c673cae FG |
416 | return p->first; |
417 | } | |
418 | T range_end() const { | |
419 | assert(!empty()); | |
94b18763 | 420 | typename Map::const_iterator p = m.end(); |
7c673cae FG |
421 | p--; |
422 | return p->first+p->second; | |
423 | } | |
424 | ||
425 | // interval start after p (where p not in set) | |
426 | bool starts_after(T i) const { | |
427 | assert(!contains(i)); | |
94b18763 | 428 | typename Map::const_iterator p = find_inc(i); |
7c673cae FG |
429 | if (p == m.end()) return false; |
430 | return true; | |
431 | } | |
432 | T start_after(T i) const { | |
433 | assert(!contains(i)); | |
94b18763 | 434 | typename Map::const_iterator p = find_inc(i); |
7c673cae FG |
435 | return p->first; |
436 | } | |
437 | ||
438 | // interval end that contains start | |
439 | T end_after(T start) const { | |
440 | assert(contains(start)); | |
94b18763 | 441 | typename Map::const_iterator p = find_inc(start); |
7c673cae FG |
442 | return p->first+p->second; |
443 | } | |
444 | ||
445 | void insert(T val) { | |
446 | insert(val, 1); | |
447 | } | |
448 | ||
449 | void insert(T start, T len, T *pstart=0, T *plen=0) { | |
450 | //cout << "insert " << start << "~" << len << endl; | |
451 | assert(len > 0); | |
452 | _size += len; | |
94b18763 | 453 | typename Map::iterator p = find_adj_m(start); |
7c673cae FG |
454 | if (p == m.end()) { |
455 | m[start] = len; // new interval | |
456 | if (pstart) | |
457 | *pstart = start; | |
458 | if (plen) | |
459 | *plen = len; | |
460 | } else { | |
461 | if (p->first < start) { | |
462 | ||
463 | if (p->first + p->second != start) { | |
464 | //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl; | |
465 | ceph_abort(); | |
466 | } | |
467 | ||
468 | p->second += len; // append to end | |
469 | ||
94b18763 | 470 | typename Map::iterator n = p; |
7c673cae | 471 | n++; |
94b18763 FG |
472 | if (pstart) |
473 | *pstart = p->first; | |
7c673cae FG |
474 | if (n != m.end() && |
475 | start+len == n->first) { // combine with next, too! | |
476 | p->second += n->second; | |
94b18763 FG |
477 | if (plen) |
478 | *plen = p->second; | |
7c673cae | 479 | m.erase(n); |
94b18763 FG |
480 | } else { |
481 | if (plen) | |
482 | *plen = p->second; | |
483 | } | |
7c673cae FG |
484 | } else { |
485 | if (start+len == p->first) { | |
7c673cae FG |
486 | if (pstart) |
487 | *pstart = start; | |
488 | if (plen) | |
489 | *plen = len + p->second; | |
94b18763 | 490 | T psecond = p->second; |
7c673cae | 491 | m.erase(p); |
94b18763 | 492 | m[start] = len + psecond; // append to front |
7c673cae FG |
493 | } else { |
494 | assert(p->first > start+len); | |
7c673cae FG |
495 | if (pstart) |
496 | *pstart = start; | |
497 | if (plen) | |
498 | *plen = len; | |
94b18763 | 499 | m[start] = len; // new interval |
7c673cae FG |
500 | } |
501 | } | |
502 | } | |
503 | } | |
504 | ||
94b18763 | 505 | void swap(interval_set<T,Map>& other) { |
7c673cae FG |
506 | m.swap(other.m); |
507 | std::swap(_size, other._size); | |
508 | } | |
509 | ||
510 | void erase(iterator &i) { | |
511 | _size -= i.get_len(); | |
512 | assert(_size >= 0); | |
513 | m.erase(i._iter); | |
514 | } | |
515 | ||
516 | void erase(T val) { | |
517 | erase(val, 1); | |
518 | } | |
519 | ||
28e407b8 AA |
520 | void erase(T start, T len, |
521 | std::function<bool(T, T)> claim = {}) { | |
94b18763 | 522 | typename Map::iterator p = find_inc_m(start); |
7c673cae FG |
523 | |
524 | _size -= len; | |
525 | assert(_size >= 0); | |
526 | ||
527 | assert(p != m.end()); | |
528 | assert(p->first <= start); | |
529 | ||
530 | T before = start - p->first; | |
531 | assert(p->second >= before+len); | |
532 | T after = p->second - before - len; | |
28e407b8 AA |
533 | if (before) { |
534 | if (claim && claim(p->first, before)) { | |
535 | _size -= before; | |
536 | m.erase(p); | |
537 | } else { | |
538 | p->second = before; // shorten bit before | |
539 | } | |
94b18763 | 540 | } else { |
7c673cae | 541 | m.erase(p); |
94b18763 | 542 | } |
28e407b8 AA |
543 | if (after) { |
544 | if (claim && claim(start + len, after)) { | |
545 | _size -= after; | |
546 | } else { | |
547 | m[start + len] = after; | |
548 | } | |
94b18763 | 549 | } |
7c673cae FG |
550 | } |
551 | ||
7c673cae | 552 | void subtract(const interval_set &a) { |
94b18763 | 553 | for (typename Map::const_iterator p = a.m.begin(); |
7c673cae FG |
554 | p != a.m.end(); |
555 | p++) | |
556 | erase(p->first, p->second); | |
557 | } | |
558 | ||
559 | void insert(const interval_set &a) { | |
94b18763 | 560 | for (typename Map::const_iterator p = a.m.begin(); |
7c673cae FG |
561 | p != a.m.end(); |
562 | p++) | |
563 | insert(p->first, p->second); | |
564 | } | |
565 | ||
566 | ||
567 | void intersection_of(const interval_set &a, const interval_set &b) { | |
568 | assert(&a != this); | |
569 | assert(&b != this); | |
570 | clear(); | |
571 | ||
94b18763 FG |
572 | const interval_set *s, *l; |
573 | ||
574 | if (a.size() < b.size()) { | |
575 | s = &a; | |
576 | l = &b; | |
577 | } else { | |
578 | s = &b; | |
579 | l = &a; | |
580 | } | |
581 | ||
582 | if (!s->size()) | |
583 | return; | |
584 | ||
585 | /* | |
586 | * Use the lower_bound algorithm for larger size ratios | |
587 | * where it performs better, but not for smaller size | |
588 | * ratios where sequential search performs better. | |
589 | */ | |
590 | if (l->size() / s->size() >= 10) { | |
591 | intersection_size_asym(*s, *l); | |
592 | return; | |
593 | } | |
594 | ||
595 | typename Map::const_iterator pa = a.m.begin(); | |
596 | typename Map::const_iterator pb = b.m.begin(); | |
181888fb FG |
597 | typename decltype(m)::iterator mi = m.begin(); |
598 | ||
7c673cae FG |
599 | while (pa != a.m.end() && pb != b.m.end()) { |
600 | // passing? | |
601 | if (pa->first + pa->second <= pb->first) | |
602 | { pa++; continue; } | |
603 | if (pb->first + pb->second <= pa->first) | |
604 | { pb++; continue; } | |
181888fb FG |
605 | |
606 | if (*pa == *pb) { | |
607 | do { | |
608 | mi = m.insert(mi, *pa); | |
609 | _size += pa->second; | |
610 | ++pa; | |
611 | ++pb; | |
612 | } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb); | |
613 | continue; | |
614 | } | |
615 | ||
7c673cae FG |
616 | T start = MAX(pa->first, pb->first); |
617 | T en = MIN(pa->first+pa->second, pb->first+pb->second); | |
618 | assert(en > start); | |
181888fb FG |
619 | typename decltype(m)::value_type i{start, en - start}; |
620 | mi = m.insert(mi, i); | |
621 | _size += i.second; | |
7c673cae FG |
622 | if (pa->first+pa->second > pb->first+pb->second) |
623 | pb++; | |
624 | else | |
625 | pa++; | |
626 | } | |
627 | } | |
628 | void intersection_of(const interval_set& b) { | |
629 | interval_set a; | |
630 | swap(a); | |
631 | intersection_of(a, b); | |
632 | } | |
633 | ||
634 | void union_of(const interval_set &a, const interval_set &b) { | |
635 | assert(&a != this); | |
636 | assert(&b != this); | |
637 | clear(); | |
638 | ||
639 | //cout << "union_of" << endl; | |
640 | ||
641 | // a | |
642 | m = a.m; | |
643 | _size = a._size; | |
644 | ||
645 | // - (a*b) | |
646 | interval_set ab; | |
647 | ab.intersection_of(a, b); | |
648 | subtract(ab); | |
649 | ||
650 | // + b | |
651 | insert(b); | |
652 | return; | |
653 | } | |
654 | void union_of(const interval_set &b) { | |
655 | interval_set a; | |
656 | swap(a); | |
657 | union_of(a, b); | |
658 | } | |
659 | void union_insert(T off, T len) { | |
660 | interval_set a; | |
661 | a.insert(off, len); | |
662 | union_of(a); | |
663 | } | |
664 | ||
665 | bool subset_of(const interval_set &big) const { | |
94b18763 FG |
666 | if (!size()) |
667 | return true; | |
668 | if (size() > big.size()) | |
669 | return false; | |
670 | if (range_end() > big.range_end()) | |
671 | return false; | |
672 | ||
673 | /* | |
674 | * Use the lower_bound algorithm for larger size ratios | |
675 | * where it performs better, but not for smaller size | |
676 | * ratios where sequential search performs better. | |
677 | */ | |
678 | if (big.size() / size() < 10) | |
679 | return subset_size_sym(big); | |
680 | ||
681 | for (typename Map::const_iterator i = m.begin(); | |
7c673cae FG |
682 | i != m.end(); |
683 | i++) | |
684 | if (!big.contains(i->first, i->second)) return false; | |
685 | return true; | |
686 | } | |
687 | ||
94b18763 FG |
688 | /* |
689 | * build a subset of @other for given rage [@start, @end) | |
690 | * E.g.: | |
691 | * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5] | |
692 | * subset_of([5~10,20~5], 5, 25) -> [5~10,20~5] | |
693 | * subset_of([5~10,20~5], 1, 10) -> [5~5] | |
694 | * subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4] | |
695 | */ | |
696 | void subset_of(const interval_set &other, T start, T end) { | |
697 | assert(end >= start); | |
698 | clear(); | |
699 | if (end == start) { | |
700 | return; | |
701 | } | |
702 | typename Map::const_iterator p = other.find_inc(start); | |
703 | if (p == other.m.end()) | |
704 | return; | |
705 | if (p->first < start) { | |
706 | if (p->first + p->second >= end) { | |
707 | insert(start, end - start); | |
708 | return; | |
709 | } else { | |
710 | insert(start, p->first + p->second - start); | |
711 | ++p; | |
712 | } | |
713 | } | |
714 | while (p != other.m.end()) { | |
715 | assert(p->first >= start); | |
716 | if (p->first >= end) { | |
717 | return; | |
718 | } | |
719 | if (p->first + p->second >= end) { | |
720 | insert(p->first, end - p->first); | |
721 | return; | |
722 | } else { | |
723 | // whole | |
724 | insert(p->first, p->second); | |
725 | ++p; | |
726 | } | |
727 | } | |
728 | } | |
729 | ||
7c673cae FG |
730 | /* |
731 | * build a subset of @other, starting at or after @start, and including | |
732 | * @len worth of values, skipping holes. e.g., | |
733 | * span_of([5~10,20~5], 8, 5) -> [8~2,20~3] | |
734 | */ | |
735 | void span_of(const interval_set &other, T start, T len) { | |
736 | clear(); | |
94b18763 | 737 | typename Map::const_iterator p = other.find_inc(start); |
7c673cae FG |
738 | if (p == other.m.end()) |
739 | return; | |
740 | if (p->first < start) { | |
741 | if (p->first + p->second < start) | |
742 | return; | |
743 | if (p->first + p->second < start + len) { | |
744 | T howmuch = p->second - (start - p->first); | |
745 | insert(start, howmuch); | |
746 | len -= howmuch; | |
747 | p++; | |
748 | } else { | |
749 | insert(start, len); | |
750 | return; | |
751 | } | |
752 | } | |
753 | while (p != other.m.end() && len > 0) { | |
754 | if (p->second < len) { | |
755 | insert(p->first, p->second); | |
756 | len -= p->second; | |
757 | p++; | |
758 | } else { | |
759 | insert(p->first, len); | |
760 | return; | |
761 | } | |
762 | } | |
763 | } | |
764 | ||
765 | /* | |
94b18763 FG |
766 | * Move contents of m into another Map. Use that instead of |
767 | * encoding interval_set into bufferlist then decoding it back into Map. | |
7c673cae | 768 | */ |
94b18763 | 769 | void move_into(Map& other) { |
7c673cae FG |
770 | other = std::move(m); |
771 | } | |
772 | ||
773 | private: | |
774 | // data | |
775 | int64_t _size; | |
94b18763 | 776 | Map m; // map start -> len |
7c673cae FG |
777 | }; |
778 | ||
779 | // declare traits explicitly because (1) it's templatized, and (2) we | |
780 | // want to include _nohead variants. | |
94b18763 FG |
781 | template<typename T, typename Map> |
782 | struct denc_traits<interval_set<T,Map>> { | |
7c673cae FG |
783 | static constexpr bool supported = true; |
784 | static constexpr bool bounded = false; | |
785 | static constexpr bool featured = false; | |
94b18763 FG |
786 | static constexpr bool need_contiguous = denc_traits<T,Map>::need_contiguous; |
787 | static void bound_encode(const interval_set<T,Map>& v, size_t& p) { | |
7c673cae FG |
788 | v.bound_encode(p); |
789 | } | |
94b18763 | 790 | static void encode(const interval_set<T,Map>& v, |
7c673cae FG |
791 | bufferlist::contiguous_appender& p) { |
792 | v.encode(p); | |
793 | } | |
94b18763 | 794 | static void decode(interval_set<T,Map>& v, bufferptr::iterator& p) { |
7c673cae FG |
795 | v.decode(p); |
796 | } | |
31f18b77 FG |
797 | template<typename U=T> |
798 | static typename std::enable_if<sizeof(U) && !need_contiguous>::type | |
94b18763 | 799 | decode(interval_set<T,Map>& v, bufferlist::iterator& p) { |
31f18b77 FG |
800 | v.decode(p); |
801 | } | |
94b18763 | 802 | static void encode_nohead(const interval_set<T,Map>& v, |
7c673cae FG |
803 | bufferlist::contiguous_appender& p) { |
804 | v.encode_nohead(p); | |
805 | } | |
94b18763 | 806 | static void decode_nohead(size_t n, interval_set<T,Map>& v, |
7c673cae FG |
807 | bufferptr::iterator& p) { |
808 | v.decode_nohead(n, p); | |
809 | } | |
810 | }; | |
811 | ||
812 | ||
94b18763 FG |
813 | template<class T, typename Map> |
814 | inline std::ostream& operator<<(std::ostream& out, const interval_set<T,Map> &s) { | |
7c673cae FG |
815 | out << "["; |
816 | const char *prequel = ""; | |
94b18763 | 817 | for (typename interval_set<T,Map>::const_iterator i = s.begin(); |
7c673cae FG |
818 | i != s.end(); |
819 | ++i) | |
820 | { | |
821 | out << prequel << i.get_start() << "~" << i.get_len(); | |
822 | prequel = ","; | |
823 | } | |
824 | out << "]"; | |
825 | return out; | |
826 | } | |
827 | ||
828 | ||
829 | #endif |