2 * Ceph - scalable distributed file system
4 * Copyright (C) 2015 Red Hat, Inc
6 * This is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License version 2.1, as published by the Free Software
9 * Foundation. See file COPYING.
12 #ifndef CEPH_COMPACT_SET_H
13 #define CEPH_COMPACT_SET_H
17 #include "include/buffer.h"
18 #include "include/encoding.h"
21 template <class T, class Set>
22 class compact_set_base {
25 void alloc_internal() {
29 void free_internal() {
38 const compact_set_base* set;
40 iterator_base() : set(0) { }
41 iterator_base(const compact_set_base* s) : set(s) { }
42 iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
43 friend class compact_set_base;
45 iterator_base(const iterator_base& o) {
49 bool operator==(const iterator_base& o) const {
50 return (set == o.set) && (!set->set || it == o.it);
52 bool operator!=(const iterator_base& o) const {
53 return !(*this == o);;
55 iterator_base& operator=(const iterator_base& o) {
60 iterator_base& operator++() {
64 iterator_base operator++(int) {
65 iterator_base tmp = *this;
69 iterator_base& operator--() {
73 const T& operator*() {
78 class const_iterator : public iterator_base<typename Set::const_iterator> {
81 const_iterator(const iterator_base<typename Set::const_iterator>& o)
82 : iterator_base<typename Set::const_iterator>(o) { }
83 const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
84 const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
85 : iterator_base<typename Set::const_iterator>(s, i) { }
87 class iterator : public iterator_base<typename Set::iterator> {
90 iterator(const iterator_base<typename Set::iterator>& o)
91 : iterator_base<typename Set::iterator>(o) { }
92 iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
93 iterator(compact_set_base* s, const typename Set::iterator& i)
94 : iterator_base<typename Set::iterator>(s, i) { }
95 operator const_iterator() const {
96 return const_iterator(this->set, this->it);
99 class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
101 const_reverse_iterator() { }
102 const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
103 : iterator_base<typename Set::const_reverse_iterator>(o) { }
104 const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
105 const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
106 : iterator_base<typename Set::const_reverse_iterator>(s, i) { }
108 class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
110 reverse_iterator() { }
111 reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
112 : iterator_base<typename Set::reverse_iterator>(o) { }
113 reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
114 reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
115 : iterator_base<typename Set::reverse_iterator>(s, i) { }
116 operator const_iterator() const {
117 return const_iterator(this->set, this->it);
121 compact_set_base() : set(0) {}
122 compact_set_base(const compact_set_base& o) : set(0) {
128 ~compact_set_base() { delete set; }
132 return !set || set->empty();
134 size_t size() const {
135 return set ? set->size() : 0;
137 bool operator==(const compact_set_base& o) const {
138 return (empty() && o.empty()) || (set && o.set && *set == *o.set);
140 bool operator!=(const compact_set_base& o) const {
141 return !(*this == o);
143 size_t count(const T& t) const {
144 return set ? set->count(t) : 0;
146 void erase (iterator p) {
148 assert(this == p.set);
154 size_t erase (const T& t) {
157 size_t r = set->erase(t);
165 void swap(compact_set_base& o) {
170 compact_set_base& operator=(const compact_set_base& o) {
178 std::pair<iterator,bool> insert(const T& t) {
180 std::pair<typename Set::iterator,bool> r = set->insert(t);
181 return std::make_pair(iterator(this, r.first), r.second);
185 return iterator(this);
186 return iterator(this, set->begin());
190 return iterator(this);
191 return iterator(this, set->end());
193 reverse_iterator rbegin() {
195 return reverse_iterator(this);
196 return reverse_iterator(this, set->rbegin());
198 reverse_iterator rend() {
200 return reverse_iterator(this);
201 return reverse_iterator(this, set->rend());
203 iterator find(const T& t) {
205 return iterator(this);
206 return iterator(this, set->find(t));
208 iterator lower_bound(const T& t) {
210 return iterator(this);
211 return iterator(this, set->lower_bound(t));
213 iterator upper_bound(const T& t) {
215 return iterator(this);
216 return iterator(this, set->upper_bound(t));
218 const_iterator begin() const {
220 return const_iterator(this);
221 return const_iterator(this, set->begin());
223 const_iterator end() const {
225 return const_iterator(this);
226 return const_iterator(this, set->end());
228 const_reverse_iterator rbegin() const {
230 return const_reverse_iterator(this);
231 return const_reverse_iterator(this, set->rbegin());
233 const_reverse_iterator rend() const {
235 return const_reverse_iterator(this);
236 return const_reverse_iterator(this, set->rend());
238 const_iterator find(const T& t) const {
240 return const_iterator(this);
241 return const_iterator(this, set->find(t));
243 const_iterator lower_bound(const T& t) const {
245 return const_iterator(this);
246 return const_iterator(this, set->lower_bound(t));
248 const_iterator upper_bound(const T& t) const {
250 return const_iterator(this);
251 return const_iterator(this, set->upper_bound(t));
253 void encode(bufferlist &bl) const {
257 ::encode((uint32_t)0, bl);
259 void decode(bufferlist::iterator& p) {
264 ::decode_nohead(n, *set, p);
270 template<class T, class Set>
271 inline void encode(const compact_set_base<T, Set>& m, bufferlist& bl) {
274 template<class T, class Set>
275 inline void decode(compact_set_base<T, Set>& m, bufferlist::iterator& p) {
280 class compact_set : public compact_set_base<T, std::set<T> > {
284 inline std::ostream& operator<<(std::ostream& out, const compact_set<T>& s)
286 for (typename compact_set<T>::const_iterator it = s.begin();
287 it != s.end(); ++it) {
290 out << it->first << "=" << it->second;