ceph/src/include/compact_map.h

   1 /*
   2  * Ceph - scalable distributed file system
   3  *
   4  * Copyright (C) 2015 Red Hat, Inc
   5  *
   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.
  10  *
  11  */
  12 #ifndef CEPH_COMPACT_MAP_H
  13 #define CEPH_COMPACT_MAP_H
  14
  15 #include <map>
  16
  17 template <class Key, class T, class Map>
  18 class compact_map_base {
  19 protected:
  20   Map *map;
  21   void alloc_internal() {
  22     if (!map)
  23       map = new Map;
  24   }
  25   void free_internal() {
  26     if (map) {
  27       delete map;
  28       map = 0;
  29     }
  30   }
  31   template <class It>
  32   class const_iterator_base {
  33     const compact_map_base *map;
  34     It it;
  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;
  40   public:
  41     const_iterator_base(const const_iterator_base& o) {
  42       map = o.map;
  43       it = o.it;
  44     }
  45     bool operator==(const const_iterator_base& o) const {
  46       return (map == o.map) && (!map->map || it == o.it);
  47     }
  48     bool operator!=(const const_iterator_base& o) const {
  49       return !(*this == o);;
  50     }
  51     const_iterator_base& operator=(const const_iterator_base& o) {
  52       map = o.map;
  53       it = o.it;
  54       return *this;
  55     }
  56     const_iterator_base& operator++() {
  57       ++it;
  58       return *this;
  59     }
  60     const_iterator_base& operator--() {
  61       --it;
  62       return *this;
  63     }
  64     const std::pair<const Key,T>* operator->() {
  65       return it.operator->();
  66     }
  67   };
  68   template <class It>
  69   class iterator_base {
  70   private:
  71     const compact_map_base* map;
  72     It it;
  73     iterator_base() : map(0) { }
  74     iterator_base(compact_map_base* m) : map(m) { }
  75     iterator_base(compact_map_base* m, const It& i) : map(m), it(i) { }
  76     friend class compact_map_base;
  77   public:
  78     iterator_base(const iterator_base& o) {
  79       map = o.map;
  80       it = o.it;
  81     }
  82     bool operator==(const iterator_base& o) const {
  83       return (map == o.map) && (!map->map || it == o.it);
  84     }
  85     bool operator!=(const iterator_base& o) const {
  86       return !(*this == o);;
  87     }
  88     iterator_base& operator=(const iterator_base& o) {
  89       map = o.map;
  90       it = o.it;
  91       return *this;
  92     }
  93     iterator_base& operator++() {
  94       ++it;
  95       return *this;
  96     }
  97     iterator_base operator++(int) {
  98       iterator_base tmp = *this;
  99       ++it;
 100       return tmp;
 101     }
 102     iterator_base& operator--() {
 103       --it;
 104       return *this;
 105     }
 106     std::pair<const Key,T>* operator->() {
 107       return it.operator->();
 108     }
 109     operator const_iterator_base<It>() const {
 110       return const_iterator_base<It>(map, it);
 111     }
 112   };
 113
 114 public:
 115   class iterator : public iterator_base<typename Map::iterator> {
 116     public:
 117       iterator() { }
 118       iterator(const iterator_base<typename Map::iterator>& o)
 119         : iterator_base<typename Map::iterator>(o) { }
 120       iterator(compact_map_base* m) : iterator_base<typename Map::iterator>(m) { }
 121       iterator(compact_map_base* m, const typename Map::iterator& i)
 122         : iterator_base<typename Map::iterator>(m, i) { }
 123   };
 124   class const_iterator : public const_iterator_base<typename Map::const_iterator> {
 125     public:
 126       const_iterator() { }
 127       const_iterator(const iterator_base<typename Map::const_iterator>& o)
 128         : const_iterator_base<typename Map::const_iterator>(o) { }
 129       const_iterator(const compact_map_base* m) : const_iterator_base<typename Map::const_iterator>(m) { }
 130       const_iterator(const compact_map_base* m, const typename Map::const_iterator& i)
 131         : const_iterator_base<typename Map::const_iterator>(m, i) { }
 132   };
 133   class reverse_iterator : public iterator_base<typename Map::reverse_iterator> {
 134     public:
 135       reverse_iterator() { }
 136       reverse_iterator(const iterator_base<typename Map::reverse_iterator>& o)
 137         : iterator_base<typename Map::reverse_iterator>(o) { }
 138       reverse_iterator(compact_map_base* m) : iterator_base<typename Map::reverse_iterator>(m) { }
 139       reverse_iterator(compact_map_base* m, const typename Map::reverse_iterator& i)
 140         : iterator_base<typename Map::reverse_iterator>(m, i) { }
 141   };
 142   class const_reverse_iterator : public const_iterator_base<typename Map::const_reverse_iterator> {
 143     public:
 144       const_reverse_iterator() { }
 145       const_reverse_iterator(const iterator_base<typename Map::const_reverse_iterator>& o)
 146         : iterator_base<typename Map::const_reverse_iterator>(o) { }
 147       const_reverse_iterator(const compact_map_base* m) : const_iterator_base<typename Map::const_reverse_iterator>(m) { }
 148       const_reverse_iterator(const compact_map_base* m, const typename Map::const_reverse_iterator& i)
 149         : const_iterator_base<typename Map::const_reverse_iterator>(m, i) { }
 150   };
 151   compact_map_base() : map(0) {}
 152   compact_map_base(const compact_map_base& o) : map(0) {
 153     if (o.map) {
 154       alloc_internal();
 155       *map = *o.map;
 156     }
 157   }
 158   ~compact_map_base() { delete map; }
 159
 160   bool empty() const {
 161     return !map || map->empty();
 162   }
 163   size_t size() const {
 164     return map ? map->size() : 0;
 165   }
 166   bool operator==(const compact_map_base& o) const {
 167     return (empty() && o.empty()) || (map && o.map && *map == *o.map);
 168   }
 169   bool operator!=(const compact_map_base& o) const {
 170     return !(*this == o);
 171   }
 172   size_t count (const Key& k) const {
 173     return map ? map->count(k) : 0;
 174   }
 175   void erase (iterator p) {
 176     if (map) {
 177       assert(this == p.map);
 178       map->erase(p.it);
 179       if (map->empty())
 180         free_internal();
 181     }
 182   }
 183   size_t erase (const Key& k) {
 184     if (!map)
 185       return 0;
 186     size_t r = map->erase(k);
 187     if (map->empty())
 188         free_internal();
 189     return r;
 190   }
 191   void clear() {
 192     free_internal();
 193   }
 194   void swap(compact_map_base& o) {
 195     Map *tmp = map;
 196     map = o.map;
 197     o.map = tmp;
 198   }
 199   compact_map_base& operator=(const compact_map_base& o) {
 200     if (o.map) {
 201       alloc_internal();
 202       *map = *o.map;
 203     } else
 204       free_internal();
 205     return *this;
 206   }
 207   iterator insert(const std::pair<const Key, T>& val) {
 208     alloc_internal();
 209     return iterator(this, map->insert(val));
 210   }
 211   iterator begin() {
 212    if (!map)
 213      return iterator(this);
 214    return iterator(this, map->begin());
 215   }
 216   iterator end() {
 217    if (!map)
 218      return iterator(this);
 219    return iterator(this, map->end());
 220   }
 221   reverse_iterator rbegin() {
 222    if (!map)
 223      return reverse_iterator(this);
 224    return reverse_iterator(this, map->rbegin());
 225   }
 226   reverse_iterator rend() {
 227    if (!map)
 228      return reverse_iterator(this);
 229    return reverse_iterator(this, map->rend());
 230   }
 231   iterator find(const Key& k) {
 232     if (!map)
 233       return iterator(this);
 234     return iterator(this, map->find(k));
 235   }
 236   iterator lower_bound(const Key& k) {
 237     if (!map)
 238       return iterator(this);
 239     return iterator(this, map->lower_bound(k));
 240   }
 241   iterator upper_bound(const Key& k) {
 242     if (!map)
 243       return iterator(this);
 244     return iterator(this, map->upper_bound(k));
 245   }
 246   const_iterator begin() const {
 247    if (!map)
 248      return const_iterator(this);
 249    return const_iterator(this, map->begin());
 250   }
 251   const_iterator end() const {
 252    if (!map)
 253      return const_iterator(this);
 254    return const_iterator(this, map->end());
 255   }
 256   const_reverse_iterator rbegin() const {
 257    if (!map)
 258      return const_reverse_iterator(this);
 259    return const_reverse_iterator(this, map->rbegin());
 260   }
 261   const_reverse_iterator rend() const {
 262    if (!map)
 263      return const_reverse_iterator(this);
 264    return const_reverse_iterator(this, map->rend());
 265   }
 266   const_iterator find(const Key& k) const {
 267     if (!map)
 268       return const_iterator(this);
 269     return const_iterator(this, map->find(k));
 270   }
 271   const_iterator lower_bound(const Key& k) const {
 272     if (!map)
 273       return const_iterator(this);
 274     return const_iterator(this, map->lower_bound(k));
 275   }
 276   const_iterator upper_bound(const Key& k) const {
 277     if (!map)
 278       return const_iterator(this);
 279     return const_iterator(this, map->upper_bound(k));
 280   }
 281   void encode(bufferlist &bl) const {
 282     if (map)
 283       ::encode(*map, bl);
 284     else
 285       ::encode((uint32_t)0, bl);
 286   }
 287   void encode(bufferlist &bl, uint64_t features) const {
 288     if (map)
 289       ::encode(*map, bl, features);
 290     else
 291       ::encode((uint32_t)0, bl);
 292   }
 293   void decode(bufferlist::iterator& p) {
 294     uint32_t n;
 295     ::decode(n, p);
 296     if (n > 0) {
 297       alloc_internal();
 298       ::decode_nohead(n, *map, p);
 299     } else
 300       free_internal();
 301   }
 302 };
 303
 304 template<class Key, class T, class Map>
 305 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl) {
 306   m.encode(bl);
 307 }
 308 template<class Key, class T, class Map>
 309 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl,
 310                    uint64_t features) {
 311   m.encode(bl, features);
 312 }
 313 template<class Key, class T, class Map>
 314 inline void decode(compact_map_base<Key, T, Map>& m, bufferlist::iterator& p) {
 315   m.decode(p);
 316 }
 317
 318 template <class Key, class T>
 319 class compact_map : public compact_map_base<Key, T, std::map<Key,T> > {
 320 public:
 321   T& operator[](const Key& k) {
 322     this->alloc_internal();
 323     return (*(this->map))[k];
 324   }
 325 };
 326
 327 template <class Key, class T>
 328 inline std::ostream& operator<<(std::ostream& out, const compact_map<Key, T>& m)
 329 {
 330   out << "{";
 331   for (typename compact_map<Key, T>::const_iterator it = m.begin();
 332        it != m.end();
 333        ++it) {
 334     if (it != m.begin())
 335       out << ",";
 336     out << it->first << "=" << it->second;
 337   }
 338   out << "}";
 339   return out;
 340 }
 341
 342 template <class Key, class T>
 343 class compact_multimap : public compact_map_base<Key, T, std::multimap<Key,T> > {
 344 };
 345
 346 template <class Key, class T>
 347 inline std::ostream& operator<<(std::ostream& out, const compact_multimap<Key, T>& m)
 348 {
 349   out << "{{";
 350   for (typename compact_map<Key, T>::const_iterator it = m.begin(); !it.end(); ++it) {
 351     if (it != m.begin())
 352       out << ",";
 353     out << it->first << "=" << it->second;
 354   }
 355   out << "}}";
 356   return out;
 357 }
 358 #endif