silo/static_vector.h

   1 #ifndef _STATIC_VECTOR_H_
   2 #define _STATIC_VECTOR_H_
   3
   4 #include <algorithm>
   5 #include <type_traits>
   6 #include "macros.h"
   7 #include "ndb_type_traits.h"
   8
   9 template <typename T, size_t StaticSize = SMALL_SIZE_VEC>
  10 class static_vector {
  11
  12   static const bool is_trivially_destructible =
  13     private_::is_trivially_destructible<T>::value;
  14
  15   // std::is_trivially_copyable not supported in g++-4.7
  16   static const bool is_trivially_copyable = std::is_scalar<T>::value;
  17
  18 public:
  19
  20   typedef T value_type;
  21   typedef T & reference;
  22   typedef const T & const_reference;
  23   typedef size_t size_type;
  24
  25   inline static_vector() : n(0) {}
  26   inline ~static_vector() { clear(); }
  27
  28   inline static_vector(const static_vector &that)
  29     : n(0)
  30   {
  31     assignFrom(that);
  32   }
  33
  34   // not efficient, don't use in performance critical parts
  35   static_vector(std::initializer_list<T> l)
  36     : n(0)
  37   {
  38     for (auto &p : l)
  39       push_back(p);
  40   }
  41
  42   static_vector &
  43   operator=(const static_vector &that)
  44   {
  45     assignFrom(that);
  46     return *this;
  47   }
  48
  49   inline size_t
  50   size() const
  51   {
  52     return n;
  53   }
  54
  55   inline bool
  56   empty() const
  57   {
  58     return !n;
  59   }
  60
  61   inline reference
  62   front()
  63   {
  64     INVARIANT(n > 0);
  65     INVARIANT(n <= StaticSize);
  66     return *ptr();
  67   }
  68
  69   inline const_reference
  70   front() const
  71   {
  72     return const_cast<static_vector *>(this)->front();
  73   }
  74
  75   inline reference
  76   back()
  77   {
  78     INVARIANT(n > 0);
  79     INVARIANT(n <= StaticSize);
  80     return ptr()[n - 1];
  81   }
  82
  83   inline const_reference
  84   back() const
  85   {
  86     return const_cast<static_vector *>(this)->back();
  87   }
  88
  89   inline void
  90   pop_back()
  91   {
  92     INVARIANT(n > 0);
  93     if (!is_trivially_destructible)
  94       ptr()[n - 1].~T();
  95     n--;
  96   }
  97
  98   inline void
  99   push_back(const T &obj)
 100   {
 101     emplace_back(obj);
 102   }
 103
 104   inline void
 105   push_back(T &&obj)
 106   {
 107     emplace_back(std::move(obj));
 108   }
 109
 110   // C++11 goodness- a strange syntax this is
 111
 112   template <class... Args>
 113   inline void
 114   emplace_back(Args &&... args)
 115   {
 116     INVARIANT(n < StaticSize);
 117     new (&(ptr()[n++])) T(std::forward<Args>(args)...);
 118   }
 119
 120   inline reference
 121   operator[](int i)
 122   {
 123     return ptr()[i];
 124   }
 125
 126   inline const_reference
 127   operator[](int i) const
 128   {
 129     return const_cast<static_vector *>(this)->operator[](i);
 130   }
 131
 132   void
 133   clear()
 134   {
 135     if (!is_trivially_destructible)
 136       for (size_t i = 0; i < n; i++)
 137         ptr()[i].~T();
 138     n = 0;
 139   }
 140
 141   inline void
 142   reserve(size_t n)
 143   {
 144   }
 145
 146   inline void
 147   resize(size_t n, value_type val = value_type())
 148   {
 149     INVARIANT(n <= StaticSize);
 150     if (n > this->n) {
 151       // expand
 152       while (this->n < n)
 153         new (&ptr()[this->n++]) T(val);
 154     } else if (n < this->n) {
 155       // shrink
 156       while (this->n > n) {
 157         if (!is_trivially_destructible)
 158           ptr()[this->n - 1].~T();
 159         this->n--;
 160       }
 161     }
 162   }
 163
 164   // non-standard API
 165   inline bool is_small_type() const { return true; }
 166
 167   template <typename Compare = std::less<T>>
 168   inline void
 169   sort(Compare c = Compare())
 170   {
 171     std::sort(begin(), end(), c);
 172   }
 173
 174 private:
 175
 176   template <typename ObjType>
 177   class iterator_ : public std::iterator<std::bidirectional_iterator_tag, ObjType> {
 178     friend class static_vector;
 179   public:
 180     inline iterator_() : p(0) {}
 181
 182     template <typename O>
 183     inline iterator_(const iterator_<O> &other)
 184       : p(other.p)
 185     {}
 186
 187     inline ObjType &
 188     operator*() const
 189     {
 190       return *p;
 191     }
 192
 193     inline ObjType *
 194     operator->() const
 195     {
 196       return p;
 197     }
 198
 199     inline bool
 200     operator==(const iterator_ &o) const
 201     {
 202       return p == o.p;
 203     }
 204
 205     inline bool
 206     operator!=(const iterator_ &o) const
 207     {
 208       return !operator==(o);
 209     }
 210
 211     inline bool
 212     operator<(const iterator_ &o) const
 213     {
 214       return p < o.p;
 215     }
 216
 217     inline bool
 218     operator>=(const iterator_ &o) const
 219     {
 220       return !operator<(o);
 221     }
 222
 223     inline bool
 224     operator>(const iterator_ &o) const
 225     {
 226       return p > o.p;
 227     }
 228
 229     inline bool
 230     operator<=(const iterator_ &o) const
 231     {
 232       return !operator>(o);
 233     }
 234
 235     inline iterator_ &
 236     operator+=(int n)
 237     {
 238       p += n;
 239       return *this;
 240     }
 241
 242     inline iterator_ &
 243     operator-=(int n)
 244     {
 245       p -= n;
 246       return *this;
 247     }
 248
 249     inline iterator_
 250     operator+(int n) const
 251     {
 252       iterator_ cpy = *this;
 253       return cpy += n;
 254     }
 255
 256     inline iterator_
 257     operator-(int n) const
 258     {
 259       iterator_ cpy = *this;
 260       return cpy -= n;
 261     }
 262
 263     inline intptr_t
 264     operator-(const iterator_ &o) const
 265     {
 266       return p - o.p;
 267     }
 268
 269     inline iterator_ &
 270     operator++()
 271     {
 272       ++p;
 273       return *this;
 274     }
 275
 276     inline iterator_
 277     operator++(int)
 278     {
 279       iterator_ cur = *this;
 280       ++(*this);
 281       return cur;
 282     }
 283
 284     inline iterator_ &
 285     operator--()
 286     {
 287       --p;
 288       return *this;
 289     }
 290
 291     inline iterator_
 292     operator--(int)
 293     {
 294       iterator_ cur = *this;
 295       --(*this);
 296       return cur;
 297     }
 298
 299   protected:
 300     inline iterator_(ObjType *p) : p(p) {}
 301
 302   private:
 303     ObjType *p;
 304   };
 305
 306 public:
 307
 308   typedef iterator_<T> iterator;
 309   typedef iterator_<const T> const_iterator;
 310
 311   typedef std::reverse_iterator<iterator> reverse_iterator;
 312   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 313
 314   inline iterator
 315   begin()
 316   {
 317     return iterator(ptr());
 318   }
 319
 320   inline const_iterator
 321   begin() const
 322   {
 323     return const_iterator(ptr());
 324   }
 325
 326   inline iterator
 327   end()
 328   {
 329     return iterator(endptr());
 330   }
 331
 332   inline const_iterator
 333   end() const
 334   {
 335     return const_iterator(endptr());
 336   }
 337
 338   inline reverse_iterator
 339   rbegin()
 340   {
 341     return reverse_iterator(end());
 342   }
 343
 344   inline const_reverse_iterator
 345   rbegin() const
 346   {
 347     return const_reverse_iterator(end());
 348   }
 349
 350   inline reverse_iterator
 351   rend()
 352   {
 353     return reverse_iterator(begin());
 354   }
 355
 356   inline const_reverse_iterator
 357   rend() const
 358   {
 359     return const_reverse_iterator(begin());
 360   }
 361
 362 private:
 363   void
 364   assignFrom(const static_vector &that)
 365   {
 366     if (unlikely(this == &that))
 367       return;
 368     clear();
 369     INVARIANT(that.n <= StaticSize);
 370     if (is_trivially_copyable) {
 371       NDB_MEMCPY(ptr(), that.ptr(), that.n * sizeof(T));
 372     } else {
 373       for (size_t i = 0; i < that.n; i++)
 374         new (&(ptr()[i])) T(that.ptr()[i]);
 375     }
 376     n = that.n;
 377   }
 378
 379   inline ALWAYS_INLINE T *
 380   ptr()
 381   {
 382     return reinterpret_cast<T *>(&elems_buf[0]);
 383   }
 384
 385   inline ALWAYS_INLINE const T *
 386   ptr() const
 387   {
 388     return reinterpret_cast<const T *>(&elems_buf[0]);
 389   }
 390
 391   inline ALWAYS_INLINE T *
 392   endptr()
 393   {
 394     return ptr() + n;
 395   }
 396
 397   inline ALWAYS_INLINE const T *
 398   endptr() const
 399   {
 400     return ptr() + n;
 401   }
 402
 403   size_t n;
 404   char elems_buf[sizeof(T) * StaticSize];
 405 };
 406
 407 #endif /* _STATIC_VECTOR_H_ */