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;
  66     }
  67     const std::pair<const Key,T>* operator->() {
  68       return it.operator->();
  69     }
  70   };
  71   template <class It>
  72   class iterator_base {
  73   private:
  74     const compact_map_base* map;
  75     It it;
  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;
  80   public:
  81     iterator_base(const iterator_base& o) {
  82       map = o.map;
  83       it = o.it;
  84     }
  85     bool operator==(const iterator_base& o) const {
  86       return (map == o.map) && (!map->map || it == o.it);
  87     }
  88     bool operator!=(const iterator_base& o) const {
  89       return !(*this == o);;
  90     }
  91     iterator_base& operator=(const iterator_base& o) {
  92       map = o.map;
  93       it = o.it;
  94       return *this;
  95     }
  96     iterator_base& operator++() {
  97       ++it;
  98       return *this;
  99     }
 100     iterator_base operator++(int) {
 101       iterator_base tmp = *this;
 102       ++it;
 103       return tmp;
 104     }
 105     iterator_base& operator--() {
 106       --it;
 107       return *this;
 108     }
 109     std::pair<const Key,T>& operator*() {
 110       return *it;
 111     }
 112     std::pair<const Key,T>* operator->() {
 113       return it.operator->();
 114     }
 115     operator const_iterator_base<It>() const {
 116       return const_iterator_base<It>(map, it);
 117     }
 118   };
 119
 120 public:
 121   class iterator : public iterator_base<typename Map::iterator> {
 122     public:
 123       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) { }
 129   };
 130   class const_iterator : public const_iterator_base<typename Map::const_iterator> {
 131     public:
 132       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) { }
 138   };
 139   class reverse_iterator : public iterator_base<typename Map::reverse_iterator> {
 140     public:
 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) { }
 147   };
 148   class const_reverse_iterator : public const_iterator_base<typename Map::const_reverse_iterator> {
 149     public:
 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) { }
 156   };
 157   compact_map_base() : map(0) {}
 158   compact_map_base(const compact_map_base& o) : map(0) {
 159     if (o.map) {
 160       alloc_internal();
 161       *map = *o.map;
 162     }
 163   }
 164   ~compact_map_base() { delete map; }
 165
 166   bool empty() const {
 167     return !map || map->empty();
 168   }
 169   size_t size() const {
 170     return map ? map->size() : 0;
 171   }
 172   bool operator==(const compact_map_base& o) const {
 173     return (empty() && o.empty()) || (map && o.map && *map == *o.map);
 174   }
 175   bool operator!=(const compact_map_base& o) const {
 176     return !(*this == o);
 177   }
 178   size_t count (const Key& k) const {
 179     return map ? map->count(k) : 0;
 180   }
 181   void erase (iterator p) {
 182     if (map) {
 183       assert(this == p.map);
 184       map->erase(p.it);
 185       if (map->empty())
 186         free_internal();
 187     }
 188   }
 189   size_t erase (const Key& k) {
 190     if (!map)
 191       return 0;
 192     size_t r = map->erase(k);
 193     if (map->empty())
 194         free_internal();
 195     return r;
 196   }
 197   void clear() {
 198     free_internal();
 199   }
 200   void swap(compact_map_base& o) {
 201     Map *tmp = map;
 202     map = o.map;
 203     o.map = tmp;
 204   }
 205   compact_map_base& operator=(const compact_map_base& o) {
 206     if (o.map) {
 207       alloc_internal();
 208       *map = *o.map;
 209     } else
 210       free_internal();
 211     return *this;
 212   }
 213   iterator insert(const std::pair<const Key, T>& val) {
 214     alloc_internal();
 215     return iterator(this, map->insert(val));
 216   }
 217   iterator begin() {
 218    if (!map)
 219      return iterator(this);
 220    return iterator(this, map->begin());
 221   }
 222   iterator end() {
 223    if (!map)
 224      return iterator(this);
 225    return iterator(this, map->end());
 226   }
 227   reverse_iterator rbegin() {
 228    if (!map)
 229      return reverse_iterator(this);
 230    return reverse_iterator(this, map->rbegin());
 231   }
 232   reverse_iterator rend() {
 233    if (!map)
 234      return reverse_iterator(this);
 235    return reverse_iterator(this, map->rend());
 236   }
 237   iterator find(const Key& k) {
 238     if (!map)
 239       return iterator(this);
 240     return iterator(this, map->find(k));
 241   }
 242   iterator lower_bound(const Key& k) {
 243     if (!map)
 244       return iterator(this);
 245     return iterator(this, map->lower_bound(k));
 246   }
 247   iterator upper_bound(const Key& k) {
 248     if (!map)
 249       return iterator(this);
 250     return iterator(this, map->upper_bound(k));
 251   }
 252   const_iterator begin() const {
 253    if (!map)
 254      return const_iterator(this);
 255    return const_iterator(this, map->begin());
 256   }
 257   const_iterator end() const {
 258    if (!map)
 259      return const_iterator(this);
 260    return const_iterator(this, map->end());
 261   }
 262   const_reverse_iterator rbegin() const {
 263    if (!map)
 264      return const_reverse_iterator(this);
 265    return const_reverse_iterator(this, map->rbegin());
 266   }
 267   const_reverse_iterator rend() const {
 268    if (!map)
 269      return const_reverse_iterator(this);
 270    return const_reverse_iterator(this, map->rend());
 271   }
 272   const_iterator find(const Key& k) const {
 273     if (!map)
 274       return const_iterator(this);
 275     return const_iterator(this, map->find(k));
 276   }
 277   const_iterator lower_bound(const Key& k) const {
 278     if (!map)
 279       return const_iterator(this);
 280     return const_iterator(this, map->lower_bound(k));
 281   }
 282   const_iterator upper_bound(const Key& k) const {
 283     if (!map)
 284       return const_iterator(this);
 285     return const_iterator(this, map->upper_bound(k));
 286   }
 287   void encode(bufferlist &bl) const {
 288     if (map)
 289       ::encode(*map, bl);
 290     else
 291       ::encode((uint32_t)0, bl);
 292   }
 293   void encode(bufferlist &bl, uint64_t features) const {
 294     if (map)
 295       ::encode(*map, bl, features);
 296     else
 297       ::encode((uint32_t)0, bl);
 298   }
 299   void decode(bufferlist::iterator& p) {
 300     uint32_t n;
 301     ::decode(n, p);
 302     if (n > 0) {
 303       alloc_internal();
 304       ::decode_nohead(n, *map, p);
 305     } else
 306       free_internal();
 307   }
 308 };
 309
 310 template<class Key, class T, class Map>
 311 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl) {
 312   m.encode(bl);
 313 }
 314 template<class Key, class T, class Map>
 315 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl,
 316                    uint64_t features) {
 317   m.encode(bl, features);
 318 }
 319 template<class Key, class T, class Map>
 320 inline void decode(compact_map_base<Key, T, Map>& m, bufferlist::iterator& p) {
 321   m.decode(p);
 322 }
 323
 324 template <class Key, class T>
 325 class compact_map : public compact_map_base<Key, T, std::map<Key,T> > {
 326 public:
 327   T& operator[](const Key& k) {
 328     this->alloc_internal();
 329     return (*(this->map))[k];
 330   }
 331 };
 332
 333 template <class Key, class T>
 334 inline std::ostream& operator<<(std::ostream& out, const compact_map<Key, T>& m)
 335 {
 336   out << "{";
 337   for (typename compact_map<Key, T>::const_iterator it = m.begin();
 338        it != m.end();
 339        ++it) {
 340     if (it != m.begin())
 341       out << ",";
 342     out << it->first << "=" << it->second;
 343   }
 344   out << "}";
 345   return out;
 346 }
 347
 348 template <class Key, class T>
 349 class compact_multimap : public compact_map_base<Key, T, std::multimap<Key,T> > {
 350 };
 351
 352 template <class Key, class T>
 353 inline std::ostream& operator<<(std::ostream& out, const compact_multimap<Key, T>& m)
 354 {
 355   out << "{{";
 356   for (typename compact_map<Key, T>::const_iterator it = m.begin(); !it.end(); ++it) {
 357     if (it != m.begin())
 358       out << ",";
 359     out << it->first << "=" << it->second;
 360   }
 361   out << "}}";
 362   return out;
 363 }
 364 #endif