ceph/src/include/compact_set.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_SET_H
  13 #define CEPH_COMPACT_SET_H
  14
  15 #include <stdlib.h>
  16
  17 #include "include/buffer.h"
  18 #include "include/encoding.h"
  19
  20
  21 template <class T, class Set>
  22 class compact_set_base {
  23 protected:
  24   Set *set;
  25   void alloc_internal() {
  26     if (!set)
  27       set = new Set;
  28   }
  29   void free_internal() {
  30     if (set) {
  31       delete set;
  32       set = 0;
  33     }
  34   }
  35   template <class It>
  36   class iterator_base {
  37   private:
  38     const compact_set_base* set;
  39     It it;
  40     iterator_base() : set(0) { }
  41     iterator_base(const compact_set_base* s) : set(s) { }
  42     iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
  43     friend class compact_set_base;
  44   public:
  45     iterator_base(const iterator_base& o) {
  46       set = o.set;
  47       it = o.it;
  48     }
  49     bool operator==(const iterator_base& o) const {
  50       return (set == o.set) && (!set->set || it == o.it);
  51     }
  52     bool operator!=(const iterator_base& o) const {
  53       return !(*this == o);;
  54     }
  55     iterator_base& operator=(const iterator_base& o) {
  56       set->set = o.set;
  57       it = o.it;
  58       return *this;
  59     }
  60     iterator_base& operator++() {
  61       ++it;
  62       return *this;
  63     }
  64     iterator_base operator++(int) {
  65       iterator_base tmp = *this;
  66       ++it;
  67       return tmp;
  68     }
  69     iterator_base& operator--() {
  70       --it;
  71       return *this;
  72     }
  73     const T& operator*() {
  74       return *it;
  75     }
  76   };
  77 public:
  78   class const_iterator : public iterator_base<typename Set::const_iterator> {
  79     public:
  80       const_iterator() { }
  81       const_iterator(const iterator_base<typename Set::const_iterator>& o)
  82         : iterator_base<typename Set::const_iterator>(o) { }
  83       const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
  84       const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
  85         : iterator_base<typename Set::const_iterator>(s, i) { }
  86   };
  87   class iterator : public iterator_base<typename Set::iterator> {
  88     public:
  89       iterator() { }
  90       iterator(const iterator_base<typename Set::iterator>& o)
  91         : iterator_base<typename Set::iterator>(o) { }
  92       iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
  93       iterator(compact_set_base* s, const typename Set::iterator& i)
  94         : iterator_base<typename Set::iterator>(s, i) { }
  95       operator const_iterator() const {
  96         return const_iterator(this->set, this->it);
  97       }
  98   };
  99   class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
 100     public:
 101       const_reverse_iterator() { }
 102       const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
 103         : iterator_base<typename Set::const_reverse_iterator>(o) { }
 104       const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
 105       const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
 106         : iterator_base<typename Set::const_reverse_iterator>(s, i) { }
 107   };
 108   class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
 109     public:
 110       reverse_iterator() { }
 111       reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
 112         : iterator_base<typename Set::reverse_iterator>(o) { }
 113       reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
 114       reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
 115         : iterator_base<typename Set::reverse_iterator>(s, i) { }
 116       operator const_iterator() const {
 117         return const_iterator(this->set, this->it);
 118       }
 119   };
 120
 121   compact_set_base() : set(0) {}
 122   compact_set_base(const compact_set_base& o) : set(0) {
 123     if (o.set) {
 124       alloc_internal();
 125       *set = *o.set;
 126     }
 127   }
 128   ~compact_set_base() { delete set; }
 129
 130
 131   bool empty() const {
 132     return !set || set->empty();
 133   }
 134   size_t size() const {
 135     return set ? set->size() : 0;
 136   }
 137   bool operator==(const compact_set_base& o) const {
 138     return (empty() && o.empty()) || (set && o.set && *set == *o.set);
 139   }
 140   bool operator!=(const compact_set_base& o) const {
 141     return !(*this == o);
 142   }
 143   size_t count(const T& t) const {
 144     return set ? set->count(t) : 0;
 145   }
 146   void erase (iterator p) {
 147     if (set) {
 148       assert(this == p.set);
 149       set->erase(p.it);
 150       if (set->empty())
 151         free_internal();
 152     }
 153   }
 154   size_t erase (const T& t) {
 155     if (!set)
 156       return 0;
 157     size_t r = set->erase(t);
 158     if (set->empty())
 159         free_internal();
 160     return r;
 161   }
 162   void clear() {
 163     free_internal();
 164   }
 165   void swap(compact_set_base& o) {
 166     Set *tmp = set;
 167     set = o.set;
 168     o.set = tmp;
 169   }
 170   compact_set_base& operator=(const compact_set_base& o) {
 171     if (o.set) {
 172       alloc_internal();
 173       *set = *o.set;
 174     } else
 175       free_internal();
 176     return *this;
 177   }
 178   std::pair<iterator,bool> insert(const T& t) {
 179     alloc_internal();
 180     std::pair<typename Set::iterator,bool> r = set->insert(t);
 181     return std::make_pair(iterator(this, r.first), r.second);
 182   }
 183   iterator begin() {
 184    if (!set)
 185      return iterator(this);
 186    return iterator(this, set->begin());
 187   }
 188   iterator end() {
 189    if (!set)
 190      return iterator(this);
 191    return iterator(this, set->end());
 192   }
 193   reverse_iterator rbegin() {
 194    if (!set)
 195      return reverse_iterator(this);
 196    return reverse_iterator(this, set->rbegin());
 197   }
 198   reverse_iterator rend() {
 199    if (!set)
 200      return reverse_iterator(this);
 201    return reverse_iterator(this, set->rend());
 202   }
 203   iterator find(const T& t) {
 204     if (!set)
 205       return iterator(this);
 206     return iterator(this, set->find(t));
 207   }
 208   iterator lower_bound(const T& t) {
 209     if (!set)
 210       return iterator(this);
 211     return iterator(this, set->lower_bound(t));
 212   }
 213   iterator upper_bound(const T& t) {
 214     if (!set)
 215       return iterator(this);
 216     return iterator(this, set->upper_bound(t));
 217   }
 218   const_iterator begin() const {
 219    if (!set)
 220      return const_iterator(this);
 221    return const_iterator(this, set->begin());
 222   }
 223   const_iterator end() const {
 224    if (!set)
 225      return const_iterator(this);
 226    return const_iterator(this, set->end());
 227   }
 228   const_reverse_iterator rbegin() const {
 229    if (!set)
 230      return const_reverse_iterator(this);
 231    return const_reverse_iterator(this, set->rbegin());
 232   }
 233   const_reverse_iterator rend() const {
 234    if (!set)
 235      return const_reverse_iterator(this);
 236    return const_reverse_iterator(this, set->rend());
 237   }
 238   const_iterator find(const T& t) const {
 239     if (!set)
 240       return const_iterator(this);
 241     return const_iterator(this, set->find(t));
 242   }
 243   const_iterator lower_bound(const T& t) const {
 244     if (!set)
 245       return const_iterator(this);
 246     return const_iterator(this, set->lower_bound(t));
 247   }
 248   const_iterator upper_bound(const T& t) const {
 249     if (!set)
 250       return const_iterator(this);
 251     return const_iterator(this, set->upper_bound(t));
 252   }
 253   void encode(bufferlist &bl) const {
 254     if (set)
 255       ::encode(*set, bl);
 256     else
 257       ::encode((uint32_t)0, bl);
 258   }
 259   void decode(bufferlist::iterator& p) {
 260     uint32_t n;
 261     ::decode(n, p);
 262     if (n > 0) {
 263       alloc_internal();
 264       ::decode_nohead(n, *set, p);
 265     } else
 266       free_internal();
 267   }
 268 };
 269
 270 template<class T, class Set>
 271 inline void encode(const compact_set_base<T, Set>& m, bufferlist& bl) {
 272   m.encode(bl);
 273 }
 274 template<class T, class Set>
 275 inline void decode(compact_set_base<T, Set>& m, bufferlist::iterator& p) {
 276   m.decode(p);
 277 }
 278
 279 template <class T>
 280 class compact_set : public compact_set_base<T, std::set<T> > {
 281 };
 282
 283 template <class T>
 284 inline std::ostream& operator<<(std::ostream& out, const compact_set<T>& s)
 285 {
 286   for (typename compact_set<T>::const_iterator it = s.begin();
 287        it != s.end(); ++it) {
 288     if (it != s.begin())
 289       out << ",";
 290     out << it->first << "=" << it->second;
 291   }
 292   return out;
 293 }
 294 #endif