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