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