]>
git.proxmox.com Git - ceph.git/blob - ceph/src/include/compact_set.h
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
;