]>
git.proxmox.com Git - ceph.git/blob - ceph/src/common/interval_map.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) 2016 Red Hat
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.
15 #ifndef INTERVAL_MAP_H
16 #define INTERVAL_MAP_H
18 #include "include/interval_set.h"
19 #include <initializer_list>
21 template <typename K
, typename V
, typename S
>
25 * Maps intervals to values. Erasing or inserting over an existing
26 * range will use S::operator() to split any overlapping existing
29 * Surprisingly, boost/icl/interval_map doesn't seem to be appropriate
30 * for this use case. The aggregation concept seems to assume
31 * commutativity, which doesn't work if we want more recent insertions
32 * to overwrite previous ones.
36 using map
= std::map
<K
, std::pair
<K
, V
> >;
37 using mapiter
= typename
std::map
<K
, std::pair
<K
, V
> >::iterator
;
38 using cmapiter
= typename
std::map
<K
, std::pair
<K
, V
> >::const_iterator
;
40 std::pair
<mapiter
, mapiter
> get_range(K off
, K len
) {
41 // fst is first iterator with end after off (may be end)
42 auto fst
= m
.upper_bound(off
);
45 if (fst
!= m
.end() && off
>= (fst
->first
+ fst
->second
.first
))
48 // lst is first iterator with start after off + len (may be end)
49 auto lst
= m
.lower_bound(off
+ len
);
50 return std::make_pair(fst
, lst
);
52 std::pair
<cmapiter
, cmapiter
> get_range(K off
, K len
) const {
53 // fst is first iterator with end after off (may be end)
54 auto fst
= m
.upper_bound(off
);
57 if (fst
!= m
.end() && off
>= (fst
->first
+ fst
->second
.first
))
60 // lst is first iterator with start after off + len (may be end)
61 auto lst
= m
.lower_bound(off
+ len
);
62 return std::make_pair(fst
, lst
);
64 void try_merge(mapiter niter
) {
65 if (niter
!= m
.begin()) {
68 if (prev
->first
+ prev
->second
.first
== niter
->first
&&
69 s
.can_merge(prev
->second
.second
, niter
->second
.second
)) {
71 std::move(prev
->second
.second
),
72 std::move(niter
->second
.second
));
74 K len
= niter
->first
+ niter
->second
.first
- off
;
80 std::make_pair(len
, std::move(n
))));
81 ceph_assert(p
.second
);
87 if (next
!= m
.end() &&
88 niter
->first
+ niter
->second
.first
== next
->first
&&
89 s
.can_merge(niter
->second
.second
, next
->second
.second
)) {
91 std::move(niter
->second
.second
),
92 std::move(next
->second
.second
));
94 K len
= next
->first
+ next
->second
.first
- off
;
100 std::make_pair(len
, std::move(n
))));
101 ceph_assert(p
.second
);
105 interval_map() = default;
106 interval_map(std::initializer_list
<typename
map::value_type
> l
) {
108 insert(v
.first
, v
.second
.first
, v
.second
.second
);
112 interval_map
intersect(K off
, K len
) const {
114 auto limits
= get_range(off
, len
);
115 for (auto i
= limits
.first
; i
!= limits
.second
; ++i
) {
117 K l
= i
->second
.first
;
118 V v
= i
->second
.second
;
122 v
= s
.split(off
- o
, l
, p
);
125 if ((o
+ l
) > (off
+ len
)) {
127 l
-= (o
+ l
) - (off
+ len
);
128 v
= s
.split(0, l
, p
);
137 void erase(K off
, K len
) {
140 auto range
= get_range(off
, len
);
146 for (auto i
= range
.first
; i
!= range
.second
; ++i
) {
147 if (i
->first
< off
) {
148 to_insert
.emplace_back(
153 s
.split(0, off
- i
->first
, i
->second
.second
))));
155 if ((off
+ len
) < (i
->first
+ i
->second
.first
)) {
156 K nlen
= (i
->first
+ i
->second
.first
) - (off
+ len
);
157 to_insert
.emplace_back(
162 s
.split(i
->second
.first
- nlen
, nlen
, i
->second
.second
))));
165 m
.erase(range
.first
, range
.second
);
166 m
.insert(to_insert
.begin(), to_insert
.end());
168 void insert(K off
, K len
, V
&&v
) {
169 ceph_assert(len
> 0);
170 ceph_assert(len
== s
.length(v
));
172 auto p
= m
.insert(make_pair(off
, std::make_pair(len
, std::forward
<V
>(v
))));
173 ceph_assert(p
.second
);
176 void insert(interval_map
&&other
) {
177 for (auto i
= other
.m
.begin();
179 other
.m
.erase(i
++)) {
180 insert(i
->first
, i
->second
.first
, std::move(i
->second
.second
));
183 void insert(K off
, K len
, const V
&v
) {
184 ceph_assert(len
> 0);
185 ceph_assert(len
== s
.length(v
));
187 auto p
= m
.insert(make_pair(off
, std::make_pair(len
, v
)));
188 ceph_assert(p
.second
);
191 void insert(const interval_map
&other
) {
192 for (auto &&i
: other
) {
193 insert(i
.get_off(), i
.get_len(), i
.get_val());
199 interval_set
<K
> get_interval_set() const {
201 for (auto &&i
: *this) {
202 ret
.insert(i
.get_off(), i
.get_len());
206 class const_iterator
{
208 const_iterator(cmapiter
&&it
) : it(std::move(it
)) {}
209 const_iterator(const cmapiter
&it
) : it(it
) {}
211 friend class interval_map
;
213 const_iterator(const const_iterator
&) = default;
214 const_iterator
&operator=(const const_iterator
&) = default;
216 const_iterator
&operator++() {
220 const_iterator
operator++(int) {
221 return const_iterator(it
++);
223 const_iterator
&operator--() {
227 const_iterator
operator--(int) {
228 return const_iterator(it
--);
230 bool operator==(const const_iterator
&rhs
) const {
233 bool operator!=(const const_iterator
&rhs
) const {
240 return it
->second
.first
;
242 const V
&get_val() const {
243 return it
->second
.second
;
245 const_iterator
&operator*() {
249 const_iterator
begin() const {
250 return const_iterator(m
.begin());
252 const_iterator
end() const {
253 return const_iterator(m
.end());
255 std::pair
<const_iterator
, const_iterator
> get_containing_range(
258 auto rng
= get_range(off
, len
);
259 return std::make_pair(const_iterator(rng
.first
), const_iterator(rng
.second
));
261 unsigned ext_count() const {
264 bool operator==(const interval_map
&rhs
) const {
268 std::ostream
&print(std::ostream
&out
) const {
271 for (auto &&i
: *this) {
277 out
<< i
.get_off() << "~" << i
.get_len() << "("
278 << s
.length(i
.get_val()) << ")";
284 template <typename K
, typename V
, typename S
>
285 std::ostream
&operator<<(std::ostream
&out
, const interval_map
<K
, V
, S
> &m
) {