]>
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_BTREE_INTERVAL_SET_H | |
17 | #define CEPH_BTREE_INTERVAL_SET_H | |
18 | ||
19 | #include <iterator> | |
20 | #include <map> | |
21 | #include <ostream> | |
22 | ||
23 | #include "encoding.h" | |
24 | ||
25 | #ifndef MIN | |
26 | # define MIN(a,b) ((a)<=(b) ? (a):(b)) | |
27 | #endif | |
28 | #ifndef MAX | |
29 | # define MAX(a,b) ((a)>=(b) ? (a):(b)) | |
30 | #endif | |
31 | ||
32 | #include "cpp-btree/btree_map.h" | |
33 | #include "assert.h" | |
34 | #include "encoding_btree.h" | |
35 | ||
181888fb FG |
36 | template<typename T, |
37 | typename Alloc = std::allocator<std::pair<const T, T>>> | |
7c673cae FG |
38 | class btree_interval_set { |
39 | public: | |
40 | ||
181888fb | 41 | typedef btree::btree_map<T,T, std::less<T>, Alloc> map_t; |
7c673cae FG |
42 | |
43 | class const_iterator; | |
44 | ||
45 | class iterator : public std::iterator <std::forward_iterator_tag, T> | |
46 | { | |
47 | public: | |
48 | explicit iterator(typename map_t::iterator iter) | |
49 | : _iter(iter) | |
50 | { } | |
51 | ||
52 | // For the copy constructor and assignment operator, the compiler-generated functions, which | |
53 | // perform simple bitwise copying, should be fine. | |
54 | ||
55 | bool operator==(const iterator& rhs) const { | |
56 | return (_iter == rhs._iter); | |
57 | } | |
58 | ||
59 | bool operator!=(const iterator& rhs) const { | |
60 | return (_iter != rhs._iter); | |
61 | } | |
62 | ||
63 | // Dereference this iterator to get a pair. | |
64 | std::pair < T, T > &operator*() { | |
65 | return *_iter; | |
66 | } | |
67 | ||
68 | // Return the interval start. | |
69 | T get_start() const { | |
70 | return _iter->first; | |
71 | } | |
72 | ||
73 | // Return the interval length. | |
74 | T get_len() const { | |
75 | return _iter->second; | |
76 | } | |
77 | ||
78 | // Set the interval length. | |
79 | void set_len(T len) { | |
80 | _iter->second = len; | |
81 | } | |
82 | ||
83 | // Preincrement | |
84 | iterator &operator++() | |
85 | { | |
86 | ++_iter; | |
87 | return *this; | |
88 | } | |
89 | ||
90 | // Postincrement | |
91 | iterator operator++(int) | |
92 | { | |
93 | iterator prev(_iter); | |
94 | ++_iter; | |
95 | return prev; | |
96 | } | |
97 | ||
98 | friend class btree_interval_set<T>::const_iterator; | |
99 | ||
100 | protected: | |
101 | typename map_t::iterator _iter; | |
102 | friend class btree_interval_set<T>; | |
103 | }; | |
104 | ||
105 | class const_iterator : public std::iterator <std::forward_iterator_tag, T> | |
106 | { | |
107 | public: | |
108 | explicit const_iterator(typename map_t::const_iterator iter) | |
109 | : _iter(iter) | |
110 | { } | |
111 | ||
112 | const_iterator(const iterator &i) | |
113 | : _iter(i._iter) | |
114 | { } | |
115 | ||
116 | // For the copy constructor and assignment operator, the compiler-generated functions, which | |
117 | // perform simple bitwise copying, should be fine. | |
118 | ||
119 | bool operator==(const const_iterator& rhs) const { | |
120 | return (_iter == rhs._iter); | |
121 | } | |
122 | ||
123 | bool operator!=(const const_iterator& rhs) const { | |
124 | return (_iter != rhs._iter); | |
125 | } | |
126 | ||
127 | // Dereference this iterator to get a pair. | |
128 | std::pair < T, T > operator*() const { | |
129 | return *_iter; | |
130 | } | |
131 | ||
132 | // Return the interval start. | |
133 | T get_start() const { | |
134 | return _iter->first; | |
135 | } | |
136 | ||
137 | // Return the interval length. | |
138 | T get_len() const { | |
139 | return _iter->second; | |
140 | } | |
141 | ||
142 | // Preincrement | |
143 | const_iterator &operator++() | |
144 | { | |
145 | ++_iter; | |
146 | return *this; | |
147 | } | |
148 | ||
149 | // Postincrement | |
150 | const_iterator operator++(int) | |
151 | { | |
152 | const_iterator prev(_iter); | |
153 | ++_iter; | |
154 | return prev; | |
155 | } | |
156 | ||
157 | protected: | |
158 | typename map_t::const_iterator _iter; | |
159 | }; | |
160 | ||
161 | btree_interval_set() : _size(0) {} | |
162 | ||
163 | int num_intervals() const | |
164 | { | |
165 | return m.size(); | |
166 | } | |
167 | ||
181888fb FG |
168 | typename btree_interval_set<T,Alloc>::iterator begin() { |
169 | return typename btree_interval_set<T,Alloc>::iterator(m.begin()); | |
7c673cae FG |
170 | } |
171 | ||
181888fb FG |
172 | typename btree_interval_set<T,Alloc>::iterator lower_bound(T start) { |
173 | return typename btree_interval_set<T,Alloc>::iterator(find_inc_m(start)); | |
7c673cae FG |
174 | } |
175 | ||
181888fb FG |
176 | typename btree_interval_set<T,Alloc>::iterator end() { |
177 | return typename btree_interval_set<T,Alloc>::iterator(m.end()); | |
7c673cae FG |
178 | } |
179 | ||
181888fb FG |
180 | typename btree_interval_set<T,Alloc>::const_iterator begin() const { |
181 | return typename btree_interval_set<T,Alloc>::const_iterator(m.begin()); | |
7c673cae FG |
182 | } |
183 | ||
181888fb FG |
184 | typename btree_interval_set<T,Alloc>::const_iterator lower_bound(T start) const { |
185 | return typename btree_interval_set<T,Alloc>::const_iterator(find_inc(start)); | |
7c673cae FG |
186 | } |
187 | ||
181888fb FG |
188 | typename btree_interval_set<T,Alloc>::const_iterator end() const { |
189 | return typename btree_interval_set<T,Alloc>::const_iterator(m.end()); | |
7c673cae FG |
190 | } |
191 | ||
192 | // helpers | |
193 | private: | |
194 | typename map_t::const_iterator find_inc(T start) const { | |
195 | typename map_t::const_iterator p = m.lower_bound(start); // p->first >= start | |
196 | if (p != m.begin() && | |
197 | (p == m.end() || p->first > start)) { | |
198 | p--; // might overlap? | |
199 | if (p->first + p->second <= start) | |
200 | p++; // it doesn't. | |
201 | } | |
202 | return p; | |
203 | } | |
204 | ||
205 | typename map_t::iterator find_inc_m(T start) { | |
206 | typename map_t::iterator p = m.lower_bound(start); | |
207 | if (p != m.begin() && | |
208 | (p == m.end() || p->first > start)) { | |
209 | p--; // might overlap? | |
210 | if (p->first + p->second <= start) | |
211 | p++; // it doesn't. | |
212 | } | |
213 | return p; | |
214 | } | |
215 | ||
216 | typename map_t::const_iterator find_adj(T start) const { | |
217 | typename map_t::const_iterator p = m.lower_bound(start); | |
218 | if (p != m.begin() && | |
219 | (p == m.end() || p->first > start)) { | |
220 | p--; // might touch? | |
221 | if (p->first + p->second < start) | |
222 | p++; // it doesn't. | |
223 | } | |
224 | return p; | |
225 | } | |
226 | ||
227 | typename map_t::iterator find_adj_m(T start) { | |
228 | typename map_t::iterator p = m.lower_bound(start); | |
229 | if (p != m.begin() && | |
230 | (p == m.end() || p->first > start)) { | |
231 | p--; // might touch? | |
232 | if (p->first + p->second < start) | |
233 | p++; // it doesn't. | |
234 | } | |
235 | return p; | |
236 | } | |
237 | ||
238 | public: | |
239 | bool operator==(const btree_interval_set& other) const { | |
240 | return _size == other._size && m == other.m; | |
241 | } | |
242 | ||
243 | int64_t size() const { | |
244 | return _size; | |
245 | } | |
246 | ||
247 | void encode(bufferlist& bl) const { | |
248 | ::encode(m, bl); | |
249 | } | |
250 | void encode_nohead(bufferlist& bl) const { | |
251 | ::encode_nohead(m, bl); | |
252 | } | |
253 | void decode(bufferlist::iterator& bl) { | |
254 | ::decode(m, bl); | |
255 | _size = 0; | |
256 | for (typename map_t::const_iterator p = m.begin(); | |
257 | p != m.end(); | |
258 | p++) | |
259 | _size += p->second; | |
260 | } | |
261 | void decode_nohead(int n, bufferlist::iterator& bl) { | |
262 | ::decode_nohead(n, m, bl); | |
263 | _size = 0; | |
264 | for (typename map_t::const_iterator p = m.begin(); | |
265 | p != m.end(); | |
266 | p++) | |
267 | _size += p->second; | |
268 | } | |
269 | ||
270 | void clear() { | |
271 | m.clear(); | |
272 | _size = 0; | |
273 | } | |
274 | ||
275 | bool contains(T i, T *pstart=0, T *plen=0) const { | |
276 | typename map_t::const_iterator p = find_inc(i); | |
277 | if (p == m.end()) return false; | |
278 | if (p->first > i) return false; | |
279 | if (p->first+p->second <= i) return false; | |
280 | assert(p->first <= i && p->first+p->second > i); | |
281 | if (pstart) | |
282 | *pstart = p->first; | |
283 | if (plen) | |
284 | *plen = p->second; | |
285 | return true; | |
286 | } | |
287 | bool contains(T start, T len) const { | |
288 | typename map_t::const_iterator p = find_inc(start); | |
289 | if (p == m.end()) return false; | |
290 | if (p->first > start) return false; | |
291 | if (p->first+p->second <= start) return false; | |
292 | assert(p->first <= start && p->first+p->second > start); | |
293 | if (p->first+p->second < start+len) return false; | |
294 | return true; | |
295 | } | |
296 | bool intersects(T start, T len) const { | |
297 | btree_interval_set a; | |
298 | a.insert(start, len); | |
299 | btree_interval_set i; | |
300 | i.intersection_of( *this, a ); | |
301 | if (i.empty()) return false; | |
302 | return true; | |
303 | } | |
304 | ||
305 | // outer range of set | |
306 | bool empty() const { | |
307 | return m.empty(); | |
308 | } | |
309 | T range_start() const { | |
310 | assert(!empty()); | |
311 | typename map_t::const_iterator p = m.begin(); | |
312 | return p->first; | |
313 | } | |
314 | T range_end() const { | |
315 | assert(!empty()); | |
316 | typename map_t::const_iterator p = m.end(); | |
317 | p--; | |
318 | return p->first+p->second; | |
319 | } | |
320 | ||
321 | // interval start after p (where p not in set) | |
322 | bool starts_after(T i) const { | |
323 | assert(!contains(i)); | |
324 | typename map_t::const_iterator p = find_inc(i); | |
325 | if (p == m.end()) return false; | |
326 | return true; | |
327 | } | |
328 | T start_after(T i) const { | |
329 | assert(!contains(i)); | |
330 | typename map_t::const_iterator p = find_inc(i); | |
331 | return p->first; | |
332 | } | |
333 | ||
334 | // interval end that contains start | |
335 | T end_after(T start) const { | |
336 | assert(contains(start)); | |
337 | typename map_t::const_iterator p = find_inc(start); | |
338 | return p->first+p->second; | |
339 | } | |
340 | ||
341 | void insert(T val) { | |
342 | insert(val, 1); | |
343 | } | |
344 | ||
345 | void insert(T start, T len, T *pstart=0, T *plen=0) { | |
346 | //cout << "insert " << start << "~" << len << endl; | |
347 | assert(len > 0); | |
348 | _size += len; | |
349 | typename map_t::iterator p = find_adj_m(start); | |
350 | if (p == m.end()) { | |
351 | m[start] = len; // new interval | |
352 | if (pstart) | |
353 | *pstart = start; | |
354 | if (plen) | |
355 | *plen = len; | |
356 | } else { | |
357 | if (p->first < start) { | |
358 | ||
359 | if (p->first + p->second != start) { | |
360 | //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl; | |
361 | ceph_abort(); | |
362 | } | |
363 | ||
364 | p->second += len; // append to end | |
365 | ||
366 | typename map_t::iterator n = p; | |
367 | n++; | |
368 | if (pstart) | |
369 | *pstart = p->first; | |
370 | if (n != m.end() && | |
371 | start+len == n->first) { // combine with next, too! | |
372 | p->second += n->second; | |
373 | if (plen) | |
374 | *plen = p->second; | |
375 | m.erase(n); | |
376 | } else { | |
377 | if (plen) | |
378 | *plen = p->second; | |
379 | } | |
380 | } else { | |
381 | if (start+len == p->first) { | |
382 | if (pstart) | |
383 | *pstart = start; | |
384 | if (plen) | |
385 | *plen = len + p->second; | |
386 | T plen = p->second; | |
387 | m.erase(p); | |
388 | m[start] = len + plen; // append to front | |
389 | } else { | |
390 | assert(p->first > start+len); | |
391 | if (pstart) | |
392 | *pstart = start; | |
393 | if (plen) | |
394 | *plen = len; | |
395 | m[start] = len; // new interval | |
396 | } | |
397 | } | |
398 | } | |
399 | } | |
400 | ||
401 | void swap(btree_interval_set<T>& other) { | |
402 | m.swap(other.m); | |
403 | std::swap(_size, other._size); | |
404 | } | |
405 | ||
406 | void erase(iterator &i) { | |
407 | _size -= i.get_len(); | |
408 | assert(_size >= 0); | |
409 | m.erase(i._iter); | |
410 | } | |
411 | ||
412 | void erase(T val) { | |
413 | erase(val, 1); | |
414 | } | |
415 | ||
416 | void erase(T start, T len) { | |
417 | typename map_t::iterator p = find_inc_m(start); | |
418 | ||
419 | _size -= len; | |
420 | assert(_size >= 0); | |
421 | ||
422 | assert(p != m.end()); | |
423 | assert(p->first <= start); | |
424 | ||
425 | T before = start - p->first; | |
426 | assert(p->second >= before+len); | |
427 | T after = p->second - before - len; | |
428 | ||
429 | if (before) | |
430 | p->second = before; // shorten bit before | |
431 | else | |
432 | m.erase(p); | |
433 | if (after) | |
434 | m[start+len] = after; | |
435 | } | |
436 | ||
437 | ||
438 | void subtract(const btree_interval_set &a) { | |
439 | for (typename map_t::const_iterator p = a.m.begin(); | |
440 | p != a.m.end(); | |
441 | p++) | |
442 | erase(p->first, p->second); | |
443 | } | |
444 | ||
445 | void insert(const btree_interval_set &a) { | |
446 | for (typename map_t::const_iterator p = a.m.begin(); | |
447 | p != a.m.end(); | |
448 | p++) | |
449 | insert(p->first, p->second); | |
450 | } | |
451 | ||
452 | ||
453 | void intersection_of(const btree_interval_set &a, const btree_interval_set &b) { | |
454 | assert(&a != this); | |
455 | assert(&b != this); | |
456 | clear(); | |
457 | ||
458 | typename map_t::const_iterator pa = a.m.begin(); | |
459 | typename map_t::const_iterator pb = b.m.begin(); | |
460 | ||
461 | while (pa != a.m.end() && pb != b.m.end()) { | |
462 | // passing? | |
463 | if (pa->first + pa->second <= pb->first) | |
464 | { pa++; continue; } | |
465 | if (pb->first + pb->second <= pa->first) | |
466 | { pb++; continue; } | |
467 | T start = MAX(pa->first, pb->first); | |
468 | T en = MIN(pa->first+pa->second, pb->first+pb->second); | |
469 | assert(en > start); | |
470 | insert(start, en-start); | |
471 | if (pa->first+pa->second > pb->first+pb->second) | |
472 | pb++; | |
473 | else | |
474 | pa++; | |
475 | } | |
476 | } | |
477 | void intersection_of(const btree_interval_set& b) { | |
478 | btree_interval_set a; | |
479 | swap(a); | |
480 | intersection_of(a, b); | |
481 | } | |
482 | ||
483 | void union_of(const btree_interval_set &a, const btree_interval_set &b) { | |
484 | assert(&a != this); | |
485 | assert(&b != this); | |
486 | clear(); | |
487 | ||
488 | //cout << "union_of" << endl; | |
489 | ||
490 | // a | |
491 | m = a.m; | |
492 | _size = a._size; | |
493 | ||
494 | // - (a*b) | |
495 | btree_interval_set ab; | |
496 | ab.intersection_of(a, b); | |
497 | subtract(ab); | |
498 | ||
499 | // + b | |
500 | insert(b); | |
501 | return; | |
502 | } | |
503 | void union_of(const btree_interval_set &b) { | |
504 | btree_interval_set a; | |
505 | swap(a); | |
506 | union_of(a, b); | |
507 | } | |
508 | ||
509 | bool subset_of(const btree_interval_set &big) const { | |
510 | for (typename map_t::const_iterator i = m.begin(); | |
511 | i != m.end(); | |
512 | i++) | |
513 | if (!big.contains(i->first, i->second)) return false; | |
514 | return true; | |
515 | } | |
516 | ||
517 | /* | |
518 | * build a subset of @other, starting at or after @start, and including | |
519 | * @len worth of values, skipping holes. e.g., | |
520 | * span_of([5~10,20~5], 8, 5) -> [8~2,20~3] | |
521 | */ | |
522 | void span_of(const btree_interval_set &other, T start, T len) { | |
523 | clear(); | |
524 | typename map_t::const_iterator p = other.find_inc(start); | |
525 | if (p == other.m.end()) | |
526 | return; | |
527 | if (p->first < start) { | |
528 | if (p->first + p->second < start) | |
529 | return; | |
530 | if (p->first + p->second < start + len) { | |
531 | T howmuch = p->second - (start - p->first); | |
532 | insert(start, howmuch); | |
533 | len -= howmuch; | |
534 | p++; | |
535 | } else { | |
536 | insert(start, len); | |
537 | return; | |
538 | } | |
539 | } | |
540 | while (p != other.m.end() && len > 0) { | |
541 | if (p->second < len) { | |
542 | insert(p->first, p->second); | |
543 | len -= p->second; | |
544 | p++; | |
545 | } else { | |
546 | insert(p->first, len); | |
547 | return; | |
548 | } | |
549 | } | |
550 | } | |
551 | ||
552 | private: | |
553 | // data | |
554 | int64_t _size; | |
555 | map_t m; // map start -> len | |
556 | }; | |
557 | ||
558 | ||
181888fb FG |
559 | template<class T, class A> |
560 | inline std::ostream& operator<<(std::ostream& out, const btree_interval_set<T,A> &s) { | |
7c673cae FG |
561 | out << "["; |
562 | const char *prequel = ""; | |
181888fb | 563 | for (auto i = s.begin(); |
7c673cae FG |
564 | i != s.end(); |
565 | ++i) | |
566 | { | |
567 | out << prequel << i.get_start() << "~" << i.get_len(); | |
568 | prequel = ","; | |
569 | } | |
570 | out << "]"; | |
571 | return out; | |
572 | } | |
573 | ||
181888fb FG |
574 | template<class T,typename A> |
575 | inline void encode(const btree_interval_set<T,A>& s, bufferlist& bl) | |
7c673cae FG |
576 | { |
577 | s.encode(bl); | |
578 | } | |
181888fb FG |
579 | template<class T,typename A> |
580 | inline void decode(btree_interval_set<T,A>& s, bufferlist::iterator& p) | |
7c673cae FG |
581 | { |
582 | s.decode(p); | |
583 | } | |
584 | ||
585 | #endif |