ceph/src/include/interval_set.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) 2004-2006 Sage Weil <sage@newdream.net>
   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
  16 #ifndef CEPH_INTERVAL_SET_H
  17 #define CEPH_INTERVAL_SET_H
  18
  19 #include <iterator>
  20 #include <map>
  21 #include <ostream>
  22
  23 #include "encoding.h"
  24
  25 #ifndef MIN
  26 # define MIN(a,b)  ((a)<=(b) ? (a):(b))
  27 #endif
  28 #ifndef MAX
  29 # define MAX(a,b)  ((a)>=(b) ? (a):(b))
  30 #endif
  31
  32
  33 template<typename T>
  34 class interval_set {
  35  public:
  36
  37   class const_iterator;
  38
  39   class iterator : public std::iterator <std::forward_iterator_tag, T>
  40   {
  41     public:
  42         explicit iterator(typename std::map<T,T>::iterator iter)
  43           : _iter(iter)
  44         { }
  45
  46         // For the copy constructor and assignment operator, the compiler-generated functions, which
  47         // perform simple bitwise copying, should be fine.
  48
  49         bool operator==(const iterator& rhs) const {
  50           return (_iter == rhs._iter);
  51         }
  52
  53         bool operator!=(const iterator& rhs) const {
  54           return (_iter != rhs._iter);
  55         }
  56
  57         // Dereference this iterator to get a pair.
  58         std::pair < T, T > &operator*() {
  59                 return *_iter;
  60         }
  61
  62         // Return the interval start.
  63         T get_start() const {
  64                 return _iter->first;
  65         }
  66
  67         // Return the interval length.
  68         T get_len() const {
  69                 return _iter->second;
  70         }
  71
  72         // Set the interval length.
  73         void set_len(T len) {
  74                 _iter->second = len;
  75         }
  76
  77         // Preincrement
  78         iterator &operator++()
  79         {
  80                 ++_iter;
  81                 return *this;
  82         }
  83
  84         // Postincrement
  85         iterator operator++(int)
  86         {
  87                 iterator prev(_iter);
  88                 ++_iter;
  89                 return prev;
  90         }
  91
  92     friend class interval_set<T>::const_iterator;
  93
  94     protected:
  95         typename std::map<T,T>::iterator _iter;
  96     friend class interval_set<T>;
  97   };
  98
  99   class const_iterator : public std::iterator <std::forward_iterator_tag, T>
 100   {
 101     public:
 102         explicit const_iterator(typename std::map<T,T>::const_iterator iter)
 103           : _iter(iter)
 104         { }
 105
 106         const_iterator(const iterator &i)
 107           : _iter(i._iter)
 108         { }
 109
 110         // For the copy constructor and assignment operator, the compiler-generated functions, which
 111         // perform simple bitwise copying, should be fine.
 112
 113         bool operator==(const const_iterator& rhs) const {
 114           return (_iter == rhs._iter);
 115         }
 116
 117         bool operator!=(const const_iterator& rhs) const {
 118           return (_iter != rhs._iter);
 119         }
 120
 121         // Dereference this iterator to get a pair.
 122         std::pair < T, T > operator*() const {
 123                 return *_iter;
 124         }
 125
 126         // Return the interval start.
 127         T get_start() const {
 128                 return _iter->first;
 129         }
 130
 131         // Return the interval length.
 132         T get_len() const {
 133                 return _iter->second;
 134         }
 135
 136         // Preincrement
 137         const_iterator &operator++()
 138         {
 139                 ++_iter;
 140                 return *this;
 141         }
 142
 143         // Postincrement
 144         const_iterator operator++(int)
 145         {
 146                 const_iterator prev(_iter);
 147                 ++_iter;
 148                 return prev;
 149         }
 150
 151     protected:
 152         typename std::map<T,T>::const_iterator _iter;
 153   };
 154
 155   interval_set() : _size(0) {}
 156   interval_set(std::map<T,T>& other) {
 157     m.swap(other);
 158     _size = 0;
 159     for (auto& i : m) {
 160       _size += i.second;
 161     }
 162   }
 163
 164   int num_intervals() const
 165   {
 166     return m.size();
 167   }
 168
 169   typename interval_set<T>::iterator begin() {
 170     return typename interval_set<T>::iterator(m.begin());
 171   }
 172
 173   typename interval_set<T>::iterator lower_bound(T start) {
 174     return typename interval_set<T>::iterator(find_inc_m(start));
 175   }
 176
 177   typename interval_set<T>::iterator end() {
 178     return typename interval_set<T>::iterator(m.end());
 179   }
 180
 181   typename interval_set<T>::const_iterator begin() const {
 182     return typename interval_set<T>::const_iterator(m.begin());
 183   }
 184
 185   typename interval_set<T>::const_iterator lower_bound(T start) const {
 186     return typename interval_set<T>::const_iterator(find_inc(start));
 187   }
 188
 189   typename interval_set<T>::const_iterator end() const {
 190     return typename interval_set<T>::const_iterator(m.end());
 191   }
 192
 193   // helpers
 194  private:
 195   typename std::map<T,T>::const_iterator find_inc(T start) const {
 196     typename std::map<T,T>::const_iterator p = m.lower_bound(start);  // p->first >= start
 197     if (p != m.begin() &&
 198         (p == m.end() || p->first > start)) {
 199       p--;   // might overlap?
 200       if (p->first + p->second <= start)
 201         p++; // it doesn't.
 202     }
 203     return p;
 204   }
 205
 206   typename std::map<T,T>::iterator find_inc_m(T start) {
 207     typename std::map<T,T>::iterator p = m.lower_bound(start);
 208     if (p != m.begin() &&
 209         (p == m.end() || p->first > start)) {
 210       p--;   // might overlap?
 211       if (p->first + p->second <= start)
 212         p++; // it doesn't.
 213     }
 214     return p;
 215   }
 216
 217   typename std::map<T,T>::const_iterator find_adj(T start) const {
 218     typename std::map<T,T>::const_iterator p = m.lower_bound(start);
 219     if (p != m.begin() &&
 220         (p == m.end() || p->first > start)) {
 221       p--;   // might touch?
 222       if (p->first + p->second < start)
 223         p++; // it doesn't.
 224     }
 225     return p;
 226   }
 227
 228   typename std::map<T,T>::iterator find_adj_m(T start) {
 229     typename std::map<T,T>::iterator p = m.lower_bound(start);
 230     if (p != m.begin() &&
 231         (p == m.end() || p->first > start)) {
 232       p--;   // might touch?
 233       if (p->first + p->second < start)
 234         p++; // it doesn't.
 235     }
 236     return p;
 237   }
 238
 239  public:
 240   bool operator==(const interval_set& other) const {
 241     return _size == other._size && m == other.m;
 242   }
 243
 244   int64_t size() const {
 245     return _size;
 246   }
 247
 248   void bound_encode(size_t& p) const {
 249     denc_traits<std::map<T,T>>::bound_encode(m, p);
 250   }
 251   void encode(bufferlist::contiguous_appender& p) const {
 252     denc(m, p);
 253   }
 254   void decode(bufferptr::iterator& p) {
 255     denc(m, p);
 256     _size = 0;
 257     for (const auto& i : m) {
 258       _size += i.second;
 259     }
 260   }
 261   void decode(bufferlist::iterator& p) {
 262     denc(m, p);
 263     _size = 0;
 264     for (const auto& i : m) {
 265       _size += i.second;
 266     }
 267   }
 268
 269   void encode_nohead(bufferlist::contiguous_appender& p) const {
 270     denc_traits<std::map<T,T>>::encode_nohead(m, p);
 271   }
 272   void decode_nohead(int n, bufferptr::iterator& p) {
 273     denc_traits<std::map<T,T>>::decode_nohead(n, m, p);
 274     _size = 0;
 275     for (const auto& i : m) {
 276       _size += i.second;
 277     }
 278   }
 279
 280   void clear() {
 281     m.clear();
 282     _size = 0;
 283   }
 284
 285   bool contains(T i, T *pstart=0, T *plen=0) const {
 286     typename std::map<T,T>::const_iterator p = find_inc(i);
 287     if (p == m.end()) return false;
 288     if (p->first > i) return false;
 289     if (p->first+p->second <= i) return false;
 290     assert(p->first <= i && p->first+p->second > i);
 291     if (pstart)
 292       *pstart = p->first;
 293     if (plen)
 294       *plen = p->second;
 295     return true;
 296   }
 297   bool contains(T start, T len) const {
 298     typename std::map<T,T>::const_iterator p = find_inc(start);
 299     if (p == m.end()) return false;
 300     if (p->first > start) return false;
 301     if (p->first+p->second <= start) return false;
 302     assert(p->first <= start && p->first+p->second > start);
 303     if (p->first+p->second < start+len) return false;
 304     return true;
 305   }
 306   bool intersects(T start, T len) const {
 307     interval_set a;
 308     a.insert(start, len);
 309     interval_set i;
 310     i.intersection_of( *this, a );
 311     if (i.empty()) return false;
 312     return true;
 313   }
 314
 315   // outer range of set
 316   bool empty() const {
 317     return m.empty();
 318   }
 319   T range_start() const {
 320     assert(!empty());
 321     typename std::map<T,T>::const_iterator p = m.begin();
 322     return p->first;
 323   }
 324   T range_end() const {
 325     assert(!empty());
 326     typename std::map<T,T>::const_iterator p = m.end();
 327     p--;
 328     return p->first+p->second;
 329   }
 330
 331   // interval start after p (where p not in set)
 332   bool starts_after(T i) const {
 333     assert(!contains(i));
 334     typename std::map<T,T>::const_iterator p = find_inc(i);
 335     if (p == m.end()) return false;
 336     return true;
 337   }
 338   T start_after(T i) const {
 339     assert(!contains(i));
 340     typename std::map<T,T>::const_iterator p = find_inc(i);
 341     return p->first;
 342   }
 343
 344   // interval end that contains start
 345   T end_after(T start) const {
 346     assert(contains(start));
 347     typename std::map<T,T>::const_iterator p = find_inc(start);
 348     return p->first+p->second;
 349   }
 350
 351   void insert(T val) {
 352     insert(val, 1);
 353   }
 354
 355   void insert(T start, T len, T *pstart=0, T *plen=0) {
 356     //cout << "insert " << start << "~" << len << endl;
 357     assert(len > 0);
 358     _size += len;
 359     typename std::map<T,T>::iterator p = find_adj_m(start);
 360     if (p == m.end()) {
 361       m[start] = len;                  // new interval
 362       if (pstart)
 363         *pstart = start;
 364       if (plen)
 365         *plen = len;
 366     } else {
 367       if (p->first < start) {
 368
 369         if (p->first + p->second != start) {
 370           //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
 371           ceph_abort();
 372         }
 373
 374         p->second += len;               // append to end
 375
 376         typename std::map<T,T>::iterator n = p;
 377         n++;
 378         if (n != m.end() &&
 379             start+len == n->first) {   // combine with next, too!
 380           p->second += n->second;
 381           m.erase(n);
 382         }
 383         if (pstart)
 384           *pstart = p->first;
 385         if (plen)
 386           *plen = p->second;
 387       } else {
 388         if (start+len == p->first) {
 389           m[start] = len + p->second;  // append to front
 390           if (pstart)
 391             *pstart = start;
 392           if (plen)
 393             *plen = len + p->second;
 394           m.erase(p);
 395         } else {
 396           assert(p->first > start+len);
 397           m[start] = len;              // new interval
 398           if (pstart)
 399             *pstart = start;
 400           if (plen)
 401             *plen = len;
 402         }
 403       }
 404     }
 405   }
 406
 407   void swap(interval_set<T>& other) {
 408     m.swap(other.m);
 409     std::swap(_size, other._size);
 410   }
 411
 412   void erase(iterator &i) {
 413     _size -= i.get_len();
 414     assert(_size >= 0);
 415     m.erase(i._iter);
 416   }
 417
 418   void erase(T val) {
 419     erase(val, 1);
 420   }
 421
 422   void erase(T start, T len) {
 423     typename std::map<T,T>::iterator p = find_inc_m(start);
 424
 425     _size -= len;
 426     assert(_size >= 0);
 427
 428     assert(p != m.end());
 429     assert(p->first <= start);
 430
 431     T before = start - p->first;
 432     assert(p->second >= before+len);
 433     T after = p->second - before - len;
 434
 435     if (before)
 436       p->second = before;        // shorten bit before
 437     else
 438       m.erase(p);
 439     if (after)
 440       m[start+len] = after;
 441   }
 442
 443
 444   void subtract(const interval_set &a) {
 445     for (typename std::map<T,T>::const_iterator p = a.m.begin();
 446          p != a.m.end();
 447          p++)
 448       erase(p->first, p->second);
 449   }
 450
 451   void insert(const interval_set &a) {
 452     for (typename std::map<T,T>::const_iterator p = a.m.begin();
 453          p != a.m.end();
 454          p++)
 455       insert(p->first, p->second);
 456   }
 457
 458
 459   void intersection_of(const interval_set &a, const interval_set &b) {
 460     assert(&a != this);
 461     assert(&b != this);
 462     clear();
 463
 464     typename std::map<T,T>::const_iterator pa = a.m.begin();
 465     typename std::map<T,T>::const_iterator pb = b.m.begin();
 466     typename decltype(m)::iterator mi = m.begin();
 467
 468     while (pa != a.m.end() && pb != b.m.end()) {
 469       // passing?
 470       if (pa->first + pa->second <= pb->first)
 471         { pa++;  continue; }
 472       if (pb->first + pb->second <= pa->first)
 473         { pb++;  continue; }
 474
 475       if (*pa == *pb) {
 476         do {
 477           mi = m.insert(mi, *pa);
 478           _size += pa->second;
 479           ++pa;
 480           ++pb;
 481         } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
 482         continue;
 483       }
 484
 485       T start = MAX(pa->first, pb->first);
 486       T en = MIN(pa->first+pa->second, pb->first+pb->second);
 487       assert(en > start);
 488       typename decltype(m)::value_type i{start, en - start};
 489       mi = m.insert(mi, i);
 490       _size += i.second;
 491       if (pa->first+pa->second > pb->first+pb->second)
 492         pb++;
 493       else
 494         pa++;
 495     }
 496   }
 497   void intersection_of(const interval_set& b) {
 498     interval_set a;
 499     swap(a);
 500     intersection_of(a, b);
 501   }
 502
 503   void union_of(const interval_set &a, const interval_set &b) {
 504     assert(&a != this);
 505     assert(&b != this);
 506     clear();
 507
 508     //cout << "union_of" << endl;
 509
 510     // a
 511     m = a.m;
 512     _size = a._size;
 513
 514     // - (a*b)
 515     interval_set ab;
 516     ab.intersection_of(a, b);
 517     subtract(ab);
 518
 519     // + b
 520     insert(b);
 521     return;
 522   }
 523   void union_of(const interval_set &b) {
 524     interval_set a;
 525     swap(a);
 526     union_of(a, b);
 527   }
 528   void union_insert(T off, T len) {
 529     interval_set a;
 530     a.insert(off, len);
 531     union_of(a);
 532   }
 533
 534   bool subset_of(const interval_set &big) const {
 535     for (typename std::map<T,T>::const_iterator i = m.begin();
 536          i != m.end();
 537          i++)
 538       if (!big.contains(i->first, i->second)) return false;
 539     return true;
 540   }
 541
 542   /*
 543    * build a subset of @other, starting at or after @start, and including
 544    * @len worth of values, skipping holes.  e.g.,
 545    *  span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
 546    */
 547   void span_of(const interval_set &other, T start, T len) {
 548     clear();
 549     typename std::map<T,T>::const_iterator p = other.find_inc(start);
 550     if (p == other.m.end())
 551       return;
 552     if (p->first < start) {
 553       if (p->first + p->second < start)
 554         return;
 555       if (p->first + p->second < start + len) {
 556         T howmuch = p->second - (start - p->first);
 557         insert(start, howmuch);
 558         len -= howmuch;
 559         p++;
 560       } else {
 561         insert(start, len);
 562         return;
 563       }
 564     }
 565     while (p != other.m.end() && len > 0) {
 566       if (p->second < len) {
 567         insert(p->first, p->second);
 568         len -= p->second;
 569         p++;
 570       } else {
 571         insert(p->first, len);
 572         return;
 573       }
 574     }
 575   }
 576
 577   /*
 578    * Move contents of m into another std::map<T,T>. Use that instead of
 579    * encoding interval_set into bufferlist then decoding it back into std::map.
 580    */
 581   void move_into(std::map<T,T>& other) {
 582     other = std::move(m);
 583   }
 584
 585 private:
 586   // data
 587   int64_t _size;
 588   std::map<T,T> m;   // map start -> len
 589 };
 590
 591 // declare traits explicitly because (1) it's templatized, and (2) we
 592 // want to include _nohead variants.
 593 template<typename T>
 594 struct denc_traits<interval_set<T>> {
 595   static constexpr bool supported = true;
 596   static constexpr bool bounded = false;
 597   static constexpr bool featured = false;
 598   static constexpr bool need_contiguous = denc_traits<T>::need_contiguous;
 599   static void bound_encode(const interval_set<T>& v, size_t& p) {
 600     v.bound_encode(p);
 601   }
 602   static void encode(const interval_set<T>& v,
 603                      bufferlist::contiguous_appender& p) {
 604     v.encode(p);
 605   }
 606   static void decode(interval_set<T>& v, bufferptr::iterator& p) {
 607     v.decode(p);
 608   }
 609   template<typename U=T>
 610     static typename std::enable_if<sizeof(U) && !need_contiguous>::type
 611     decode(interval_set<T>& v, bufferlist::iterator& p) {
 612     v.decode(p);
 613   }
 614   static void encode_nohead(const interval_set<T>& v,
 615                             bufferlist::contiguous_appender& p) {
 616     v.encode_nohead(p);
 617   }
 618   static void decode_nohead(size_t n, interval_set<T>& v,
 619                             bufferptr::iterator& p) {
 620     v.decode_nohead(n, p);
 621   }
 622 };
 623
 624
 625 template<class T>
 626 inline std::ostream& operator<<(std::ostream& out, const interval_set<T> &s) {
 627   out << "[";
 628   const char *prequel = "";
 629   for (typename interval_set<T>::const_iterator i = s.begin();
 630        i != s.end();
 631        ++i)
 632   {
 633     out << prequel << i.get_start() << "~" << i.get_len();
 634     prequel = ",";
 635   }
 636   out << "]";
 637   return out;
 638 }
 639
 640
 641 #endif