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 #ifndef MIN
  34 # define MIN(a,b)  ((a)<=(b) ? (a):(b))
  35 #endif
  36 #ifndef MAX
  37 # define MAX(a,b)  ((a)>=(b) ? (a):(b))
  38 #endif
  39
  40
  41 template<typename T, typename Map = std::map<T,T>>
  42 class interval_set {
  43  public:
  44
  45   class const_iterator;
  46
  47   class iterator : public std::iterator <std::forward_iterator_tag, T>
  48   {
  49     public:
  50         explicit iterator(typename Map::iterator iter)
  51           : _iter(iter)
  52         { }
  53
  54         // For the copy constructor and assignment operator, the compiler-generated functions, which
  55         // perform simple bitwise copying, should be fine.
  56
  57         bool operator==(const iterator& rhs) const {
  58           return (_iter == rhs._iter);
  59         }
  60
  61         bool operator!=(const iterator& rhs) const {
  62           return (_iter != rhs._iter);
  63         }
  64
  65         // Dereference this iterator to get a pair.
  66         std::pair < T, T > &operator*() {
  67                 return *_iter;
  68         }
  69
  70         // Return the interval start.
  71         T get_start() const {
  72                 return _iter->first;
  73         }
  74
  75         // Return the interval length.
  76         T get_len() const {
  77                 return _iter->second;
  78         }
  79
  80         // Set the interval length.
  81         void set_len(T len) {
  82                 _iter->second = len;
  83         }
  84
  85         // Preincrement
  86         iterator &operator++()
  87         {
  88                 ++_iter;
  89                 return *this;
  90         }
  91
  92         // Postincrement
  93         iterator operator++(int)
  94         {
  95                 iterator prev(_iter);
  96                 ++_iter;
  97                 return prev;
  98         }
  99
 100     friend class interval_set<T,Map>::const_iterator;
 101
 102     protected:
 103         typename Map::iterator _iter;
 104     friend class interval_set<T,Map>;
 105   };
 106
 107   class const_iterator : public std::iterator <std::forward_iterator_tag, T>
 108   {
 109     public:
 110         explicit const_iterator(typename Map::const_iterator iter)
 111           : _iter(iter)
 112         { }
 113
 114         const_iterator(const iterator &i)
 115           : _iter(i._iter)
 116         { }
 117
 118         // For the copy constructor and assignment operator, the compiler-generated functions, which
 119         // perform simple bitwise copying, should be fine.
 120
 121         bool operator==(const const_iterator& rhs) const {
 122           return (_iter == rhs._iter);
 123         }
 124
 125         bool operator!=(const const_iterator& rhs) const {
 126           return (_iter != rhs._iter);
 127         }
 128
 129         // Dereference this iterator to get a pair.
 130         std::pair < T, T > operator*() const {
 131                 return *_iter;
 132         }
 133
 134         // Return the interval start.
 135         T get_start() const {
 136                 return _iter->first;
 137         }
 138
 139         // Return the interval length.
 140         T get_len() const {
 141                 return _iter->second;
 142         }
 143
 144         // Preincrement
 145         const_iterator &operator++()
 146         {
 147                 ++_iter;
 148                 return *this;
 149         }
 150
 151         // Postincrement
 152         const_iterator operator++(int)
 153         {
 154                 const_iterator prev(_iter);
 155                 ++_iter;
 156                 return prev;
 157         }
 158
 159     protected:
 160         typename Map::const_iterator _iter;
 161   };
 162
 163   interval_set() : _size(0) {}
 164   interval_set(Map& other) {
 165     m.swap(other);
 166     _size = 0;
 167     for (auto& i : m) {
 168       _size += i.second;
 169     }
 170   }
 171
 172   int num_intervals() const
 173   {
 174     return m.size();
 175   }
 176
 177   typename interval_set<T,Map>::iterator begin() {
 178     return typename interval_set<T,Map>::iterator(m.begin());
 179   }
 180
 181   typename interval_set<T,Map>::iterator lower_bound(T start) {
 182     return typename interval_set<T,Map>::iterator(find_inc_m(start));
 183   }
 184
 185   typename interval_set<T,Map>::iterator end() {
 186     return typename interval_set<T,Map>::iterator(m.end());
 187   }
 188
 189   typename interval_set<T,Map>::const_iterator begin() const {
 190     return typename interval_set<T,Map>::const_iterator(m.begin());
 191   }
 192
 193   typename interval_set<T,Map>::const_iterator lower_bound(T start) const {
 194     return typename interval_set<T,Map>::const_iterator(find_inc(start));
 195   }
 196
 197   typename interval_set<T,Map>::const_iterator end() const {
 198     return typename interval_set<T,Map>::const_iterator(m.end());
 199   }
 200
 201   // helpers
 202  private:
 203   typename Map::const_iterator find_inc(T start) const {
 204     typename Map::const_iterator p = m.lower_bound(start);  // p->first >= start
 205     if (p != m.begin() &&
 206         (p == m.end() || p->first > start)) {
 207       p--;   // might overlap?
 208       if (p->first + p->second <= start)
 209         p++; // it doesn't.
 210     }
 211     return p;
 212   }
 213
 214   typename Map::iterator find_inc_m(T start) {
 215     typename Map::iterator p = m.lower_bound(start);
 216     if (p != m.begin() &&
 217         (p == m.end() || p->first > start)) {
 218       p--;   // might overlap?
 219       if (p->first + p->second <= start)
 220         p++; // it doesn't.
 221     }
 222     return p;
 223   }
 224
 225   typename Map::const_iterator find_adj(T start) const {
 226     typename Map::const_iterator p = m.lower_bound(start);
 227     if (p != m.begin() &&
 228         (p == m.end() || p->first > start)) {
 229       p--;   // might touch?
 230       if (p->first + p->second < start)
 231         p++; // it doesn't.
 232     }
 233     return p;
 234   }
 235
 236   typename Map::iterator find_adj_m(T start) {
 237     typename Map::iterator p = m.lower_bound(start);
 238     if (p != m.begin() &&
 239         (p == m.end() || p->first > start)) {
 240       p--;   // might touch?
 241       if (p->first + p->second < start)
 242         p++; // it doesn't.
 243     }
 244     return p;
 245   }
 246
 247   void intersection_size_asym(const interval_set &s, const interval_set &l) {
 248     typename decltype(m)::const_iterator ps = s.m.begin(), pl;
 249     assert(ps != s.m.end());
 250     T offset = ps->first, prev_offset;
 251     bool first = true;
 252     typename decltype(m)::iterator mi = m.begin();
 253
 254     while (1) {
 255       if (first)
 256         first = false;
 257       else
 258         assert(offset > prev_offset);
 259       pl = l.find_inc(offset);
 260       prev_offset = offset;
 261       if (pl == l.m.end())
 262         break;
 263       while (ps != s.m.end() && ps->first + ps->second <= pl->first)
 264         ++ps;
 265       if (ps == s.m.end())
 266         break;
 267       offset = pl->first + pl->second;
 268       if (offset <= ps->first) {
 269         offset = ps->first;
 270         continue;
 271       }
 272
 273       if (*ps == *pl) {
 274         do {
 275           mi = m.insert(mi, *ps);
 276           _size += ps->second;
 277           ++ps;
 278           ++pl;
 279         } while (ps != s.m.end() && pl != l.m.end() && *ps == *pl);
 280         if (ps == s.m.end())
 281           break;
 282         offset = ps->first;
 283         continue;
 284       }
 285
 286       T start = std::max<T>(ps->first, pl->first);
 287       T en = std::min<T>(ps->first + ps->second, offset);
 288       assert(en > start);
 289       typename decltype(m)::value_type i{start, en - start};
 290       mi = m.insert(mi, i);
 291       _size += i.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   int64_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(bufferlist::contiguous_appender& p) const {
 346     denc(m, p);
 347   }
 348   void decode(bufferptr::iterator& p) {
 349     denc(m, p);
 350     _size = 0;
 351     for (const auto& i : m) {
 352       _size += i.second;
 353     }
 354   }
 355   void decode(bufferlist::iterator& p) {
 356     denc(m, p);
 357     _size = 0;
 358     for (const auto& i : m) {
 359       _size += i.second;
 360     }
 361   }
 362
 363   void encode_nohead(bufferlist::contiguous_appender& p) const {
 364     denc_traits<Map>::encode_nohead(m, p);
 365   }
 366   void decode_nohead(int n, bufferptr::iterator& p) {
 367     denc_traits<Map>::decode_nohead(n, m, p);
 368     _size = 0;
 369     for (const auto& i : m) {
 370       _size += i.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     typename Map::const_iterator 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     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     typename Map::const_iterator 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     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   T range_start() const {
 414     assert(!empty());
 415     typename Map::const_iterator p = m.begin();
 416     return p->first;
 417   }
 418   T range_end() const {
 419     assert(!empty());
 420     typename Map::const_iterator 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     assert(!contains(i));
 428     typename Map::const_iterator p = find_inc(i);
 429     if (p == m.end()) return false;
 430     return true;
 431   }
 432   T start_after(T i) const {
 433     assert(!contains(i));
 434     typename Map::const_iterator p = find_inc(i);
 435     return p->first;
 436   }
 437
 438   // interval end that contains start
 439   T end_after(T start) const {
 440     assert(contains(start));
 441     typename Map::const_iterator 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     assert(len > 0);
 452     _size += len;
 453     typename Map::iterator 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         typename Map::iterator 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           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<T,Map>& 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     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     typename Map::iterator p = find_inc_m(start);
 523
 524     _size -= len;
 525     assert(_size >= 0);
 526
 527     assert(p != m.end());
 528     assert(p->first <= start);
 529
 530     T before = start - p->first;
 531     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 (typename Map::const_iterator p = a.m.begin();
 554          p != a.m.end();
 555          p++)
 556       erase(p->first, p->second);
 557   }
 558
 559   void insert(const interval_set &a) {
 560     for (typename Map::const_iterator p = a.m.begin();
 561          p != a.m.end();
 562          p++)
 563       insert(p->first, p->second);
 564   }
 565
 566
 567   void intersection_of(const interval_set &a, const interval_set &b) {
 568     assert(&a != this);
 569     assert(&b != this);
 570     clear();
 571
 572     const interval_set *s, *l;
 573
 574     if (a.size() < b.size()) {
 575       s = &a;
 576       l = &b;
 577     } else {
 578       s = &b;
 579       l = &a;
 580     }
 581
 582     if (!s->size())
 583       return;
 584
 585     /*
 586      * Use the lower_bound algorithm for larger size ratios
 587      * where it performs better, but not for smaller size
 588      * ratios where sequential search performs better.
 589      */
 590     if (l->size() / s->size() >= 10) {
 591       intersection_size_asym(*s, *l);
 592       return;
 593     }
 594
 595     typename Map::const_iterator pa = a.m.begin();
 596     typename Map::const_iterator pb = b.m.begin();
 597     typename decltype(m)::iterator mi = m.begin();
 598
 599     while (pa != a.m.end() && pb != b.m.end()) {
 600       // passing?
 601       if (pa->first + pa->second <= pb->first)
 602         { pa++;  continue; }
 603       if (pb->first + pb->second <= pa->first)
 604         { pb++;  continue; }
 605
 606       if (*pa == *pb) {
 607         do {
 608           mi = m.insert(mi, *pa);
 609           _size += pa->second;
 610           ++pa;
 611           ++pb;
 612         } while (pa != a.m.end() && pb != b.m.end() && *pa == *pb);
 613         continue;
 614       }
 615
 616       T start = MAX(pa->first, pb->first);
 617       T en = MIN(pa->first+pa->second, pb->first+pb->second);
 618       assert(en > start);
 619       typename decltype(m)::value_type i{start, en - start};
 620       mi = m.insert(mi, i);
 621       _size += i.second;
 622       if (pa->first+pa->second > pb->first+pb->second)
 623         pb++;
 624       else
 625         pa++;
 626     }
 627   }
 628   void intersection_of(const interval_set& b) {
 629     interval_set a;
 630     swap(a);
 631     intersection_of(a, b);
 632   }
 633
 634   void union_of(const interval_set &a, const interval_set &b) {
 635     assert(&a != this);
 636     assert(&b != this);
 637     clear();
 638
 639     //cout << "union_of" << endl;
 640
 641     // a
 642     m = a.m;
 643     _size = a._size;
 644
 645     // - (a*b)
 646     interval_set ab;
 647     ab.intersection_of(a, b);
 648     subtract(ab);
 649
 650     // + b
 651     insert(b);
 652     return;
 653   }
 654   void union_of(const interval_set &b) {
 655     interval_set a;
 656     swap(a);
 657     union_of(a, b);
 658   }
 659   void union_insert(T off, T len) {
 660     interval_set a;
 661     a.insert(off, len);
 662     union_of(a);
 663   }
 664
 665   bool subset_of(const interval_set &big) const {
 666     if (!size())
 667       return true;
 668     if (size() > big.size())
 669       return false;
 670     if (range_end() > big.range_end())
 671       return false;
 672
 673     /*
 674      * Use the lower_bound algorithm for larger size ratios
 675      * where it performs better, but not for smaller size
 676      * ratios where sequential search performs better.
 677      */
 678     if (big.size() / size() < 10)
 679       return subset_size_sym(big);
 680
 681     for (typename Map::const_iterator i = m.begin();
 682          i != m.end();
 683          i++)
 684       if (!big.contains(i->first, i->second)) return false;
 685     return true;
 686   }
 687
 688  /*
 689    * build a subset of @other for given rage [@start, @end)
 690    * E.g.:
 691    * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5]
 692    * subset_of([5~10,20~5], 5, 25)  -> [5~10,20~5]
 693    * subset_of([5~10,20~5], 1, 10)  -> [5~5]
 694    * subset_of([5~10,20~5], 8, 24)  -> [8~7, 20~4]
 695    */
 696   void subset_of(const interval_set &other, T start, T end) {
 697     assert(end >= start);
 698     clear();
 699     if (end == start) {
 700       return;
 701     }
 702     typename Map::const_iterator p = other.find_inc(start);
 703     if (p == other.m.end())
 704       return;
 705     if (p->first < start) {
 706       if (p->first + p->second >= end) {
 707         insert(start, end - start);
 708         return;
 709       } else {
 710         insert(start, p->first + p->second - start);
 711         ++p;
 712       }
 713     }
 714     while (p != other.m.end()) {
 715       assert(p->first >= start);
 716       if (p->first >= end) {
 717         return;
 718       }
 719       if (p->first + p->second >= end) {
 720         insert(p->first, end - p->first);
 721         return;
 722       } else {
 723         // whole
 724         insert(p->first, p->second);
 725         ++p;
 726       }
 727     }
 728   }
 729
 730   /*
 731    * build a subset of @other, starting at or after @start, and including
 732    * @len worth of values, skipping holes.  e.g.,
 733    *  span_of([5~10,20~5], 8, 5) -> [8~2,20~3]
 734    */
 735   void span_of(const interval_set &other, T start, T len) {
 736     clear();
 737     typename Map::const_iterator p = other.find_inc(start);
 738     if (p == other.m.end())
 739       return;
 740     if (p->first < start) {
 741       if (p->first + p->second < start)
 742         return;
 743       if (p->first + p->second < start + len) {
 744         T howmuch = p->second - (start - p->first);
 745         insert(start, howmuch);
 746         len -= howmuch;
 747         p++;
 748       } else {
 749         insert(start, len);
 750         return;
 751       }
 752     }
 753     while (p != other.m.end() && len > 0) {
 754       if (p->second < len) {
 755         insert(p->first, p->second);
 756         len -= p->second;
 757         p++;
 758       } else {
 759         insert(p->first, len);
 760         return;
 761       }
 762     }
 763   }
 764
 765   /*
 766    * Move contents of m into another Map. Use that instead of
 767    * encoding interval_set into bufferlist then decoding it back into Map.
 768    */
 769   void move_into(Map& other) {
 770     other = std::move(m);
 771   }
 772
 773 private:
 774   // data
 775   int64_t _size;
 776   Map m;   // map start -> len
 777 };
 778
 779 // declare traits explicitly because (1) it's templatized, and (2) we
 780 // want to include _nohead variants.
 781 template<typename T, typename Map>
 782 struct denc_traits<interval_set<T,Map>> {
 783   static constexpr bool supported = true;
 784   static constexpr bool bounded = false;
 785   static constexpr bool featured = false;
 786   static constexpr bool need_contiguous = denc_traits<T,Map>::need_contiguous;
 787   static void bound_encode(const interval_set<T,Map>& v, size_t& p) {
 788     v.bound_encode(p);
 789   }
 790   static void encode(const interval_set<T,Map>& v,
 791                      bufferlist::contiguous_appender& p) {
 792     v.encode(p);
 793   }
 794   static void decode(interval_set<T,Map>& v, bufferptr::iterator& p) {
 795     v.decode(p);
 796   }
 797   template<typename U=T>
 798     static typename std::enable_if<sizeof(U) && !need_contiguous>::type
 799     decode(interval_set<T,Map>& v, bufferlist::iterator& p) {
 800     v.decode(p);
 801   }
 802   static void encode_nohead(const interval_set<T,Map>& v,
 803                             bufferlist::contiguous_appender& p) {
 804     v.encode_nohead(p);
 805   }
 806   static void decode_nohead(size_t n, interval_set<T,Map>& v,
 807                             bufferptr::iterator& p) {
 808     v.decode_nohead(n, p);
 809   }
 810 };
 811
 812
 813 template<class T, typename Map>
 814 inline std::ostream& operator<<(std::ostream& out, const interval_set<T,Map> &s) {
 815   out << "[";
 816   const char *prequel = "";
 817   for (typename interval_set<T,Map>::const_iterator i = s.begin();
 818        i != s.end();
 819        ++i)
 820   {
 821     out << prequel << i.get_start() << "~" << i.get_len();
 822     prequel = ",";
 823   }
 824   out << "]";
 825   return out;
 826 }
 827
 828
 829 #endif