From 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 27 Apr 2024 20:24:20 +0200 Subject: Adding upstream version 14.2.21. Signed-off-by: Daniel Baumann --- src/include/rangeset.h | 250 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 250 insertions(+) create mode 100644 src/include/rangeset.h (limited to 'src/include/rangeset.h') 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 + * + * 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 + +//typedef int T; + +template +struct _rangeset_base { + map ranges; // pair(first,last) (inclusive, e.g. [first,last]) + + typedef typename map::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::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 rangeset_iterator : + public std::iterator +{ + //typedef typename map::iterator mapit; + + map ranges; + typename map::iterator it; + T current; + +public: + // cons + rangeset_iterator() {} + + rangeset_iterator(typename map::iterator& it, map& ranges) { + this->ranges = ranges; + this->it = it; + if (this->it != ranges.end()) + current = it->first; + } + + bool operator==(rangeset_iterator rit) { + return (it == rit.it && rit.current == current); + } + bool operator!=(rangeset_iterator rit) { + return (it != rit.it) || (rit.current != current); + } + + T& operator*() { + return current; + } + + rangeset_iterator operator++(int) { + if (current < it->second) + current++; + else { + it++; + if (it != ranges.end()) + current = it->first; + } + + return *this; + } +}; + + +template +class rangeset +{ + typedef typename map::iterator map_iterator; + + _rangeset_base theset; + inodeno_t _size; + +public: + rangeset() { _size = 0; } + typedef rangeset_iterator 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(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(val, right->second)); + theset.ranges.erase(val+1); + _size++; + return; + } + + // new range + theset.ranges.insert(pair(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(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(it->first, val-1)); + theset.ranges.insert(pair(val+1, it->second)); + theset.ranges.erase(it); + _size--; + return; + } + + void dump() { + for (typename map::iterator it = theset.ranges.begin(); + it != theset.ranges.end(); + it++) { + cout << " " << it->first << "-" << it->second << endl; + } + } + +}; + + +#endif -- cgit v1.2.3