Chris@47: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors Chris@47: // Licensed under the MIT License: Chris@47: // Chris@47: // Permission is hereby granted, free of charge, to any person obtaining a copy Chris@47: // of this software and associated documentation files (the "Software"), to deal Chris@47: // in the Software without restriction, including without limitation the rights Chris@47: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell Chris@47: // copies of the Software, and to permit persons to whom the Software is Chris@47: // furnished to do so, subject to the following conditions: Chris@47: // Chris@47: // The above copyright notice and this permission notice shall be included in Chris@47: // all copies or substantial portions of the Software. Chris@47: // Chris@47: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR Chris@47: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, Chris@47: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE Chris@47: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER Chris@47: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, Chris@47: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN Chris@47: // THE SOFTWARE. Chris@47: Chris@47: #ifndef KJ_ARRAY_H_ Chris@47: #define KJ_ARRAY_H_ Chris@47: Chris@47: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS Chris@47: #pragma GCC system_header Chris@47: #endif Chris@47: Chris@47: #include "common.h" Chris@47: #include Chris@47: #include Chris@47: Chris@47: namespace kj { Chris@47: Chris@47: // ======================================================================================= Chris@47: // ArrayDisposer -- Implementation details. Chris@47: Chris@47: class ArrayDisposer { Chris@47: // Much like Disposer from memory.h. Chris@47: Chris@47: protected: Chris@47: // Do not declare a destructor, as doing so will force a global initializer for Chris@47: // HeapArrayDisposer::instance. Chris@47: Chris@47: virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount, Chris@47: size_t capacity, void (*destroyElement)(void*)) const = 0; Chris@47: // Disposes of the array. `destroyElement` invokes the destructor of each element, or is nullptr Chris@47: // if the elements have trivial destructors. `capacity` is the amount of space that was Chris@47: // allocated while `elementCount` is the number of elements that were actually constructed; Chris@47: // these are always the same number for Array but may be different when using ArrayBuilder. Chris@47: Chris@47: public: Chris@47: Chris@47: template Chris@47: void dispose(T* firstElement, size_t elementCount, size_t capacity) const; Chris@47: // Helper wrapper around disposeImpl(). Chris@47: // Chris@47: // Callers must not call dispose() on the same array twice, even if the first call throws Chris@47: // an exception. Chris@47: Chris@47: private: Chris@47: template Chris@47: struct Dispose_; Chris@47: }; Chris@47: Chris@47: class ExceptionSafeArrayUtil { Chris@47: // Utility class that assists in constructing or destroying elements of an array, where the Chris@47: // constructor or destructor could throw exceptions. In case of an exception, Chris@47: // ExceptionSafeArrayUtil's destructor will call destructors on all elements that have been Chris@47: // constructed but not destroyed. Remember that destructors that throw exceptions are required Chris@47: // to use UnwindDetector to detect unwind and avoid exceptions in this case. Therefore, no more Chris@47: // than one exception will be thrown (and the program will not terminate). Chris@47: Chris@47: public: Chris@47: inline ExceptionSafeArrayUtil(void* ptr, size_t elementSize, size_t constructedElementCount, Chris@47: void (*destroyElement)(void*)) Chris@47: : pos(reinterpret_cast(ptr) + elementSize * constructedElementCount), Chris@47: elementSize(elementSize), constructedElementCount(constructedElementCount), Chris@47: destroyElement(destroyElement) {} Chris@47: KJ_DISALLOW_COPY(ExceptionSafeArrayUtil); Chris@47: Chris@47: inline ~ExceptionSafeArrayUtil() noexcept(false) { Chris@47: if (constructedElementCount > 0) destroyAll(); Chris@47: } Chris@47: Chris@47: void construct(size_t count, void (*constructElement)(void*)); Chris@47: // Construct the given number of elements. Chris@47: Chris@47: void destroyAll(); Chris@47: // Destroy all elements. Call this immediately before ExceptionSafeArrayUtil goes out-of-scope Chris@47: // to ensure that one element throwing an exception does not prevent the others from being Chris@47: // destroyed. Chris@47: Chris@47: void release() { constructedElementCount = 0; } Chris@47: // Prevent ExceptionSafeArrayUtil's destructor from destroying the constructed elements. Chris@47: // Call this after you've successfully finished constructing. Chris@47: Chris@47: private: Chris@47: byte* pos; Chris@47: size_t elementSize; Chris@47: size_t constructedElementCount; Chris@47: void (*destroyElement)(void*); Chris@47: }; Chris@47: Chris@47: class DestructorOnlyArrayDisposer: public ArrayDisposer { Chris@47: public: Chris@47: static const DestructorOnlyArrayDisposer instance; Chris@47: Chris@47: void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount, Chris@47: size_t capacity, void (*destroyElement)(void*)) const override; Chris@47: }; Chris@47: Chris@47: class NullArrayDisposer: public ArrayDisposer { Chris@47: // An ArrayDisposer that does nothing. Can be used to construct a fake Arrays that doesn't Chris@47: // actually own its content. Chris@47: Chris@47: public: Chris@47: static const NullArrayDisposer instance; Chris@47: Chris@47: void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount, Chris@47: size_t capacity, void (*destroyElement)(void*)) const override; Chris@47: }; Chris@47: Chris@47: // ======================================================================================= Chris@47: // Array Chris@47: Chris@47: template Chris@47: class Array { Chris@47: // An owned array which will automatically be disposed of (using an ArrayDisposer) in the Chris@47: // destructor. Can be moved, but not copied. Much like Own, but for arrays rather than Chris@47: // single objects. Chris@47: Chris@47: public: Chris@47: inline Array(): ptr(nullptr), size_(0), disposer(nullptr) {} Chris@47: inline Array(decltype(nullptr)): ptr(nullptr), size_(0), disposer(nullptr) {} Chris@47: inline Array(Array&& other) noexcept Chris@47: : ptr(other.ptr), size_(other.size_), disposer(other.disposer) { Chris@47: other.ptr = nullptr; Chris@47: other.size_ = 0; Chris@47: } Chris@47: inline Array(Array>&& other) noexcept Chris@47: : ptr(other.ptr), size_(other.size_), disposer(other.disposer) { Chris@47: other.ptr = nullptr; Chris@47: other.size_ = 0; Chris@47: } Chris@47: inline Array(T* firstElement, size_t size, const ArrayDisposer& disposer) Chris@47: : ptr(firstElement), size_(size), disposer(&disposer) {} Chris@47: Chris@47: KJ_DISALLOW_COPY(Array); Chris@47: inline ~Array() noexcept { dispose(); } Chris@47: Chris@47: inline operator ArrayPtr() { Chris@47: return ArrayPtr(ptr, size_); Chris@47: } Chris@47: inline operator ArrayPtr() const { Chris@47: return ArrayPtr(ptr, size_); Chris@47: } Chris@47: inline ArrayPtr asPtr() { Chris@47: return ArrayPtr(ptr, size_); Chris@47: } Chris@47: inline ArrayPtr asPtr() const { Chris@47: return ArrayPtr(ptr, size_); Chris@47: } Chris@47: Chris@47: inline size_t size() const { return size_; } Chris@47: inline T& operator[](size_t index) const { Chris@47: KJ_IREQUIRE(index < size_, "Out-of-bounds Array access."); Chris@47: return ptr[index]; Chris@47: } Chris@47: Chris@47: inline const T* begin() const { return ptr; } Chris@47: inline const T* end() const { return ptr + size_; } Chris@47: inline const T& front() const { return *ptr; } Chris@47: inline const T& back() const { return *(ptr + size_ - 1); } Chris@47: inline T* begin() { return ptr; } Chris@47: inline T* end() { return ptr + size_; } Chris@47: inline T& front() { return *ptr; } Chris@47: inline T& back() { return *(ptr + size_ - 1); } Chris@47: Chris@47: inline ArrayPtr slice(size_t start, size_t end) { Chris@47: KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice()."); Chris@47: return ArrayPtr(ptr + start, end - start); Chris@47: } Chris@47: inline ArrayPtr slice(size_t start, size_t end) const { Chris@47: KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice()."); Chris@47: return ArrayPtr(ptr + start, end - start); Chris@47: } Chris@47: Chris@47: inline ArrayPtr asBytes() const { return asPtr().asBytes(); } Chris@47: inline ArrayPtr> asBytes() { return asPtr().asBytes(); } Chris@47: inline ArrayPtr asChars() const { return asPtr().asChars(); } Chris@47: inline ArrayPtr> asChars() { return asPtr().asChars(); } Chris@47: Chris@47: inline Array> releaseAsBytes() { Chris@47: // Like asBytes() but transfers ownership. Chris@47: static_assert(sizeof(T) == sizeof(byte), Chris@47: "releaseAsBytes() only possible on arrays with byte-size elements (e.g. chars)."); Chris@47: Array> result( Chris@47: reinterpret_cast*>(ptr), size_, *disposer); Chris@47: ptr = nullptr; Chris@47: size_ = 0; Chris@47: return result; Chris@47: } Chris@47: inline Array> releaseAsChars() { Chris@47: // Like asChars() but transfers ownership. Chris@47: static_assert(sizeof(T) == sizeof(PropagateConst), Chris@47: "releaseAsChars() only possible on arrays with char-size elements (e.g. bytes)."); Chris@47: Array> result( Chris@47: reinterpret_cast*>(ptr), size_, *disposer); Chris@47: ptr = nullptr; Chris@47: size_ = 0; Chris@47: return result; Chris@47: } Chris@47: Chris@47: inline bool operator==(decltype(nullptr)) const { return size_ == 0; } Chris@47: inline bool operator!=(decltype(nullptr)) const { return size_ != 0; } Chris@47: Chris@47: inline Array& operator=(decltype(nullptr)) { Chris@47: dispose(); Chris@47: return *this; Chris@47: } Chris@47: Chris@47: inline Array& operator=(Array&& other) { Chris@47: dispose(); Chris@47: ptr = other.ptr; Chris@47: size_ = other.size_; Chris@47: disposer = other.disposer; Chris@47: other.ptr = nullptr; Chris@47: other.size_ = 0; Chris@47: return *this; Chris@47: } Chris@47: Chris@47: private: Chris@47: T* ptr; Chris@47: size_t size_; Chris@47: const ArrayDisposer* disposer; Chris@47: Chris@47: inline void dispose() { Chris@47: // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly Chris@47: // dispose again. Chris@47: T* ptrCopy = ptr; Chris@47: size_t sizeCopy = size_; Chris@47: if (ptrCopy != nullptr) { Chris@47: ptr = nullptr; Chris@47: size_ = 0; Chris@47: disposer->dispose(ptrCopy, sizeCopy, sizeCopy); Chris@47: } Chris@47: } Chris@47: Chris@47: template Chris@47: friend class Array; Chris@47: }; Chris@47: Chris@47: namespace _ { // private Chris@47: Chris@47: class HeapArrayDisposer final: public ArrayDisposer { Chris@47: public: Chris@47: template Chris@47: static T* allocate(size_t count); Chris@47: template Chris@47: static T* allocateUninitialized(size_t count); Chris@47: Chris@47: static const HeapArrayDisposer instance; Chris@47: Chris@47: private: Chris@47: static void* allocateImpl(size_t elementSize, size_t elementCount, size_t capacity, Chris@47: void (*constructElement)(void*), void (*destroyElement)(void*)); Chris@47: // Allocates and constructs the array. Both function pointers are null if the constructor is Chris@47: // trivial, otherwise destroyElement is null if the constructor doesn't throw. Chris@47: Chris@47: virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount, Chris@47: size_t capacity, void (*destroyElement)(void*)) const override; Chris@47: Chris@47: template Chris@47: struct Allocate_; Chris@47: }; Chris@47: Chris@47: } // namespace _ (private) Chris@47: Chris@47: template Chris@47: inline Array heapArray(size_t size) { Chris@47: // Much like `heap()` from memory.h, allocates a new array on the heap. Chris@47: Chris@47: return Array(_::HeapArrayDisposer::allocate(size), size, Chris@47: _::HeapArrayDisposer::instance); Chris@47: } Chris@47: Chris@47: template Array heapArray(const T* content, size_t size); Chris@47: template Array heapArray(ArrayPtr content); Chris@47: template Array heapArray(ArrayPtr content); Chris@47: template Array heapArray(Iterator begin, Iterator end); Chris@47: template Array heapArray(std::initializer_list init); Chris@47: // Allocate a heap array containing a copy of the given content. Chris@47: Chris@47: template Chris@47: Array heapArrayFromIterable(Container&& a) { return heapArray(a.begin(), a.end()); } Chris@47: template Chris@47: Array heapArrayFromIterable(Array&& a) { return mv(a); } Chris@47: Chris@47: // ======================================================================================= Chris@47: // ArrayBuilder Chris@47: Chris@47: template Chris@47: class ArrayBuilder { Chris@47: // Class which lets you build an Array specifying the exact constructor arguments for each Chris@47: // element, rather than starting by default-constructing them. Chris@47: Chris@47: public: Chris@47: ArrayBuilder(): ptr(nullptr), pos(nullptr), endPtr(nullptr) {} Chris@47: ArrayBuilder(decltype(nullptr)): ptr(nullptr), pos(nullptr), endPtr(nullptr) {} Chris@47: explicit ArrayBuilder(RemoveConst* firstElement, size_t capacity, Chris@47: const ArrayDisposer& disposer) Chris@47: : ptr(firstElement), pos(firstElement), endPtr(firstElement + capacity), Chris@47: disposer(&disposer) {} Chris@47: ArrayBuilder(ArrayBuilder&& other) Chris@47: : ptr(other.ptr), pos(other.pos), endPtr(other.endPtr), disposer(other.disposer) { Chris@47: other.ptr = nullptr; Chris@47: other.pos = nullptr; Chris@47: other.endPtr = nullptr; Chris@47: } Chris@47: KJ_DISALLOW_COPY(ArrayBuilder); Chris@47: inline ~ArrayBuilder() noexcept(false) { dispose(); } Chris@47: Chris@47: inline operator ArrayPtr() { Chris@47: return arrayPtr(ptr, pos); Chris@47: } Chris@47: inline operator ArrayPtr() const { Chris@47: return arrayPtr(ptr, pos); Chris@47: } Chris@47: inline ArrayPtr asPtr() { Chris@47: return arrayPtr(ptr, pos); Chris@47: } Chris@47: inline ArrayPtr asPtr() const { Chris@47: return arrayPtr(ptr, pos); Chris@47: } Chris@47: Chris@47: inline size_t size() const { return pos - ptr; } Chris@47: inline size_t capacity() const { return endPtr - ptr; } Chris@47: inline T& operator[](size_t index) const { Chris@47: KJ_IREQUIRE(index < implicitCast(pos - ptr), "Out-of-bounds Array access."); Chris@47: return ptr[index]; Chris@47: } Chris@47: Chris@47: inline const T* begin() const { return ptr; } Chris@47: inline const T* end() const { return pos; } Chris@47: inline const T& front() const { return *ptr; } Chris@47: inline const T& back() const { return *(pos - 1); } Chris@47: inline T* begin() { return ptr; } Chris@47: inline T* end() { return pos; } Chris@47: inline T& front() { return *ptr; } Chris@47: inline T& back() { return *(pos - 1); } Chris@47: Chris@47: ArrayBuilder& operator=(ArrayBuilder&& other) { Chris@47: dispose(); Chris@47: ptr = other.ptr; Chris@47: pos = other.pos; Chris@47: endPtr = other.endPtr; Chris@47: disposer = other.disposer; Chris@47: other.ptr = nullptr; Chris@47: other.pos = nullptr; Chris@47: other.endPtr = nullptr; Chris@47: return *this; Chris@47: } Chris@47: ArrayBuilder& operator=(decltype(nullptr)) { Chris@47: dispose(); Chris@47: return *this; Chris@47: } Chris@47: Chris@47: template Chris@47: T& add(Params&&... params) { Chris@47: KJ_IREQUIRE(pos < endPtr, "Added too many elements to ArrayBuilder."); Chris@47: ctor(*pos, kj::fwd(params)...); Chris@47: return *pos++; Chris@47: } Chris@47: Chris@47: template Chris@47: void addAll(Container&& container) { Chris@47: addAll(container.begin(), container.end()); Chris@47: } Chris@47: Chris@47: template Chris@47: void addAll(Iterator start, Iterator end); Chris@47: Chris@47: void removeLast() { Chris@47: KJ_IREQUIRE(pos > ptr, "No elements present to remove."); Chris@47: kj::dtor(*--pos); Chris@47: } Chris@47: Chris@47: Array finish() { Chris@47: // We could safely remove this check if we assume that the disposer implementation doesn't Chris@47: // need to know the original capacity, as is thes case with HeapArrayDisposer since it uses Chris@47: // operator new() or if we created a custom disposer for ArrayBuilder which stores the capacity Chris@47: // in a prefix. But that would make it hard to write cleverer heap allocators, and anyway this Chris@47: // check might catch bugs. Probably people should use Vector if they want to build arrays Chris@47: // without knowing the final size in advance. Chris@47: KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely."); Chris@47: Array result(reinterpret_cast(ptr), pos - ptr, *disposer); Chris@47: ptr = nullptr; Chris@47: pos = nullptr; Chris@47: endPtr = nullptr; Chris@47: return result; Chris@47: } Chris@47: Chris@47: inline bool isFull() const { Chris@47: return pos == endPtr; Chris@47: } Chris@47: Chris@47: private: Chris@47: T* ptr; Chris@47: RemoveConst* pos; Chris@47: T* endPtr; Chris@47: const ArrayDisposer* disposer; Chris@47: Chris@47: inline void dispose() { Chris@47: // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly Chris@47: // dispose again. Chris@47: T* ptrCopy = ptr; Chris@47: T* posCopy = pos; Chris@47: T* endCopy = endPtr; Chris@47: if (ptrCopy != nullptr) { Chris@47: ptr = nullptr; Chris@47: pos = nullptr; Chris@47: endPtr = nullptr; Chris@47: disposer->dispose(ptrCopy, posCopy - ptrCopy, endCopy - ptrCopy); Chris@47: } Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: inline ArrayBuilder heapArrayBuilder(size_t size) { Chris@47: // Like `heapArray()` but does not default-construct the elements. You must construct them Chris@47: // manually by calling `add()`. Chris@47: Chris@47: return ArrayBuilder(_::HeapArrayDisposer::allocateUninitialized>(size), Chris@47: size, _::HeapArrayDisposer::instance); Chris@47: } Chris@47: Chris@47: // ======================================================================================= Chris@47: // Inline Arrays Chris@47: Chris@47: template Chris@47: class FixedArray { Chris@47: // A fixed-width array whose storage is allocated inline rather than on the heap. Chris@47: Chris@47: public: Chris@47: inline size_t size() const { return fixedSize; } Chris@47: inline T* begin() { return content; } Chris@47: inline T* end() { return content + fixedSize; } Chris@47: inline const T* begin() const { return content; } Chris@47: inline const T* end() const { return content + fixedSize; } Chris@47: Chris@47: inline operator ArrayPtr() { Chris@47: return arrayPtr(content, fixedSize); Chris@47: } Chris@47: inline operator ArrayPtr() const { Chris@47: return arrayPtr(content, fixedSize); Chris@47: } Chris@47: Chris@47: inline T& operator[](size_t index) { return content[index]; } Chris@47: inline const T& operator[](size_t index) const { return content[index]; } Chris@47: Chris@47: private: Chris@47: T content[fixedSize]; Chris@47: }; Chris@47: Chris@47: template Chris@47: class CappedArray { Chris@47: // Like `FixedArray` but can be dynamically resized as long as the size does not exceed the limit Chris@47: // specified by the template parameter. Chris@47: // Chris@47: // TODO(someday): Don't construct elements past currentSize? Chris@47: Chris@47: public: Chris@47: inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {} Chris@47: inline explicit constexpr CappedArray(size_t s): currentSize(s) {} Chris@47: Chris@47: inline size_t size() const { return currentSize; } Chris@47: inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; } Chris@47: inline T* begin() { return content; } Chris@47: inline T* end() { return content + currentSize; } Chris@47: inline const T* begin() const { return content; } Chris@47: inline const T* end() const { return content + currentSize; } Chris@47: Chris@47: inline operator ArrayPtr() { Chris@47: return arrayPtr(content, currentSize); Chris@47: } Chris@47: inline operator ArrayPtr() const { Chris@47: return arrayPtr(content, currentSize); Chris@47: } Chris@47: Chris@47: inline T& operator[](size_t index) { return content[index]; } Chris@47: inline const T& operator[](size_t index) const { return content[index]; } Chris@47: Chris@47: private: Chris@47: size_t currentSize; Chris@47: T content[fixedSize]; Chris@47: }; Chris@47: Chris@47: // ======================================================================================= Chris@47: // KJ_MAP Chris@47: Chris@47: #define KJ_MAP(elementName, array) \ Chris@47: ::kj::_::Mapper(array) * [&](decltype(*(array).begin()) elementName) Chris@47: // Applies some function to every element of an array, returning an Array of the results, with Chris@47: // nice syntax. Example: Chris@47: // Chris@47: // StringPtr foo = "abcd"; Chris@47: // Array bar = KJ_MAP(c, foo) -> char { return c + 1; }; Chris@47: // KJ_ASSERT(str(bar) == "bcde"); Chris@47: Chris@47: namespace _ { // private Chris@47: Chris@47: template Chris@47: struct Mapper { Chris@47: T array; Chris@47: Mapper(T&& array): array(kj::fwd(array)) {} Chris@47: template Chris@47: auto operator*(Func&& func) -> Array { Chris@47: auto builder = heapArrayBuilder(array.size()); Chris@47: for (auto iter = array.begin(); iter != array.end(); ++iter) { Chris@47: builder.add(func(*iter)); Chris@47: } Chris@47: return builder.finish(); Chris@47: } Chris@47: }; Chris@47: Chris@47: } // namespace _ (private) Chris@47: Chris@47: // ======================================================================================= Chris@47: // Inline implementation details Chris@47: Chris@47: template Chris@47: struct ArrayDisposer::Dispose_ { Chris@47: static void dispose(T* firstElement, size_t elementCount, size_t capacity, Chris@47: const ArrayDisposer& disposer) { Chris@47: disposer.disposeImpl(const_cast*>(firstElement), Chris@47: sizeof(T), elementCount, capacity, nullptr); Chris@47: } Chris@47: }; Chris@47: template Chris@47: struct ArrayDisposer::Dispose_ { Chris@47: static void destruct(void* ptr) { Chris@47: kj::dtor(*reinterpret_cast(ptr)); Chris@47: } Chris@47: Chris@47: static void dispose(T* firstElement, size_t elementCount, size_t capacity, Chris@47: const ArrayDisposer& disposer) { Chris@47: disposer.disposeImpl(firstElement, sizeof(T), elementCount, capacity, &destruct); Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: void ArrayDisposer::dispose(T* firstElement, size_t elementCount, size_t capacity) const { Chris@47: Dispose_::dispose(firstElement, elementCount, capacity, *this); Chris@47: } Chris@47: Chris@47: namespace _ { // private Chris@47: Chris@47: template Chris@47: struct HeapArrayDisposer::Allocate_ { Chris@47: static T* allocate(size_t elementCount, size_t capacity) { Chris@47: return reinterpret_cast(allocateImpl( Chris@47: sizeof(T), elementCount, capacity, nullptr, nullptr)); Chris@47: } Chris@47: }; Chris@47: template Chris@47: struct HeapArrayDisposer::Allocate_ { Chris@47: static void construct(void* ptr) { Chris@47: kj::ctor(*reinterpret_cast(ptr)); Chris@47: } Chris@47: static T* allocate(size_t elementCount, size_t capacity) { Chris@47: return reinterpret_cast(allocateImpl( Chris@47: sizeof(T), elementCount, capacity, &construct, nullptr)); Chris@47: } Chris@47: }; Chris@47: template Chris@47: struct HeapArrayDisposer::Allocate_ { Chris@47: static void construct(void* ptr) { Chris@47: kj::ctor(*reinterpret_cast(ptr)); Chris@47: } Chris@47: static void destruct(void* ptr) { Chris@47: kj::dtor(*reinterpret_cast(ptr)); Chris@47: } Chris@47: static T* allocate(size_t elementCount, size_t capacity) { Chris@47: return reinterpret_cast(allocateImpl( Chris@47: sizeof(T), elementCount, capacity, &construct, &destruct)); Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: T* HeapArrayDisposer::allocate(size_t count) { Chris@47: return Allocate_::allocate(count, count); Chris@47: } Chris@47: Chris@47: template Chris@47: T* HeapArrayDisposer::allocateUninitialized(size_t count) { Chris@47: return Allocate_::allocate(0, count); Chris@47: } Chris@47: Chris@47: template ()> Chris@47: struct CopyConstructArray_; Chris@47: Chris@47: template Chris@47: struct CopyConstructArray_ { Chris@47: static inline T* apply(T* __restrict__ pos, T* start, T* end) { Chris@47: memcpy(pos, start, reinterpret_cast(end) - reinterpret_cast(start)); Chris@47: return pos + (end - start); Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: struct CopyConstructArray_ { Chris@47: static inline T* apply(T* __restrict__ pos, const T* start, const T* end) { Chris@47: memcpy(pos, start, reinterpret_cast(end) - reinterpret_cast(start)); Chris@47: return pos + (end - start); Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: struct CopyConstructArray_ { Chris@47: static inline T* apply(T* __restrict__ pos, Iterator start, Iterator end) { Chris@47: // Since both the copy constructor and assignment operator are trivial, we know that assignment Chris@47: // is equivalent to copy-constructing. So we can make this case somewhat easier for the Chris@47: // compiler to optimize. Chris@47: while (start != end) { Chris@47: *pos++ = *start++; Chris@47: } Chris@47: return pos; Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: struct CopyConstructArray_ { Chris@47: struct ExceptionGuard { Chris@47: T* start; Chris@47: T* pos; Chris@47: inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {} Chris@47: ~ExceptionGuard() noexcept(false) { Chris@47: while (pos > start) { Chris@47: dtor(*--pos); Chris@47: } Chris@47: } Chris@47: }; Chris@47: Chris@47: static T* apply(T* __restrict__ pos, Iterator start, Iterator end) { Chris@47: // Verify that T can be *implicitly* constructed from the source values. Chris@47: if (false) implicitCast(*start); Chris@47: Chris@47: if (noexcept(T(*start))) { Chris@47: while (start != end) { Chris@47: ctor(*pos++, *start++); Chris@47: } Chris@47: return pos; Chris@47: } else { Chris@47: // Crap. This is complicated. Chris@47: ExceptionGuard guard(pos); Chris@47: while (start != end) { Chris@47: ctor(*guard.pos, *start++); Chris@47: ++guard.pos; Chris@47: } Chris@47: guard.start = guard.pos; Chris@47: return guard.pos; Chris@47: } Chris@47: } Chris@47: }; Chris@47: Chris@47: template Chris@47: inline T* copyConstructArray(T* dst, Iterator start, Iterator end) { Chris@47: return CopyConstructArray_>::apply(dst, start, end); Chris@47: } Chris@47: Chris@47: } // namespace _ (private) Chris@47: Chris@47: template Chris@47: template Chris@47: void ArrayBuilder::addAll(Iterator start, Iterator end) { Chris@47: pos = _::copyConstructArray(pos, start, end); Chris@47: } Chris@47: Chris@47: template Chris@47: Array heapArray(const T* content, size_t size) { Chris@47: ArrayBuilder builder = heapArrayBuilder(size); Chris@47: builder.addAll(content, content + size); Chris@47: return builder.finish(); Chris@47: } Chris@47: Chris@47: template Chris@47: Array heapArray(T* content, size_t size) { Chris@47: ArrayBuilder builder = heapArrayBuilder(size); Chris@47: builder.addAll(content, content + size); Chris@47: return builder.finish(); Chris@47: } Chris@47: Chris@47: template Chris@47: Array heapArray(ArrayPtr content) { Chris@47: ArrayBuilder builder = heapArrayBuilder(content.size()); Chris@47: builder.addAll(content); Chris@47: return builder.finish(); Chris@47: } Chris@47: Chris@47: template Chris@47: Array heapArray(ArrayPtr content) { Chris@47: ArrayBuilder builder = heapArrayBuilder(content.size()); Chris@47: builder.addAll(content); Chris@47: return builder.finish(); Chris@47: } Chris@47: Chris@47: template Array Chris@47: heapArray(Iterator begin, Iterator end) { Chris@47: ArrayBuilder builder = heapArrayBuilder(end - begin); Chris@47: builder.addAll(begin, end); Chris@47: return builder.finish(); Chris@47: } Chris@47: Chris@47: template Chris@47: inline Array heapArray(std::initializer_list init) { Chris@47: return heapArray(init.begin(), init.end()); Chris@47: } Chris@47: Chris@47: } // namespace kj Chris@47: Chris@47: #endif // KJ_ARRAY_H_