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
17 template <class Key, class T, class Map>
18 class compact_map_base {
21 void alloc_internal() {
25 void free_internal() {
32 class const_iterator_base {
33 const compact_map_base *map;
35 const_iterator_base() : map(0) { }
36 const_iterator_base(const compact_map_base* m) : map(m) { }
37 const_iterator_base(const compact_map_base *m, const It& i) : map(m), it(i) { }
38 friend class compact_map_base;
39 friend class iterator_base;
41 const_iterator_base(const const_iterator_base& o) {
45 bool operator==(const const_iterator_base& o) const {
46 return (map == o.map) && (!map->map || it == o.it);
48 bool operator!=(const const_iterator_base& o) const {
49 return !(*this == o);;
51 const_iterator_base& operator=(const const_iterator_base& o) {
56 const_iterator_base& operator++() {
60 const_iterator_base& operator--() {
64 const std::pair<const Key,T>& operator*() {
67 const std::pair<const Key,T>* operator->() {
68 return it.operator->();
74 const compact_map_base* map;
76 iterator_base() : map(0) { }
77 iterator_base(compact_map_base* m) : map(m) { }
78 iterator_base(compact_map_base* m, const It& i) : map(m), it(i) { }
79 friend class compact_map_base;
81 iterator_base(const iterator_base& o) {
85 bool operator==(const iterator_base& o) const {
86 return (map == o.map) && (!map->map || it == o.it);
88 bool operator!=(const iterator_base& o) const {
89 return !(*this == o);;
91 iterator_base& operator=(const iterator_base& o) {
96 iterator_base& operator++() {
100 iterator_base operator++(int) {
101 iterator_base tmp = *this;
105 iterator_base& operator--() {
109 std::pair<const Key,T>& operator*() {
112 std::pair<const Key,T>* operator->() {
113 return it.operator->();
115 operator const_iterator_base<It>() const {
116 return const_iterator_base<It>(map, it);
121 class iterator : public iterator_base<typename Map::iterator> {
124 iterator(const iterator_base<typename Map::iterator>& o)
125 : iterator_base<typename Map::iterator>(o) { }
126 iterator(compact_map_base* m) : iterator_base<typename Map::iterator>(m) { }
127 iterator(compact_map_base* m, const typename Map::iterator& i)
128 : iterator_base<typename Map::iterator>(m, i) { }
130 class const_iterator : public const_iterator_base<typename Map::const_iterator> {
133 const_iterator(const iterator_base<typename Map::const_iterator>& o)
134 : const_iterator_base<typename Map::const_iterator>(o) { }
135 const_iterator(const compact_map_base* m) : const_iterator_base<typename Map::const_iterator>(m) { }
136 const_iterator(const compact_map_base* m, const typename Map::const_iterator& i)
137 : const_iterator_base<typename Map::const_iterator>(m, i) { }
139 class reverse_iterator : public iterator_base<typename Map::reverse_iterator> {
141 reverse_iterator() { }
142 reverse_iterator(const iterator_base<typename Map::reverse_iterator>& o)
143 : iterator_base<typename Map::reverse_iterator>(o) { }
144 reverse_iterator(compact_map_base* m) : iterator_base<typename Map::reverse_iterator>(m) { }
145 reverse_iterator(compact_map_base* m, const typename Map::reverse_iterator& i)
146 : iterator_base<typename Map::reverse_iterator>(m, i) { }
148 class const_reverse_iterator : public const_iterator_base<typename Map::const_reverse_iterator> {
150 const_reverse_iterator() { }
151 const_reverse_iterator(const iterator_base<typename Map::const_reverse_iterator>& o)
152 : iterator_base<typename Map::const_reverse_iterator>(o) { }
153 const_reverse_iterator(const compact_map_base* m) : const_iterator_base<typename Map::const_reverse_iterator>(m) { }
154 const_reverse_iterator(const compact_map_base* m, const typename Map::const_reverse_iterator& i)
155 : const_iterator_base<typename Map::const_reverse_iterator>(m, i) { }
157 compact_map_base() : map(0) {}
158 compact_map_base(const compact_map_base& o) : map(0) {
164 ~compact_map_base() { delete map; }
167 return !map || map->empty();
169 size_t size() const {
170 return map ? map->size() : 0;
172 bool operator==(const compact_map_base& o) const {
173 return (empty() && o.empty()) || (map && o.map && *map == *o.map);
175 bool operator!=(const compact_map_base& o) const {
176 return !(*this == o);
178 size_t count (const Key& k) const {
179 return map ? map->count(k) : 0;
181 void erase (iterator p) {
183 assert(this == p.map);
189 size_t erase (const Key& k) {
192 size_t r = map->erase(k);
200 void swap(compact_map_base& o) {
205 compact_map_base& operator=(const compact_map_base& o) {
213 iterator insert(const std::pair<const Key, T>& val) {
215 return iterator(this, map->insert(val));
219 return iterator(this);
220 return iterator(this, map->begin());
224 return iterator(this);
225 return iterator(this, map->end());
227 reverse_iterator rbegin() {
229 return reverse_iterator(this);
230 return reverse_iterator(this, map->rbegin());
232 reverse_iterator rend() {
234 return reverse_iterator(this);
235 return reverse_iterator(this, map->rend());
237 iterator find(const Key& k) {
239 return iterator(this);
240 return iterator(this, map->find(k));
242 iterator lower_bound(const Key& k) {
244 return iterator(this);
245 return iterator(this, map->lower_bound(k));
247 iterator upper_bound(const Key& k) {
249 return iterator(this);
250 return iterator(this, map->upper_bound(k));
252 const_iterator begin() const {
254 return const_iterator(this);
255 return const_iterator(this, map->begin());
257 const_iterator end() const {
259 return const_iterator(this);
260 return const_iterator(this, map->end());
262 const_reverse_iterator rbegin() const {
264 return const_reverse_iterator(this);
265 return const_reverse_iterator(this, map->rbegin());
267 const_reverse_iterator rend() const {
269 return const_reverse_iterator(this);
270 return const_reverse_iterator(this, map->rend());
272 const_iterator find(const Key& k) const {
274 return const_iterator(this);
275 return const_iterator(this, map->find(k));
277 const_iterator lower_bound(const Key& k) const {
279 return const_iterator(this);
280 return const_iterator(this, map->lower_bound(k));
282 const_iterator upper_bound(const Key& k) const {
284 return const_iterator(this);
285 return const_iterator(this, map->upper_bound(k));
287 void encode(bufferlist &bl) const {
291 ::encode((uint32_t)0, bl);
293 void encode(bufferlist &bl, uint64_t features) const {
295 ::encode(*map, bl, features);
297 ::encode((uint32_t)0, bl);
299 void decode(bufferlist::iterator& p) {
304 ::decode_nohead(n, *map, p);
310 template<class Key, class T, class Map>
311 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl) {
314 template<class Key, class T, class Map>
315 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl,
317 m.encode(bl, features);
319 template<class Key, class T, class Map>
320 inline void decode(compact_map_base<Key, T, Map>& m, bufferlist::iterator& p) {
324 template <class Key, class T>
325 class compact_map : public compact_map_base<Key, T, std::map<Key,T> > {
327 T& operator[](const Key& k) {
328 this->alloc_internal();
329 return (*(this->map))[k];
333 template <class Key, class T>
334 inline std::ostream& operator<<(std::ostream& out, const compact_map<Key, T>& m)
337 for (typename compact_map<Key, T>::const_iterator it = m.begin();
342 out << it->first << "=" << it->second;
348 template <class Key, class T>
349 class compact_multimap : public compact_map_base<Key, T, std::multimap<Key,T> > {
352 template <class Key, class T>
353 inline std::ostream& operator<<(std::ostream& out, const compact_multimap<Key, T>& m)
356 for (typename compact_map<Key, T>::const_iterator it = m.begin(); !it.end(); ++it) {
359 out << it->first << "=" << it->second;