#include "encoding.h"
+/*
+ * *** NOTE ***
+ *
+ * This class is written to work with a variety of map-like containers,
+ * *include* ones that invalidate iterators when they are modified (e.g.,
+ * flat_map and btree_map).
+ */
+
#ifndef MIN
# define MIN(a,b) ((a)<=(b) ? (a):(b))
#endif
#endif
-template<typename T>
+template<typename T, typename Map = std::map<T,T>>
class interval_set {
public:
class iterator : public std::iterator <std::forward_iterator_tag, T>
{
public:
- explicit iterator(typename std::map<T,T>::iterator iter)
+ explicit iterator(typename Map::iterator iter)
: _iter(iter)
{ }
return prev;
}
- friend class interval_set<T>::const_iterator;
+ friend class interval_set<T,Map>::const_iterator;
protected:
- typename std::map<T,T>::iterator _iter;
- friend class interval_set<T>;
+ typename Map::iterator _iter;
+ friend class interval_set<T,Map>;
};
class const_iterator : public std::iterator <std::forward_iterator_tag, T>
{
public:
- explicit const_iterator(typename std::map<T,T>::const_iterator iter)
+ explicit const_iterator(typename Map::const_iterator iter)
: _iter(iter)
{ }
}
protected:
- typename std::map<T,T>::const_iterator _iter;
+ typename Map::const_iterator _iter;
};
interval_set() : _size(0) {}
- interval_set(std::map<T,T>& other) {
+ interval_set(Map& other) {
m.swap(other);
_size = 0;
for (auto& i : m) {
return m.size();
}
- typename interval_set<T>::iterator begin() {
- return typename interval_set<T>::iterator(m.begin());
+ typename interval_set<T,Map>::iterator begin() {
+ return typename interval_set<T,Map>::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,Map>::iterator lower_bound(T start) {
+ return typename interval_set<T,Map>::iterator(find_inc_m(start));
}
- typename interval_set<T>::iterator end() {
- return typename interval_set<T>::iterator(m.end());
+ typename interval_set<T,Map>::iterator end() {
+ return typename interval_set<T,Map>::iterator(m.end());
}
- typename interval_set<T>::const_iterator begin() const {
- return typename interval_set<T>::const_iterator(m.begin());
+ typename interval_set<T,Map>::const_iterator begin() const {
+ return typename interval_set<T,Map>::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,Map>::const_iterator lower_bound(T start) const {
+ return typename interval_set<T,Map>::const_iterator(find_inc(start));
}
- typename interval_set<T>::const_iterator end() const {
- return typename interval_set<T>::const_iterator(m.end());
+ typename interval_set<T,Map>::const_iterator end() const {
+ return typename interval_set<T,Map>::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
+ typename Map::const_iterator find_inc(T start) const {
+ typename Map::const_iterator p = m.lower_bound(start); // p->first >= start
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
p--; // might overlap?
return p;
}
- typename std::map<T,T>::iterator find_inc_m(T start) {
- typename std::map<T,T>::iterator p = m.lower_bound(start);
+ typename Map::iterator find_inc_m(T start) {
+ typename Map::iterator p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
p--; // might overlap?
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);
+ typename Map::const_iterator find_adj(T start) const {
+ typename Map::const_iterator p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
p--; // might touch?
return p;
}
- typename std::map<T,T>::iterator find_adj_m(T start) {
- typename std::map<T,T>::iterator p = m.lower_bound(start);
+ typename Map::iterator find_adj_m(T start) {
+ typename Map::iterator p = m.lower_bound(start);
if (p != m.begin() &&
(p == m.end() || p->first > start)) {
p--; // might touch?
}
return p;
}
+
+ void intersection_size_asym(const interval_set &s, const interval_set &l) {
+ typename decltype(m)::const_iterator ps = s.m.begin(), pl;
+ assert(ps != s.m.end());
+ T offset = ps->first, prev_offset;
+ bool first = true;
+ typename decltype(m)::iterator mi = m.begin();
+
+ while (1) {
+ if (first)
+ first = false;
+ else
+ assert(offset > prev_offset);
+ pl = l.find_inc(offset);
+ prev_offset = offset;
+ if (pl == l.m.end())
+ break;
+ while (ps != s.m.end() && ps->first + ps->second <= pl->first)
+ ++ps;
+ if (ps == s.m.end())
+ break;
+ offset = pl->first + pl->second;
+ if (offset <= ps->first) {
+ offset = ps->first;
+ continue;
+ }
+
+ if (*ps == *pl) {
+ do {
+ mi = m.insert(mi, *ps);
+ _size += ps->second;
+ ++ps;
+ ++pl;
+ } while (ps != s.m.end() && pl != l.m.end() && *ps == *pl);
+ if (ps == s.m.end())
+ break;
+ offset = ps->first;
+ continue;
+ }
+
+ T start = std::max<T>(ps->first, pl->first);
+ T en = std::min<T>(ps->first + ps->second, offset);
+ assert(en > start);
+ typename decltype(m)::value_type i{start, en - start};
+ mi = m.insert(mi, i);
+ _size += i.second;
+ if (ps->first + ps->second <= offset) {
+ ++ps;
+ if (ps == s.m.end())
+ break;
+ offset = ps->first;
+ }
+ }
+ }
+
+ bool subset_size_sym(const interval_set &b) const {
+ auto pa = m.begin(), pb = b.m.begin();
+ const auto a_end = m.end(), b_end = b.m.end();
+
+ while (pa != a_end && pb != b_end) {
+ while (pb->first + pb->second <= pa->first) {
+ ++pb;
+ if (pb == b_end)
+ return false;
+ }
+
+ if (*pa == *pb) {
+ do {
+ ++pa;
+ ++pb;
+ } while (pa != a_end && pb != b_end && *pa == *pb);
+ continue;
+ }
+
+ // interval begins before other
+ if (pa->first < pb->first)
+ return false;
+ // interval is longer than other
+ if (pa->first + pa->second > pb->first + pb->second)
+ return false;
+
+ ++pa;
+ }
+
+ return pa == a_end;
+ }
public:
bool operator==(const interval_set& other) const {
}
void bound_encode(size_t& p) const {
- denc_traits<std::map<T,T>>::bound_encode(m, p);
+ denc_traits<Map>::bound_encode(m, p);
}
void encode(bufferlist::contiguous_appender& p) const {
denc(m, p);
}
void encode_nohead(bufferlist::contiguous_appender& p) const {
- denc_traits<std::map<T,T>>::encode_nohead(m, p);
+ denc_traits<Map>::encode_nohead(m, p);
}
void decode_nohead(int n, bufferptr::iterator& p) {
- denc_traits<std::map<T,T>>::decode_nohead(n, m, p);
+ denc_traits<Map>::decode_nohead(n, m, p);
_size = 0;
for (const auto& i : m) {
_size += i.second;
}
bool contains(T i, T *pstart=0, T *plen=0) const {
- typename std::map<T,T>::const_iterator p = find_inc(i);
+ typename Map::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;
return true;
}
bool contains(T start, T len) const {
- typename std::map<T,T>::const_iterator p = find_inc(start);
+ typename Map::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;
}
T range_start() const {
assert(!empty());
- typename std::map<T,T>::const_iterator p = m.begin();
+ typename Map::const_iterator p = m.begin();
return p->first;
}
T range_end() const {
assert(!empty());
- typename std::map<T,T>::const_iterator p = m.end();
+ typename Map::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);
+ typename Map::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);
+ typename Map::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);
+ typename Map::const_iterator p = find_inc(start);
return p->first+p->second;
}
//cout << "insert " << start << "~" << len << endl;
assert(len > 0);
_size += len;
- typename std::map<T,T>::iterator p = find_adj_m(start);
+ typename Map::iterator p = find_adj_m(start);
if (p == m.end()) {
m[start] = len; // new interval
if (pstart)
p->second += len; // append to end
- typename std::map<T,T>::iterator n = p;
+ typename Map::iterator n = p;
n++;
+ if (pstart)
+ *pstart = p->first;
if (n != m.end() &&
start+len == n->first) { // combine with next, too!
p->second += n->second;
+ if (plen)
+ *plen = p->second;
m.erase(n);
- }
- if (pstart)
- *pstart = p->first;
- if (plen)
- *plen = p->second;
+ } else {
+ 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;
+ T psecond = p->second;
m.erase(p);
+ m[start] = len + psecond; // append to front
} else {
assert(p->first > start+len);
- m[start] = len; // new interval
if (pstart)
*pstart = start;
if (plen)
*plen = len;
+ m[start] = len; // new interval
}
}
}
}
- void swap(interval_set<T>& other) {
+ void swap(interval_set<T,Map>& other) {
m.swap(other.m);
std::swap(_size, other._size);
}
erase(val, 1);
}
- void erase(T start, T len) {
- typename std::map<T,T>::iterator p = find_inc_m(start);
+ void erase(T start, T len,
+ std::function<bool(T, T)> claim = {}) {
+ typename Map::iterator p = find_inc_m(start);
_size -= len;
assert(_size >= 0);
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
+ if (before) {
+ if (claim && claim(p->first, before)) {
+ _size -= before;
+ m.erase(p);
+ } else {
+ p->second = before; // shorten bit before
+ }
+ } else {
m.erase(p);
- if (after)
- m[start+len] = after;
+ }
+ if (after) {
+ if (claim && claim(start + len, after)) {
+ _size -= after;
+ } else {
+ m[start + len] = after;
+ }
+ }
}
-
void subtract(const interval_set &a) {
- for (typename std::map<T,T>::const_iterator p = a.m.begin();
+ for (typename Map::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();
+ for (typename Map::const_iterator p = a.m.begin();
p != a.m.end();
p++)
insert(p->first, p->second);
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();
-
+ const interval_set *s, *l;
+
+ if (a.size() < b.size()) {
+ s = &a;
+ l = &b;
+ } else {
+ s = &b;
+ l = &a;
+ }
+
+ if (!s->size())
+ return;
+
+ /*
+ * Use the lower_bound algorithm for larger size ratios
+ * where it performs better, but not for smaller size
+ * ratios where sequential search performs better.
+ */
+ if (l->size() / s->size() >= 10) {
+ intersection_size_asym(*s, *l);
+ return;
+ }
+
+ typename Map::const_iterator pa = a.m.begin();
+ typename Map::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);
- insert(start, 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
}
bool subset_of(const interval_set &big) const {
- for (typename std::map<T,T>::const_iterator i = m.begin();
+ if (!size())
+ return true;
+ if (size() > big.size())
+ return false;
+ if (range_end() > big.range_end())
+ return false;
+
+ /*
+ * Use the lower_bound algorithm for larger size ratios
+ * where it performs better, but not for smaller size
+ * ratios where sequential search performs better.
+ */
+ 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;
return true;
}
+ /*
+ * build a subset of @other for given rage [@start, @end)
+ * E.g.:
+ * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5]
+ * subset_of([5~10,20~5], 5, 25) -> [5~10,20~5]
+ * subset_of([5~10,20~5], 1, 10) -> [5~5]
+ * subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4]
+ */
+ void subset_of(const interval_set &other, T start, T end) {
+ assert(end >= start);
+ clear();
+ if (end == start) {
+ return;
+ }
+ typename Map::const_iterator p = other.find_inc(start);
+ if (p == other.m.end())
+ return;
+ if (p->first < start) {
+ if (p->first + p->second >= end) {
+ insert(start, end - start);
+ return;
+ } else {
+ insert(start, p->first + p->second - start);
+ ++p;
+ }
+ }
+ while (p != other.m.end()) {
+ assert(p->first >= start);
+ if (p->first >= end) {
+ return;
+ }
+ if (p->first + p->second >= end) {
+ insert(p->first, end - p->first);
+ return;
+ } else {
+ // whole
+ insert(p->first, p->second);
+ ++p;
+ }
+ }
+ }
+
/*
* build a subset of @other, starting at or after @start, and including
* @len worth of values, skipping holes. e.g.,
*/
void span_of(const interval_set &other, T start, T len) {
clear();
- typename std::map<T,T>::const_iterator p = other.find_inc(start);
+ typename Map::const_iterator p = other.find_inc(start);
if (p == other.m.end())
return;
if (p->first < start) {
}
/*
- * 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.
+ * 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(std::map<T,T>& other) {
+ void move_into(Map& other) {
other = std::move(m);
}
private:
// data
int64_t _size;
- std::map<T,T> m; // map start -> len
+ Map 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>> {
+template<typename T, typename Map>
+struct denc_traits<interval_set<T,Map>> {
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) {
+ static constexpr bool need_contiguous = denc_traits<T,Map>::need_contiguous;
+ static void bound_encode(const interval_set<T,Map>& v, size_t& p) {
v.bound_encode(p);
}
- static void encode(const interval_set<T>& v,
+ static void encode(const interval_set<T,Map>& v,
bufferlist::contiguous_appender& p) {
v.encode(p);
}
- static void decode(interval_set<T>& v, bufferptr::iterator& p) {
+ static void decode(interval_set<T,Map>& 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) {
+ decode(interval_set<T,Map>& v, bufferlist::iterator& p) {
v.decode(p);
}
- static void encode_nohead(const interval_set<T>& v,
+ static void encode_nohead(const interval_set<T,Map>& v,
bufferlist::contiguous_appender& p) {
v.encode_nohead(p);
}
- static void decode_nohead(size_t n, interval_set<T>& v,
+ static void decode_nohead(size_t n, interval_set<T,Map>& v,
bufferptr::iterator& p) {
v.decode_nohead(n, p);
}
};
-template<class T>
-inline std::ostream& operator<<(std::ostream& out, const interval_set<T> &s) {
+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>::const_iterator i = s.begin();
+ for (typename interval_set<T,Map>::const_iterator i = s.begin();
i != s.end();
++i)
{
projects / ceph.git / blobdiff