1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
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.
16 #ifndef CEPH_BTREE_INTERVAL_SET_H
17 #define CEPH_BTREE_INTERVAL_SET_H
26 # define MIN(a,b) ((a)<=(b) ? (a):(b))
29 # define MAX(a,b) ((a)>=(b) ? (a):(b))
32 #include "cpp-btree/btree_map.h"
34 #include "encoding_btree.h"
37 typename Alloc = std::allocator<std::pair<const T, T>>>
38 class btree_interval_set {
41 typedef btree::btree_map<T,T, std::less<T>, Alloc> map_t;
45 class iterator : public std::iterator <std::forward_iterator_tag, T>
48 explicit iterator(typename map_t::iterator iter)
52 // For the copy constructor and assignment operator, the compiler-generated functions, which
53 // perform simple bitwise copying, should be fine.
55 bool operator==(const iterator& rhs) const {
56 return (_iter == rhs._iter);
59 bool operator!=(const iterator& rhs) const {
60 return (_iter != rhs._iter);
63 // Dereference this iterator to get a pair.
64 std::pair < T, T > &operator*() {
68 // Return the interval start.
73 // Return the interval length.
78 // Set the interval length.
84 iterator &operator++()
91 iterator operator++(int)
98 friend class btree_interval_set<T>::const_iterator;
101 typename map_t::iterator _iter;
102 friend class btree_interval_set<T>;
105 class const_iterator : public std::iterator <std::forward_iterator_tag, T>
108 explicit const_iterator(typename map_t::const_iterator iter)
112 const_iterator(const iterator &i)
116 // For the copy constructor and assignment operator, the compiler-generated functions, which
117 // perform simple bitwise copying, should be fine.
119 bool operator==(const const_iterator& rhs) const {
120 return (_iter == rhs._iter);
123 bool operator!=(const const_iterator& rhs) const {
124 return (_iter != rhs._iter);
127 // Dereference this iterator to get a pair.
128 std::pair < T, T > operator*() const {
132 // Return the interval start.
133 T get_start() const {
137 // Return the interval length.
139 return _iter->second;
143 const_iterator &operator++()
150 const_iterator operator++(int)
152 const_iterator prev(_iter);
158 typename map_t::const_iterator _iter;
161 btree_interval_set() : _size(0) {}
163 int num_intervals() const
168 typename btree_interval_set<T,Alloc>::iterator begin() {
169 return typename btree_interval_set<T,Alloc>::iterator(m.begin());
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));
176 typename btree_interval_set<T,Alloc>::iterator end() {
177 return typename btree_interval_set<T,Alloc>::iterator(m.end());
180 typename btree_interval_set<T,Alloc>::const_iterator begin() const {
181 return typename btree_interval_set<T,Alloc>::const_iterator(m.begin());
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));
188 typename btree_interval_set<T,Alloc>::const_iterator end() const {
189 return typename btree_interval_set<T,Alloc>::const_iterator(m.end());
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)
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)
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)) {
221 if (p->first + p->second < start)
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)) {
232 if (p->first + p->second < start)
239 bool operator==(const btree_interval_set& other) const {
240 return _size == other._size && m == other.m;
243 int64_t size() const {
247 void encode(bufferlist& bl) const {
250 void encode_nohead(bufferlist& bl) const {
251 ::encode_nohead(m, bl);
253 void decode(bufferlist::iterator& bl) {
256 for (typename map_t::const_iterator p = m.begin();
261 void decode_nohead(int n, bufferlist::iterator& bl) {
262 ::decode_nohead(n, m, bl);
264 for (typename map_t::const_iterator p = m.begin();
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);
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;
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;
305 // outer range of set
309 T range_start() const {
311 typename map_t::const_iterator p = m.begin();
314 T range_end() const {
316 typename map_t::const_iterator p = m.end();
318 return p->first+p->second;
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;
328 T start_after(T i) const {
329 assert(!contains(i));
330 typename map_t::const_iterator p = find_inc(i);
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;
345 void insert(T start, T len, T *pstart=0, T *plen=0) {
346 //cout << "insert " << start << "~" << len << endl;
349 typename map_t::iterator p = find_adj_m(start);
351 m[start] = len; // new interval
357 if (p->first < start) {
359 if (p->first + p->second != start) {
360 //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
364 p->second += len; // append to end
366 typename map_t::iterator n = p;
371 start+len == n->first) { // combine with next, too!
372 p->second += n->second;
381 if (start+len == p->first) {
385 *plen = len + p->second;
388 m[start] = len + plen; // append to front
390 assert(p->first > start+len);
395 m[start] = len; // new interval
401 void swap(btree_interval_set<T>& other) {
403 std::swap(_size, other._size);
406 void erase(iterator &i) {
407 _size -= i.get_len();
416 void erase(T start, T len) {
417 typename map_t::iterator p = find_inc_m(start);
422 assert(p != m.end());
423 assert(p->first <= start);
425 T before = start - p->first;
426 assert(p->second >= before+len);
427 T after = p->second - before - len;
430 p->second = before; // shorten bit before
434 m[start+len] = after;
438 void subtract(const btree_interval_set &a) {
439 for (typename map_t::const_iterator p = a.m.begin();
442 erase(p->first, p->second);
445 void insert(const btree_interval_set &a) {
446 for (typename map_t::const_iterator p = a.m.begin();
449 insert(p->first, p->second);
453 void intersection_of(const btree_interval_set &a, const btree_interval_set &b) {
458 typename map_t::const_iterator pa = a.m.begin();
459 typename map_t::const_iterator pb = b.m.begin();
461 while (pa != a.m.end() && pb != b.m.end()) {
463 if (pa->first + pa->second <= pb->first)
465 if (pb->first + pb->second <= pa->first)
467 T start = MAX(pa->first, pb->first);
468 T en = MIN(pa->first+pa->second, pb->first+pb->second);
470 insert(start, en-start);
471 if (pa->first+pa->second > pb->first+pb->second)
477 void intersection_of(const btree_interval_set& b) {
478 btree_interval_set a;
480 intersection_of(a, b);
483 void union_of(const btree_interval_set &a, const btree_interval_set &b) {
488 //cout << "union_of" << endl;
495 btree_interval_set ab;
496 ab.intersection_of(a, b);
503 void union_of(const btree_interval_set &b) {
504 btree_interval_set a;
509 bool subset_of(const btree_interval_set &big) const {
510 for (typename map_t::const_iterator i = m.begin();
513 if (!big.contains(i->first, i->second)) return false;
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]
522 void span_of(const btree_interval_set &other, T start, T len) {
524 typename map_t::const_iterator p = other.find_inc(start);
525 if (p == other.m.end())
527 if (p->first < start) {
528 if (p->first + p->second < start)
530 if (p->first + p->second < start + len) {
531 T howmuch = p->second - (start - p->first);
532 insert(start, howmuch);
540 while (p != other.m.end() && len > 0) {
541 if (p->second < len) {
542 insert(p->first, p->second);
546 insert(p->first, len);
555 map_t m; // map start -> len
559 template<class T, class A>
560 inline std::ostream& operator<<(std::ostream& out, const btree_interval_set<T,A> &s) {
562 const char *prequel = "";
563 for (auto i = s.begin();
567 out << prequel << i.get_start() << "~" << i.get_len();
574 template<class T,typename A>
575 inline void encode(const btree_interval_set<T,A>& s, bufferlist& bl)
579 template<class T,typename A>
580 inline void decode(btree_interval_set<T,A>& s, bufferlist::iterator& p)