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"
20 template <typename K, typename V, typename S>
24 * Maps intervals to values. Erasing or inserting over an existing
25 * range will use S::operator() to split any overlapping existing
28 * Surprisingly, boost/icl/interval_map doesn't seem to be appropriate
29 * for this use case. The aggregation concept seems to assume
30 * commutativity, which doesn't work if we want more recent insertions
31 * to overwrite previous ones.
35 using map = std::map<K, std::pair<K, V> >;
36 using mapiter = typename std::map<K, std::pair<K, V> >::iterator;
37 using cmapiter = typename std::map<K, std::pair<K, V> >::const_iterator;
39 std::pair<mapiter, mapiter> get_range(K off, K len) {
40 // fst is first iterator with end after off (may be end)
41 auto fst = m.upper_bound(off);
44 if (fst != m.end() && off >= (fst->first + fst->second.first))
47 // lst is first iterator with start after off + len (may be end)
48 auto lst = m.lower_bound(off + len);
49 return std::make_pair(fst, lst);
51 std::pair<cmapiter, cmapiter> get_range(K off, K len) const {
52 // fst is first iterator with end after off (may be end)
53 auto fst = m.upper_bound(off);
56 if (fst != m.end() && off >= (fst->first + fst->second.first))
59 // lst is first iterator with start after off + len (may be end)
60 auto lst = m.lower_bound(off + len);
61 return std::make_pair(fst, lst);
63 void try_merge(mapiter niter) {
64 if (niter != m.begin()) {
67 if (prev->first + prev->second.first == niter->first &&
68 s.can_merge(prev->second.second, niter->second.second)) {
70 std::move(prev->second.second),
71 std::move(niter->second.second));
73 K len = niter->first + niter->second.first - off;
79 std::make_pair(len, std::move(n))));
86 if (next != m.end() &&
87 niter->first + niter->second.first == next->first &&
88 s.can_merge(niter->second.second, next->second.second)) {
90 std::move(niter->second.second),
91 std::move(next->second.second));
93 K len = next->first + next->second.first - off;
99 std::make_pair(len, std::move(n))));
104 interval_map intersect(K off, K len) const {
106 auto limits = get_range(off, len);
107 for (auto i = limits.first; i != limits.second; ++i) {
109 K l = i->second.first;
110 V v = i->second.second;
114 v = s.split(off - o, l, p);
117 if ((o + l) > (off + len)) {
119 l -= (o + l) - (off + len);
120 v = s.split(0, l, p);
129 void erase(K off, K len) {
132 auto range = get_range(off, len);
138 for (auto i = range.first; i != range.second; ++i) {
139 if (i->first < off) {
140 to_insert.emplace_back(
145 s.split(0, off - i->first, i->second.second))));
147 if ((off + len) < (i->first + i->second.first)) {
148 K nlen = (i->first + i->second.first) - (off + len);
149 to_insert.emplace_back(
154 s.split(i->second.first - nlen, nlen, i->second.second))));
157 m.erase(range.first, range.second);
158 m.insert(to_insert.begin(), to_insert.end());
160 void insert(K off, K len, V &&v) {
162 assert(len == s.length(v));
164 auto p = m.insert(make_pair(off, std::make_pair(len, std::forward<V>(v))));
168 void insert(interval_map &&other) {
169 for (auto i = other.m.begin();
171 other.m.erase(i++)) {
172 insert(i->first, i->second.first, std::move(i->second.second));
175 void insert(K off, K len, const V &v) {
177 assert(len == s.length(v));
179 auto p = m.insert(make_pair(off, std::make_pair(len, v)));
183 void insert(const interval_map &other) {
184 for (auto &&i: other) {
185 insert(i.get_off(), i.get_len(), i.get_val());
191 interval_set<K> get_interval_set() const {
193 for (auto &&i: *this) {
194 ret.insert(i.get_off(), i.get_len());
198 class const_iterator {
200 const_iterator(cmapiter &&it) : it(std::move(it)) {}
201 const_iterator(const cmapiter &it) : it(it) {}
203 friend class interval_map;
205 const_iterator(const const_iterator &) = default;
206 const_iterator &operator=(const const_iterator &) = default;
208 const_iterator &operator++() {
212 const_iterator operator++(int) {
213 return const_iterator(it++);
215 const_iterator &operator--() {
219 const_iterator operator--(int) {
220 return const_iterator(it--);
222 bool operator==(const const_iterator &rhs) const {
225 bool operator!=(const const_iterator &rhs) const {
232 return it->second.first;
234 const V &get_val() const {
235 return it->second.second;
237 const_iterator &operator*() {
241 const_iterator begin() const {
242 return const_iterator(m.begin());
244 const_iterator end() const {
245 return const_iterator(m.end());
247 std::pair<const_iterator, const_iterator> get_containing_range(
250 auto rng = get_range(off, len);
251 return std::make_pair(const_iterator(rng.first), const_iterator(rng.second));
253 unsigned ext_count() const {
256 bool operator==(const interval_map &rhs) const {
260 std::ostream &print(std::ostream &out) const {
263 for (auto &&i: *this) {
269 out << i.get_off() << "~" << i.get_len() << "("
270 << s.length(i.get_val()) << ")";
276 template <typename K, typename V, typename S>
277 std::ostream &operator<<(std::ostream &out, const interval_map<K, V, S> &m) {