template<typename T, typename Map = std::map<T,T>>
class interval_set {
public:
- using value_type = T;
+ using value_type = typename Map::value_type;
+ using offset_type = T;
+ using length_type = T;
+ using reference = value_type&;
+ using const_reference = const value_type&;
+ using size_type = typename Map::size_type;
class const_iterator;
}
// Dereference this iterator to get a pair.
- std::pair < T, T > &operator*() {
- return *_iter;
+ reference operator*() const {
+ return *_iter;
}
// Return the interval start.
- T get_start() const {
- return _iter->first;
+ offset_type get_start() const {
+ return _iter->first;
}
// Return the interval length.
- T get_len() const {
- return _iter->second;
+ length_type get_len() const {
+ return _iter->second;
}
- T get_end() const {
- return _iter->first + _iter->second;
+
+ offset_type get_end() const {
+ return _iter->first + _iter->second;
}
// Set the interval length.
- void set_len(T len) {
- _iter->second = len;
+ void set_len(const length_type& len) {
+ _iter->second = len;
}
// Preincrement
- iterator &operator++()
+ iterator& operator++()
{
- ++_iter;
- return *this;
+ ++_iter;
+ return *this;
}
// Postincrement
iterator operator++(int)
{
- iterator prev(_iter);
- ++_iter;
- return prev;
+ iterator prev(_iter);
+ ++_iter;
+ return prev;
}
- friend class interval_set<T,Map>::const_iterator;
+ friend class interval_set::const_iterator;
protected:
typename Map::iterator _iter;
- friend class interval_set<T,Map>;
+ friend class interval_set;
};
class const_iterator : public std::iterator <std::forward_iterator_tag, T>
}
// Dereference this iterator to get a pair.
- std::pair < T, T > operator*() const {
- return *_iter;
+ const_reference operator*() const {
+ return *_iter;
}
// Return the interval start.
- T get_start() const {
- return _iter->first;
+ offset_type get_start() const {
+ return _iter->first;
}
- T get_end() const {
- return _iter->first + _iter->second;
+ offset_type get_end() const {
+ return _iter->first + _iter->second;
}
// Return the interval length.
- T get_len() const {
- return _iter->second;
+ length_type get_len() const {
+ return _iter->second;
}
// Preincrement
- const_iterator &operator++()
+ const_iterator& operator++()
{
- ++_iter;
- return *this;
+ ++_iter;
+ return *this;
}
// Postincrement
const_iterator operator++(int)
{
- const_iterator prev(_iter);
- ++_iter;
- return prev;
+ const_iterator prev(_iter);
+ ++_iter;
+ return prev;
}
protected:
typename Map::const_iterator _iter;
};
- interval_set() : _size(0) {}
- interval_set(Map& other) {
+ interval_set() = default;
+ interval_set(Map&& other) {
m.swap(other);
- _size = 0;
- for (auto& i : m) {
- _size += i.second;
+ for (const auto& p : m) {
+ _size += p.second;
}
}
- int num_intervals() const
+ size_type num_intervals() const
{
return m.size();
}
- typename interval_set<T,Map>::iterator begin() {
- return typename interval_set<T,Map>::iterator(m.begin());
+ iterator begin() {
+ return iterator(m.begin());
}
- typename interval_set<T,Map>::iterator lower_bound(T start) {
- return typename interval_set<T,Map>::iterator(find_inc_m(start));
+ iterator lower_bound(T start) {
+ return iterator(find_inc_m(start));
}
- typename interval_set<T,Map>::iterator end() {
- return typename interval_set<T,Map>::iterator(m.end());
+ iterator end() {
+ return iterator(m.end());
}
- typename interval_set<T,Map>::const_iterator begin() const {
- return typename interval_set<T,Map>::const_iterator(m.begin());
+ const_iterator begin() const {
+ return const_iterator(m.begin());
}
- typename interval_set<T,Map>::const_iterator lower_bound(T start) const {
- return typename interval_set<T,Map>::const_iterator(find_inc(start));
+ const_iterator lower_bound(T start) const {
+ return const_iterator(find_inc(start));
}
- typename interval_set<T,Map>::const_iterator end() const {
- return typename interval_set<T,Map>::const_iterator(m.end());
+ const_iterator end() const {
+ return const_iterator(m.end());
}
// helpers
private:
- typename Map::const_iterator find_inc(T start) const {
- typename Map::const_iterator p = m.lower_bound(start); // p->first >= start
+ auto find_inc(T start) const {
+ auto p = m.lower_bound(start); // p->first >= start
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
- p--; // might overlap?
+ --p; // might overlap?
if (p->first + p->second <= start)
- p++; // it doesn't.
+ ++p; // it doesn't.
}
return p;
}
- typename Map::iterator find_inc_m(T start) {
- typename Map::iterator p = m.lower_bound(start);
+ auto find_inc_m(T start) {
+ auto p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
- p--; // might overlap?
+ --p; // might overlap?
if (p->first + p->second <= start)
- p++; // it doesn't.
+ ++p; // it doesn't.
}
return p;
}
- typename Map::const_iterator find_adj(T start) const {
- typename Map::const_iterator p = m.lower_bound(start);
+ auto find_adj(T start) const {
+ auto p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
- p--; // might touch?
+ --p; // might touch?
if (p->first + p->second < start)
- p++; // it doesn't.
+ ++p; // it doesn't.
}
return p;
}
- typename Map::iterator find_adj_m(T start) {
- typename Map::iterator p = m.lower_bound(start);
+ auto find_adj_m(T start) {
+ auto p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
- p--; // might touch?
+ --p; // might touch?
if (p->first + p->second < start)
- p++; // it doesn't.
+ ++p; // it doesn't.
}
return p;
}
void intersection_size_asym(const interval_set &s, const interval_set &l) {
- typename decltype(m)::const_iterator ps = s.m.begin(), pl;
+ auto ps = s.m.begin();
ceph_assert(ps != s.m.end());
- T offset = ps->first;
+ auto offset = ps->first;
bool first = true;
- typename decltype(m)::iterator mi = m.begin();
+ auto mi = m.begin();
while (1) {
if (first)
first = false;
- pl = l.find_inc(offset);
+ auto pl = l.find_inc(offset);
if (pl == l.m.end())
break;
while (ps != s.m.end() && ps->first + ps->second <= pl->first)
continue;
}
- T start = std::max<T>(ps->first, pl->first);
- T en = std::min<T>(ps->first + ps->second, offset);
+ auto start = std::max<T>(ps->first, pl->first);
+ auto en = std::min<T>(ps->first + ps->second, offset);
ceph_assert(en > start);
- typename decltype(m)::value_type i{start, en - start};
- mi = m.insert(mi, i);
- _size += i.second;
+ mi = m.emplace_hint(mi, start, en - start);
+ _size += mi->second;
if (ps->first + ps->second <= offset) {
++ps;
if (ps == s.m.end())
return _size == other._size && m == other.m;
}
- int64_t size() const {
+ uint64_t size() const {
return _size;
}
void bound_encode(size_t& p) const {
denc_traits<Map>::bound_encode(m, p);
}
- void encode(bufferlist::contiguous_appender& p) const {
+ void encode(ceph::buffer::list::contiguous_appender& p) const {
denc(m, p);
}
- void decode(bufferptr::const_iterator& p) {
+ void decode(ceph::buffer::ptr::const_iterator& p) {
denc(m, p);
_size = 0;
- for (const auto& i : m) {
- _size += i.second;
+ for (const auto& p : m) {
+ _size += p.second;
}
}
- void decode(bufferlist::iterator& p) {
+ void decode(ceph::buffer::list::iterator& p) {
denc(m, p);
_size = 0;
- for (const auto& i : m) {
- _size += i.second;
+ for (const auto& p : m) {
+ _size += p.second;
}
}
- void encode_nohead(bufferlist::contiguous_appender& p) const {
+ void encode_nohead(ceph::buffer::list::contiguous_appender& p) const {
denc_traits<Map>::encode_nohead(m, p);
}
- void decode_nohead(int n, bufferptr::const_iterator& p) {
+ void decode_nohead(int n, ceph::buffer::ptr::const_iterator& p) {
denc_traits<Map>::decode_nohead(n, m, p);
_size = 0;
- for (const auto& i : m) {
- _size += i.second;
+ for (const auto& p : m) {
+ _size += p.second;
}
}
}
bool contains(T i, T *pstart=0, T *plen=0) const {
- typename Map::const_iterator p = find_inc(i);
+ auto p = find_inc(i);
if (p == m.end()) return false;
if (p->first > i) return false;
if (p->first+p->second <= i) return false;
return true;
}
bool contains(T start, T len) const {
- typename Map::const_iterator p = find_inc(start);
+ auto p = find_inc(start);
if (p == m.end()) return false;
if (p->first > start) return false;
if (p->first+p->second <= start) return false;
bool empty() const {
return m.empty();
}
- T range_start() const {
+ offset_type range_start() const {
ceph_assert(!empty());
- typename Map::const_iterator p = m.begin();
+ auto p = m.begin();
return p->first;
}
- T range_end() const {
+ offset_type range_end() const {
ceph_assert(!empty());
- typename Map::const_iterator p = m.end();
+ auto p = m.end();
p--;
return p->first+p->second;
}
// interval start after p (where p not in set)
bool starts_after(T i) const {
ceph_assert(!contains(i));
- typename Map::const_iterator p = find_inc(i);
+ auto p = find_inc(i);
if (p == m.end()) return false;
return true;
}
- T start_after(T i) const {
+ offset_type start_after(T i) const {
ceph_assert(!contains(i));
- typename Map::const_iterator p = find_inc(i);
+ auto p = find_inc(i);
return p->first;
}
// interval end that contains start
- T end_after(T start) const {
+ offset_type end_after(T start) const {
ceph_assert(contains(start));
- typename Map::const_iterator p = find_inc(start);
+ auto p = find_inc(start);
return p->first+p->second;
}
//cout << "insert " << start << "~" << len << endl;
ceph_assert(len > 0);
_size += len;
- typename Map::iterator p = find_adj_m(start);
+ auto p = find_adj_m(start);
if (p == m.end()) {
m[start] = len; // new interval
if (pstart)
p->second += len; // append to end
- typename Map::iterator n = p;
- n++;
+ auto n = p;
+ ++n;
if (pstart)
*pstart = p->first;
if (n != m.end() &&
}
}
- void swap(interval_set<T,Map>& other) {
+ void swap(interval_set& other) {
m.swap(other.m);
std::swap(_size, other._size);
}
void erase(T start, T len,
std::function<bool(T, T)> claim = {}) {
- typename Map::iterator p = find_inc_m(start);
+ auto p = find_inc_m(start);
_size -= len;
ceph_assert(_size >= 0);
}
void subtract(const interval_set &a) {
- for (typename Map::const_iterator p = a.m.begin();
- p != a.m.end();
- p++)
- erase(p->first, p->second);
+ for (const auto& [start, len] : a.m) {
+ erase(start, len);
+ }
}
void insert(const interval_set &a) {
- for (typename Map::const_iterator p = a.m.begin();
- p != a.m.end();
- p++)
- insert(p->first, p->second);
+ for (const auto& [start, len] : a.m) {
+ insert(start, len);
+ }
}
return;
}
- typename Map::const_iterator pa = a.m.begin();
- typename Map::const_iterator pb = b.m.begin();
- typename decltype(m)::iterator mi = m.begin();
+ auto pa = a.m.begin();
+ auto pb = b.m.begin();
+ auto mi = m.begin();
while (pa != a.m.end() && pb != b.m.end()) {
// passing?
T start = std::max(pa->first, pb->first);
T en = std::min(pa->first+pa->second, pb->first+pb->second);
ceph_assert(en > start);
- typename decltype(m)::value_type i{start, en - start};
- mi = m.insert(mi, i);
- _size += i.second;
+ mi = m.emplace_hint(mi, start, en - start);
+ _size += mi->second;
if (pa->first+pa->second > pb->first+pb->second)
pb++;
else
if (big.size() / size() < 10)
return subset_size_sym(big);
- for (typename Map::const_iterator i = m.begin();
- i != m.end();
- i++)
- if (!big.contains(i->first, i->second)) return false;
+ for (const auto& [start, len] : m) {
+ if (!big.contains(start, len)) return false;
+ }
return true;
}
*/
void span_of(const interval_set &other, T start, T len) {
clear();
- typename Map::const_iterator p = other.find_inc(start);
+ auto p = other.find_inc(start);
if (p == other.m.end())
return;
if (p->first < start) {
* Move contents of m into another Map. Use that instead of
* encoding interval_set into bufferlist then decoding it back into Map.
*/
- void move_into(Map& other) {
- other = std::move(m);
+ Map detach() && {
+ return std::move(m);
}
private:
// data
- int64_t _size;
+ uint64_t _size = 0;
Map m; // map start -> len
};
v.bound_encode(p);
}
static void encode(const interval_set<T,Map>& v,
- bufferlist::contiguous_appender& p) {
+ ceph::buffer::list::contiguous_appender& p) {
v.encode(p);
}
- static void decode(interval_set<T,Map>& v, bufferptr::const_iterator& p) {
+ static void decode(interval_set<T,Map>& v, ceph::buffer::ptr::const_iterator& p) {
v.decode(p);
}
template<typename U=T>
static typename std::enable_if<sizeof(U) && !need_contiguous>::type
- decode(interval_set<T,Map>& v, bufferlist::iterator& p) {
+ decode(interval_set<T,Map>& v, ceph::buffer::list::iterator& p) {
v.decode(p);
}
static void encode_nohead(const interval_set<T,Map>& v,
- bufferlist::contiguous_appender& p) {
+ ceph::buffer::list::contiguous_appender& p) {
v.encode_nohead(p);
}
static void decode_nohead(size_t n, interval_set<T,Map>& v,
- bufferptr::const_iterator& p) {
+ ceph::buffer::ptr::const_iterator& p) {
v.decode_nohead(n, p);
}
};
template<class T, typename Map>
inline std::ostream& operator<<(std::ostream& out, const interval_set<T,Map> &s) {
out << "[";
- const char *prequel = "";
- for (typename interval_set<T,Map>::const_iterator i = s.begin();
- i != s.end();
- ++i)
- {
- out << prequel << i.get_start() << "~" << i.get_len();
- prequel = ",";
+ bool first = true;
+ for (const auto& [start, len] : s) {
+ if (!first) out << ",";
+ out << start << "~" << len;
+ first = false;
}
out << "]";
return out;
projects / ceph.git / blobdiff