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 #pragma once
  18
  19 #include <cstdlib>
  20 #include <cstdint>
  21
  22 #include "hphp/util/assertions.h"
  23
  24 namespace HPHP { namespace jit {
  25 ////////////////////////////////////////////////////////////////////////////////
  26
  27 /*
  28  * A vector of elements that will increase its capacity when it fills up.  It
  29  * differs from std::vector in that it only takes up 8 bytes of space, its
  30  * elements must be trivially destructible, and it cannot erase individual
  31  * elements.
  32  */
  33 template<typename T>
  34 struct GrowableVector {
  35   explicit GrowableVector() {}
  36
  37   GrowableVector(GrowableVector&& other) noexcept : m_vec(other.m_vec) {
  38     other.m_vec = nullptr;
  39   }
  40
  41   GrowableVector& operator=(GrowableVector&& other) {
  42     m_vec = other.m_vec;
  43     other.m_vec = nullptr;
  44     return *this;
  45   }
  46
  47   GrowableVector(const GrowableVector&) = delete;
  48   GrowableVector& operator=(const GrowableVector&) = delete;
  49
  50   //////////////////////////////////////////////////////////////////////////////
  51
  52   bool empty() const {
  53     return !m_vec;
  54   }
  55
  56   size_t size() const {
  57     return m_vec ? m_vec->m_size : 0;
  58   }
  59
  60   void clear() {
  61     free(m_vec);
  62     m_vec = nullptr;
  63   }
  64
  65   T& operator[](const size_t idx) {
  66     assertx(idx < size());
  67     return m_vec->m_data[idx];
  68   }
  69
  70   const T& operator[](const size_t idx) const {
  71     assertx(idx < size());
  72     return m_vec->m_data[idx];
  73   }
  74
  75   void push_back(const T& datum) {
  76     if (!m_vec) {
  77       m_vec = Impl::make();
  78     }
  79     m_vec = m_vec->push_back(datum);
  80   }
  81
  82   void swap(GrowableVector<T>& other) {
  83     std::swap(m_vec, other.m_vec);
  84   }
  85
  86   T* begin() const {
  87     return m_vec ? m_vec->m_data : (T*)this;
  88   }
  89
  90   T* end() const {
  91     return m_vec ? &m_vec->m_data[m_vec->m_size] : (T*)this;
  92   }
  93
  94   void setEnd(T* newEnd) {
  95     if (newEnd == begin()) {
  96       free(m_vec);
  97       m_vec = nullptr;
  98       return;
  99     }
 100     m_vec->m_size = newEnd - m_vec->m_data;
 101   }
 102
 103 private:
 104   struct Impl {
 105     static Impl* make() {
 106       static_assert(
 107         std::is_trivially_destructible<T>::value,
 108         "GrowableVector can only hold trivially destructible types"
 109       );
 110       auto const mem = malloc(sizeof(Impl));
 111       return new (mem) Impl();
 112     }
 113
 114     Impl* push_back(const T& datum) {
 115       // m_data always has room for at least one element due to the m_data[1]
 116       // declaration, so the realloc() code first has to kick in when a second
 117       // element is about to be pushed.
 118       auto gv = [&] {
 119         if (!folly::isPowTwo(m_size)) return this;
 120         return (Impl*)realloc(
 121           this,
 122           offsetof(Impl, m_data) + 2 * m_size * sizeof(T)
 123         );
 124       }();
 125
 126       gv->m_data[gv->m_size++] = datum;
 127       return gv;
 128     }
 129
 130     ////////////////////////////////////////////////////////////////////////////
 131
 132     uint32_t m_size{0};
 133     /* Actually variable length. */
 134     T m_data[1];
 135   };
 136
 137   //////////////////////////////////////////////////////////////////////////////
 138
 139   Impl* m_vec{nullptr};
 140 };
 141
 142 ////////////////////////////////////////////////////////////////////////////////
 143 }}
 144