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