summaryrefslogtreecommitdiffstats
path: root/src/include/rangeset.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/include/rangeset.h')
-rw-r--r--src/include/rangeset.h250
1 files changed, 250 insertions, 0 deletions
diff --git a/src/include/rangeset.h b/src/include/rangeset.h
new file mode 100644
index 00000000..e7e3d047
--- /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