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 /*
  26  * *** NOTE ***
  27  *
  28  * This class is written to work with a variety of map-like containers,
  29  * *include* ones that invalidate iterators when they are modified (e.g.,
  30  * flat_map and btree_map).
  31  */
  32
  33 template<typename T, typename Map = std::map<T,T>>
  34 class interval_set {
  35  public:
  36   using value_type = typename Map::value_type;
  37   using offset_type = T;
  38   using length_type = T;
  39   using reference = value_type&;
  40   using const_reference = const value_type&;
  41   using size_type = typename Map::size_type;
  42
  43   class const_iterator;
  44
  45   class iterator : public std::iterator <std::forward_iterator_tag, T>
  46   {
  47     public:
  48         explicit iterator(typename Map::iterator iter)
  49           : _iter(iter)
  50         { }
  51
  52         // For the copy constructor and assignment operator, the compiler-generated functions, which
  53         // perform simple bitwise copying, should be fine.
  54
  55         bool operator==(const iterator& rhs) const {
  56           return (_iter == rhs._iter);
  57         }
  58
  59         bool operator!=(const iterator& rhs) const {
  60           return (_iter != rhs._iter);
  61         }
  62
  63         // Dereference this iterator to get a pair.
  64         reference operator*() const {
  65           return *_iter;
  66         }
  67
  68         // Return the interval start.
  69         offset_type get_start() const {
  70           return _iter->first;
  71         }
  72
  73         // Return the interval length.
  74         length_type get_len() const {
  75           return _iter->second;
  76         }
  77
  78         offset_type get_end() const {
  79           return _iter->first + _iter->second;
  80         }
  81
  82         // Set the interval length.
  83         void set_len(const length_type& len) {
  84           _iter->second = len;
  85         }
  86
  87         // Preincrement
  88         iterator& operator++()
  89         {
  90           ++_iter;
  91           return *this;
  92         }
  93
  94         // Postincrement
  95         iterator operator++(int)
  96         {
  97           iterator prev(_iter);
  98           ++_iter;
  99           return prev;
 100         }
 101
 102     friend class interval_set::const_iterator;
 103
 104     protected:
 105         typename Map::iterator _iter;
 106     friend class interval_set;
 107   };
 108
 109   class const_iterator : public std::iterator <std::forward_iterator_tag, T>
 110   {
 111     public:
 112         explicit const_iterator(typename Map::const_iterator iter)
 113           : _iter(iter)
 114         { }
 115
 116         const_iterator(const iterator &i)
 117           : _iter(i._iter)
 118         { }
 119
 120         // For the copy constructor and assignment operator, the compiler-generated functions, which
 121         // perform simple bitwise copying, should be fine.
 122
 123         bool operator==(const const_iterator& rhs) const {
 124           return (_iter == rhs._iter);
 125         }
 126
 127         bool operator!=(const const_iterator& rhs) const {
 128           return (_iter != rhs._iter);
 129         }
 130
 131         // Dereference this iterator to get a pair.
 132         const_reference operator*() const {
 133           return *_iter;
 134         }
 135
 136         // Return the interval start.
 137         offset_type get_start() const {
 138           return _iter->first;
 139         }
 140         offset_type get_end() const {
 141           return _iter->first + _iter->second;
 142         }
 143
 144         // Return the interval length.
 145         length_type get_len() const {
 146           return _iter->second;
 147         }
 148
 149         // Preincrement
 150         const_iterator& operator++()
 151         {
 152           ++_iter;
 153           return *this;
 154         }
 155
 156         // Postincrement
 157         const_iterator operator++(int)
 158         {
 159           const_iterator prev(_iter);
 160           ++_iter;
 161           return prev;
 162         }
 163
 164     protected:
 165         typename Map::const_iterator _iter;
 166   };
 167
 168   interval_set() = default;
 169   interval_set(Map&& other) {
 170     m.swap(other);
 171     for (const auto& p : m) {
 172       _size += p.second;
 173     }
 174   }
 175
 176   size_type num_intervals() const
 177   {
 178     return m.size();
 179   }
 180
 181   iterator begin() {
 182     return iterator(m.begin());
 183   }
 184
 185   iterator lower_bound(T start) {
 186     return iterator(find_inc_m(start));
 187   }
 188
 189   iterator end() {
 190     return iterator(m.end());
 191   }
 192
 193   const_iterator begin() const {
 194     return const_iterator(m.begin());
 195   }
 196
 197   const_iterator lower_bound(T start) const {
 198     return const_iterator(find_inc(start));
 199   }
 200
 201   const_iterator end() const {
 202     return const_iterator(m.end());
 203   }
 204
 205   // helpers
 206  private:
 207   auto find_inc(T start) const {
 208     auto p = m.lower_bound(start);  // p->first >= start
 209     if (p != m.begin() &&
 210         (p == m.end() || p->first > start)) {
 211       --p;   // might overlap?
 212       if (p->first + p->second <= start)
 213         ++p; // it doesn't.
 214     }
 215     return p;
 216   }
 217
 218   auto find_inc_m(T start) {
 219     auto p = m.lower_bound(start);
 220     if (p != m.begin() &&
 221         (p == m.end() || p->first > start)) {
 222       --p;   // might overlap?
 223       if (p->first + p->second <= start)
 224         ++p; // it doesn't.
 225     }
 226     return p;
 227   }
 228
 229   auto find_adj(T start) const {
 230     auto p = m.lower_bound(start);
 231     if (p != m.begin() &&
 232         (p == m.end() || p->first > start)) {
 233       --p;   // might touch?
 234       if (p->first + p->second < start)
 235         ++p; // it doesn't.
 236     }
 237     return p;
 238   }
 239
 240   auto find_adj_m(T start) {
 241     auto p = m.lower_bound(start);
 242     if (p != m.begin() &&
 243         (p == m.end() || p->first > start)) {
 244       --p;   // might touch?
 245       if (p->first + p->second < start)
 246         ++p; // it doesn't.
 247     }
 248     return p;
 249   }
 250
 251   void intersection_size_asym(const interval_set &s, const interval_set &l) {
 252     auto ps = s.m.begin();
 253     ceph_assert(ps != s.m.end());
 254     auto offset = ps->first;
 255     bool first = true;
 256     auto mi = m.begin();
 257
 258     while (1) {
 259       if (first)
 260         first = false;
 261       auto pl = l.find_inc(offset);
 262       if (pl == l.m.end())
 263         break;
 264       while (ps != s.m.end() && ps->first + ps->second <= pl->first)
 265         ++ps;
 266       if (ps == s.m.end())
 267         break;
 268       offset = pl->first + pl->second;
 269       if (offset <= ps->first) {
 270         offset = ps->first;
 271         continue;
 272       }
 273
 274       if (*ps == *pl) {
 275         do {
 276           mi = m.insert(mi, *ps);
 277           _size += ps->second;
 278           ++ps;
 279           ++pl;
 280         } while (ps != s.m.end() && pl != l.m.end() && *ps == *pl);
 281         if (ps == s.m.end())
 282           break;
 283         offset = ps->first;
 284         continue;
 285       }
 286
 287       auto start = std::max<T>(ps->first, pl->first);
 288       auto en = std::min<T>(ps->first + ps->second, offset);
 289       ceph_assert(en > start);
 290       mi = m.emplace_hint(mi, start, en - start);
 291       _size += mi->second;
 292       if (ps->first + ps->second <= offset) {
 293         ++ps;
 294         if (ps == s.m.end())
 295           break;
 296         offset = ps->first;
 297       }
 298     }
 299   }
 300
 301   bool subset_size_sym(const interval_set &b) const {
 302     auto pa = m.begin(), pb = b.m.begin();
 303     const auto a_end = m.end(), b_end = b.m.end();
 304
 305     while (pa != a_end && pb != b_end) {
 306       while (pb->first + pb->second <= pa->first) {
 307         ++pb;
 308         if (pb == b_end)
 309           return false;
 310       }
 311
 312       if (*pa == *pb) {
 313         do {
 314           ++pa;
 315           ++pb;
 316         } while (pa != a_end && pb != b_end && *pa == *pb);
 317         continue;
 318       }
 319
 320       // interval begins before other
 321       if (pa->first < pb->first)
 322         return false;
 323       // interval is longer than other
 324       if (pa->first + pa->second > pb->first + pb->second)
 325         return false;
 326
 327       ++pa;
 328     }
 329
 330     return pa == a_end;
 331   }
 332
 333  public:
 334   bool operator==(const interval_set& other) const {
 335     return _size == other._size && m == other.m;
 336   }
 337
 338   uint64_t size() const {
 339     return _size;
 340   }
 341
 342   void bound_encode(size_t& p) const {
 343     denc_traits<Map>::bound_encode(m, p);
 344   }
 345   void encode(ceph::buffer::list::contiguous_appender& p) const {
 346     denc(m, p);
 347   }
 348   void decode(ceph::buffer::ptr::const_iterator& p) {
 349     denc(m, p);
 350     _size = 0;
 351     for (const auto& p : m) {
 352       _size += p.second;
 353     }
 354   }
 355   void decode(ceph::buffer::list::iterator& p) {
 356     denc(m, p);
 357     _size = 0;
 358     for (const auto& p : m) {
 359       _size += p.second;
 360     }
 361   }
 362
 363   void encode_nohead(ceph::buffer::list::contiguous_appender& p) const {
 364     denc_traits<Map>::encode_nohead(m, p);
 365   }
 366   void decode_nohead(int n, ceph::buffer::ptr::const_iterator& p) {
 367     denc_traits<Map>::decode_nohead(n, m, p);
 368     _size = 0;
 369     for (const auto& p : m) {
 370       _size += p.second;
 371     }
 372   }
 373
 374   void clear() {
 375     m.clear();
 376     _size = 0;
 377   }
 378
 379   bool contains(T i, T *pstart=0, T *plen=0) const {
 380     auto p = find_inc(i);
 381     if (p == m.end()) return false;
 382     if (p->first > i) return false;
 383     if (p->first+p->second <= i) return false;
 384     ceph_assert(p->first <= i && p->first+p->second > i);
 385     if (pstart)
 386       *pstart = p->first;
 387     if (plen)
 388       *plen = p->second;
 389     return true;
 390   }
 391   bool contains(T start, T len) const {
 392     auto p = find_inc(start);
 393     if (p == m.end()) return false;
 394     if (p->first > start) return false;
 395     if (p->first+p->second <= start) return false;
 396     ceph_assert(p->first <= start && p->first+p->second > start);
 397     if (p->first+p->second < start+len) return false;
 398     return true;
 399   }
 400   bool intersects(T start, T len) const {
 401     interval_set a;
 402     a.insert(start, len);
 403     interval_set i;
 404     i.intersection_of( *this, a );
 405     if (i.empty()) return false;
 406     return true;
 407   }
 408
 409   // outer range of set
 410   bool empty() const {
 411     return m.empty();
 412   }
 413   offset_type range_start() const {
 414     ceph_assert(!empty());
 415     auto p = m.begin();
 416     return p->first;
 417   }
 418   offset_type range_end() const {
 419     ceph_assert(!empty());
 420     auto p = m.end();
 421     p--;
 422     return p->first+p->second;
 423   }
 424
 425   // interval start after p (where p not in set)
 426   bool starts_after(T i) const {
 427     ceph_assert(!contains(i));
 428     auto p = find_inc(i);
 429     if (p == m.end()) return false;
 430     return true;
 431   }
 432   offset_type start_after(T i) const {
 433     ceph_assert(!contains(i));
 434     auto p = find_inc(i);
 435     return p->first;
 436   }
 437
 438   // interval end that contains start
 439   offset_type end_after(T start) const {
 440     ceph_assert(contains(start));
 441     auto p = find_inc(start);
 442     return p->first+p->second;
 443   }
 444
 445   void insert(T val) {
 446     insert(val, 1);
 447   }
 448
 449   void insert(T start, T len, T *pstart=0, T *plen=0) {
 450     //cout << "insert " << start << "~" << len << endl;
 451     ceph_assert(len > 0);
 452     _size += len;
 453     auto p = find_adj_m(start);
 454     if (p == m.end()) {
 455       m[start] = len;                  // new interval
 456       if (pstart)
 457         *pstart = start;
 458       if (plen)
 459         *plen = len;
 460     } else {
 461       if (p->first < start) {
 462
 463         if (p->first + p->second != start) {
 464           //cout << "p is " << p->first << "~" << p->second << ", start is " << start << ", len is " << len << endl;
 465           ceph_abort();
 466         }
 467
 468         p->second += len;               // append to end
 469
 470         auto n = p;
 471         ++n;
 472         if (pstart)
 473           *pstart = p->first;
 474         if (n != m.end() &&
 475             start+len == n->first) {   // combine with next, too!
 476           p->second += n->second;
 477           if (plen)
 478             *plen = p->second;
 479           m.erase(n);
 480         } else {
 481           if (plen)
 482             *plen = p->second;
 483         }
 484       } else {
 485         if (start+len == p->first) {
 486           if (pstart)
 487             *pstart = start;
 488           if (plen)
 489             *plen = len + p->second;
 490           T psecond = p->second;
 491           m.erase(p);
 492           m[start] = len + psecond;  // append to front
 493         } else {
 494           ceph_assert(p->first > start+len);
 495           if (pstart)
 496             *pstart = start;
 497           if (plen)
 498             *plen = len;
 499           m[start] = len;              // new interval
 500         }
 501       }
 502     }
 503   }
 504
 505   void swap(interval_set& other) {
 506     m.swap(other.m);
 507     std::swap(_size, other._size);
 508   }
 509
 510   void erase(iterator &i) {
 511     _size -= i.get_len();
 512     ceph_assert(_size >= 0);
 513     m.erase(i._iter);
 514   }
 515
 516   void erase(T val) {
 517     erase(val, 1);
 518   }
 519
 520   void erase(T start, T len,
 521     std::function<bool(T, T)> claim = {}) {
 522     auto p = find_inc_m(start);
 523
 524     _size -= len;
 525     ceph_assert(_size >= 0);
 526
 527     ceph_assert(p != m.end());
 528     ceph_assert(p->first <= start);
 529
 530     T before = start - p->first;
 531     ceph_assert(p->second >= before+len);
 532     T after = p->second - before - len;
 533     if (before) {
 534       if (claim && claim(p->first, before)) {
 535         _size -= before;
 536         m.erase(p);
 537       } else {
 538         p->second = before;        // shorten bit before
 539       }
 540     } else {
 541       m.erase(p);
 542     }
 543     if (after) {
 544       if (claim && claim(start + len, after)) {
 545         _size -= after;
 546       } else {
 547         m[start + len] = after;
 548       }
 549     }
 550   }
 551
 552   void subtract(const interval_set &a) {
 553     for (const auto& [start, len] : a.m) {
 554       erase(start, len);
 555     }
 556   }
 557
 558   void insert(const interval_set &a) {
 559     for (const auto& [start, len] : a.m) {
 560       insert(start, len);
 561     }
 562   }
 563
 564
 565   void intersection_of(const interval_set &a, const interval_set &b) {
 566     ceph_assert(&a != this);
 567     ceph_assert(&b != this);
 568     clear();
 569
 570     const interval_set *s, *l;
 571
 572     if (a.size() < b.size()) {
 573       s = &a;
 574       l = &b;
 575     } else {
 576       s = &b;
 577       l = &a;
 578     }
 579
 580     if (!s->size())
 581       return;
 582
 583     /*
 584      * Use the lower_bound algorithm for larger size ratios
 585      * where it performs better, but not for smaller size
 586      * ratios where sequential search performs better.
 587      */
 588     if (l->size() / s->size() >= 10) {
 589       intersection_size_asym(*s, *l);
 590       return;
 591     }
 592
 593     auto pa = a.m.begin();
 594     auto pb = b.m.begin();
 595     auto mi = m.begin();
 596
 597     while (pa != a.m.end() && pb != b.m.end()) {
 598       // passing?
 599       if (pa->first + pa->second <= pb->first)
 600         { pa++;  continue; }
 601       if (pb->first + pb->second <= pa->first)
 602         { pb++;  continue; }
 603
 604       if (*pa == *pb) {
 605         do {
 606           mi = m.insert(mi, *pa);
 607           _size += pa->second;
 608           ++pa;
 609           ++pb;
 610         } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
 611         continue;
 612       }
 613
 614       T start = std::max(pa->first, pb->first);
 615       T en = std::min(pa->first+pa->second, pb->first+pb->second);
 616       ceph_assert(en > start);
 617       mi = m.emplace_hint(mi, start, en - start);
 618       _size += mi->second;
 619       if (pa->first+pa->second > pb->first+pb->second)
 620         pb++;
 621       else
 622         pa++;
 623     }
 624   }
 625   void intersection_of(const interval_set& b) {
 626     interval_set a;
 627     swap(a);
 628     intersection_of(a, b);
 629   }
 630
 631   void union_of(const interval_set &a, const interval_set &b) {
 632     ceph_assert(&a != this);
 633     ceph_assert(&b != this);
 634     clear();
 635
 636     //cout << "union_of" << endl;
 637
 638     // a
 639     m = a.m;
 640     _size = a._size;
 641
 642     // - (a*b)
 643     interval_set ab;
 644     ab.intersection_of(a, b);
 645     subtract(ab);
 646
 647     // + b
 648     insert(b);
 649     return;
 650   }
 651   void union_of(const interval_set &b) {
 652     interval_set a;
 653     swap(a);
 654     union_of(a, b);
 655   }
 656   void union_insert(T off, T len) {
 657     interval_set a;
 658     a.insert(off, len);
 659     union_of(a);
 660   }
 661
 662   bool subset_of(const interval_set &big) const {
 663     if (!size())
 664       return true;
 665     if (size() > big.size())
 666       return false;
 667     if (range_end() > big.range_end())
 668       return false;
 669
 670     /*
 671      * Use the lower_bound algorithm for larger size ratios
 672      * where it performs better, but not for smaller size
 673      * ratios where sequential search performs better.
 674      */
 675     if (big.size() / size() < 10)
 676       return subset_size_sym(big);
 677
 678     for (const auto& [start, len] : m) {
 679       if (!big.contains(start, len)) return false;
 680     }
 681     return true;
 682   }
 683
 684   /*
 685    * build a subset of @other, starting at or after @start, and including
 686    * @len worth of values, skipping holes.  e.g.,
 687    *  span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
 688    */
 689   void span_of(const interval_set &other, T start, T len) {
 690     clear();
 691     auto p = other.find_inc(start);
 692     if (p == other.m.end())
 693       return;
 694     if (p->first < start) {
 695       if (p->first + p->second < start)
 696         return;
 697       if (p->first + p->second < start + len) {
 698         T howmuch = p->second - (start - p->first);
 699         insert(start, howmuch);
 700         len -= howmuch;
 701         p++;
 702       } else {
 703         insert(start, len);
 704         return;
 705       }
 706     }
 707     while (p != other.m.end() && len > 0) {
 708       if (p->second < len) {
 709         insert(p->first, p->second);
 710         len -= p->second;
 711         p++;
 712       } else {
 713         insert(p->first, len);
 714         return;
 715       }
 716     }
 717   }
 718
 719   /*
 720    * Move contents of m into another Map. Use that instead of
 721    * encoding interval_set into bufferlist then decoding it back into Map.
 722    */
 723   Map detach() && {
 724     return std::move(m);
 725   }
 726
 727 private:
 728   // data
 729   uint64_t _size = 0;
 730   Map m;   // map start -> len
 731 };
 732
 733 // declare traits explicitly because (1) it's templatized, and (2) we
 734 // want to include _nohead variants.
 735 template<typename T, typename Map>
 736 struct denc_traits<interval_set<T,Map>> {
 737   static constexpr bool supported = true;
 738   static constexpr bool bounded = false;
 739   static constexpr bool featured = false;
 740   static constexpr bool need_contiguous = denc_traits<T,Map>::need_contiguous;
 741   static void bound_encode(const interval_set<T,Map>& v, size_t& p) {
 742     v.bound_encode(p);
 743   }
 744   static void encode(const interval_set<T,Map>& v,
 745                      ceph::buffer::list::contiguous_appender& p) {
 746     v.encode(p);
 747   }
 748   static void decode(interval_set<T,Map>& v, ceph::buffer::ptr::const_iterator& p) {
 749     v.decode(p);
 750   }
 751   template<typename U=T>
 752     static typename std::enable_if<sizeof(U) && !need_contiguous>::type
 753   decode(interval_set<T,Map>& v, ceph::buffer::list::iterator& p) {
 754     v.decode(p);
 755   }
 756   static void encode_nohead(const interval_set<T,Map>& v,
 757                             ceph::buffer::list::contiguous_appender& p) {
 758     v.encode_nohead(p);
 759   }
 760   static void decode_nohead(size_t n, interval_set<T,Map>& v,
 761                             ceph::buffer::ptr::const_iterator& p) {
 762     v.decode_nohead(n, p);
 763   }
 764 };
 765
 766
 767 template<class T, typename Map>
 768 inline std::ostream& operator<<(std::ostream& out, const interval_set<T,Map> &s) {
 769   out << "[";
 770   bool first = true;
 771   for (const auto& [start, len] : s) {
 772     if (!first) out << ",";
 773     out << start << "~" << len;
 774     first = false;
 775   }
 776   out << "]";
 777   return out;
 778 }
 779
 780
 781 #endif