ceph/src/include/rangeset.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_RANGESET_H
  17 #define CEPH_RANGESET_H
  18
  19 /*
  20  *
  21  * my first container with iterator!   it's pretty ugly.
  22  *
  23  */
  24
  25 #include <map>
  26 using namespace std;
  27
  28 //typedef int T;
  29
  30 template <class T>
  31 struct _rangeset_base {
  32   map<T,T> ranges;  // pair(first,last) (inclusive, e.g. [first,last])
  33
  34   typedef typename map<T,T>::iterator mapit;
  35
  36   // get iterator for range including val.  or ranges.end().
  37   mapit get_range_for(T val) {
  38     mapit it = ranges.lower_bound(val);
  39     if (it == ranges.end()) {
  40       // search backwards
  41       typename map<T,T>::reverse_iterator it = ranges.rbegin();
  42       if (it == ranges.rend()) return ranges.end();
  43       if (it->first <= val && it->second >= val)
  44         return ranges.find(it->first);
  45       return ranges.end();
  46     } else {
  47       if (it->first == val) return
  48       it--;
  49       if (it->first <= val && it->second >= val)
  50         return it;
  51       return ranges.end();
  52     }
  53   }
  54
  55 };
  56
  57
  58 template <class T>
  59 class rangeset_iterator :
  60   public std::iterator<std::input_iterator_tag, T>
  61 {
  62   //typedef typename map<T,T>::iterator mapit;
  63
  64   map<T,T> ranges;
  65   typename map<T,T>::iterator it;
  66   T current;
  67
  68 public:
  69   // cons
  70   rangeset_iterator() {}
  71
  72   rangeset_iterator(typename map<T,T>::iterator& it, map<T,T>& ranges) {
  73     this->ranges = ranges;
  74     this->it = it;
  75     if (this->it != ranges.end())
  76       current = it->first;
  77   }
  78
  79   bool operator==(rangeset_iterator<T> rit) {
  80     return (it == rit.it && rit.current == current);
  81   }
  82   bool operator!=(rangeset_iterator<T> rit) {
  83     return (it != rit.it) || (rit.current != current);
  84   }
  85
  86   T& operator*() {
  87     return current;
  88   }
  89
  90   rangeset_iterator<T> operator++(int) {
  91     if (current < it->second)
  92       current++;
  93     else {
  94       it++;
  95       if (it != ranges.end())
  96         current = it->first;
  97     }
  98
  99     return *this;
 100   }
 101 };
 102
 103
 104 template <class T>
 105 class rangeset
 106 {
 107   typedef typename map<T,T>::iterator map_iterator;
 108
 109   _rangeset_base<T> theset;
 110   inodeno_t _size;
 111
 112 public:
 113   rangeset() { _size = 0; }
 114   typedef rangeset_iterator<T> iterator;
 115
 116   iterator begin() {
 117     map_iterator it = theset.ranges.begin();
 118     return iterator(it, theset.ranges);
 119   }
 120
 121   iterator end() {
 122     map_iterator it = theset.ranges.end();
 123     return iterator(it, theset.ranges);
 124   }
 125
 126   map_iterator map_begin() {
 127     return theset.ranges.begin();
 128   }
 129   map_iterator map_end() {
 130     return theset.ranges.end();
 131   }
 132   int map_size() {
 133     return theset.ranges.size();
 134   }
 135
 136   void map_insert(T v1, T v2) {
 137     theset.ranges.insert(pair<T,T>(v1,v2));
 138     _size += v2 - v1+1;
 139   }
 140
 141
 142   // ...
 143   bool contains(T val) {
 144     if (theset.get_range_for(val) == theset.ranges.end()) return false;
 145     assert(!empty());
 146     return true;
 147   }
 148
 149   void insert(T val) {
 150     assert(!contains(val));
 151
 152     map_iterator left = theset.get_range_for(val-1);
 153     map_iterator right = theset.get_range_for(val+1);
 154
 155     if (left != theset.ranges.end() &&
 156         right != theset.ranges.end()) {
 157       // join!
 158       left->second = right->second;
 159       theset.ranges.erase(right);
 160       _size++;
 161       return;
 162     }
 163
 164     if (left != theset.ranges.end()) {
 165       // add to left range
 166       left->second = val;
 167       _size++;
 168       return;
 169     }
 170
 171     if (right != theset.ranges.end()) {
 172       // add to right range
 173       theset.ranges.insert(pair<T,T>(val, right->second));
 174       theset.ranges.erase(val+1);
 175       _size++;
 176       return;
 177     }
 178
 179     // new range
 180     theset.ranges.insert(pair<T,T>(val,val));
 181     _size++;
 182     return;
 183   }
 184
 185   unsigned size() {
 186     return size();
 187   }
 188
 189   bool empty() {
 190     if (theset.ranges.empty()) {
 191       assert(_size == 0);
 192       return true;
 193     }
 194     assert(_size>0);
 195     return false;
 196   }
 197
 198
 199   T first() {
 200     assert(!empty());
 201     map_iterator it = theset.ranges.begin();
 202     return it->first;
 203   }
 204
 205   void erase(T val) {
 206     assert(contains(val));
 207     map_iterator it = theset.get_range_for(val);
 208     assert(it != theset.ranges.end());
 209
 210     // entire range
 211     if (val == it->first && val == it->second) {
 212       theset.ranges.erase(it);
 213       _size--;
 214       return;
 215     }
 216
 217     // beginning
 218     if (val == it->first) {
 219       theset.ranges.insert(pair<T,T>(val+1, it->second));
 220       theset.ranges.erase(it);
 221       _size--;
 222       return;
 223     }
 224
 225     // end
 226     if (val == it->second) {
 227       it->second = val-1;
 228       _size--;
 229       return;
 230     }
 231
 232     // middle split
 233     theset.ranges.insert(pair<T,T>(it->first, val-1));
 234     theset.ranges.insert(pair<T,T>(val+1, it->second));
 235     theset.ranges.erase(it);
 236     _size--;
 237     return;
 238   }
 239
 240   void dump() {
 241     for (typename map<T,T>::iterator it = theset.ranges.begin();
 242          it != theset.ranges.end();
 243          it++) {
 244       cout << " " << it->first << "-" << it->second << endl;
 245     }
 246   }
 247
 248 };
 249
 250
 251 #endif