hphp/util/pointer-list.h

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