hphp/util/growable-vector.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_GROWABLE_VECTOR_H_
  18 #define incl_HPHP_GROWABLE_VECTOR_H_
  19
  20 #include <cstdlib>
  21 #include <cstdint>
  22
  23 #include "hphp/util/assertions.h"
  24
  25 namespace HPHP { namespace jit {
  26 ////////////////////////////////////////////////////////////////////////////////
  27
  28 /*
  29  * A vector of elements that will increase its capacity when it fills up.  It
  30  * differs from std::vector in that it only takes up 8 bytes of space, its
  31  * elements must be trivially destructible, and it cannot erase individual
  32  * elements.
  33  */
  34 template<typename T>
  35 struct GrowableVector {
  36   explicit GrowableVector() {}
  37
  38   GrowableVector(GrowableVector&& other) noexcept : m_vec(other.m_vec) {
  39     other.m_vec = nullptr;
  40   }
  41
  42   GrowableVector& operator=(GrowableVector&& other) {
  43     m_vec = other.m_vec;
  44     other.m_vec = nullptr;
  45     return *this;
  46   }
  47
  48   GrowableVector(const GrowableVector&) = delete;
  49   GrowableVector& operator=(const GrowableVector&) = delete;
  50
  51   //////////////////////////////////////////////////////////////////////////////
  52
  53   bool empty() const {
  54     return !m_vec;
  55   }
  56
  57   size_t size() const {
  58     return m_vec ? m_vec->m_size : 0;
  59   }
  60
  61   void clear() {
  62     free(m_vec);
  63     m_vec = nullptr;
  64   }
  65
  66   T& operator[](const size_t idx) {
  67     assertx(idx < size());
  68     return m_vec->m_data[idx];
  69   }
  70
  71   const T& operator[](const size_t idx) const {
  72     assertx(idx < size());
  73     return m_vec->m_data[idx];
  74   }
  75
  76   void push_back(const T& datum) {
  77     if (!m_vec) {
  78       m_vec = Impl::make();
  79     }
  80     m_vec = m_vec->push_back(datum);
  81   }
  82
  83   void swap(GrowableVector<T>& other) {
  84     std::swap(m_vec, other.m_vec);
  85   }
  86
  87   T* begin() const {
  88     return m_vec ? m_vec->m_data : (T*)this;
  89   }
  90
  91   T* end() const {
  92     return m_vec ? &m_vec->m_data[m_vec->m_size] : (T*)this;
  93   }
  94
  95   void setEnd(T* newEnd) {
  96     if (newEnd == begin()) {
  97       free(m_vec);
  98       m_vec = nullptr;
  99       return;
 100     }
 101     m_vec->m_size = newEnd - m_vec->m_data;
 102   }
 103
 104 private:
 105   struct Impl {
 106     static Impl* make() {
 107       static_assert(
 108         std::is_trivially_destructible<T>::value,
 109         "GrowableVector can only hold trivially destructible types"
 110       );
 111       auto const mem = malloc(sizeof(Impl));
 112       return new (mem) Impl();
 113     }
 114
 115     Impl* push_back(const T& datum) {
 116       // m_data always has room for at least one element due to the m_data[1]
 117       // declaration, so the realloc() code first has to kick in when a second
 118       // element is about to be pushed.
 119       auto gv = [&] {
 120         if (!folly::isPowTwo(m_size)) return this;
 121         return (Impl*)realloc(
 122           this,
 123           offsetof(Impl, m_data) + 2 * m_size * sizeof(T)
 124         );
 125       }();
 126
 127       gv->m_data[gv->m_size++] = datum;
 128       return gv;
 129     }
 130
 131     ////////////////////////////////////////////////////////////////////////////
 132
 133     uint32_t m_size{0};
 134     /* Actually variable length. */
 135     T m_data[1];
 136   };
 137
 138   //////////////////////////////////////////////////////////////////////////////
 139
 140   Impl* m_vec{nullptr};
 141 };
 142
 143 ////////////////////////////////////////////////////////////////////////////////
 144 }}
 145
 146 #endif