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 "buffer.h"
  16 #include "encoding.h"
  17
  18 #include <map>
  19 #include <memory>
  20
  21 #include "include/encoding.h"
  22
  23 template <class Key, class T, class Map>
  24 class compact_map_base {
  25 protected:
  26   std::unique_ptr<Map> map;
  27   void alloc_internal() {
  28     if (!map)
  29       map.reset(new Map);
  30   }
  31   void free_internal() {
  32     map.reset();
  33   }
  34   template <class It>
  35   class const_iterator_base {
  36     const compact_map_base *map;
  37     It it;
  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;
  43   public:
  44     const_iterator_base(const const_iterator_base& o) {
  45       map = o.map;
  46       it = o.it;
  47     }
  48     bool operator==(const const_iterator_base& o) const {
  49       return (map == o.map) && (!map->map || it == o.it);
  50     }
  51     bool operator!=(const const_iterator_base& o) const {
  52       return !(*this == o);;
  53     }
  54     const_iterator_base& operator=(const const_iterator_base& o) {
  55       map = o.map;
  56       it = o.it;
  57       return *this;
  58     }
  59     const_iterator_base& operator++() {
  60       ++it;
  61       return *this;
  62     }
  63     const_iterator_base& operator--() {
  64       --it;
  65       return *this;
  66     }
  67     const std::pair<const Key,T>& operator*() {
  68       return *it;
  69     }
  70     const std::pair<const Key,T>* operator->() {
  71       return it.operator->();
  72     }
  73   };
  74   template <class It>
  75   class iterator_base {
  76   private:
  77     const compact_map_base* map;
  78     It it;
  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;
  83   public:
  84     iterator_base(const iterator_base& o) {
  85       map = o.map;
  86       it = o.it;
  87     }
  88     bool operator==(const iterator_base& o) const {
  89       return (map == o.map) && (!map->map || it == o.it);
  90     }
  91     bool operator!=(const iterator_base& o) const {
  92       return !(*this == o);;
  93     }
  94     iterator_base& operator=(const iterator_base& o) {
  95       map = o.map;
  96       it = o.it;
  97       return *this;
  98     }
  99     iterator_base& operator++() {
 100       ++it;
 101       return *this;
 102     }
 103     iterator_base operator++(int) {
 104       iterator_base tmp = *this;
 105       ++it;
 106       return tmp;
 107     }
 108     iterator_base& operator--() {
 109       --it;
 110       return *this;
 111     }
 112     std::pair<const Key,T>& operator*() {
 113       return *it;
 114     }
 115     std::pair<const Key,T>* operator->() {
 116       return it.operator->();
 117     }
 118     operator const_iterator_base<It>() const {
 119       return const_iterator_base<It>(map, it);
 120     }
 121   };
 122
 123 public:
 124   class iterator : public iterator_base<typename Map::iterator> {
 125     public:
 126       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) { }
 132   };
 133   class const_iterator : public const_iterator_base<typename Map::const_iterator> {
 134     public:
 135       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) { }
 141   };
 142   class reverse_iterator : public iterator_base<typename Map::reverse_iterator> {
 143     public:
 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) { }
 150   };
 151   class const_reverse_iterator : public const_iterator_base<typename Map::const_reverse_iterator> {
 152     public:
 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) { }
 159   };
 160   compact_map_base(const compact_map_base& o) {
 161     if (o.map) {
 162       alloc_internal();
 163       *map = *o.map;
 164     }
 165   }
 166   compact_map_base() {}
 167   ~compact_map_base() {}
 168
 169   bool empty() const {
 170     return !map || map->empty();
 171   }
 172   size_t size() const {
 173     return map ? map->size() : 0;
 174   }
 175   bool operator==(const compact_map_base& o) const {
 176     return (empty() && o.empty()) || (map && o.map && *map == *o.map);
 177   }
 178   bool operator!=(const compact_map_base& o) const {
 179     return !(*this == o);
 180   }
 181   size_t count (const Key& k) const {
 182     return map ? map->count(k) : 0;
 183   }
 184   iterator erase (iterator p) {
 185     if (map) {
 186       ceph_assert(this == p.map);
 187       auto it = map->erase(p.it);
 188       if (map->empty()) {
 189         free_internal();
 190         return iterator(this);
 191       } else {
 192         return iterator(this, it);
 193       }
 194     } else {
 195       return iterator(this);
 196     }
 197   }
 198   size_t erase (const Key& k) {
 199     if (!map)
 200       return 0;
 201     size_t r = map->erase(k);
 202     if (map->empty())
 203         free_internal();
 204     return r;
 205   }
 206   void clear() {
 207     free_internal();
 208   }
 209   void swap(compact_map_base& o) {
 210     map.swap(o.map);
 211   }
 212   compact_map_base& operator=(const compact_map_base& o) {
 213     if (o.map) {
 214       alloc_internal();
 215       *map = *o.map;
 216     } else
 217       free_internal();
 218     return *this;
 219   }
 220   iterator insert(const std::pair<const Key, T>& val) {
 221     alloc_internal();
 222     return iterator(this, map->insert(val));
 223   }
 224   template <class... Args>
 225   std::pair<iterator,bool> emplace ( Args&&... args ) {
 226     alloc_internal();
 227     auto em = map->emplace(std::forward<Args>(args)...);
 228     return std::pair<iterator,bool>(iterator(this, em.first), em.second);
 229   }
 230   iterator begin() {
 231    if (!map)
 232      return iterator(this);
 233    return iterator(this, map->begin());
 234   }
 235   iterator end() {
 236    if (!map)
 237      return iterator(this);
 238    return iterator(this, map->end());
 239   }
 240   reverse_iterator rbegin() {
 241    if (!map)
 242      return reverse_iterator(this);
 243    return reverse_iterator(this, map->rbegin());
 244   }
 245   reverse_iterator rend() {
 246    if (!map)
 247      return reverse_iterator(this);
 248    return reverse_iterator(this, map->rend());
 249   }
 250   iterator find(const Key& k) {
 251     if (!map)
 252       return iterator(this);
 253     return iterator(this, map->find(k));
 254   }
 255   iterator lower_bound(const Key& k) {
 256     if (!map)
 257       return iterator(this);
 258     return iterator(this, map->lower_bound(k));
 259   }
 260   iterator upper_bound(const Key& k) {
 261     if (!map)
 262       return iterator(this);
 263     return iterator(this, map->upper_bound(k));
 264   }
 265   const_iterator begin() const {
 266    if (!map)
 267      return const_iterator(this);
 268    return const_iterator(this, map->begin());
 269   }
 270   const_iterator end() const {
 271    if (!map)
 272      return const_iterator(this);
 273    return const_iterator(this, map->end());
 274   }
 275   const_reverse_iterator rbegin() const {
 276    if (!map)
 277      return const_reverse_iterator(this);
 278    return const_reverse_iterator(this, map->rbegin());
 279   }
 280   const_reverse_iterator rend() const {
 281    if (!map)
 282      return const_reverse_iterator(this);
 283    return const_reverse_iterator(this, map->rend());
 284   }
 285   const_iterator find(const Key& k) const {
 286     if (!map)
 287       return const_iterator(this);
 288     return const_iterator(this, map->find(k));
 289   }
 290   const_iterator lower_bound(const Key& k) const {
 291     if (!map)
 292       return const_iterator(this);
 293     return const_iterator(this, map->lower_bound(k));
 294   }
 295   const_iterator upper_bound(const Key& k) const {
 296     if (!map)
 297       return const_iterator(this);
 298     return const_iterator(this, map->upper_bound(k));
 299   }
 300   void encode(bufferlist &bl) const {
 301     using ceph::encode;
 302     if (map)
 303       encode(*map, bl);
 304     else
 305       encode((uint32_t)0, bl);
 306   }
 307   void encode(bufferlist &bl, uint64_t features) const {
 308     using ceph::encode;
 309     if (map)
 310       encode(*map, bl, features);
 311     else
 312       encode((uint32_t)0, bl);
 313   }
 314   void decode(bufferlist::const_iterator& p) {
 315     using ceph::decode;
 316     using ceph::decode_nohead;
 317     uint32_t n;
 318     decode(n, p);
 319     if (n > 0) {
 320       alloc_internal();
 321       decode_nohead(n, *map, p);
 322     } else
 323       free_internal();
 324   }
 325 };
 326
 327 template<class Key, class T, class Map>
 328 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl) {
 329   m.encode(bl);
 330 }
 331 template<class Key, class T, class Map>
 332 inline void encode(const compact_map_base<Key, T, Map>& m, bufferlist& bl,
 333                    uint64_t features) {
 334   m.encode(bl, features);
 335 }
 336 template<class Key, class T, class Map>
 337 inline void decode(compact_map_base<Key, T, Map>& m, bufferlist::const_iterator& p) {
 338   m.decode(p);
 339 }
 340
 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> > {
 343 public:
 344   T& operator[](const Key& k) {
 345     this->alloc_internal();
 346     return (*(this->map))[k];
 347   }
 348 };
 349
 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)
 352 {
 353   out << "{";
 354   bool first = true;
 355   for (const auto &p : m) {
 356     if (!first)
 357       out << ",";
 358     out << p.first << "=" << p.second;
 359     first = false;
 360   }
 361   out << "}";
 362   return out;
 363 }
 364
 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> > {
 367 };
 368
 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)
 371 {
 372   out << "{{";
 373   bool first = true;
 374   for (const auto &p : m) {
 375     if (!first)
 376       out << ",";
 377     out << p.first << "=" << p.second;
 378     first = false;
 379   }
 380   out << "}}";
 381   return out;
 382 }
 383 #endif