]>
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
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();
467 while (pa
!= a
.m
.end() && pb
!= b
.m
.end()) {
469 if (pa
->first
+ pa
->second
<= pb
->first
)
471 if (pb
->first
+ pb
->second
<= pa
->first
)
473 T start
= MAX(pa
->first
, pb
->first
);
474 T en
= MIN(pa
->first
+pa
->second
, pb
->first
+pb
->second
);
476 insert(start
, en
-start
);
477 if (pa
->first
+pa
->second
> pb
->first
+pb
->second
)
483 void intersection_of(const interval_set
& b
) {
486 intersection_of(a
, b
);
489 void union_of(const interval_set
&a
, const interval_set
&b
) {
494 //cout << "union_of" << endl;
502 ab
.intersection_of(a
, b
);
509 void union_of(const interval_set
&b
) {
514 void union_insert(T off
, T len
) {
520 bool subset_of(const interval_set
&big
) const {
521 for (typename
std::map
<T
,T
>::const_iterator i
= m
.begin();
524 if (!big
.contains(i
->first
, i
->second
)) return false;
529 * build a subset of @other, starting at or after @start, and including
530 * @len worth of values, skipping holes. e.g.,
531 * span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
533 void span_of(const interval_set
&other
, T start
, T len
) {
535 typename
std::map
<T
,T
>::const_iterator p
= other
.find_inc(start
);
536 if (p
== other
.m
.end())
538 if (p
->first
< start
) {
539 if (p
->first
+ p
->second
< start
)
541 if (p
->first
+ p
->second
< start
+ len
) {
542 T howmuch
= p
->second
- (start
- p
->first
);
543 insert(start
, howmuch
);
551 while (p
!= other
.m
.end() && len
> 0) {
552 if (p
->second
< len
) {
553 insert(p
->first
, p
->second
);
557 insert(p
->first
, len
);
564 * Move contents of m into another std::map<T,T>. Use that instead of
565 * encoding interval_set into bufferlist then decoding it back into std::map.
567 void move_into(std::map
<T
,T
>& other
) {
568 other
= std::move(m
);
574 std::map
<T
,T
> m
; // map start -> len
577 // declare traits explicitly because (1) it's templatized, and (2) we
578 // want to include _nohead variants.
580 struct denc_traits
<interval_set
<T
>> {
581 static constexpr bool supported
= true;
582 static constexpr bool bounded
= false;
583 static constexpr bool featured
= false;
584 static constexpr bool need_contiguous
= denc_traits
<T
>::need_contiguous
;
585 static void bound_encode(const interval_set
<T
>& v
, size_t& p
) {
588 static void encode(const interval_set
<T
>& v
,
589 bufferlist::contiguous_appender
& p
) {
592 static void decode(interval_set
<T
>& v
, bufferptr::iterator
& p
) {
595 template<typename U
=T
>
596 static typename
std::enable_if
<sizeof(U
) && !need_contiguous
>::type
597 decode(interval_set
<T
>& v
, bufferlist::iterator
& p
) {
600 static void encode_nohead(const interval_set
<T
>& v
,
601 bufferlist::contiguous_appender
& p
) {
604 static void decode_nohead(size_t n
, interval_set
<T
>& v
,
605 bufferptr::iterator
& p
) {
606 v
.decode_nohead(n
, p
);
612 inline std::ostream
& operator<<(std::ostream
& out
, const interval_set
<T
> &s
) {
614 const char *prequel
= "";
615 for (typename interval_set
<T
>::const_iterator i
= s
.begin();
619 out
<< prequel
<< i
.get_start() << "~" << i
.get_len();