Loading...
--- dyld/dyld-1340/lsl/Vector.h
+++ /dev/null
@@ -1,348 +0,0 @@
-/*
-* Copyright (c) 2019 Apple Inc. All rights reserved.
-*
-* @APPLE_LICENSE_HEADER_START@
-*
-* "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
-* Reserved. This file contains Original Code and/or Modifications of
-* Original Code as defined in and that are subject to the Apple Public
-* Source License Version 1.0 (the 'License'). You may not use this file
-* except in compliance with the License. Please obtain a copy of the
-* License at http://www.apple.com/publicsource and read it before using
-* this file.
-*
-* The Original Code and all software distributed under the License are
-* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
-* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
-* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
-* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
-* License for the specific language governing rights and limitations
-* under the License."
-*
-* @APPLE_LICENSE_HEADER_END@
-*/
-
-// This is a mostly complete reimplementation of std::vector that can be safely used in dyld
-// It does not support a methods we don't use like max_capacity
-
-//FIXME: All the erase functions are broken
-
-#ifndef LSL_Vector_h
-#define LSL_Vector_h
-
-#include <span>
-#include <cassert>
-#include <cstdlib>
-#include <cstddef>
-#include <algorithm>
-
-#include "Defines.h"
-#include "BitUtils.h"
-#include "Allocator.h"
-
-
-namespace lsl {
-
-template<typename T>
-requires std::is_trivially_destructible_v<T>
-struct TRIVIAL_ABI Vector {
-#pragma mark -
-#pragma mark Typedefs
- using value_type = T;
- using size_type = uint64_t;
- using difference_type = std::ptrdiff_t;
- using reference = value_type&;
- using const_reference = const value_type&;
- using pointer = value_type*;
- using const_pointer = const value_type*;
- using iterator = value_type*;
- using const_iterator = const value_type*;
-#pragma mark -
-#pragma mark Constructors / Destructors / Assignment Operators / swap
- Vector() = delete;
- //Vector(const Vector& other); Implementation is private
- Vector& operator=(const Vector& other) {
- auto tmp = other;
- swap(tmp);
- return *this;
- }
- Vector(Vector&& other) {
- swap(other);
- }
- Vector& operator=(Vector&& other) {
- swap(other);
- return *this;
- }
- ~Vector() {
- if (_buffer) {
- resize(0);
- }
- }
- explicit Vector(Allocator& allocator) : _allocator(&allocator) {}
- Vector(const Vector& other, Allocator& allocator) :
- _allocator(&allocator),
- _size(0) {
- contract(_allocator != nullptr);
- reserve(other._size);
- _size = other._size;
- std::copy(other.begin(), other.end(), _buffer);
- }
- Vector(Vector&& other, Allocator& allocator) : _allocator(&allocator) {
- std::swap(_size, other._size);
- if (_allocator == other._allocator) {
- std::swap(_capacity, other._capacity);
- std::swap(_buffer, other._buffer);
- } else {
- reserve(_size);
- for(auto&& i : other) {
- push_back(i);
- }
- other.resize(0);
- }
- }
- template< class InputIt >
- Vector(InputIt first, InputIt last, Allocator& allocator) : _allocator(&allocator) {
- using category = typename std::iterator_traits<InputIt>::iterator_category;
- if constexpr (std::is_same_v<category, std::random_access_iterator_tag>) {
- reserve(last-first);
- std::copy(first, last, begin());
- _size = last-first;
- } else {
- for (auto i = first; i != last; ++i) {
- push_back(*i);
- }
- }
- }
- static Vector<T>* make(Allocator& allocator) {
- void* storage = allocator.malloc(sizeof(Vector<T>));
- return new (storage) Vector<T>(allocator);
- }
- Vector(std::initializer_list<T> ilist, Allocator& allocator) : _allocator(&allocator) {
- auto first = ilist.begin();
- auto last = ilist.end();
- reserve(last-first);
- std::copy(first, last, begin());
- _size = last-first;
- }
- explicit operator std::span<T>() {
- return std::span(begin(), end());
- }
- friend void swap(Vector<T> x, Vector<T> y) {
- return x.swap(y);
- }
-#pragma mark -
-#pragma mark Iterator support
- iterator begin() { return _buffer; }
- iterator end() { return _buffer + _size; }
- const_iterator begin() const { return _buffer; }
- const_iterator end() const { return _buffer + _size; }
- const_iterator cbegin() const noexcept { return _buffer; }
- const_iterator cend() const noexcept { return _buffer + _size; }
-
- reference at(size_type pos) { return *(_buffer + pos); }
- const_reference at(size_type pos) const { return *(_buffer + pos); }
- reference operator[](size_type pos) { return *(_buffer + pos); }
- const_reference operator[](size_type pos) const { return *(_buffer + pos); }
-
- reference front() { return *_buffer; }
- const_reference front() const { return *_buffer; }
- reference back() { return *(_buffer + _size - 1); }
- const_reference back() const { return *(_buffer + _size - 1); }
-#pragma mark -
- constexpr pointer data() { return _buffer; }
- constexpr const_pointer data() const { return _buffer; }
-
- [[nodiscard]] constexpr bool empty() const { return (_size == 0); }
- size_type size() const { return _size; }
- size_type capacity() const { return _capacity; }
- void clear() {
- deleteElements(0, _size);
- _size = 0;
- }
- void resize(size_type newCapacity) {
- if (newCapacity > capacity()) {
- reserve(newCapacity);
- _size = newCapacity;
- _capacity = newCapacity;
- } else if (newCapacity == 0) {
- deleteElements(0, _size);
- if (_buffer) {
- _allocator->free((void*)_buffer);
- }
- _buffer = nullptr;
- _size = 0;
- _capacity = 0;
- } else {
- deleteElements(newCapacity, _size);
- _size = newCapacity;
- _capacity = newCapacity;
- (void)_allocator->realloc((void*)_buffer, sizeof(T)*newCapacity);
- }
- }
- // This function exists purely to support stack allocated arrays
- void reserveExact(size_type newCapacity) {
- if (newCapacity <= capacity()) { return; }
- if (_allocator->realloc((void*)_buffer, sizeof(T)*newCapacity)) {
- _capacity = newCapacity;
- return;
- }
- auto buffer = _allocator->aligned_alloc(std::max(16UL, alignof(T)), sizeof(T)*newCapacity);
- for (auto i = 0; i < _size; ++i) {
- (void)new ((void*)((uintptr_t)buffer+(i*sizeof(T)))) T(std::move(_buffer[i]));
- }
- deleteElements(0, _size);
- if (_buffer) {
- _allocator->free((void*)_buffer);
- }
- _buffer = (value_type *)buffer;
- _size = std::min(newCapacity, _size);
- _capacity = newCapacity;
- assert(_capacity >= newCapacity);
- }
- void reserve(size_type newCapacity) {
- if (newCapacity <= _capacity) { return; }
- if (newCapacity < 16) {
- newCapacity = 16;
- } else {
- newCapacity = (uint64_t)lsl::bit_ceil(newCapacity);
- }
- reserveExact(newCapacity);
- }
- iterator insert( const_iterator pos, const T& value ) {
- auto offset = pos-begin();
- reserve(_size+1);
- std::copy_backward(_buffer + offset, _buffer + _size, _buffer + _size + 1);
- ++_size;
- _buffer[offset] = value;
- return &_buffer[offset];
- }
- iterator insert( const_iterator pos, T&& value ) {
- auto offset = pos-begin();
- reserve(_size+1);
- std::move_backward(_buffer + offset , _buffer + _size, _buffer + _size + 1);
- ++_size;
- std::swap(_buffer[offset], value);
- return &_buffer[offset];
- }
- iterator insert( const_iterator pos, size_type count, const T& value ) {
- auto offset = pos-begin();
- reserve(_size+count);
- std::move_backward(_buffer + offset, _buffer + _size, _buffer + _size + count);
- for(auto i = 0; i < count; ++i) {
- _buffer[offset+i] = value;
- }
- _size += count;
- return &_buffer[offset];
- }
- template< class InputIt >
- iterator insert( const_iterator pos, InputIt first, InputIt last ) {
- auto offset = pos-begin();
- auto count = last-first;
- reserve(_size+count);
- std::copy_backward(_buffer + offset, _buffer + _size, _buffer + _size + count);
- std::copy(first, last, _buffer + offset );
- _size += count;
- return _buffer + offset;
- }
- iterator erase(iterator pos) {
- if (pos == end()) {
- return end();
- }
- return erase(pos, pos + 1);
- }
- iterator erase(const_iterator pos) {
- if (pos == end()) {
- return end();
- }
- return erase(pos, pos + 1);
- }
- iterator erase(iterator first, iterator last) {
- if (first == last) {
- return end();
- }
- uint64_t firstIdx = first - _buffer;
- uint64_t count = last - first;
- std::move(last, end(), first);
- deleteElements(_size-count, _size);
- _size -= count;
- return _buffer + std::min(firstIdx, _size);
- }
- iterator erase(const_iterator first, const_iterator last) {
- if (first == last) {
- return end();
- }
- uint64_t firstIdx = first - _buffer;
- uint64_t count = last - first;
- std::move(last, cend(), (iterator)first);
- deleteElements(_size-count, _size);
- _size -= count;
- return _buffer + std::min(firstIdx, _size);
-
- }
- void push_back(const T& value) {
- reserve(_size+1);
- _buffer[_size++] = value;
- }
- void push_back(T&& value) {
- reserve(_size+1);
- _buffer[_size++] = std::move(value);
- }
- template< class... Args >
- reference emplace_back( Args&&... args ) {
- reserve(_size+1);
- (void)new((void*)(_buffer + _size)) value_type(std::forward<Args>(args)...);
- return _buffer[_size++];
- }
- void pop_back() {
- assert(_size > 0);
- deleteElements(_size-1, _size);
- _size--;
- }
- Allocator* allocator() const {
- return _allocator;
- }
-private:
- Vector(const Vector& other): _allocator(other._allocator) {
- assert(_allocator != nullptr);
- resize(0);
- reserve(other._size);
- _size = other._size;
- std::copy(other.begin(), other.end(), _buffer);
- };
- void swap(Vector& other) {
- using std::swap;
- if (this == &other) { return; }
- swap(_allocator, other._allocator);
- swap(_size, other._size);
- swap(_capacity, other._capacity);
- swap(_buffer, other._buffer);
- }
- void deleteElements(uint64_t startIdx, uint64_t endIdx) {
- if constexpr(!std::is_trivially_destructible<value_type>::value) {
- for (auto i = _buffer + startIdx; i != _buffer + endIdx; ++i) {
- i->~value_type();
- }
- }
- }
- Allocator* _allocator = nullptr;
- value_type* _buffer = nullptr;
- uint64_t _size = 0;
- uint64_t _capacity = 0;
-};
-
-} // namespace lsl
-
-#define STACK_ALLOC_VECTOR_BYTE_SIZE(_type, _count) (16UL + alignof(_type) + sizeof(_type)*_count \
- + alignof(lsl::Vector<_type>) + sizeof(lsl::Vector<_type>))
-
-#define STACK_ALLOC_VECTOR(_type, _name, _count) \
- STACK_ALLOCATOR(__##_name##_allocator, STACK_ALLOC_VECTOR_BYTE_SIZE(_type,_count)) \
- lsl::Vector<_type> _name(__##_name##_allocator); \
- _name.reserveExact(_count);
-
-#define BLOCK_STACK_ALLOC_VECTOR(_type, _name, _count) \
- STACK_ALLOCATOR(__##_name##_allocator, STACK_ALLOC_VECTOR_BYTE_SIZE(_type,_count)) \
- __block lsl::Vector<_type> _name(__##_name##_allocator); \
- _name.reserveExact(_count);
-
-#endif /* LSL_Vector_h */