X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Fcommon%2Finterval_map.h;fp=src%2Fceph%2Fsrc%2Fcommon%2Finterval_map.h;h=5357dff9fee781133199f5e283a023027655860d;hb=812ff6ca9fcd3e629e49d4328905f33eee8ca3f5;hp=0000000000000000000000000000000000000000;hpb=15280273faafb77777eab341909a3f495cf248d9;p=stor4nfv.git diff --git a/src/ceph/src/common/interval_map.h b/src/ceph/src/common/interval_map.h new file mode 100644 index 0000000..5357dff --- /dev/null +++ b/src/ceph/src/common/interval_map.h @@ -0,0 +1,281 @@ +// -*- 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) 2016 Red Hat + * + * 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 INTERVAL_MAP_H +#define INTERVAL_MAP_H + +#include "include/interval_set.h" + +template +/** + * interval_map + * + * Maps intervals to values. Erasing or inserting over an existing + * range will use S::operator() to split any overlapping existing + * values. + * + * Surprisingly, boost/icl/interval_map doesn't seem to be appropriate + * for this use case. The aggregation concept seems to assume + * commutativity, which doesn't work if we want more recent insertions + * to overwrite previous ones. + */ +class interval_map { + S s; + using map = std::map >; + using mapiter = typename std::map >::iterator; + using cmapiter = typename std::map >::const_iterator; + map m; + std::pair get_range(K off, K len) { + // fst is first iterator with end after off (may be end) + auto fst = m.upper_bound(off); + if (fst != m.begin()) + --fst; + if (fst != m.end() && off >= (fst->first + fst->second.first)) + ++fst; + + // lst is first iterator with start after off + len (may be end) + auto lst = m.lower_bound(off + len); + return std::make_pair(fst, lst); + } + std::pair get_range(K off, K len) const { + // fst is first iterator with end after off (may be end) + auto fst = m.upper_bound(off); + if (fst != m.begin()) + --fst; + if (fst != m.end() && off >= (fst->first + fst->second.first)) + ++fst; + + // lst is first iterator with start after off + len (may be end) + auto lst = m.lower_bound(off + len); + return std::make_pair(fst, lst); + } + void try_merge(mapiter niter) { + if (niter != m.begin()) { + auto prev = niter; + prev--; + if (prev->first + prev->second.first == niter->first && + s.can_merge(prev->second.second, niter->second.second)) { + V n = s.merge( + std::move(prev->second.second), + std::move(niter->second.second)); + K off = prev->first; + K len = niter->first + niter->second.first - off; + niter++; + m.erase(prev, niter); + auto p = m.insert( + std::make_pair( + off, + std::make_pair(len, std::move(n)))); + assert(p.second); + niter = p.first; + } + } + auto next = niter; + next++; + if (next != m.end() && + niter->first + niter->second.first == next->first && + s.can_merge(niter->second.second, next->second.second)) { + V n = s.merge( + std::move(niter->second.second), + std::move(next->second.second)); + K off = niter->first; + K len = next->first + next->second.first - off; + next++; + m.erase(niter, next); + auto p = m.insert( + std::make_pair( + off, + std::make_pair(len, std::move(n)))); + assert(p.second); + } + } +public: + interval_map intersect(K off, K len) const { + interval_map ret; + auto limits = get_range(off, len); + for (auto i = limits.first; i != limits.second; ++i) { + K o = i->first; + K l = i->second.first; + V v = i->second.second; + if (o < off) { + V p = v; + l -= (off - o); + v = s.split(off - o, l, p); + o = off; + } + if ((o + l) > (off + len)) { + V p = v; + l -= (o + l) - (off + len); + v = s.split(0, l, p); + } + ret.insert(o, l, v); + } + return ret; + } + void clear() { + m.clear(); + } + void erase(K off, K len) { + if (len == 0) + return; + auto range = get_range(off, len); + std::vector< + std::pair< + K, + std::pair + >> to_insert; + for (auto i = range.first; i != range.second; ++i) { + if (i->first < off) { + to_insert.emplace_back( + std::make_pair( + i->first, + std::make_pair( + off - i->first, + s.split(0, off - i->first, i->second.second)))); + } + if ((off + len) < (i->first + i->second.first)) { + K nlen = (i->first + i->second.first) - (off + len); + to_insert.emplace_back( + std::make_pair( + off + len, + std::make_pair( + nlen, + s.split(i->second.first - nlen, nlen, i->second.second)))); + } + } + m.erase(range.first, range.second); + m.insert(to_insert.begin(), to_insert.end()); + } + void insert(K off, K len, V &&v) { + assert(len > 0); + assert(len == s.length(v)); + erase(off, len); + auto p = m.insert(make_pair(off, std::make_pair(len, std::forward(v)))); + assert(p.second); + try_merge(p.first); + } + void insert(interval_map &&other) { + for (auto i = other.m.begin(); + i != other.m.end(); + other.m.erase(i++)) { + insert(i->first, i->second.first, std::move(i->second.second)); + } + } + void insert(K off, K len, const V &v) { + assert(len > 0); + assert(len == s.length(v)); + erase(off, len); + auto p = m.insert(make_pair(off, std::make_pair(len, v))); + assert(p.second); + try_merge(p.first); + } + void insert(const interval_map &other) { + for (auto &&i: other) { + insert(i.get_off(), i.get_len(), i.get_val()); + } + } + bool empty() const { + return m.empty(); + } + interval_set get_interval_set() const { + interval_set ret; + for (auto &&i: *this) { + ret.insert(i.get_off(), i.get_len()); + } + return ret; + } + class const_iterator { + cmapiter it; + const_iterator(cmapiter &&it) : it(std::move(it)) {} + const_iterator(const cmapiter &it) : it(it) {} + + friend class interval_map; + public: + const_iterator(const const_iterator &) = default; + const_iterator &operator=(const const_iterator &) = default; + + const_iterator &operator++() { + ++it; + return *this; + } + const_iterator operator++(int) { + return const_iterator(it++); + } + const_iterator &operator--() { + --it; + return *this; + } + const_iterator operator--(int) { + return const_iterator(it--); + } + bool operator==(const const_iterator &rhs) const { + return it == rhs.it; + } + bool operator!=(const const_iterator &rhs) const { + return it != rhs.it; + } + K get_off() const { + return it->first; + } + K get_len() const { + return it->second.first; + } + const V &get_val() const { + return it->second.second; + } + const_iterator &operator*() { + return *this; + } + }; + const_iterator begin() const { + return const_iterator(m.begin()); + } + const_iterator end() const { + return const_iterator(m.end()); + } + std::pair get_containing_range( + K off, + K len) const { + auto rng = get_range(off, len); + return std::make_pair(const_iterator(rng.first), const_iterator(rng.second)); + } + unsigned ext_count() const { + return m.size(); + } + bool operator==(const interval_map &rhs) const { + return m == rhs.m; + } + + std::ostream &print(std::ostream &out) const { + bool first = true; + out << "{"; + for (auto &&i: *this) { + if (first) { + first = false; + } else { + out << ","; + } + out << i.get_off() << "~" << i.get_len() << "(" + << s.length(i.get_val()) << ")"; + } + return out << "}"; + } +}; + +template +std::ostream &operator<<(std::ostream &out, const interval_map &m) { + return m.print(out); +} + +#endif