#ifndef Array_h
#define Array_h
#include <algorithm>
#include <stdint.h>
#include <stddef.h>
#include <mach/mach.h>
#if !TARGET_OS_DRIVERKIT && (BUILDING_LIBDYLD || BUILDING_DYLD)
#include <CrashReporterClient.h>
#else
#define CRSetCrashLogMessage(x)
#define CRSetCrashLogMessage2(x)
#endif
#define VIS_HIDDEN __attribute__((visibility("hidden")))
namespace dyld3 {
template <typename T>
class VIS_HIDDEN Array
{
public:
Array() : _elements(nullptr), _allocCount(0), _usedCount(0) {}
Array(T* storage, uintptr_t allocCount, uintptr_t usedCount=0) : _elements(storage), _allocCount(allocCount), _usedCount(usedCount) {}
void setInitialStorage(T* storage, uintptr_t allocCount) { assert(_usedCount == 0); _elements=storage; _allocCount=allocCount; }
T& operator[](size_t idx) { assert(idx < _usedCount); return _elements[idx]; }
const T& operator[](size_t idx) const { assert(idx < _usedCount); return _elements[idx]; }
T& back() { assert(_usedCount > 0); return _elements[_usedCount-1]; }
uintptr_t count() const { return _usedCount; }
uintptr_t maxCount() const { return _allocCount; }
uintptr_t freeCount() const { return _allocCount - _usedCount; }
bool empty() const { return (_usedCount == 0); }
uintptr_t index(const T& element) { return &element - _elements; }
void push_back(const T& t) { assert(_usedCount < _allocCount); _elements[_usedCount++] = t; }
void default_constuct_back() { assert(_usedCount < _allocCount); new (&_elements[_usedCount++])T(); }
void pop_back() { assert(_usedCount > 0); _usedCount--; }
T* begin() { return &_elements[0]; }
T* end() { return &_elements[_usedCount]; }
const T* begin() const { return &_elements[0]; }
const T* end() const { return &_elements[_usedCount]; }
const Array<T> subArray(uintptr_t start, uintptr_t size) const { assert(start+size <= _usedCount);
return Array<T>(&_elements[start], size, size); }
bool contains(const T& targ) const { for (const T& a : *this) { if ( a == targ ) return true; } return false; }
void remove(size_t idx) { assert(idx < _usedCount); ::memmove(&_elements[idx], &_elements[idx+1], sizeof(T)*(_usedCount-idx-1)); }
protected:
T* _elements;
uintptr_t _allocCount;
uintptr_t _usedCount;
};
template <typename T>
class VIS_HIDDEN ArrayFinalizer
{
public:
typedef void (^CleanUp)(T& element);
ArrayFinalizer(Array<T>& array, CleanUp handler) : _array(array), _handler(handler) { }
~ArrayFinalizer() { for(T& element : _array) _handler(element); }
private:
Array<T>& _array;
CleanUp _handler;
};
template <typename T, uintptr_t MAXCOUNT=0xFFFFFFFF>
class VIS_HIDDEN OverflowSafeArray : public Array<T>
{
public:
OverflowSafeArray() : Array<T>(nullptr, 0) {}
OverflowSafeArray(T* stackStorage, uintptr_t stackAllocCount) : Array<T>(stackStorage, stackAllocCount) {}
~OverflowSafeArray();
OverflowSafeArray(OverflowSafeArray&) = default;
OverflowSafeArray& operator=(OverflowSafeArray&& other);
void push_back(const T& t) { verifySpace(1); this->_elements[this->_usedCount++] = t; }
void default_constuct_back() { verifySpace(1); new (&this->_elements[this->_usedCount++])T(); }
void clear() { this->_usedCount = 0; }
void reserve(uintptr_t n) { if (this->_allocCount < n) growTo(n); }
void resize(uintptr_t n) {
if (n == this->_usedCount)
return;
if (n < this->_usedCount) {
this->_usedCount = n;
return;
}
reserve(n);
this->_usedCount = n;
}
protected:
void growTo(uintptr_t n);
void verifySpace(uintptr_t n) { if (this->_usedCount+n > this->_allocCount) growTo(this->_usedCount + n); }
private:
vm_address_t _overflowBuffer = 0;
vm_size_t _overflowBufferSize = 0;
};
template <typename T, uintptr_t MAXCOUNT>
inline void OverflowSafeArray<T,MAXCOUNT>::growTo(uintptr_t n)
{
vm_address_t oldBuffer = _overflowBuffer;
vm_size_t oldBufferSize = _overflowBufferSize;
if ( MAXCOUNT != 0xFFFFFFFF ) {
assert(oldBufferSize == 0); _overflowBufferSize = round_page(std::max(MAXCOUNT, n) * sizeof(T));
}
else {
_overflowBufferSize = round_page(std::max(this->_allocCount * 2, n) * sizeof(T));
}
kern_return_t kr = ::vm_allocate(mach_task_self(), &_overflowBuffer, _overflowBufferSize, VM_FLAGS_ANYWHERE);
if (kr != KERN_SUCCESS) {
#if BUILDING_LIBDYLD
char crashString[256];
snprintf(crashString, 256, "OverflowSafeArray failed to allocate %lu bytes, vm_allocate returned: %d\n",
_overflowBufferSize, kr);
CRSetCrashLogMessage(crashString);
#endif
assert(0);
}
::memcpy((void*)_overflowBuffer, this->_elements, this->_usedCount*sizeof(T));
this->_elements = (T*)_overflowBuffer;
this->_allocCount = _overflowBufferSize / sizeof(T);
if ( oldBuffer != 0 )
::vm_deallocate(mach_task_self(), oldBuffer, oldBufferSize);
}
template <typename T, uintptr_t MAXCOUNT>
inline OverflowSafeArray<T,MAXCOUNT>::~OverflowSafeArray()
{
if ( _overflowBuffer != 0 )
::vm_deallocate(mach_task_self(), _overflowBuffer, _overflowBufferSize);
}
template <typename T, uintptr_t MAXCOUNT>
inline OverflowSafeArray<T,MAXCOUNT>& OverflowSafeArray<T,MAXCOUNT>::operator=(OverflowSafeArray<T,MAXCOUNT>&& other)
{
if (this == &other)
return *this;
if ( _overflowBuffer != 0 )
::vm_deallocate(mach_task_self(), _overflowBuffer, _overflowBufferSize);
this->_elements = other._elements;
this->_allocCount = other._allocCount;
this->_usedCount = other._usedCount;
_overflowBuffer = other._overflowBuffer;
_overflowBufferSize = other._overflowBufferSize;
other._elements = nullptr;
other._allocCount = 0;
other._usedCount = 0;
other._overflowBuffer = 0;
other._overflowBufferSize = 0;
return *this;
}
#if BUILDING_LIBDYLD
template <typename T, int QUANT=4, int INIT=1>
class VIS_HIDDEN GrowableArray
{
public:
T& operator[](size_t idx) { assert(idx < _usedCount); return _elements[idx]; }
const T& operator[](size_t idx) const { assert(idx < _usedCount); return _elements[idx]; }
T& back() { assert(_usedCount > 0); return _elements[_usedCount-1]; }
uintptr_t count() const { return _usedCount; }
uintptr_t maxCount() const { return _allocCount; }
bool empty() const { return (_usedCount == 0); }
uintptr_t index(const T& element) { return &element - _elements; }
void push_back(const T& t) { verifySpace(1); _elements[_usedCount++] = t; }
void append(const Array<T>& a);
void pop_back() { assert(_usedCount > 0); _usedCount--; }
T* begin() { return &_elements[0]; }
T* end() { return &_elements[_usedCount]; }
const T* begin() const { return &_elements[0]; }
const T* end() const { return &_elements[_usedCount]; }
const Array<T> subArray(uintptr_t start, uintptr_t size) const { assert(start+size <= _usedCount);
return Array<T>(&_elements[start], size, size); }
const Array<T>& array() const { return *((Array<T>*)this); }
bool contains(const T& targ) const { for (const T& a : *this) { if ( a == targ ) return true; } return false; }
void erase(T& targ);
protected:
void growTo(uintptr_t n);
void verifySpace(uintptr_t n) { if (this->_usedCount+n > this->_allocCount) growTo(this->_usedCount + n); }
private:
T* _elements = _initialAlloc;
uintptr_t _allocCount = INIT;
uintptr_t _usedCount = 0;
T _initialAlloc[INIT] = { };
};
template <typename T, int QUANT, int INIT>
inline void GrowableArray<T,QUANT,INIT>::growTo(uintptr_t n)
{
uintptr_t newCount = (n + QUANT - 1) & (-QUANT);
T* newArray = (T*)::malloc(sizeof(T)*newCount);
T* oldArray = this->_elements;
if ( this->_usedCount != 0 )
::memcpy(newArray, oldArray, sizeof(T)*this->_usedCount);
this->_elements = newArray;
this->_allocCount = newCount;
if ( oldArray != this->_initialAlloc )
::free(oldArray);
}
template <typename T, int QUANT, int INIT>
inline void GrowableArray<T,QUANT,INIT>::append(const Array<T>& a)
{
verifySpace(a.count());
::memcpy(&_elements[_usedCount], a.begin(), a.count()*sizeof(T));
_usedCount += a.count();
}
template <typename T, int QUANT, int INIT>
inline void GrowableArray<T,QUANT,INIT>::erase(T& targ)
{
intptr_t index = &targ - _elements;
assert(index >= 0);
assert(index < (intptr_t)_usedCount);
intptr_t moveCount = _usedCount-index-1;
if ( moveCount > 0 )
::memcpy(&_elements[index], &_elements[index+1], moveCount*sizeof(T));
_usedCount -= 1;
}
#endif // BUILDING_LIBDYLD
#define STACK_ALLOC_ARRAY(_type, _name, _count) \
uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
__block dyld3::Array<_type> _name((_type*)__##_name##_array_alloc, _count);
#define STACK_ALLOC_OVERFLOW_SAFE_ARRAY(_type, _name, _count) \
uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
__block dyld3::OverflowSafeArray<_type> _name((_type*)__##_name##_array_alloc, _count);
#define BLOCK_ACCCESSIBLE_ARRAY(_type, _name, _count) \
_type __##_name##_array_alloc[_count]; \
_type* _name = __##_name##_array_alloc;
}
#endif