]>
git.proxmox.com Git - ceph.git/blob - ceph/src/include/compact_map.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_MAP_H
13 #define CEPH_COMPACT_MAP_H
21 #include "include/encoding.h"
23 template <class Key
, class T
, class Map
>
24 class compact_map_base
{
26 std::unique_ptr
<Map
> map
;
27 void alloc_internal() {
31 void free_internal() {
35 class const_iterator_base
{
36 const compact_map_base
*map
;
38 const_iterator_base() : map(0) { }
39 const_iterator_base(const compact_map_base
* m
) : map(m
) { }
40 const_iterator_base(const compact_map_base
*m
, const It
& i
) : map(m
), it(i
) { }
41 friend class compact_map_base
;
42 friend class iterator_base
;
44 const_iterator_base(const const_iterator_base
& o
) {
48 bool operator==(const const_iterator_base
& o
) const {
49 return (map
== o
.map
) && (!map
->map
|| it
== o
.it
);
51 bool operator!=(const const_iterator_base
& o
) const {
52 return !(*this == o
);;
54 const_iterator_base
& operator=(const const_iterator_base
& o
) {
59 const_iterator_base
& operator++() {
63 const_iterator_base
& operator--() {
67 const std::pair
<const Key
,T
>& operator*() {
70 const std::pair
<const Key
,T
>* operator->() {
71 return it
.operator->();
77 const compact_map_base
* map
;
79 iterator_base() : map(0) { }
80 iterator_base(compact_map_base
* m
) : map(m
) { }
81 iterator_base(compact_map_base
* m
, const It
& i
) : map(m
), it(i
) { }
82 friend class compact_map_base
;
84 iterator_base(const iterator_base
& o
) {
88 bool operator==(const iterator_base
& o
) const {
89 return (map
== o
.map
) && (!map
->map
|| it
== o
.it
);
91 bool operator!=(const iterator_base
& o
) const {
92 return !(*this == o
);;
94 iterator_base
& operator=(const iterator_base
& o
) {
99 iterator_base
& operator++() {
103 iterator_base
operator++(int) {
104 iterator_base tmp
= *this;
108 iterator_base
& operator--() {
112 std::pair
<const Key
,T
>& operator*() {
115 std::pair
<const Key
,T
>* operator->() {
116 return it
.operator->();
118 operator const_iterator_base
<It
>() const {
119 return const_iterator_base
<It
>(map
, it
);
124 class iterator
: public iterator_base
<typename
Map::iterator
> {
127 iterator(const iterator_base
<typename
Map::iterator
>& o
)
128 : iterator_base
<typename
Map::iterator
>(o
) { }
129 iterator(compact_map_base
* m
) : iterator_base
<typename
Map::iterator
>(m
) { }
130 iterator(compact_map_base
* m
, const typename
Map::iterator
& i
)
131 : iterator_base
<typename
Map::iterator
>(m
, i
) { }
133 class const_iterator
: public const_iterator_base
<typename
Map::const_iterator
> {
136 const_iterator(const iterator_base
<typename
Map::const_iterator
>& o
)
137 : const_iterator_base
<typename
Map::const_iterator
>(o
) { }
138 const_iterator(const compact_map_base
* m
) : const_iterator_base
<typename
Map::const_iterator
>(m
) { }
139 const_iterator(const compact_map_base
* m
, const typename
Map::const_iterator
& i
)
140 : const_iterator_base
<typename
Map::const_iterator
>(m
, i
) { }
142 class reverse_iterator
: public iterator_base
<typename
Map::reverse_iterator
> {
144 reverse_iterator() { }
145 reverse_iterator(const iterator_base
<typename
Map::reverse_iterator
>& o
)
146 : iterator_base
<typename
Map::reverse_iterator
>(o
) { }
147 reverse_iterator(compact_map_base
* m
) : iterator_base
<typename
Map::reverse_iterator
>(m
) { }
148 reverse_iterator(compact_map_base
* m
, const typename
Map::reverse_iterator
& i
)
149 : iterator_base
<typename
Map::reverse_iterator
>(m
, i
) { }
151 class const_reverse_iterator
: public const_iterator_base
<typename
Map::const_reverse_iterator
> {
153 const_reverse_iterator() { }
154 const_reverse_iterator(const iterator_base
<typename
Map::const_reverse_iterator
>& o
)
155 : iterator_base
<typename
Map::const_reverse_iterator
>(o
) { }
156 const_reverse_iterator(const compact_map_base
* m
) : const_iterator_base
<typename
Map::const_reverse_iterator
>(m
) { }
157 const_reverse_iterator(const compact_map_base
* m
, const typename
Map::const_reverse_iterator
& i
)
158 : const_iterator_base
<typename
Map::const_reverse_iterator
>(m
, i
) { }
160 compact_map_base(const compact_map_base
& o
) {
166 compact_map_base() {}
167 ~compact_map_base() {}
170 return !map
|| map
->empty();
172 size_t size() const {
173 return map
? map
->size() : 0;
175 bool operator==(const compact_map_base
& o
) const {
176 return (empty() && o
.empty()) || (map
&& o
.map
&& *map
== *o
.map
);
178 bool operator!=(const compact_map_base
& o
) const {
179 return !(*this == o
);
181 size_t count (const Key
& k
) const {
182 return map
? map
->count(k
) : 0;
184 iterator
erase (iterator p
) {
186 ceph_assert(this == p
.map
);
187 auto it
= map
->erase(p
.it
);
190 return iterator(this);
192 return iterator(this, it
);
195 return iterator(this);
198 size_t erase (const Key
& k
) {
201 size_t r
= map
->erase(k
);
209 void swap(compact_map_base
& o
) {
212 compact_map_base
& operator=(const compact_map_base
& o
) {
220 iterator
insert(const std::pair
<const Key
, T
>& val
) {
222 return iterator(this, map
->insert(val
));
224 template <class... Args
>
225 std::pair
<iterator
,bool> emplace ( Args
&&... args
) {
227 auto em
= map
->emplace(std::forward
<Args
>(args
)...);
228 return std::pair
<iterator
,bool>(iterator(this, em
.first
), em
.second
);
232 return iterator(this);
233 return iterator(this, map
->begin());
237 return iterator(this);
238 return iterator(this, map
->end());
240 reverse_iterator
rbegin() {
242 return reverse_iterator(this);
243 return reverse_iterator(this, map
->rbegin());
245 reverse_iterator
rend() {
247 return reverse_iterator(this);
248 return reverse_iterator(this, map
->rend());
250 iterator
find(const Key
& k
) {
252 return iterator(this);
253 return iterator(this, map
->find(k
));
255 iterator
lower_bound(const Key
& k
) {
257 return iterator(this);
258 return iterator(this, map
->lower_bound(k
));
260 iterator
upper_bound(const Key
& k
) {
262 return iterator(this);
263 return iterator(this, map
->upper_bound(k
));
265 const_iterator
begin() const {
267 return const_iterator(this);
268 return const_iterator(this, map
->begin());
270 const_iterator
end() const {
272 return const_iterator(this);
273 return const_iterator(this, map
->end());
275 const_reverse_iterator
rbegin() const {
277 return const_reverse_iterator(this);
278 return const_reverse_iterator(this, map
->rbegin());
280 const_reverse_iterator
rend() const {
282 return const_reverse_iterator(this);
283 return const_reverse_iterator(this, map
->rend());
285 const_iterator
find(const Key
& k
) const {
287 return const_iterator(this);
288 return const_iterator(this, map
->find(k
));
290 const_iterator
lower_bound(const Key
& k
) const {
292 return const_iterator(this);
293 return const_iterator(this, map
->lower_bound(k
));
295 const_iterator
upper_bound(const Key
& k
) const {
297 return const_iterator(this);
298 return const_iterator(this, map
->upper_bound(k
));
300 void encode(ceph::buffer::list
&bl
) const {
305 encode((uint32_t)0, bl
);
307 void encode(ceph::buffer::list
&bl
, uint64_t features
) const {
310 encode(*map
, bl
, features
);
312 encode((uint32_t)0, bl
);
314 void decode(ceph::buffer::list::const_iterator
& p
) {
316 using ceph::decode_nohead
;
321 decode_nohead(n
, *map
, p
);
327 template<class Key
, class T
, class Map
>
328 inline void encode(const compact_map_base
<Key
, T
, Map
>& m
, ceph::buffer::list
& bl
) {
331 template<class Key
, class T
, class Map
>
332 inline void encode(const compact_map_base
<Key
, T
, Map
>& m
, ceph::buffer::list
& bl
,
334 m
.encode(bl
, features
);
336 template<class Key
, class T
, class Map
>
337 inline void decode(compact_map_base
<Key
, T
, Map
>& m
, ceph::buffer::list::const_iterator
& p
) {
341 template <class Key
, class T
, class Compare
= std::less
<Key
>, class Alloc
= std::allocator
< std::pair
<const Key
, T
> > >
342 class compact_map
: public compact_map_base
<Key
, T
, std::map
<Key
,T
,Compare
,Alloc
> > {
344 T
& operator[](const Key
& k
) {
345 this->alloc_internal();
346 return (*(this->map
))[k
];
350 template <class Key
, class T
, class Compare
= std::less
<Key
>, class Alloc
= std::allocator
< std::pair
<const Key
, T
> > >
351 inline std::ostream
& operator<<(std::ostream
& out
, const compact_map
<Key
, T
, Compare
, Alloc
>& m
)
355 for (const auto &p
: m
) {
358 out
<< p
.first
<< "=" << p
.second
;
365 template <class Key
, class T
, class Compare
= std::less
<Key
>, class Alloc
= std::allocator
< std::pair
<const Key
, T
> > >
366 class compact_multimap
: public compact_map_base
<Key
, T
, std::multimap
<Key
,T
,Compare
,Alloc
> > {
369 template <class Key
, class T
, class Compare
= std::less
<Key
>, class Alloc
= std::allocator
< std::pair
<const Key
, T
> > >
370 inline std::ostream
& operator<<(std::ostream
& out
, const compact_multimap
<Key
, T
, Compare
, Alloc
>& m
)
374 for (const auto &p
: m
) {
377 out
<< p
.first
<< "=" << p
.second
;