2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_POINTERLIST_H_
18 #define incl_HPHP_POINTERLIST_H_
21 #include "hphp/util/assertions.h"
24 ///////////////////////////////////////////////////////////////////////////////
26 #define INITIAL_CAPACITY 4
28 struct PointerListData
;
31 * During its lifetime, an instance of PointerList can transition
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.
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
54 T
* get(int index
) const;
55 void set(int index
, T
* val
);
65 PointerList(const PointerList
&);
66 PointerList
& operator=(const PointerList
&);
69 struct PointerListData
{
75 PointerList
<T
>::PointerList() {
80 PointerList
<T
>::~PointerList() {
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
90 // Clear the low bit before returning the value
91 return (T
*)(m_val
& ~(uintptr_t(1U)));
93 // Index into the malloced block of memory
95 assert(index
>= 0 && index
< m_data
->m_len
);
96 return *((T
**)(m_data
+1) + index
);
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.
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,
109 m_val
= uintptr_t(val
) | uintptr_t(1U);
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.
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)));
122 assert(index
>= 0 && index
< m_data
->m_len
);
123 // Index into the malloced block of memory
124 *((T
**)(m_data
+1) + index
) = val
;
127 template <typename T
>
128 bool PointerList
<T
>::empty() const {
129 if (!m_val
) return true;
133 template <typename T
>
134 int PointerList
<T
>::size() const {
136 if (m_val
& uintptr_t(1U)) {
137 // If the low bit is set, that means we have exactly one element
140 // Read the malloced block of memory to find out how many elements
142 return m_data
->m_len
;
144 // If m_data is NULL, that means we have no elements
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
;
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.
163 template <typename T
>
164 void PointerList
<T
>::clear() {
166 if (!(m_val
& uintptr_t(1U))) {
167 // If the low bit is not set, we need to free the malloced block
171 // Set m_data to NULL
176 template <typename T
>
177 void PointerList
<T
>::grow() {
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.
189 newCapacity
= INITIAL_CAPACITY
;
190 m_val
= m_val
& ~(uintptr_t(1U));
191 elms
= (void*)(&m_val
);
195 newCapacity
= m_data
->m_capacity
* 2;
196 elms
= (void*)(m_data
+1);
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
);
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
);
216 m_data
->m_capacity
= INITIAL_CAPACITY
;
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)));
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
231 m_val
= (uintptr_t(val
) | uintptr_t(1U));
235 if (sz
>= capacity()) grow();
240 template <typename T
>
241 void PointerList
<T
>::pop() {
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
247 } else if (m_data
->m_len
> 0) {
248 // Otherwise, we just decrement the length
254 #undef INITIAL_CAPACITY
256 ///////////////////////////////////////////////////////////////////////////////