1 files changed, 250 insertions, 0 deletions
diff --git a/src/include/rangeset.h b/src/include/rangeset.h
new file mode 100644
index 000000000..e7e3d047c
--- /dev/null
+++ b/src/include/rangeset.h
@@ -0,0 +1,250 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph - scalable distributed file system
+ *
+ * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
+ *
+ * This is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software 
+ * Foundation.  See file COPYING.
+ * 
+ */
+
+
+#ifndef CEPH_RANGESET_H
+#define CEPH_RANGESET_H
+
+/*
+ *
+ * my first container with iterator!   it's pretty ugly.
+ *
+ */
+
+#include <map>
+
+//typedef int T;
+
+template <class T>
+struct _rangeset_base {
+  map<T,T> ranges;  // pair(first,last) (inclusive, e.g. [first,last])
+                    
+  typedef typename map<T,T>::iterator mapit;
+
+  // get iterator for range including val.  or ranges.end().
+  mapit get_range_for(T val) {
+    mapit it = ranges.lower_bound(val);
+    if (it == ranges.end()) {
+      // search backwards
+      typename map<T,T>::reverse_iterator it = ranges.rbegin();
+      if (it == ranges.rend()) return ranges.end();
+      if (it->first <= val && it->second >= val)
+        return ranges.find(it->first);
+      return ranges.end();
+    } else {
+      if (it->first == val) return 
+      it--;
+      if (it->first <= val && it->second >= val)
+        return it;
+      return ranges.end();
+    }
+  }
+
+};
+
+
+template <class T>
+class rangeset_iterator :
+  public std::iterator<std::input_iterator_tag, T>
+{
+  //typedef typename map<T,T>::iterator mapit;
+
+  map<T,T> ranges;
+  typename map<T,T>::iterator it;
+  T current;
+
+public:
+  // cons
+  rangeset_iterator() {}
+
+  rangeset_iterator(typename map<T,T>::iterator& it, map<T,T>& ranges) {
+    this->ranges = ranges;
+    this->it = it;
+    if (this->it != ranges.end())
+      current = it->first;
+  }
+
+  bool operator==(rangeset_iterator<T> rit) {
+    return (it == rit.it && rit.current == current);
+  }
+  bool operator!=(rangeset_iterator<T> rit) {
+    return (it != rit.it) || (rit.current != current);
+  }
+  
+  T& operator*() {
+    return current;
+  }
+
+  rangeset_iterator<T> operator++(int) {
+    if (current < it->second)
+      current++;
+    else {
+      it++;
+      if (it != ranges.end())
+        current = it->first;
+    }
+    
+    return *this;
+  }
+};
+
+
+template <class T>
+class rangeset
+{
+  typedef typename map<T,T>::iterator map_iterator;
+
+  _rangeset_base<T> theset;
+  inodeno_t _size;
+
+public:
+  rangeset() { _size = 0; }
+  typedef rangeset_iterator<T> iterator;
+
+  iterator begin() {
+    map_iterator it = theset.ranges.begin();
+    return iterator(it, theset.ranges);
+  }
+
+  iterator end() {
+    map_iterator it = theset.ranges.end();
+    return iterator(it, theset.ranges);
+  }
+
+  map_iterator map_begin() {
+    return theset.ranges.begin();
+  }
+  map_iterator map_end() {
+    return theset.ranges.end();
+  }
+  int map_size() {
+    return theset.ranges.size();
+  }
+
+  void map_insert(T v1, T v2) {
+    theset.ranges.insert(pair<T,T>(v1,v2));
+    _size += v2 - v1+1;
+  }
+
+
+  // ...
+  bool contains(T val) {
+    if (theset.get_range_for(val) == theset.ranges.end()) return false;
+    ceph_assert(!empty());
+    return true;
+  }
+  
+  void insert(T val) {
+    ceph_assert(!contains(val));
+
+    map_iterator left = theset.get_range_for(val-1);
+    map_iterator right = theset.get_range_for(val+1);
+
+    if (left != theset.ranges.end() &&
+        right != theset.ranges.end()) {
+      // join!
+      left->second = right->second;
+      theset.ranges.erase(right);
+      _size++;
+      return;
+    }
+
+    if (left != theset.ranges.end()) {
+      // add to left range
+      left->second = val;
+      _size++;
+      return;
+    }
+
+    if (right != theset.ranges.end()) {
+      // add to right range
+      theset.ranges.insert(pair<T,T>(val, right->second));
+      theset.ranges.erase(val+1);
+      _size++;
+      return;
+    }
+
+    // new range
+    theset.ranges.insert(pair<T,T>(val,val));
+    _size++;
+    return;
+  }
+
+  unsigned size() {
+    return size();
+  }
+
+  bool empty() {
+    if (theset.ranges.empty()) {
+      ceph_assert(_size == 0);
+      return true;
+    }
+    ceph_assert(_size>0);
+    return false;
+  }
+
+  
+  T first() {
+    ceph_assert(!empty());
+    map_iterator it = theset.ranges.begin();
+    return it->first;
+  }
+  
+  void erase(T val) {
+    ceph_assert(contains(val));
+    map_iterator it = theset.get_range_for(val);
+    ceph_assert(it != theset.ranges.end());
+    
+    // entire range
+    if (val == it->first && val == it->second) {
+      theset.ranges.erase(it);
+      _size--;
+      return;
+    }
+
+    // beginning
+    if (val == it->first) {
+      theset.ranges.insert(pair<T,T>(val+1, it->second));
+      theset.ranges.erase(it);
+      _size--;
+      return;      
+    }
+
+    // end
+    if (val == it->second) {
+      it->second = val-1;
+      _size--;
+      return;
+    }
+
+    // middle split
+    theset.ranges.insert(pair<T,T>(it->first, val-1));
+    theset.ranges.insert(pair<T,T>(val+1, it->second));
+    theset.ranges.erase(it);
+    _size--;
+    return;
+  }
+
+  void dump() {
+    for (typename map<T,T>::iterator it = theset.ranges.begin();
+         it != theset.ranges.end();
+         it++) {
+      cout << " " << it->first << "-" << it->second << endl;
+    }
+  }
+
+};
+
+
+#endif