+++ /dev/null
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
-// vim: ts=8 sw=2 smarttab
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
- *
- * This is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License version 2.1, as published by the Free Software
- * Foundation. See file COPYING.
- *
- */
-
-
-#ifndef CEPH_INTERVAL_SET_H
-#define CEPH_INTERVAL_SET_H
-
-#include <iterator>
-#include <map>
-#include <ostream>
-
-#include "encoding.h"
-
-#ifndef MIN
-# define MIN(a,b) ((a)<=(b) ? (a):(b))
-#endif
-#ifndef MAX
-# define MAX(a,b) ((a)>=(b) ? (a):(b))
-#endif
-
-
-template<typename T>
-class interval_set {
- public:
-
- class const_iterator;
-
- class iterator : public std::iterator <std::forward_iterator_tag, T>
- {
- public:
- explicit iterator(typename std::map<T,T>::iterator iter)
- : _iter(iter)
- { }
-
- // For the copy constructor and assignment operator, the compiler-generated functions, which
- // perform simple bitwise copying, should be fine.
-
- bool operator==(const iterator& rhs) const {
- return (_iter == rhs._iter);
- }
-
- bool operator!=(const iterator& rhs) const {
- return (_iter != rhs._iter);
- }
-
- // Dereference this iterator to get a pair.
- std::pair < T, T > &operator*() {
- return *_iter;
- }
-
- // Return the interval start.
- T get_start() const {
- return _iter->first;
- }
-
- // Return the interval length.
- T get_len() const {
- return _iter->second;
- }
-
- // Set the interval length.
- void set_len(T len) {
- _iter->second = len;
- }
-
- // Preincrement
- iterator &operator++()
- {
- ++_iter;
- return *this;
- }
-
- // Postincrement
- iterator operator++(int)
- {
- iterator prev(_iter);
- ++_iter;
- return prev;
- }
-
- friend class interval_set<T>::const_iterator;
-
- protected:
- typename std::map<T,T>::iterator _iter;
- friend class interval_set<T>;
- };
-
- class const_iterator : public std::iterator <std::forward_iterator_tag, T>
- {
- public:
- explicit const_iterator(typename std::map<T,T>::const_iterator iter)
- : _iter(iter)
- { }
-
- const_iterator(const iterator &i)
- : _iter(i._iter)
- { }
-
- // For the copy constructor and assignment operator, the compiler-generated functions, which
- // perform simple bitwise copying, should be fine.
-
- bool operator==(const const_iterator& rhs) const {
- return (_iter == rhs._iter);
- }
-
- bool operator!=(const const_iterator& rhs) const {
- return (_iter != rhs._iter);
- }
-
- // Dereference this iterator to get a pair.
- std::pair < T, T > operator*() const {
- return *_iter;
- }
-
- // Return the interval start.
- T get_start() const {
- return _iter->first;
- }
-
- // Return the interval length.
- T get_len() const {
- return _iter->second;
- }
-
- // Preincrement
- const_iterator &operator++()
- {
- ++_iter;
- return *this;
- }
-
- // Postincrement
- const_iterator operator++(int)
- {
- const_iterator prev(_iter);
- ++_iter;
- return prev;
- }
-
- protected:
- typename std::map<T,T>::const_iterator _iter;
- };
-
- interval_set() : _size(0) {}
- interval_set(std::map<T,T>& other) {
- m.swap(other);
- _size = 0;
- for (auto& i : m) {
- _size += i.second;
- }
- }
-
- int num_intervals() const
- {
- return m.size();
- }
-
- typename interval_set<T>::iterator begin() {
- return typename interval_set<T>::iterator(m.begin());
- }
-
- typename interval_set<T>::iterator lower_bound(T start) {
- return typename interval_set<T>::iterator(find_inc_m(start));
- }
-
- typename interval_set<T>::iterator end() {
- return typename interval_set<T>::iterator(m.end());
- }
-
- typename interval_set<T>::const_iterator begin() const {
- return typename interval_set<T>::const_iterator(m.begin());
- }
-
- typename interval_set<T>::const_iterator lower_bound(T start) const {
- return typename interval_set<T>::const_iterator(find_inc(start));
- }
-
- typename interval_set<T>::const_iterator end() const {
- return typename interval_set<T>::const_iterator(m.end());
- }
-
- // helpers
- private:
- typename std::map<T,T>::const_iterator find_inc(T start) const {
- typename std::map<T,T>::const_iterator p = m.lower_bound(start); // p->first >= start
- if (p != m.begin() &&
- (p == m.end() || p->first > start)) {
- p--; // might overlap?
- if (p->first + p->second <= start)
- p++; // it doesn't.
- }
- return p;
- }
-
- typename std::map<T,T>::iterator find_inc_m(T start) {
- typename std::map<T,T>::iterator p = m.lower_bound(start);
- if (p != m.begin() &&
- (p == m.end() || p->first > start)) {
- p--; // might overlap?
- if (p->first + p->second <= start)
- p++; // it doesn't.
- }
- return p;
- }
-
- typename std::map<T,T>::const_iterator find_adj(T start) const {
- typename std::map<T,T>::const_iterator p = m.lower_bound(start);
- if (p != m.begin() &&
- (p == m.end() || p->first > start)) {
- p--; // might touch?
- if (p->first + p->second < start)
- p++; // it doesn't.
- }
- return p;
- }
-
- typename std::map<T,T>::iterator find_adj_m(T start) {
- typename std::map<T,T>::iterator p = m.lower_bound(start);
- if (p != m.begin() &&
- (p == m.end() || p->first > start)) {
- p--; // might touch?
- if (p->first + p->second < start)
- p++; // it doesn't.
- }
- return p;
- }
-
- public:
- bool operator==(const interval_set& other) const {
- return _size == other._size && m == other.m;
- }
-
- int64_t size() const {
- return _size;
- }
-
- void bound_encode(size_t& p) const {
- denc_traits<std::map<T,T>>::bound_encode(m, p);
- }
- void encode(bufferlist::contiguous_appender& p) const {
- denc(m, p);
- }
- void decode(bufferptr::iterator& p) {
- denc(m, p);
- _size = 0;
- for (const auto& i : m) {
- _size += i.second;
- }
- }
- void decode(bufferlist::iterator& p) {
- denc(m, p);
- _size = 0;
- for (const auto& i : m) {
- _size += i.second;
- }
- }
-
- void encode_nohead(bufferlist::contiguous_appender& p) const {
- denc_traits<std::map<T,T>>::encode_nohead(m, p);
- }
- void decode_nohead(int n, bufferptr::iterator& p) {
- denc_traits<std::map<T,T>>::decode_nohead(n, m, p);
- _size = 0;
- for (const auto& i : m) {
- _size += i.second;
- }
- }
-
- void clear() {
- m.clear();
- _size = 0;
- }
-
- bool contains(T i, T *pstart=0, T *plen=0) const {
- typename std::map<T,T>::const_iterator p = find_inc(i);
- if (p == m.end()) return false;
- if (p->first > i) return false;
- if (p->first+p->second <= i) return false;
- assert(p->first <= i && p->first+p->second > i);
- if (pstart)
- *pstart = p->first;
- if (plen)
- *plen = p->second;
- return true;
- }
- bool contains(T start, T len) const {
- typename std::map<T,T>::const_iterator p = find_inc(start);
- if (p == m.end()) return false;
- if (p->first > start) return false;
- if (p->first+p->second <= start) return false;
- assert(p->first <= start && p->first+p->second > start);
- if (p->first+p->second < start+len) return false;
- return true;
- }
- bool intersects(T start, T len) const {
- interval_set a;
- a.insert(start, len);
- interval_set i;
- i.intersection_of( *this, a );
- if (i.empty()) return false;
- return true;
- }
-
- // outer range of set
- bool empty() const {
- return m.empty();
- }
- T range_start() const {
- assert(!empty());
- typename std::map<T,T>::const_iterator p = m.begin();
- return p->first;
- }
- T range_end() const {
- assert(!empty());
- typename std::map<T,T>::const_iterator p = m.end();
- p--;
- return p->first+p->second;
- }
-
- // interval start after p (where p not in set)
- bool starts_after(T i) const {
- assert(!contains(i));
- typename std::map<T,T>::const_iterator p = find_inc(i);
- if (p == m.end()) return false;
- return true;
- }
- T start_after(T i) const {
- assert(!contains(i));
- typename std::map<T,T>::const_iterator p = find_inc(i);
- return p->first;
- }
-
- // interval end that contains start
- T end_after(T start) const {
- assert(contains(start));
- typename std::map<T,T>::const_iterator p = find_inc(start);
- return p->first+p->second;
- }
-
- void insert(T val) {
- insert(val, 1);
- }
-
- void insert(T start, T len, T *pstart=0, T *plen=0) {
- //cout << "insert " << start << "~" << len << endl;
- assert(len > 0);
- _size += len;
- typename std::map<T,T>::iterator p = find_adj_m(start);
- if (p == m.end()) {
- m[start] = len; // new interval
- if (pstart)
- *pstart = start;
- if (plen)
- *plen = len;
- } else {
- if (p->first < start) {
-
- if (p->first + p->second != start) {
- //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
- ceph_abort();
- }
-
- p->second += len; // append to end
-
- typename std::map<T,T>::iterator n = p;
- n++;
- if (n != m.end() &&
- start+len == n->first) { // combine with next, too!
- p->second += n->second;
- m.erase(n);
- }
- if (pstart)
- *pstart = p->first;
- if (plen)
- *plen = p->second;
- } else {
- if (start+len == p->first) {
- m[start] = len + p->second; // append to front
- if (pstart)
- *pstart = start;
- if (plen)
- *plen = len + p->second;
- m.erase(p);
- } else {
- assert(p->first > start+len);
- m[start] = len; // new interval
- if (pstart)
- *pstart = start;
- if (plen)
- *plen = len;
- }
- }
- }
- }
-
- void swap(interval_set<T>& other) {
- m.swap(other.m);
- std::swap(_size, other._size);
- }
-
- void erase(iterator &i) {
- _size -= i.get_len();
- assert(_size >= 0);
- m.erase(i._iter);
- }
-
- void erase(T val) {
- erase(val, 1);
- }
-
- void erase(T start, T len) {
- typename std::map<T,T>::iterator p = find_inc_m(start);
-
- _size -= len;
- assert(_size >= 0);
-
- assert(p != m.end());
- assert(p->first <= start);
-
- T before = start - p->first;
- assert(p->second >= before+len);
- T after = p->second - before - len;
-
- if (before)
- p->second = before; // shorten bit before
- else
- m.erase(p);
- if (after)
- m[start+len] = after;
- }
-
-
- void subtract(const interval_set &a) {
- for (typename std::map<T,T>::const_iterator p = a.m.begin();
- p != a.m.end();
- p++)
- erase(p->first, p->second);
- }
-
- void insert(const interval_set &a) {
- for (typename std::map<T,T>::const_iterator p = a.m.begin();
- p != a.m.end();
- p++)
- insert(p->first, p->second);
- }
-
-
- void intersection_of(const interval_set &a, const interval_set &b) {
- assert(&a != this);
- assert(&b != this);
- clear();
-
- typename std::map<T,T>::const_iterator pa = a.m.begin();
- typename std::map<T,T>::const_iterator pb = b.m.begin();
- typename decltype(m)::iterator mi = m.begin();
-
- while (pa != a.m.end() && pb != b.m.end()) {
- // passing?
- if (pa->first + pa->second <= pb->first)
- { pa++; continue; }
- if (pb->first + pb->second <= pa->first)
- { pb++; continue; }
-
- if (*pa == *pb) {
- do {
- mi = m.insert(mi, *pa);
- _size += pa->second;
- ++pa;
- ++pb;
- } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
- continue;
- }
-
- T start = MAX(pa->first, pb->first);
- T en = MIN(pa->first+pa->second, pb->first+pb->second);
- assert(en > start);
- typename decltype(m)::value_type i{start, en - start};
- mi = m.insert(mi, i);
- _size += i.second;
- if (pa->first+pa->second > pb->first+pb->second)
- pb++;
- else
- pa++;
- }
- }
- void intersection_of(const interval_set& b) {
- interval_set a;
- swap(a);
- intersection_of(a, b);
- }
-
- void union_of(const interval_set &a, const interval_set &b) {
- assert(&a != this);
- assert(&b != this);
- clear();
-
- //cout << "union_of" << endl;
-
- // a
- m = a.m;
- _size = a._size;
-
- // - (a*b)
- interval_set ab;
- ab.intersection_of(a, b);
- subtract(ab);
-
- // + b
- insert(b);
- return;
- }
- void union_of(const interval_set &b) {
- interval_set a;
- swap(a);
- union_of(a, b);
- }
- void union_insert(T off, T len) {
- interval_set a;
- a.insert(off, len);
- union_of(a);
- }
-
- bool subset_of(const interval_set &big) const {
- for (typename std::map<T,T>::const_iterator i = m.begin();
- i != m.end();
- i++)
- if (!big.contains(i->first, i->second)) return false;
- return true;
- }
-
- /*
- * build a subset of @other, starting at or after @start, and including
- * @len worth of values, skipping holes. e.g.,
- * span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
- */
- void span_of(const interval_set &other, T start, T len) {
- clear();
- typename std::map<T,T>::const_iterator p = other.find_inc(start);
- if (p == other.m.end())
- return;
- if (p->first < start) {
- if (p->first + p->second < start)
- return;
- if (p->first + p->second < start + len) {
- T howmuch = p->second - (start - p->first);
- insert(start, howmuch);
- len -= howmuch;
- p++;
- } else {
- insert(start, len);
- return;
- }
- }
- while (p != other.m.end() && len > 0) {
- if (p->second < len) {
- insert(p->first, p->second);
- len -= p->second;
- p++;
- } else {
- insert(p->first, len);
- return;
- }
- }
- }
-
- /*
- * Move contents of m into another std::map<T,T>. Use that instead of
- * encoding interval_set into bufferlist then decoding it back into std::map.
- */
- void move_into(std::map<T,T>& other) {
- other = std::move(m);
- }
-
-private:
- // data
- int64_t _size;
- std::map<T,T> m; // map start -> len
-};
-
-// declare traits explicitly because (1) it's templatized, and (2) we
-// want to include _nohead variants.
-template<typename T>
-struct denc_traits<interval_set<T>> {
- static constexpr bool supported = true;
- static constexpr bool bounded = false;
- static constexpr bool featured = false;
- static constexpr bool need_contiguous = denc_traits<T>::need_contiguous;
- static void bound_encode(const interval_set<T>& v, size_t& p) {
- v.bound_encode(p);
- }
- static void encode(const interval_set<T>& v,
- bufferlist::contiguous_appender& p) {
- v.encode(p);
- }
- static void decode(interval_set<T>& v, bufferptr::iterator& p) {
- v.decode(p);
- }
- template<typename U=T>
- static typename std::enable_if<sizeof(U) && !need_contiguous>::type
- decode(interval_set<T>& v, bufferlist::iterator& p) {
- v.decode(p);
- }
- static void encode_nohead(const interval_set<T>& v,
- bufferlist::contiguous_appender& p) {
- v.encode_nohead(p);
- }
- static void decode_nohead(size_t n, interval_set<T>& v,
- bufferptr::iterator& p) {
- v.decode_nohead(n, p);
- }
-};
-
-
-template<class T>
-inline std::ostream& operator<<(std::ostream& out, const interval_set<T> &s) {
- out << "[";
- const char *prequel = "";
- for (typename interval_set<T>::const_iterator i = s.begin();
- i != s.end();
- ++i)
- {
- out << prequel << i.get_start() << "~" << i.get_len();
- prequel = ",";
- }
- out << "]";
- return out;
-}
-
-
-#endif