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_INTERVAL_SET_H
17 #define CEPH_INTERVAL_SET_H
26 # define MIN(a,b) ((a)<=(b) ? (a):(b))
29 # define MAX(a,b) ((a)>=(b) ? (a):(b))
39 class iterator : public std::iterator <std::forward_iterator_tag, T>
42 explicit iterator(typename std::map<T,T>::iterator iter)
46 // For the copy constructor and assignment operator, the compiler-generated functions, which
47 // perform simple bitwise copying, should be fine.
49 bool operator==(const iterator& rhs) const {
50 return (_iter == rhs._iter);
53 bool operator!=(const iterator& rhs) const {
54 return (_iter != rhs._iter);
57 // Dereference this iterator to get a pair.
58 std::pair < T, T > &operator*() {
62 // Return the interval start.
67 // Return the interval length.
72 // Set the interval length.
78 iterator &operator++()
85 iterator operator++(int)
92 friend class interval_set<T>::const_iterator;
95 typename std::map<T,T>::iterator _iter;
96 friend class interval_set<T>;
99 class const_iterator : public std::iterator <std::forward_iterator_tag, T>
102 explicit const_iterator(typename std::map<T,T>::const_iterator iter)
106 const_iterator(const iterator &i)
110 // For the copy constructor and assignment operator, the compiler-generated functions, which
111 // perform simple bitwise copying, should be fine.
113 bool operator==(const const_iterator& rhs) const {
114 return (_iter == rhs._iter);
117 bool operator!=(const const_iterator& rhs) const {
118 return (_iter != rhs._iter);
121 // Dereference this iterator to get a pair.
122 std::pair < T, T > operator*() const {
126 // Return the interval start.
127 T get_start() const {
131 // Return the interval length.
133 return _iter->second;
137 const_iterator &operator++()
144 const_iterator operator++(int)
146 const_iterator prev(_iter);
152 typename std::map<T,T>::const_iterator _iter;
155 interval_set() : _size(0) {}
156 interval_set(std::map<T,T>& other) {
164 int num_intervals() const
169 typename interval_set<T>::iterator begin() {
170 return typename interval_set<T>::iterator(m.begin());
173 typename interval_set<T>::iterator lower_bound(T start) {
174 return typename interval_set<T>::iterator(find_inc_m(start));
177 typename interval_set<T>::iterator end() {
178 return typename interval_set<T>::iterator(m.end());
181 typename interval_set<T>::const_iterator begin() const {
182 return typename interval_set<T>::const_iterator(m.begin());
185 typename interval_set<T>::const_iterator lower_bound(T start) const {
186 return typename interval_set<T>::const_iterator(find_inc(start));
189 typename interval_set<T>::const_iterator end() const {
190 return typename interval_set<T>::const_iterator(m.end());
195 typename std::map<T,T>::const_iterator find_inc(T start) const {
196 typename std::map<T,T>::const_iterator p = m.lower_bound(start); // p->first >= start
197 if (p != m.begin() &&
198 (p == m.end() || p->first > start)) {
199 p--; // might overlap?
200 if (p->first + p->second <= start)
206 typename std::map<T,T>::iterator find_inc_m(T start) {
207 typename std::map<T,T>::iterator p = m.lower_bound(start);
208 if (p != m.begin() &&
209 (p == m.end() || p->first > start)) {
210 p--; // might overlap?
211 if (p->first + p->second <= start)
217 typename std::map<T,T>::const_iterator find_adj(T start) const {
218 typename std::map<T,T>::const_iterator p = m.lower_bound(start);
219 if (p != m.begin() &&
220 (p == m.end() || p->first > start)) {
222 if (p->first + p->second < start)
228 typename std::map<T,T>::iterator find_adj_m(T start) {
229 typename std::map<T,T>::iterator p = m.lower_bound(start);
230 if (p != m.begin() &&
231 (p == m.end() || p->first > start)) {
233 if (p->first + p->second < start)
240 bool operator==(const interval_set& other) const {
241 return _size == other._size && m == other.m;
244 int64_t size() const {
248 void bound_encode(size_t& p) const {
249 denc_traits<std::map<T,T>>::bound_encode(m, p);
251 void encode(bufferlist::contiguous_appender& p) const {
254 void decode(bufferptr::iterator& p) {
257 for (const auto& i : m) {
261 void decode(bufferlist::iterator& p) {
264 for (const auto& i : m) {
269 void encode_nohead(bufferlist::contiguous_appender& p) const {
270 denc_traits<std::map<T,T>>::encode_nohead(m, p);
272 void decode_nohead(int n, bufferptr::iterator& p) {
273 denc_traits<std::map<T,T>>::decode_nohead(n, m, p);
275 for (const auto& i : m) {
285 bool contains(T i, T *pstart=0, T *plen=0) const {
286 typename std::map<T,T>::const_iterator p = find_inc(i);
287 if (p == m.end()) return false;
288 if (p->first > i) return false;
289 if (p->first+p->second <= i) return false;
290 assert(p->first <= i && p->first+p->second > i);
297 bool contains(T start, T len) const {
298 typename std::map<T,T>::const_iterator p = find_inc(start);
299 if (p == m.end()) return false;
300 if (p->first > start) return false;
301 if (p->first+p->second <= start) return false;
302 assert(p->first <= start && p->first+p->second > start);
303 if (p->first+p->second < start+len) return false;
306 bool intersects(T start, T len) const {
308 a.insert(start, len);
310 i.intersection_of( *this, a );
311 if (i.empty()) return false;
315 // outer range of set
319 T range_start() const {
321 typename std::map<T,T>::const_iterator p = m.begin();
324 T range_end() const {
326 typename std::map<T,T>::const_iterator p = m.end();
328 return p->first+p->second;
331 // interval start after p (where p not in set)
332 bool starts_after(T i) const {
333 assert(!contains(i));
334 typename std::map<T,T>::const_iterator p = find_inc(i);
335 if (p == m.end()) return false;
338 T start_after(T i) const {
339 assert(!contains(i));
340 typename std::map<T,T>::const_iterator p = find_inc(i);
344 // interval end that contains start
345 T end_after(T start) const {
346 assert(contains(start));
347 typename std::map<T,T>::const_iterator p = find_inc(start);
348 return p->first+p->second;
355 void insert(T start, T len, T *pstart=0, T *plen=0) {
356 //cout << "insert " << start << "~" << len << endl;
359 typename std::map<T,T>::iterator p = find_adj_m(start);
361 m[start] = len; // new interval
367 if (p->first < start) {
369 if (p->first + p->second != start) {
370 //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
374 p->second += len; // append to end
376 typename std::map<T,T>::iterator n = p;
379 start+len == n->first) { // combine with next, too!
380 p->second += n->second;
388 if (start+len == p->first) {
389 m[start] = len + p->second; // append to front
393 *plen = len + p->second;
396 assert(p->first > start+len);
397 m[start] = len; // new interval
407 void swap(interval_set<T>& other) {
409 std::swap(_size, other._size);
412 void erase(iterator &i) {
413 _size -= i.get_len();
422 void erase(T start, T len) {
423 typename std::map<T,T>::iterator p = find_inc_m(start);
428 assert(p != m.end());
429 assert(p->first <= start);
431 T before = start - p->first;
432 assert(p->second >= before+len);
433 T after = p->second - before - len;
436 p->second = before; // shorten bit before
440 m[start+len] = after;
444 void subtract(const interval_set &a) {
445 for (typename std::map<T,T>::const_iterator p = a.m.begin();
448 erase(p->first, p->second);
451 void insert(const interval_set &a) {
452 for (typename std::map<T,T>::const_iterator p = a.m.begin();
455 insert(p->first, p->second);
459 void intersection_of(const interval_set &a, const interval_set &b) {
464 typename std::map<T,T>::const_iterator pa = a.m.begin();
465 typename std::map<T,T>::const_iterator pb = b.m.begin();
466 typename decltype(m)::iterator mi = m.begin();
468 while (pa != a.m.end() && pb != b.m.end()) {
470 if (pa->first + pa->second <= pb->first)
472 if (pb->first + pb->second <= pa->first)
477 mi = m.insert(mi, *pa);
481 } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
485 T start = MAX(pa->first, pb->first);
486 T en = MIN(pa->first+pa->second, pb->first+pb->second);
488 typename decltype(m)::value_type i{start, en - start};
489 mi = m.insert(mi, i);
491 if (pa->first+pa->second > pb->first+pb->second)
497 void intersection_of(const interval_set& b) {
500 intersection_of(a, b);
503 void union_of(const interval_set &a, const interval_set &b) {
508 //cout << "union_of" << endl;
516 ab.intersection_of(a, b);
523 void union_of(const interval_set &b) {
528 void union_insert(T off, T len) {
534 bool subset_of(const interval_set &big) const {
535 for (typename std::map<T,T>::const_iterator i = m.begin();
538 if (!big.contains(i->first, i->second)) return false;
543 * build a subset of @other, starting at or after @start, and including
544 * @len worth of values, skipping holes. e.g.,
545 * span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
547 void span_of(const interval_set &other, T start, T len) {
549 typename std::map<T,T>::const_iterator p = other.find_inc(start);
550 if (p == other.m.end())
552 if (p->first < start) {
553 if (p->first + p->second < start)
555 if (p->first + p->second < start + len) {
556 T howmuch = p->second - (start - p->first);
557 insert(start, howmuch);
565 while (p != other.m.end() && len > 0) {
566 if (p->second < len) {
567 insert(p->first, p->second);
571 insert(p->first, len);
578 * Move contents of m into another std::map<T,T>. Use that instead of
579 * encoding interval_set into bufferlist then decoding it back into std::map.
581 void move_into(std::map<T,T>& other) {
582 other = std::move(m);
588 std::map<T,T> m; // map start -> len
591 // declare traits explicitly because (1) it's templatized, and (2) we
592 // want to include _nohead variants.
594 struct denc_traits<interval_set<T>> {
595 static constexpr bool supported = true;
596 static constexpr bool bounded = false;
597 static constexpr bool featured = false;
598 static constexpr bool need_contiguous = denc_traits<T>::need_contiguous;
599 static void bound_encode(const interval_set<T>& v, size_t& p) {
602 static void encode(const interval_set<T>& v,
603 bufferlist::contiguous_appender& p) {
606 static void decode(interval_set<T>& v, bufferptr::iterator& p) {
609 template<typename U=T>
610 static typename std::enable_if<sizeof(U) && !need_contiguous>::type
611 decode(interval_set<T>& v, bufferlist::iterator& p) {
614 static void encode_nohead(const interval_set<T>& v,
615 bufferlist::contiguous_appender& p) {
618 static void decode_nohead(size_t n, interval_set<T>& v,
619 bufferptr::iterator& p) {
620 v.decode_nohead(n, p);
626 inline std::ostream& operator<<(std::ostream& out, const interval_set<T> &s) {
628 const char *prequel = "";
629 for (typename interval_set<T>::const_iterator i = s.begin();
633 out << prequel << i.get_start() << "~" << i.get_len();