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