src/ceph/src/common/interval_map.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2016 Red Hat
   7  *
   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.
  12  *
  13  */
  14
  15 #ifndef INTERVAL_MAP_H
  16 #define INTERVAL_MAP_H
  17
  18 #include "include/interval_set.h"
  19
  20 template <typename K, typename V, typename S>
  21 /**
  22  * interval_map
  23  *
  24  * Maps intervals to values.  Erasing or inserting over an existing
  25  * range will use S::operator() to split any overlapping existing
  26  * values.
  27  *
  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.
  32  */
  33 class interval_map {
  34   S s;
  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;
  38   map m;
  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);
  42     if (fst != m.begin())
  43       --fst;
  44     if (fst != m.end() && off >= (fst->first + fst->second.first))
  45       ++fst;
  46
  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);
  50   }
  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);
  54     if (fst != m.begin())
  55       --fst;
  56     if (fst != m.end() && off >= (fst->first + fst->second.first))
  57       ++fst;
  58
  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);
  62   }
  63   void try_merge(mapiter niter) {
  64     if (niter != m.begin()) {
  65       auto prev = niter;
  66       prev--;
  67       if (prev->first + prev->second.first == niter->first &&
  68           s.can_merge(prev->second.second, niter->second.second)) {
  69         V n = s.merge(
  70           std::move(prev->second.second),
  71           std::move(niter->second.second));
  72         K off = prev->first;
  73         K len = niter->first + niter->second.first - off;
  74         niter++;
  75         m.erase(prev, niter);
  76         auto p = m.insert(
  77           std::make_pair(
  78             off,
  79             std::make_pair(len, std::move(n))));
  80         assert(p.second);
  81         niter = p.first;
  82       }
  83     }
  84     auto next = niter;
  85     next++;
  86     if (next != m.end() &&
  87         niter->first + niter->second.first == next->first &&
  88         s.can_merge(niter->second.second, next->second.second)) {
  89       V n = s.merge(
  90         std::move(niter->second.second),
  91         std::move(next->second.second));
  92       K off = niter->first;
  93       K len = next->first + next->second.first - off;
  94       next++;
  95       m.erase(niter, next);
  96       auto p = m.insert(
  97         std::make_pair(
  98           off,
  99           std::make_pair(len, std::move(n))));
 100       assert(p.second);
 101     }
 102   }
 103 public:
 104   interval_map intersect(K off, K len) const {
 105     interval_map ret;
 106     auto limits = get_range(off, len);
 107     for (auto i = limits.first; i != limits.second; ++i) {
 108       K o = i->first;
 109       K l = i->second.first;
 110       V v = i->second.second;
 111       if (o < off) {
 112         V p = v;
 113         l -= (off - o);
 114         v = s.split(off - o, l, p);
 115         o = off;
 116       }
 117       if ((o + l) > (off + len)) {
 118         V p = v;
 119         l -= (o + l) - (off + len);
 120         v = s.split(0, l, p);
 121       }
 122       ret.insert(o, l, v);
 123     }
 124     return ret;
 125   }
 126   void clear() {
 127     m.clear();
 128   }
 129   void erase(K off, K len) {
 130     if (len == 0)
 131       return;
 132     auto range = get_range(off, len);
 133     std::vector<
 134       std::pair<
 135         K,
 136         std::pair<K, V>
 137         >> to_insert;
 138     for (auto i = range.first; i != range.second; ++i) {
 139       if (i->first < off) {
 140         to_insert.emplace_back(
 141           std::make_pair(
 142             i->first,
 143             std::make_pair(
 144               off - i->first,
 145               s.split(0, off - i->first, i->second.second))));
 146       }
 147       if ((off + len) < (i->first + i->second.first)) {
 148         K nlen = (i->first + i->second.first) - (off + len);
 149         to_insert.emplace_back(
 150           std::make_pair(
 151             off + len,
 152             std::make_pair(
 153               nlen,
 154               s.split(i->second.first - nlen, nlen, i->second.second))));
 155       }
 156     }
 157     m.erase(range.first, range.second);
 158     m.insert(to_insert.begin(), to_insert.end());
 159   }
 160   void insert(K off, K len, V &&v) {
 161     assert(len > 0);
 162     assert(len == s.length(v));
 163     erase(off, len);
 164     auto p = m.insert(make_pair(off, std::make_pair(len, std::forward<V>(v))));
 165     assert(p.second);
 166     try_merge(p.first);
 167   }
 168   void insert(interval_map &&other) {
 169     for (auto i = other.m.begin();
 170          i != other.m.end();
 171          other.m.erase(i++)) {
 172       insert(i->first, i->second.first, std::move(i->second.second));
 173     }
 174   }
 175   void insert(K off, K len, const V &v) {
 176     assert(len > 0);
 177     assert(len == s.length(v));
 178     erase(off, len);
 179     auto p = m.insert(make_pair(off, std::make_pair(len, v)));
 180     assert(p.second);
 181     try_merge(p.first);
 182   }
 183   void insert(const interval_map &other) {
 184     for (auto &&i: other) {
 185       insert(i.get_off(), i.get_len(), i.get_val());
 186     }
 187   }
 188   bool empty() const {
 189     return m.empty();
 190   }
 191   interval_set<K> get_interval_set() const {
 192     interval_set<K> ret;
 193     for (auto &&i: *this) {
 194       ret.insert(i.get_off(), i.get_len());
 195     }
 196     return ret;
 197   }
 198   class const_iterator {
 199     cmapiter it;
 200     const_iterator(cmapiter &&it) : it(std::move(it)) {}
 201     const_iterator(const cmapiter &it) : it(it) {}
 202
 203     friend class interval_map;
 204   public:
 205     const_iterator(const const_iterator &) = default;
 206     const_iterator &operator=(const const_iterator &) = default;
 207
 208     const_iterator &operator++() {
 209       ++it;
 210       return *this;
 211     }
 212     const_iterator operator++(int) {
 213       return const_iterator(it++);
 214     }
 215     const_iterator &operator--() {
 216       --it;
 217       return *this;
 218     }
 219     const_iterator operator--(int) {
 220       return const_iterator(it--);
 221     }
 222     bool operator==(const const_iterator &rhs) const {
 223       return it == rhs.it;
 224     }
 225     bool operator!=(const const_iterator &rhs) const {
 226       return it != rhs.it;
 227     }
 228     K get_off() const {
 229       return it->first;
 230     }
 231     K get_len() const {
 232       return it->second.first;
 233     }
 234     const V &get_val() const {
 235       return it->second.second;
 236     }
 237     const_iterator &operator*() {
 238       return *this;
 239     }
 240   };
 241   const_iterator begin() const {
 242     return const_iterator(m.begin());
 243   }
 244   const_iterator end() const {
 245     return const_iterator(m.end());
 246   }
 247   std::pair<const_iterator, const_iterator> get_containing_range(
 248     K off,
 249     K len) const {
 250     auto rng = get_range(off, len);
 251     return std::make_pair(const_iterator(rng.first), const_iterator(rng.second));
 252   }
 253   unsigned ext_count() const {
 254     return m.size();
 255   }
 256   bool operator==(const interval_map &rhs) const {
 257     return m == rhs.m;
 258   }
 259
 260   std::ostream &print(std::ostream &out) const {
 261     bool first = true;
 262     out << "{";
 263     for (auto &&i: *this) {
 264       if (first) {
 265         first = false;
 266       } else {
 267         out << ",";
 268       }
 269       out << i.get_off() << "~" << i.get_len() << "("
 270           << s.length(i.get_val()) << ")";
 271     }
 272     return out << "}";
 273   }
 274 };
 275
 276 template <typename K, typename V, typename S>
 277 std::ostream &operator<<(std::ostream &out, const interval_map<K, V, S> &m) {
 278   return m.print(out);
 279 }
 280
 281 #endif