]>
git.proxmox.com Git - ceph.git/blob - ceph/src/include/interval_set.h
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
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).
34 # define MIN(a,b) ((a)<=(b) ? (a):(b))
37 # define MAX(a,b) ((a)>=(b) ? (a):(b))
41 template<typename T
, typename Map
= std::map
<T
,T
>>
47 class iterator
: public std::iterator
<std::forward_iterator_tag
, T
>
50 explicit iterator(typename
Map::iterator iter
)
54 // For the copy constructor and assignment operator, the compiler-generated functions, which
55 // perform simple bitwise copying, should be fine.
57 bool operator==(const iterator
& rhs
) const {
58 return (_iter
== rhs
._iter
);
61 bool operator!=(const iterator
& rhs
) const {
62 return (_iter
!= rhs
._iter
);
65 // Dereference this iterator to get a pair.
66 std::pair
< T
, T
> &operator*() {
70 // Return the interval start.
75 // Return the interval length.
80 // Set the interval length.
86 iterator
&operator++()
93 iterator
operator++(int)
100 friend class interval_set
<T
,Map
>::const_iterator
;
103 typename
Map::iterator _iter
;
104 friend class interval_set
<T
,Map
>;
107 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, T
>
110 explicit const_iterator(typename
Map::const_iterator iter
)
114 const_iterator(const iterator
&i
)
118 // For the copy constructor and assignment operator, the compiler-generated functions, which
119 // perform simple bitwise copying, should be fine.
121 bool operator==(const const_iterator
& rhs
) const {
122 return (_iter
== rhs
._iter
);
125 bool operator!=(const const_iterator
& rhs
) const {
126 return (_iter
!= rhs
._iter
);
129 // Dereference this iterator to get a pair.
130 std::pair
< T
, T
> operator*() const {
134 // Return the interval start.
135 T
get_start() const {
139 // Return the interval length.
141 return _iter
->second
;
145 const_iterator
&operator++()
152 const_iterator
operator++(int)
154 const_iterator
prev(_iter
);
160 typename
Map::const_iterator _iter
;
163 interval_set() : _size(0) {}
164 interval_set(Map
& other
) {
172 int num_intervals() const
177 typename interval_set
<T
,Map
>::iterator
begin() {
178 return typename interval_set
<T
,Map
>::iterator(m
.begin());
181 typename interval_set
<T
,Map
>::iterator
lower_bound(T start
) {
182 return typename interval_set
<T
,Map
>::iterator(find_inc_m(start
));
185 typename interval_set
<T
,Map
>::iterator
end() {
186 return typename interval_set
<T
,Map
>::iterator(m
.end());
189 typename interval_set
<T
,Map
>::const_iterator
begin() const {
190 return typename interval_set
<T
,Map
>::const_iterator(m
.begin());
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
));
197 typename interval_set
<T
,Map
>::const_iterator
end() const {
198 return typename interval_set
<T
,Map
>::const_iterator(m
.end());
203 typename
Map::const_iterator
find_inc(T start
) const {
204 typename
Map::const_iterator p
= m
.lower_bound(start
); // p->first >= start
205 if (p
!= m
.begin() &&
206 (p
== m
.end() || p
->first
> start
)) {
207 p
--; // might overlap?
208 if (p
->first
+ p
->second
<= start
)
214 typename
Map::iterator
find_inc_m(T start
) {
215 typename
Map::iterator p
= m
.lower_bound(start
);
216 if (p
!= m
.begin() &&
217 (p
== m
.end() || p
->first
> start
)) {
218 p
--; // might overlap?
219 if (p
->first
+ p
->second
<= start
)
225 typename
Map::const_iterator
find_adj(T start
) const {
226 typename
Map::const_iterator p
= m
.lower_bound(start
);
227 if (p
!= m
.begin() &&
228 (p
== m
.end() || p
->first
> start
)) {
230 if (p
->first
+ p
->second
< start
)
236 typename
Map::iterator
find_adj_m(T start
) {
237 typename
Map::iterator p
= m
.lower_bound(start
);
238 if (p
!= m
.begin() &&
239 (p
== m
.end() || p
->first
> start
)) {
241 if (p
->first
+ p
->second
< start
)
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
;
252 typename
decltype(m
)::iterator mi
= m
.begin();
258 assert(offset
> prev_offset
);
259 pl
= l
.find_inc(offset
);
260 prev_offset
= offset
;
263 while (ps
!= s
.m
.end() && ps
->first
+ ps
->second
<= pl
->first
)
267 offset
= pl
->first
+ pl
->second
;
268 if (offset
<= ps
->first
) {
275 mi
= m
.insert(mi
, *ps
);
279 } while (ps
!= s
.m
.end() && pl
!= l
.m
.end() && *ps
== *pl
);
286 T start
= std::max
<T
>(ps
->first
, pl
->first
);
287 T en
= std::min
<T
>(ps
->first
+ ps
->second
, offset
);
289 typename
decltype(m
)::value_type i
{start
, en
- start
};
290 mi
= m
.insert(mi
, i
);
292 if (ps
->first
+ ps
->second
<= offset
) {
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();
305 while (pa
!= a_end
&& pb
!= b_end
) {
306 while (pb
->first
+ pb
->second
<= pa
->first
) {
316 } while (pa
!= a_end
&& pb
!= b_end
&& *pa
== *pb
);
320 // interval begins before other
321 if (pa
->first
< pb
->first
)
323 // interval is longer than other
324 if (pa
->first
+ pa
->second
> pb
->first
+ pb
->second
)
334 bool operator==(const interval_set
& other
) const {
335 return _size
== other
._size
&& m
== other
.m
;
338 int64_t size() const {
342 void bound_encode(size_t& p
) const {
343 denc_traits
<Map
>::bound_encode(m
, p
);
345 void encode(bufferlist::contiguous_appender
& p
) const {
348 void decode(bufferptr::iterator
& p
) {
351 for (const auto& i
: m
) {
355 void decode(bufferlist::iterator
& p
) {
358 for (const auto& i
: m
) {
363 void encode_nohead(bufferlist::contiguous_appender
& p
) const {
364 denc_traits
<Map
>::encode_nohead(m
, p
);
366 void decode_nohead(int n
, bufferptr::iterator
& p
) {
367 denc_traits
<Map
>::decode_nohead(n
, m
, p
);
369 for (const auto& i
: m
) {
379 bool contains(T i
, T
*pstart
=0, T
*plen
=0) const {
380 typename
Map::const_iterator p
= find_inc(i
);
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
);
391 bool contains(T start
, T len
) const {
392 typename
Map::const_iterator p
= find_inc(start
);
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;
400 bool intersects(T start
, T len
) const {
402 a
.insert(start
, len
);
404 i
.intersection_of( *this, a
);
405 if (i
.empty()) return false;
409 // outer range of set
413 T
range_start() const {
415 typename
Map::const_iterator p
= m
.begin();
418 T
range_end() const {
420 typename
Map::const_iterator p
= m
.end();
422 return p
->first
+p
->second
;
425 // interval start after p (where p not in set)
426 bool starts_after(T i
) const {
427 assert(!contains(i
));
428 typename
Map::const_iterator p
= find_inc(i
);
429 if (p
== m
.end()) return false;
432 T
start_after(T i
) const {
433 assert(!contains(i
));
434 typename
Map::const_iterator p
= find_inc(i
);
438 // interval end that contains start
439 T
end_after(T start
) const {
440 assert(contains(start
));
441 typename
Map::const_iterator p
= find_inc(start
);
442 return p
->first
+p
->second
;
449 void insert(T start
, T len
, T
*pstart
=0, T
*plen
=0) {
450 //cout << "insert " << start << "~" << len << endl;
453 typename
Map::iterator p
= find_adj_m(start
);
455 m
[start
] = len
; // new interval
461 if (p
->first
< start
) {
463 if (p
->first
+ p
->second
!= start
) {
464 //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
468 p
->second
+= len
; // append to end
470 typename
Map::iterator n
= p
;
475 start
+len
== n
->first
) { // combine with next, too!
476 p
->second
+= n
->second
;
485 if (start
+len
== p
->first
) {
489 *plen
= len
+ p
->second
;
490 T psecond
= p
->second
;
492 m
[start
] = len
+ psecond
; // append to front
494 assert(p
->first
> start
+len
);
499 m
[start
] = len
; // new interval
505 void swap(interval_set
<T
,Map
>& other
) {
507 std::swap(_size
, other
._size
);
510 void erase(iterator
&i
) {
511 _size
-= i
.get_len();
520 void erase(T start
, T len
,
521 std::function
<bool(T
, T
)> post_process
= {}) {
522 typename
Map::iterator p
= find_inc_m(start
);
527 assert(p
!= m
.end());
528 assert(p
->first
<= start
);
530 T before
= start
- p
->first
;
531 assert(p
->second
>= before
+len
);
532 T after
= p
->second
- before
- len
;
533 if (before
&& (post_process
? post_process(p
->first
, before
) : true)) {
534 p
->second
= before
; // shorten bit before
538 if (after
&& (post_process
? post_process(start
+ len
, after
) : true)) {
539 m
[start
+ len
] = after
;
543 void subtract(const interval_set
&a
) {
544 for (typename
Map::const_iterator p
= a
.m
.begin();
547 erase(p
->first
, p
->second
);
550 void insert(const interval_set
&a
) {
551 for (typename
Map::const_iterator p
= a
.m
.begin();
554 insert(p
->first
, p
->second
);
558 void intersection_of(const interval_set
&a
, const interval_set
&b
) {
563 const interval_set
*s
, *l
;
565 if (a
.size() < b
.size()) {
577 * Use the lower_bound algorithm for larger size ratios
578 * where it performs better, but not for smaller size
579 * ratios where sequential search performs better.
581 if (l
->size() / s
->size() >= 10) {
582 intersection_size_asym(*s
, *l
);
586 typename
Map::const_iterator pa
= a
.m
.begin();
587 typename
Map::const_iterator pb
= b
.m
.begin();
588 typename
decltype(m
)::iterator mi
= m
.begin();
590 while (pa
!= a
.m
.end() && pb
!= b
.m
.end()) {
592 if (pa
->first
+ pa
->second
<= pb
->first
)
594 if (pb
->first
+ pb
->second
<= pa
->first
)
599 mi
= m
.insert(mi
, *pa
);
603 } while (pa
!= a
.m
.end() && pb
!= b
.m
.end() && *pa
== *pb
);
607 T start
= MAX(pa
->first
, pb
->first
);
608 T en
= MIN(pa
->first
+pa
->second
, pb
->first
+pb
->second
);
610 typename
decltype(m
)::value_type i
{start
, en
- start
};
611 mi
= m
.insert(mi
, i
);
613 if (pa
->first
+pa
->second
> pb
->first
+pb
->second
)
619 void intersection_of(const interval_set
& b
) {
622 intersection_of(a
, b
);
625 void union_of(const interval_set
&a
, const interval_set
&b
) {
630 //cout << "union_of" << endl;
638 ab
.intersection_of(a
, b
);
645 void union_of(const interval_set
&b
) {
650 void union_insert(T off
, T len
) {
656 bool subset_of(const interval_set
&big
) const {
659 if (size() > big
.size())
661 if (range_end() > big
.range_end())
665 * Use the lower_bound algorithm for larger size ratios
666 * where it performs better, but not for smaller size
667 * ratios where sequential search performs better.
669 if (big
.size() / size() < 10)
670 return subset_size_sym(big
);
672 for (typename
Map::const_iterator i
= m
.begin();
675 if (!big
.contains(i
->first
, i
->second
)) return false;
680 * build a subset of @other for given rage [@start, @end)
682 * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5]
683 * subset_of([5~10,20~5], 5, 25) -> [5~10,20~5]
684 * subset_of([5~10,20~5], 1, 10) -> [5~5]
685 * subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4]
687 void subset_of(const interval_set
&other
, T start
, T end
) {
688 assert(end
>= start
);
693 typename
Map::const_iterator p
= other
.find_inc(start
);
694 if (p
== other
.m
.end())
696 if (p
->first
< start
) {
697 if (p
->first
+ p
->second
>= end
) {
698 insert(start
, end
- start
);
701 insert(start
, p
->first
+ p
->second
- start
);
705 while (p
!= other
.m
.end()) {
706 assert(p
->first
>= start
);
707 if (p
->first
>= end
) {
710 if (p
->first
+ p
->second
>= end
) {
711 insert(p
->first
, end
- p
->first
);
715 insert(p
->first
, p
->second
);
722 * build a subset of @other, starting at or after @start, and including
723 * @len worth of values, skipping holes. e.g.,
724 * span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
726 void span_of(const interval_set
&other
, T start
, T len
) {
728 typename
Map::const_iterator p
= other
.find_inc(start
);
729 if (p
== other
.m
.end())
731 if (p
->first
< start
) {
732 if (p
->first
+ p
->second
< start
)
734 if (p
->first
+ p
->second
< start
+ len
) {
735 T howmuch
= p
->second
- (start
- p
->first
);
736 insert(start
, howmuch
);
744 while (p
!= other
.m
.end() && len
> 0) {
745 if (p
->second
< len
) {
746 insert(p
->first
, p
->second
);
750 insert(p
->first
, len
);
757 * Move contents of m into another Map. Use that instead of
758 * encoding interval_set into bufferlist then decoding it back into Map.
760 void move_into(Map
& other
) {
761 other
= std::move(m
);
767 Map m
; // map start -> len
770 // declare traits explicitly because (1) it's templatized, and (2) we
771 // want to include _nohead variants.
772 template<typename T
, typename Map
>
773 struct denc_traits
<interval_set
<T
,Map
>> {
774 static constexpr bool supported
= true;
775 static constexpr bool bounded
= false;
776 static constexpr bool featured
= false;
777 static constexpr bool need_contiguous
= denc_traits
<T
,Map
>::need_contiguous
;
778 static void bound_encode(const interval_set
<T
,Map
>& v
, size_t& p
) {
781 static void encode(const interval_set
<T
,Map
>& v
,
782 bufferlist::contiguous_appender
& p
) {
785 static void decode(interval_set
<T
,Map
>& v
, bufferptr::iterator
& p
) {
788 template<typename U
=T
>
789 static typename
std::enable_if
<sizeof(U
) && !need_contiguous
>::type
790 decode(interval_set
<T
,Map
>& v
, bufferlist::iterator
& p
) {
793 static void encode_nohead(const interval_set
<T
,Map
>& v
,
794 bufferlist::contiguous_appender
& p
) {
797 static void decode_nohead(size_t n
, interval_set
<T
,Map
>& v
,
798 bufferptr::iterator
& p
) {
799 v
.decode_nohead(n
, p
);
804 template<class T
, typename Map
>
805 inline std::ostream
& operator<<(std::ostream
& out
, const interval_set
<T
,Map
> &s
) {
807 const char *prequel
= "";
808 for (typename interval_set
<T
,Map
>::const_iterator i
= s
.begin();
812 out
<< prequel
<< i
.get_start() << "~" << i
.get_len();