hphp/util/pointer-list.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_POINTERLIST_H_
  18 #define incl_HPHP_POINTERLIST_H_
  19
  20 #include <stdlib.h>
  21 #include <cstring>
  22
  23 #include "hphp/util/assertions.h"
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27
  28 #define INITIAL_CAPACITY  4
  29
  30 struct PointerListData;
  31
  32 /**
  33  * During its lifetime, an instance of PointerList can transition
  34  * between 3 states:
  35  *   State 0: m_val == 0
  36  *     This is the initial state for a newly constructed PointerList.
  37  *     There are no elements and no malloced block of memory.
  38  *   State 1: (m_val & 1) != 0
  39  *     In this state there is exactly one element which resides directly
  40  *     in m_val. The element is retrieved by returning a copy of m_val
  41  *     with the low bit cleared.
  42  *   State 2: m_val != 0 && (m_val & 1) == 0
  43  *     In this state, m_data points to a malloced block of memory. The
  44  *     number of elements, the capacity of the block, and the values of
  45  *     all the elements reside in the malloced block of memory.
  46  */
  47 template <typename T>
  48 struct PointerList {
  49   union {
  50     PointerListData* m_data;
  51     uintptr_t m_val; // m_val is provided for convenience so that we don't
  52                      // have to repeatedly cast m_data to a uintptr_t
  53   };
  54   PointerList();
  55   ~PointerList();
  56   T* get(int index) const;
  57   void set(int index, T* val);
  58   bool empty() const;
  59   int size() const;
  60   int capacity();
  61   void clear();
  62   void grow();
  63   void push(T* val);
  64   void pop();
  65
  66 private:
  67   PointerList(const PointerList&);
  68   PointerList& operator=(const PointerList&);
  69 };
  70
  71 struct PointerListData {
  72   int m_len;
  73   int m_capacity;
  74 };
  75
  76 template <typename T>
  77 PointerList<T>::PointerList() {
  78   m_val = 0;
  79 }
  80
  81 template <typename T>
  82 PointerList<T>::~PointerList() {
  83   clear();
  84 }
  85
  86 template <typename T>
  87 T* PointerList<T>::get(int index) const {
  88   if (m_val & uintptr_t(1U)) {
  89     // If the low bit is set, that means that this PointerList
  90     // contains exactly one pointer which is stored in m_val
  91     assert(index == 0);
  92     // Clear the low bit before returning the value
  93     return (T*)(m_val & ~(uintptr_t(1U)));
  94   }
  95   // Index into the malloced block of memory
  96   assert(m_data);
  97   assert(index >= 0 && index < m_data->m_len);
  98   return *((T**)(m_data+1) + index);
  99 }
 100
 101 template <typename T>
 102 void PointerList<T>::set(int index, T* val) {
 103   if (m_val & uintptr_t(1U)) {
 104     // If the low bit is set, that means that this PointerList
 105     // contains exactly one pointer which is stored in m_val.
 106     assert(index == 0);
 107     if (!(uintptr_t(val) & uintptr_t(1U))) {
 108       // If the new value's lowest bit is zero, we can store
 109       // the new value directly into m_val, mark the low bit,
 110       // and return.
 111       m_val = uintptr_t(val) | uintptr_t(1U);
 112       return;
 113     }
 114     // Otherwise the new value's lowest bit is not zero, so we can't
 115     // use the trick where we store the value directly into m_val. To
 116     // handle this case we call the grow method (which will allocate
 117     // a chunk of memory) and then we fall through to the case below.
 118     grow();
 119   }
 120   // If we reach this point, m_data should be non-NULL and it should
 121   // not have its low bit set.
 122   assert(!(m_val & uintptr_t(1U)));
 123   assert(m_data);
 124   assert(index >= 0 && index < m_data->m_len);
 125   // Index into the malloced block of memory
 126   *((T**)(m_data+1) + index) = val;
 127 }
 128
 129 template <typename T>
 130 bool PointerList<T>::empty() const {
 131   if (!m_val) return true;
 132   return size() == 0;
 133 }
 134
 135 template <typename T>
 136 int PointerList<T>::size() const {
 137   if (m_val) {
 138     if (m_val & uintptr_t(1U)) {
 139       // If the low bit is set, that means we have exactly one element
 140       return 1;
 141     }
 142     // Read the malloced block of memory to find out how many elements
 143     // we have
 144     return m_data->m_len;
 145   } else {
 146     // If m_data is NULL, that means we have no elements
 147     return 0;
 148   }
 149 }
 150
 151 template <typename T>
 152 int PointerList<T>::capacity() {
 153   if (m_val && !(m_val & uintptr_t(1U))) {
 154     // If the m_data is non-NULL and the low bit is not set, read
 155     // the malloced block of memory to find out how many elements
 156     // can be stored before we need to grow.
 157     return m_data->m_capacity;
 158   }
 159   // If m_data is NULL or if the low bit is set, that means that
 160   // storing more elements may require us to grow, so we return
 161   // a capacity equal to our current size.
 162   return size();
 163 }
 164
 165 template <typename T>
 166 void PointerList<T>::clear() {
 167   if (m_val) {
 168     if (!(m_val & uintptr_t(1U))) {
 169       // If the low bit is not set, we need to free the malloced block
 170       // of memory
 171       free(m_data);
 172     }
 173     // Set m_data to NULL
 174     m_val = 0;
 175   }
 176 }
 177
 178 template <typename T>
 179 void PointerList<T>::grow() {
 180   if (m_val) {
 181     int len;
 182     int newCapacity;
 183     void* elms;
 184     bool doFree;
 185     if (m_val & uintptr_t(1U)) {
 186       // If the low bit is set, that means we have exactly one element and
 187       // that our new capacity should be INITIAL_CAPACITY. We also must clear
 188       // the low bit so that we can memcpy this one element into the newly
 189       // allocated block of memory.
 190       len = 1;
 191       newCapacity = INITIAL_CAPACITY;
 192       m_val = m_val & ~(uintptr_t(1U));
 193       elms = (void*)(&m_val);
 194       doFree = false;
 195     } else {
 196       len = m_data->m_len;
 197       newCapacity = m_data->m_capacity * 2;
 198       elms = (void*)(m_data+1);
 199       doFree = true;
 200     }
 201     PointerListData * new_data = (PointerListData*)malloc(
 202       sizeof(PointerListData) + sizeof(T*) * newCapacity);
 203     new_data->m_len = len;
 204     new_data->m_capacity = newCapacity;
 205     void* newElms = (void*)(new_data+1);
 206     // Copy over all of the elements in the newly allocated block of memory
 207     memcpy(newElms, elms, sizeof(T*) * len);
 208     if (doFree) {
 209       free(m_data);
 210     }
 211     m_data = new_data;
 212   } else {
 213     // If there are currently no elements, all we have to do is allocate a
 214     // block of memory and initialize m_len and m_capacity.
 215     m_data = (PointerListData*)malloc(
 216       sizeof(PointerListData) + sizeof(T*) * INITIAL_CAPACITY);
 217     m_data->m_len = 0;
 218     m_data->m_capacity = INITIAL_CAPACITY;
 219   }
 220   // Sanity check that malloc always returns a chunk of memory
 221   // that is aligned on a 2-byte boundary at the very least.
 222   // This is important because we steal the low bit of m_data
 223   // for our own nefarious purposes.
 224   assert(!(uintptr_t(m_data) & uintptr_t(1U)));
 225 }
 226
 227 template <typename T>
 228 void PointerList<T>::push(T* val) {
 229   if (!m_val && !(uintptr_t(val) & uintptr_t(1U))) {
 230     // If m_data is null and the low bit on the new value is zero,
 231     // we can store the new value directly into m_data and mark
 232     // the low bit.
 233     m_val = (uintptr_t(val) | uintptr_t(1U));
 234     return;
 235   }
 236   int sz = size();
 237   if (sz >= capacity()) grow();
 238   ++(m_data->m_len);
 239   set(sz, val);
 240 }
 241
 242 template <typename T>
 243 void PointerList<T>::pop() {
 244   if (m_val) {
 245     if (uintptr_t(m_val) & uintptr_t(1U)) {
 246       // If the value being popped was stored directly into m_data,
 247       // we just need to null out m_data
 248       m_val = 0;
 249     } else if (m_data->m_len > 0) {
 250       // Otherwise, we just decrement the length
 251       --(m_data->m_len);
 252     }
 253   }
 254 }
 255
 256 #undef INITIAL_CAPACITY
 257
 258 ///////////////////////////////////////////////////////////////////////////////
 259 }
 260
 261 #endif
 262