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