diff options
Diffstat (limited to 'src/include/rangeset.h')
-rw-r--r-- | src/include/rangeset.h | 250 |
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 |