summaryrefslogtreecommitdiffstats
path: root/src/include/compact_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/include/compact_set.h')
-rw-r--r--src/include/compact_set.h305
1 files changed, 305 insertions, 0 deletions
diff --git a/src/include/compact_set.h b/src/include/compact_set.h
new file mode 100644
index 00000000..ba743fb0
--- /dev/null
+++ b/src/include/compact_set.h
@@ -0,0 +1,305 @@
+/*
+ * Ceph - scalable distributed file system
+ *
+ * Copyright (C) 2015 Red Hat, Inc
+ *
+ * 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_COMPACT_SET_H
+#define CEPH_COMPACT_SET_H
+
+#include "buffer.h"
+#include "encoding.h"
+
+#include <memory>
+#include <set>
+
+template <class T, class Set>
+class compact_set_base {
+protected:
+ std::unique_ptr<Set> set;
+ void alloc_internal() {
+ if (!set)
+ set.reset(new Set);
+ }
+ void free_internal() {
+ set.reset();
+ }
+ template <class It>
+ class iterator_base {
+ private:
+ const compact_set_base* set;
+ It it;
+ iterator_base() : set(0) { }
+ iterator_base(const compact_set_base* s) : set(s) { }
+ iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
+ friend class compact_set_base;
+ public:
+ iterator_base(const iterator_base& o) {
+ set = o.set;
+ it = o.it;
+ }
+ bool operator==(const iterator_base& o) const {
+ return (set == o.set) && (!set->set || it == o.it);
+ }
+ bool operator!=(const iterator_base& o) const {
+ return !(*this == o);;
+ }
+ iterator_base& operator=(const iterator_base& o) {
+ set->set = o.set;
+ it = o.it;
+ return *this;
+ }
+ iterator_base& operator++() {
+ ++it;
+ return *this;
+ }
+ iterator_base operator++(int) {
+ iterator_base tmp = *this;
+ ++it;
+ return tmp;
+ }
+ iterator_base& operator--() {
+ --it;
+ return *this;
+ }
+ const T& operator*() {
+ return *it;
+ }
+ };
+public:
+ class const_iterator : public iterator_base<typename Set::const_iterator> {
+ public:
+ const_iterator() { }
+ const_iterator(const iterator_base<typename Set::const_iterator>& o)
+ : iterator_base<typename Set::const_iterator>(o) { }
+ const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
+ const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
+ : iterator_base<typename Set::const_iterator>(s, i) { }
+ };
+ class iterator : public iterator_base<typename Set::iterator> {
+ public:
+ iterator() { }
+ iterator(const iterator_base<typename Set::iterator>& o)
+ : iterator_base<typename Set::iterator>(o) { }
+ iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
+ iterator(compact_set_base* s, const typename Set::iterator& i)
+ : iterator_base<typename Set::iterator>(s, i) { }
+ operator const_iterator() const {
+ return const_iterator(this->set, this->it);
+ }
+ };
+ class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
+ public:
+ const_reverse_iterator() { }
+ const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
+ : iterator_base<typename Set::const_reverse_iterator>(o) { }
+ const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
+ const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
+ : iterator_base<typename Set::const_reverse_iterator>(s, i) { }
+ };
+ class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
+ public:
+ reverse_iterator() { }
+ reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
+ : iterator_base<typename Set::reverse_iterator>(o) { }
+ reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
+ reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
+ : iterator_base<typename Set::reverse_iterator>(s, i) { }
+ operator const_iterator() const {
+ return const_iterator(this->set, this->it);
+ }
+ };
+
+ compact_set_base() {}
+ compact_set_base(const compact_set_base& o) {
+ if (o.set) {
+ alloc_internal();
+ *set = *o.set;
+ }
+ }
+ ~compact_set_base() {}
+
+
+ bool empty() const {
+ return !set || set->empty();
+ }
+ size_t size() const {
+ return set ? set->size() : 0;
+ }
+ bool operator==(const compact_set_base& o) const {
+ return (empty() && o.empty()) || (set && o.set && *set == *o.set);
+ }
+ bool operator!=(const compact_set_base& o) const {
+ return !(*this == o);
+ }
+ size_t count(const T& t) const {
+ return set ? set->count(t) : 0;
+ }
+ iterator erase (iterator p) {
+ if (set) {
+ ceph_assert(this == p.set);
+ auto it = set->erase(p.it);
+ if (set->empty()) {
+ free_internal();
+ return iterator(this);
+ } else {
+ return iterator(this, it);
+ }
+ } else {
+ return iterator(this);
+ }
+ }
+ size_t erase (const T& t) {
+ if (!set)
+ return 0;
+ size_t r = set->erase(t);
+ if (set->empty())
+ free_internal();
+ return r;
+ }
+ void clear() {
+ free_internal();
+ }
+ void swap(compact_set_base& o) {
+ set.swap(o.set);
+ }
+ compact_set_base& operator=(const compact_set_base& o) {
+ if (o.set) {
+ alloc_internal();
+ *set = *o.set;
+ } else
+ free_internal();
+ return *this;
+ }
+ std::pair<iterator,bool> insert(const T& t) {
+ alloc_internal();
+ std::pair<typename Set::iterator,bool> r = set->insert(t);
+ return std::make_pair(iterator(this, r.first), r.second);
+ }
+ template <class... Args>
+ std::pair<iterator,bool> emplace ( Args&&... args ) {
+ alloc_internal();
+ auto em = set->emplace(std::forward<Args>(args)...);
+ return std::pair<iterator,bool>(iterator(this, em.first), em.second);
+ }
+
+ iterator begin() {
+ if (!set)
+ return iterator(this);
+ return iterator(this, set->begin());
+ }
+ iterator end() {
+ if (!set)
+ return iterator(this);
+ return iterator(this, set->end());
+ }
+ reverse_iterator rbegin() {
+ if (!set)
+ return reverse_iterator(this);
+ return reverse_iterator(this, set->rbegin());
+ }
+ reverse_iterator rend() {
+ if (!set)
+ return reverse_iterator(this);
+ return reverse_iterator(this, set->rend());
+ }
+ iterator find(const T& t) {
+ if (!set)
+ return iterator(this);
+ return iterator(this, set->find(t));
+ }
+ iterator lower_bound(const T& t) {
+ if (!set)
+ return iterator(this);
+ return iterator(this, set->lower_bound(t));
+ }
+ iterator upper_bound(const T& t) {
+ if (!set)
+ return iterator(this);
+ return iterator(this, set->upper_bound(t));
+ }
+ const_iterator begin() const {
+ if (!set)
+ return const_iterator(this);
+ return const_iterator(this, set->begin());
+ }
+ const_iterator end() const {
+ if (!set)
+ return const_iterator(this);
+ return const_iterator(this, set->end());
+ }
+ const_reverse_iterator rbegin() const {
+ if (!set)
+ return const_reverse_iterator(this);
+ return const_reverse_iterator(this, set->rbegin());
+ }
+ const_reverse_iterator rend() const {
+ if (!set)
+ return const_reverse_iterator(this);
+ return const_reverse_iterator(this, set->rend());
+ }
+ const_iterator find(const T& t) const {
+ if (!set)
+ return const_iterator(this);
+ return const_iterator(this, set->find(t));
+ }
+ const_iterator lower_bound(const T& t) const {
+ if (!set)
+ return const_iterator(this);
+ return const_iterator(this, set->lower_bound(t));
+ }
+ const_iterator upper_bound(const T& t) const {
+ if (!set)
+ return const_iterator(this);
+ return const_iterator(this, set->upper_bound(t));
+ }
+ void encode(bufferlist &bl) const {
+ using ceph::encode;
+ if (set)
+ encode(*set, bl);
+ else
+ encode((uint32_t)0, bl);
+ }
+ void decode(bufferlist::const_iterator& p) {
+ using ceph::decode;
+ uint32_t n;
+ decode(n, p);
+ if (n > 0) {
+ alloc_internal();
+ decode_nohead(n, *set, p);
+ } else
+ free_internal();
+ }
+};
+
+template<class T, class Set>
+inline void encode(const compact_set_base<T, Set>& m, bufferlist& bl) {
+ m.encode(bl);
+}
+template<class T, class Set>
+inline void decode(compact_set_base<T, Set>& m, bufferlist::const_iterator& p) {
+ m.decode(p);
+}
+
+template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
+class compact_set : public compact_set_base<T, std::set<T, Compare, Alloc> > {
+};
+
+template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
+inline std::ostream& operator<<(std::ostream& out, const compact_set<T,Compare,Alloc>& s)
+{
+ bool first = true;
+ for (auto &v : s) {
+ if (!first)
+ out << ",";
+ out << v;
+ first = false;
+ }
+ return out;
+}
+#endif