2 * Copyright (c) 2017 Apple Inc. All rights reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
21 * @APPLE_LICENSE_HEADER_END@
30 #include <mach/mach.h>
32 #define VIS_HIDDEN __attribute__((visibility("hidden")))
38 // Similar to std::vector<> but storage is pre-allocated and cannot be re-allocated.
39 // Storage is normally stack allocated.
41 // Use push_back() to add elements and range based for loops to iterate and [] to access by index.
44 class VIS_HIDDEN Array
47 Array() : _elements(nullptr), _allocCount(0), _usedCount(0) {}
48 Array(T
* storage
, uintptr_t allocCount
, uintptr_t usedCount
=0) : _elements(storage
), _allocCount(allocCount
), _usedCount(usedCount
) {}
49 void setInitialStorage(T
* storage
, uintptr_t allocCount
) { assert(_usedCount
== 0); _elements
=storage
; _allocCount
=allocCount
; }
51 T
& operator[](size_t idx
) { assert(idx
< _usedCount
); return _elements
[idx
]; }
52 const T
& operator[](size_t idx
) const { assert(idx
< _usedCount
); return _elements
[idx
]; }
53 T
& back() { assert(_usedCount
> 0); return _elements
[_usedCount
-1]; }
54 uintptr_t count() const { return _usedCount
; }
55 uintptr_t maxCount() const { return _allocCount
; }
56 uintptr_t freeCount() const { return _allocCount
- _usedCount
; }
57 bool empty() const { return (_usedCount
== 0); }
58 uintptr_t index(const T
& element
) { return &element
- _elements
; }
59 void push_back(const T
& t
) { assert(_usedCount
< _allocCount
); _elements
[_usedCount
++] = t
; }
60 void pop_back() { assert(_usedCount
> 0); _usedCount
--; }
61 T
* begin() { return &_elements
[0]; }
62 T
* end() { return &_elements
[_usedCount
]; }
63 const T
* begin() const { return &_elements
[0]; }
64 const T
* end() const { return &_elements
[_usedCount
]; }
65 const Array
<T
> subArray(uintptr_t start
, uintptr_t size
) const { assert(start
+size
<= _usedCount
);
66 return Array
<T
>(&_elements
[start
], size
, size
); }
67 bool contains(const T
& targ
) const { for (const T
& a
: *this) { if ( a
== targ
) return true; } return false; }
68 void remove(size_t idx
) { assert(idx
< _usedCount
); ::memmove(&_elements
[idx
], &_elements
[idx
+1], sizeof(T
)*(_usedCount
-idx
-1)); }
72 uintptr_t _allocCount
;
77 // If an Array<>.setInitialStorage() is used, the array may out live the stack space of the storage.
78 // To allow cleanup to be done to array elements when the stack goes away, you can make a local
79 // variable of ArrayFinalizer<>.
81 class VIS_HIDDEN ArrayFinalizer
84 typedef void (^CleanUp
)(T
& element
);
85 ArrayFinalizer(Array
<T
>& array
, CleanUp handler
) : _array(array
), _handler(handler
) { }
86 ~ArrayFinalizer() { for(T
& element
: _array
) _handler(element
); }
95 // Similar to Array<> but if the array overflows, it is re-allocated using vm_allocate().
96 // When the variable goes out of scope, any vm_allocate()ed storage is released.
97 // if MAXCOUNT is specified, then only one one vm_allocate() to that size is done.
99 template <typename T
, uintptr_t MAXCOUNT
=0xFFFFFFFF>
100 class VIS_HIDDEN OverflowSafeArray
: public Array
<T
>
103 OverflowSafeArray() : Array
<T
>(nullptr, 0) {}
104 OverflowSafeArray(T
* stackStorage
, uintptr_t stackAllocCount
) : Array
<T
>(stackStorage
, stackAllocCount
) {}
105 ~OverflowSafeArray();
107 void push_back(const T
& t
) { verifySpace(1); this->_elements
[this->_usedCount
++] = t
; }
108 void clear() { this->_usedCount
= 0; }
109 void reserve(uintptr_t n
) { if (this->_allocCount
< n
) growTo(n
); }
112 void growTo(uintptr_t n
);
113 void verifySpace(uintptr_t n
) { if (this->_usedCount
+n
> this->_allocCount
) growTo(this->_usedCount
+ n
); }
116 vm_address_t _overflowBuffer
= 0;
117 vm_size_t _overflowBufferSize
= 0;
121 template <typename T
, uintptr_t MAXCOUNT
>
122 inline void OverflowSafeArray
<T
,MAXCOUNT
>::growTo(uintptr_t n
)
124 vm_address_t oldBuffer
= _overflowBuffer
;
125 vm_size_t oldBufferSize
= _overflowBufferSize
;
126 if ( MAXCOUNT
!= 0xFFFFFFFF ) {
127 assert(oldBufferSize
== 0); // only re-alloc once
128 // MAXCOUNT is specified, so immediately jump to that size
129 _overflowBufferSize
= round_page(MAXCOUNT
* sizeof(T
));
132 // MAXCOUNT is not specified, keep doubling size
133 _overflowBufferSize
= round_page(std::max(this->_allocCount
* 2, n
) * sizeof(T
));
135 assert(::vm_allocate(mach_task_self(), &_overflowBuffer
, _overflowBufferSize
, VM_FLAGS_ANYWHERE
) == KERN_SUCCESS
);
136 ::memcpy((void*)_overflowBuffer
, this->_elements
, this->_usedCount
*sizeof(T
));
137 this->_elements
= (T
*)_overflowBuffer
;
138 this->_allocCount
= _overflowBufferSize
/ sizeof(T
);
140 if ( oldBuffer
!= 0 )
141 ::vm_deallocate(mach_task_self(), oldBuffer
, oldBufferSize
);
144 template <typename T
, uintptr_t MAXCOUNT
>
145 inline OverflowSafeArray
<T
,MAXCOUNT
>::~OverflowSafeArray()
147 if ( _overflowBuffer
!= 0 )
148 ::vm_deallocate(mach_task_self(), _overflowBuffer
, _overflowBufferSize
);
156 // Similar to std::vector<> but storage is initially allocated in the object. But if it needs to
157 // grow beyond, it will use malloc. The QUANT template arg is the "quantum" size for allocations.
158 // When the allocation needs to be grown, it is re-allocated at the required size rounded up to
161 // Use push_back() to add elements and range based for loops to iterate and [] to access by index.
163 // Note: this should be a subclass of Array<T> but doing so disables the compiler from optimizing away static constructors
165 template <typename T
, int QUANT
=4, int INIT
=1>
166 class VIS_HIDDEN GrowableArray
170 T
& operator[](size_t idx
) { assert(idx
< _usedCount
); return _elements
[idx
]; }
171 const T
& operator[](size_t idx
) const { assert(idx
< _usedCount
); return _elements
[idx
]; }
172 T
& back() { assert(_usedCount
> 0); return _elements
[_usedCount
-1]; }
173 uintptr_t count() const { return _usedCount
; }
174 uintptr_t maxCount() const { return _allocCount
; }
175 bool empty() const { return (_usedCount
== 0); }
176 uintptr_t index(const T
& element
) { return &element
- _elements
; }
177 void push_back(const T
& t
) { verifySpace(1); _elements
[_usedCount
++] = t
; }
178 void append(const Array
<T
>& a
);
179 void pop_back() { assert(_usedCount
> 0); _usedCount
--; }
180 T
* begin() { return &_elements
[0]; }
181 T
* end() { return &_elements
[_usedCount
]; }
182 const T
* begin() const { return &_elements
[0]; }
183 const T
* end() const { return &_elements
[_usedCount
]; }
184 const Array
<T
> subArray(uintptr_t start
, uintptr_t size
) const { assert(start
+size
<= _usedCount
);
185 return Array
<T
>(&_elements
[start
], size
, size
); }
186 const Array
<T
>& array() const { return *((Array
<T
>*)this); }
187 bool contains(const T
& targ
) const { for (const T
& a
: *this) { if ( a
== targ
) return true; } return false; }
191 void growTo(uintptr_t n
);
192 void verifySpace(uintptr_t n
) { if (this->_usedCount
+n
> this->_allocCount
) growTo(this->_usedCount
+ n
); }
195 T
* _elements
= _initialAlloc
;
196 uintptr_t _allocCount
= INIT
;
197 uintptr_t _usedCount
= 0;
198 T _initialAlloc
[INIT
] = { };
202 template <typename T
, int QUANT
, int INIT
>
203 inline void GrowableArray
<T
,QUANT
,INIT
>::growTo(uintptr_t n
)
205 uintptr_t newCount
= (n
+ QUANT
- 1) & (-QUANT
);
206 T
* newArray
= (T
*)::malloc(sizeof(T
)*newCount
);
207 T
* oldArray
= this->_elements
;
208 if ( this->_usedCount
!= 0 )
209 ::memcpy(newArray
, oldArray
, sizeof(T
)*this->_usedCount
);
210 this->_elements
= newArray
;
211 this->_allocCount
= newCount
;
212 if ( oldArray
!= this->_initialAlloc
)
216 template <typename T
, int QUANT
, int INIT
>
217 inline void GrowableArray
<T
,QUANT
,INIT
>::append(const Array
<T
>& a
)
219 verifySpace(a
.count());
220 ::memcpy(&_elements
[_usedCount
], a
.begin(), a
.count()*sizeof(T
));
221 _usedCount
+= a
.count();
224 template <typename T
, int QUANT
, int INIT
>
225 inline void GrowableArray
<T
,QUANT
,INIT
>::erase(T
& targ
)
227 intptr_t index
= &targ
- _elements
;
229 assert(index
< (intptr_t)_usedCount
);
230 intptr_t moveCount
= _usedCount
-index
-1;
232 ::memcpy(&_elements
[index
], &_elements
[index
+1], moveCount
*sizeof(T
));
236 #endif // BUILDING_LIBDYLD
240 // STACK_ALLOC_ARRAY(foo, myarray, 10);
241 // myarray is of type Array<foo>
242 #define STACK_ALLOC_ARRAY(_type, _name, _count) \
243 uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
244 __block dyld3::Array<_type> _name((_type*)__##_name##_array_alloc, _count);
247 // STACK_ALLOC_OVERFLOW_SAFE_ARRAY(foo, myarray, 10);
248 // myarray is of type OverflowSafeArray<foo>
249 #define STACK_ALLOC_OVERFLOW_SAFE_ARRAY(_type, _name, _count) \
250 uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
251 __block dyld3::OverflowSafeArray<_type> _name((_type*)__##_name##_array_alloc, _count);
254 // work around compiler bug where:
255 // __block type name[count];
256 // is not accessible in a block
257 #define BLOCK_ACCCESSIBLE_ARRAY(_type, _name, _count) \
258 _type __##_name##_array_alloc[_count]; \
259 _type* _name = __##_name##_array_alloc;