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