array.h 29.3 KB
Newer Older
Kenton Varda's avatar
Kenton Varda committed
1 2
// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
3
//
Kenton Varda's avatar
Kenton Varda committed
4 5 6 7 8 9
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
10
//
Kenton Varda's avatar
Kenton Varda committed
11 12
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
13
//
Kenton Varda's avatar
Kenton Varda committed
14 15 16 17 18 19 20
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
21

22
#pragma once
23

24 25 26 27
#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
#pragma GCC system_header
#endif

28
#include "memory.h"
29
#include <string.h>
30
#include <initializer_list>
31 32 33

namespace kj {

Kenton Varda's avatar
Kenton Varda committed
34 35 36 37 38 39 40
// =======================================================================================
// ArrayDisposer -- Implementation details.

class ArrayDisposer {
  // Much like Disposer from memory.h.

protected:
41 42
  // Do not declare a destructor, as doing so will force a global initializer for
  // HeapArrayDisposer::instance.
Kenton Varda's avatar
Kenton Varda committed
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

  virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
                           size_t capacity, void (*destroyElement)(void*)) const = 0;
  // Disposes of the array.  `destroyElement` invokes the destructor of each element, or is nullptr
  // if the elements have trivial destructors.  `capacity` is the amount of space that was
  // allocated while `elementCount` is the number of elements that were actually constructed;
  // these are always the same number for Array<T> but may be different when using ArrayBuilder<T>.

public:

  template <typename T>
  void dispose(T* firstElement, size_t elementCount, size_t capacity) const;
  // Helper wrapper around disposeImpl().
  //
  // Callers must not call dispose() on the same array twice, even if the first call throws
  // an exception.

private:
  template <typename T, bool hasTrivialDestructor = __has_trivial_destructor(T)>
  struct Dispose_;
};

65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
class ExceptionSafeArrayUtil {
  // Utility class that assists in constructing or destroying elements of an array, where the
  // constructor or destructor could throw exceptions.  In case of an exception,
  // ExceptionSafeArrayUtil's destructor will call destructors on all elements that have been
  // constructed but not destroyed.  Remember that destructors that throw exceptions are required
  // to use UnwindDetector to detect unwind and avoid exceptions in this case.  Therefore, no more
  // than one exception will be thrown (and the program will not terminate).

public:
  inline ExceptionSafeArrayUtil(void* ptr, size_t elementSize, size_t constructedElementCount,
                                void (*destroyElement)(void*))
      : pos(reinterpret_cast<byte*>(ptr) + elementSize * constructedElementCount),
        elementSize(elementSize), constructedElementCount(constructedElementCount),
        destroyElement(destroyElement) {}
  KJ_DISALLOW_COPY(ExceptionSafeArrayUtil);

  inline ~ExceptionSafeArrayUtil() noexcept(false) {
    if (constructedElementCount > 0) destroyAll();
  }

  void construct(size_t count, void (*constructElement)(void*));
  // Construct the given number of elements.

  void destroyAll();
  // Destroy all elements.  Call this immediately before ExceptionSafeArrayUtil goes out-of-scope
  // to ensure that one element throwing an exception does not prevent the others from being
  // destroyed.

  void release() { constructedElementCount = 0; }
  // Prevent ExceptionSafeArrayUtil's destructor from destroying the constructed elements.
  // Call this after you've successfully finished constructing.

private:
  byte* pos;
  size_t elementSize;
  size_t constructedElementCount;
  void (*destroyElement)(void*);
};

104 105 106 107 108 109 110 111
class DestructorOnlyArrayDisposer: public ArrayDisposer {
public:
  static const DestructorOnlyArrayDisposer instance;

  void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
                   size_t capacity, void (*destroyElement)(void*)) const override;
};

112 113 114 115 116 117 118 119 120 121 122
class NullArrayDisposer: public ArrayDisposer {
  // An ArrayDisposer that does nothing.  Can be used to construct a fake Arrays that doesn't
  // actually own its content.

public:
  static const NullArrayDisposer instance;

  void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
                   size_t capacity, void (*destroyElement)(void*)) const override;
};

123 124 125 126 127
// =======================================================================================
// Array

template <typename T>
class Array {
Kenton Varda's avatar
Kenton Varda committed
128 129 130
  // An owned array which will automatically be disposed of (using an ArrayDisposer) in the
  // destructor.  Can be moved, but not copied.  Much like Own<T>, but for arrays rather than
  // single objects.
131 132

public:
Kenton Varda's avatar
Kenton Varda committed
133 134
  inline Array(): ptr(nullptr), size_(0), disposer(nullptr) {}
  inline Array(decltype(nullptr)): ptr(nullptr), size_(0), disposer(nullptr) {}
Kenton Varda's avatar
Kenton Varda committed
135 136
  inline Array(Array&& other) noexcept
      : ptr(other.ptr), size_(other.size_), disposer(other.disposer) {
137 138 139
    other.ptr = nullptr;
    other.size_ = 0;
  }
140
  inline Array(Array<RemoveConstOrDisable<T>>&& other) noexcept
141 142 143 144
      : ptr(other.ptr), size_(other.size_), disposer(other.disposer) {
    other.ptr = nullptr;
    other.size_ = 0;
  }
Kenton Varda's avatar
Kenton Varda committed
145 146
  inline Array(T* firstElement, size_t size, const ArrayDisposer& disposer)
      : ptr(firstElement), size_(size), disposer(&disposer) {}
147 148

  KJ_DISALLOW_COPY(Array);
Kenton Varda's avatar
Kenton Varda committed
149
  inline ~Array() noexcept { dispose(); }
150 151 152 153 154 155 156 157 158 159

  inline operator ArrayPtr<T>() {
    return ArrayPtr<T>(ptr, size_);
  }
  inline operator ArrayPtr<const T>() const {
    return ArrayPtr<T>(ptr, size_);
  }
  inline ArrayPtr<T> asPtr() {
    return ArrayPtr<T>(ptr, size_);
  }
Kenton Varda's avatar
Kenton Varda committed
160 161 162
  inline ArrayPtr<const T> asPtr() const {
    return ArrayPtr<T>(ptr, size_);
  }
163 164 165

  inline size_t size() const { return size_; }
  inline T& operator[](size_t index) const {
Kenton Varda's avatar
Kenton Varda committed
166
    KJ_IREQUIRE(index < size_, "Out-of-bounds Array access.");
167 168 169
    return ptr[index];
  }

Kenton Varda's avatar
Kenton Varda committed
170 171 172 173 174 175 176 177
  inline const T* begin() const { return ptr; }
  inline const T* end() const { return ptr + size_; }
  inline const T& front() const { return *ptr; }
  inline const T& back() const { return *(ptr + size_ - 1); }
  inline T* begin() { return ptr; }
  inline T* end() { return ptr + size_; }
  inline T& front() { return *ptr; }
  inline T& back() { return *(ptr + size_ - 1); }
178

179 180 181 182 183
  template <typename U>
  inline bool operator==(const U& other) const { return asPtr() == other; }
  template <typename U>
  inline bool operator!=(const U& other) const { return asPtr() != other; }

184
  inline ArrayPtr<T> slice(size_t start, size_t end) {
Kenton Varda's avatar
Kenton Varda committed
185
    KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice().");
186 187 188
    return ArrayPtr<T>(ptr + start, end - start);
  }
  inline ArrayPtr<const T> slice(size_t start, size_t end) const {
Kenton Varda's avatar
Kenton Varda committed
189
    KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice().");
190 191 192
    return ArrayPtr<const T>(ptr + start, end - start);
  }

193 194 195 196 197
  inline ArrayPtr<const byte> asBytes() const { return asPtr().asBytes(); }
  inline ArrayPtr<PropagateConst<T, byte>> asBytes() { return asPtr().asBytes(); }
  inline ArrayPtr<const char> asChars() const { return asPtr().asChars(); }
  inline ArrayPtr<PropagateConst<T, char>> asChars() { return asPtr().asChars(); }

198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
  inline Array<PropagateConst<T, byte>> releaseAsBytes() {
    // Like asBytes() but transfers ownership.
    static_assert(sizeof(T) == sizeof(byte),
        "releaseAsBytes() only possible on arrays with byte-size elements (e.g. chars).");
    Array<PropagateConst<T, byte>> result(
        reinterpret_cast<PropagateConst<T, byte>*>(ptr), size_, *disposer);
    ptr = nullptr;
    size_ = 0;
    return result;
  }
  inline Array<PropagateConst<T, char>> releaseAsChars() {
    // Like asChars() but transfers ownership.
    static_assert(sizeof(T) == sizeof(PropagateConst<T, char>),
        "releaseAsChars() only possible on arrays with char-size elements (e.g. bytes).");
    Array<PropagateConst<T, char>> result(
        reinterpret_cast<PropagateConst<T, char>*>(ptr), size_, *disposer);
    ptr = nullptr;
    size_ = 0;
    return result;
  }

219 220 221 222
  inline bool operator==(decltype(nullptr)) const { return size_ == 0; }
  inline bool operator!=(decltype(nullptr)) const { return size_ != 0; }

  inline Array& operator=(decltype(nullptr)) {
Kenton Varda's avatar
Kenton Varda committed
223
    dispose();
224 225 226 227
    return *this;
  }

  inline Array& operator=(Array&& other) {
Kenton Varda's avatar
Kenton Varda committed
228
    dispose();
229 230
    ptr = other.ptr;
    size_ = other.size_;
Kenton Varda's avatar
Kenton Varda committed
231
    disposer = other.disposer;
232 233 234 235 236
    other.ptr = nullptr;
    other.size_ = 0;
    return *this;
  }

237 238 239 240
  template <typename... Attachments>
  Array<T> attach(Attachments&&... attachments) KJ_WARN_UNUSED_RESULT;
  // Like Own<T>::attach(), but attaches to an Array.

241 242 243
private:
  T* ptr;
  size_t size_;
Kenton Varda's avatar
Kenton Varda committed
244 245 246 247 248 249 250 251 252 253 254 255 256
  const ArrayDisposer* disposer;

  inline void dispose() {
    // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly
    // dispose again.
    T* ptrCopy = ptr;
    size_t sizeCopy = size_;
    if (ptrCopy != nullptr) {
      ptr = nullptr;
      size_ = 0;
      disposer->dispose(ptrCopy, sizeCopy, sizeCopy);
    }
  }
257 258 259

  template <typename U>
  friend class Array;
260 261
  template <typename U>
  friend class ArrayBuilder;
Kenton Varda's avatar
Kenton Varda committed
262 263
};

264 265
static_assert(!canMemcpy<Array<char>>(), "canMemcpy<>() is broken");

266
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
267 268 269 270 271 272 273

class HeapArrayDisposer final: public ArrayDisposer {
public:
  template <typename T>
  static T* allocate(size_t count);
  template <typename T>
  static T* allocateUninitialized(size_t count);
274

Kenton Varda's avatar
Kenton Varda committed
275 276 277
  static const HeapArrayDisposer instance;

private:
Kenton Varda's avatar
Kenton Varda committed
278 279 280 281 282 283 284 285
  static void* allocateImpl(size_t elementSize, size_t elementCount, size_t capacity,
                            void (*constructElement)(void*), void (*destroyElement)(void*));
  // Allocates and constructs the array.  Both function pointers are null if the constructor is
  // trivial, otherwise destroyElement is null if the constructor doesn't throw.

  virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
                           size_t capacity, void (*destroyElement)(void*)) const override;

Kenton Varda's avatar
Kenton Varda committed
286 287 288
  template <typename T, bool hasTrivialConstructor = __has_trivial_constructor(T),
                        bool hasNothrowConstructor = __has_nothrow_constructor(T)>
  struct Allocate_;
289 290
};

291
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
292

293
template <typename T>
Kenton Varda's avatar
Kenton Varda committed
294 295 296
inline Array<T> heapArray(size_t size) {
  // Much like `heap<T>()` from memory.h, allocates a new array on the heap.

297 298
  return Array<T>(_::HeapArrayDisposer::allocate<T>(size), size,
                  _::HeapArrayDisposer::instance);
299 300
}

Kenton Varda's avatar
Kenton Varda committed
301
template <typename T> Array<T> heapArray(const T* content, size_t size);
302
template <typename T> Array<T> heapArray(ArrayPtr<T> content);
Kenton Varda's avatar
Kenton Varda committed
303 304
template <typename T> Array<T> heapArray(ArrayPtr<const T> content);
template <typename T, typename Iterator> Array<T> heapArray(Iterator begin, Iterator end);
305 306
template <typename T> Array<T> heapArray(std::initializer_list<T> init);
// Allocate a heap array containing a copy of the given content.
Kenton Varda's avatar
Kenton Varda committed
307

308
template <typename T, typename Container>
309
Array<T> heapArrayFromIterable(Container&& a) { return heapArray<T>(a.begin(), a.end()); }
310 311 312
template <typename T>
Array<T> heapArrayFromIterable(Array<T>&& a) { return mv(a); }

313 314 315 316 317
// =======================================================================================
// ArrayBuilder

template <typename T>
class ArrayBuilder {
Kenton Varda's avatar
Kenton Varda committed
318 319
  // Class which lets you build an Array<T> specifying the exact constructor arguments for each
  // element, rather than starting by default-constructing them.
320 321

public:
Kenton Varda's avatar
Kenton Varda committed
322 323
  ArrayBuilder(): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
  ArrayBuilder(decltype(nullptr)): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
324 325
  explicit ArrayBuilder(RemoveConst<T>* firstElement, size_t capacity,
                        const ArrayDisposer& disposer)
Kenton Varda's avatar
Kenton Varda committed
326 327 328 329 330 331 332 333
      : ptr(firstElement), pos(firstElement), endPtr(firstElement + capacity),
        disposer(&disposer) {}
  ArrayBuilder(ArrayBuilder&& other)
      : ptr(other.ptr), pos(other.pos), endPtr(other.endPtr), disposer(other.disposer) {
    other.ptr = nullptr;
    other.pos = nullptr;
    other.endPtr = nullptr;
  }
334 335
  ArrayBuilder(Array<T>&& other)
      : ptr(other.ptr), pos(other.ptr + other.size_), endPtr(pos), disposer(other.disposer) {
Kenton Varda's avatar
Kenton Varda committed
336
    // Create an already-full ArrayBuilder from an Array of the same type. This constructor
337 338 339 340
    // primarily exists to enable Vector<T> to be constructed from Array<T>.
    other.ptr = nullptr;
    other.size_ = 0;
  }
Kenton Varda's avatar
Kenton Varda committed
341
  KJ_DISALLOW_COPY(ArrayBuilder);
342
  inline ~ArrayBuilder() noexcept(false) { dispose(); }
Kenton Varda's avatar
Kenton Varda committed
343 344 345 346 347 348 349 350 351 352

  inline operator ArrayPtr<T>() {
    return arrayPtr(ptr, pos);
  }
  inline operator ArrayPtr<const T>() const {
    return arrayPtr(ptr, pos);
  }
  inline ArrayPtr<T> asPtr() {
    return arrayPtr(ptr, pos);
  }
353 354 355
  inline ArrayPtr<const T> asPtr() const {
    return arrayPtr(ptr, pos);
  }
Kenton Varda's avatar
Kenton Varda committed
356 357 358 359

  inline size_t size() const { return pos - ptr; }
  inline size_t capacity() const { return endPtr - ptr; }
  inline T& operator[](size_t index) const {
Kenton Varda's avatar
Kenton Varda committed
360
    KJ_IREQUIRE(index < implicitCast<size_t>(pos - ptr), "Out-of-bounds Array access.");
Kenton Varda's avatar
Kenton Varda committed
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
    return ptr[index];
  }

  inline const T* begin() const { return ptr; }
  inline const T* end() const { return pos; }
  inline const T& front() const { return *ptr; }
  inline const T& back() const { return *(pos - 1); }
  inline T* begin() { return ptr; }
  inline T* end() { return pos; }
  inline T& front() { return *ptr; }
  inline T& back() { return *(pos - 1); }

  ArrayBuilder& operator=(ArrayBuilder&& other) {
    dispose();
    ptr = other.ptr;
    pos = other.pos;
    endPtr = other.endPtr;
    disposer = other.disposer;
    other.ptr = nullptr;
    other.pos = nullptr;
    other.endPtr = nullptr;
    return *this;
  }
  ArrayBuilder& operator=(decltype(nullptr)) {
    dispose();
    return *this;
387 388 389
  }

  template <typename... Params>
Kenton Varda's avatar
Kenton Varda committed
390
  T& add(Params&&... params) {
Kenton Varda's avatar
Kenton Varda committed
391
    KJ_IREQUIRE(pos < endPtr, "Added too many elements to ArrayBuilder.");
Kenton Varda's avatar
Kenton Varda committed
392
    ctor(*pos, kj::fwd<Params>(params)...);
Kenton Varda's avatar
Kenton Varda committed
393
    return *pos++;
394 395 396 397
  }

  template <typename Container>
  void addAll(Container&& container) {
398 399
    addAll<decltype(container.begin()), !isReference<Container>()>(
        container.begin(), container.end());
400 401
  }

402
  template <typename Iterator, bool move = false>
Kenton Varda's avatar
Kenton Varda committed
403 404
  void addAll(Iterator start, Iterator end);

405 406 407 408 409
  void removeLast() {
    KJ_IREQUIRE(pos > ptr, "No elements present to remove.");
    kj::dtor(*--pos);
  }

410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447
  void truncate(size_t size) {
    KJ_IREQUIRE(size <= this->size(), "can't use truncate() to expand");

    T* target = ptr + size;
    if (__has_trivial_destructor(T)) {
      pos = target;
    } else {
      while (pos > target) {
        kj::dtor(*--pos);
      }
    }
  }

  void resize(size_t size) {
    KJ_IREQUIRE(size <= capacity(), "can't resize past capacity");

    T* target = ptr + size;
    if (target > pos) {
      // expand
      if (__has_trivial_constructor(T)) {
        pos = target;
      } else {
        while (pos < target) {
          kj::ctor(*pos++);
        }
      }
    } else {
      // truncate
      if (__has_trivial_destructor(T)) {
        pos = target;
      } else {
        while (pos > target) {
          kj::dtor(*--pos);
        }
      }
    }
  }

448
  Array<T> finish() {
449 450 451 452 453 454
    // We could safely remove this check if we assume that the disposer implementation doesn't
    // need to know the original capacity, as is thes case with HeapArrayDisposer since it uses
    // operator new() or if we created a custom disposer for ArrayBuilder which stores the capacity
    // in a prefix.  But that would make it hard to write cleverer heap allocators, and anyway this
    // check might catch bugs.  Probably people should use Vector if they want to build arrays
    // without knowing the final size in advance.
Kenton Varda's avatar
Kenton Varda committed
455
    KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely.");
456
    Array<T> result(reinterpret_cast<T*>(ptr), pos - ptr, *disposer);
457 458 459
    ptr = nullptr;
    pos = nullptr;
    endPtr = nullptr;
460
    return result;
461 462
  }

463 464 465 466
  inline bool isFull() const {
    return pos == endPtr;
  }

467
private:
Kenton Varda's avatar
Kenton Varda committed
468
  T* ptr;
469
  RemoveConst<T>* pos;
Kenton Varda's avatar
Kenton Varda committed
470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
  T* endPtr;
  const ArrayDisposer* disposer;

  inline void dispose() {
    // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly
    // dispose again.
    T* ptrCopy = ptr;
    T* posCopy = pos;
    T* endCopy = endPtr;
    if (ptrCopy != nullptr) {
      ptr = nullptr;
      pos = nullptr;
      endPtr = nullptr;
      disposer->dispose(ptrCopy, posCopy - ptrCopy, endCopy - ptrCopy);
    }
  }
486 487
};

Kenton Varda's avatar
Kenton Varda committed
488 489 490 491 492
template <typename T>
inline ArrayBuilder<T> heapArrayBuilder(size_t size) {
  // Like `heapArray<T>()` but does not default-construct the elements.  You must construct them
  // manually by calling `add()`.

493 494
  return ArrayBuilder<T>(_::HeapArrayDisposer::allocateUninitialized<RemoveConst<T>>(size),
                         size, _::HeapArrayDisposer::instance);
Kenton Varda's avatar
Kenton Varda committed
495 496 497
}

// =======================================================================================
498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
// Inline Arrays

template <typename T, size_t fixedSize>
class FixedArray {
  // A fixed-width array whose storage is allocated inline rather than on the heap.

public:
  inline size_t size() const { return fixedSize; }
  inline T* begin() { return content; }
  inline T* end() { return content + fixedSize; }
  inline const T* begin() const { return content; }
  inline const T* end() const { return content + fixedSize; }

  inline operator ArrayPtr<T>() {
    return arrayPtr(content, fixedSize);
  }
  inline operator ArrayPtr<const T>() const {
    return arrayPtr(content, fixedSize);
  }

  inline T& operator[](size_t index) { return content[index]; }
  inline const T& operator[](size_t index) const { return content[index]; }

private:
  T content[fixedSize];
};

template <typename T, size_t fixedSize>
class CappedArray {
  // Like `FixedArray` but can be dynamically resized as long as the size does not exceed the limit
  // specified by the template parameter.
  //
  // TODO(someday):  Don't construct elements past currentSize?

public:
533
  inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {}
534 535 536
  inline explicit constexpr CappedArray(size_t s): currentSize(s) {}

  inline size_t size() const { return currentSize; }
537
  inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; }
538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557
  inline T* begin() { return content; }
  inline T* end() { return content + currentSize; }
  inline const T* begin() const { return content; }
  inline const T* end() const { return content + currentSize; }

  inline operator ArrayPtr<T>() {
    return arrayPtr(content, currentSize);
  }
  inline operator ArrayPtr<const T>() const {
    return arrayPtr(content, currentSize);
  }

  inline T& operator[](size_t index) { return content[index]; }
  inline const T& operator[](size_t index) const { return content[index]; }

private:
  size_t currentSize;
  T content[fixedSize];
};

558
// =======================================================================================
559
// KJ_MAP
560

561
#define KJ_MAP(elementName, array) \
562 563
  ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>(array) * \
  [&](typename ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>::Element elementName)
564 565 566 567
// Applies some function to every element of an array, returning an Array of the results,  with
// nice syntax.  Example:
//
//     StringPtr foo = "abcd";
568
//     Array<char> bar = KJ_MAP(c, foo) -> char { return c + 1; };
569 570 571 572 573 574 575
//     KJ_ASSERT(str(bar) == "bcde");

namespace _ {  // private

template <typename T>
struct Mapper {
  T array;
Kenton Varda's avatar
Kenton Varda committed
576
  Mapper(T&& array): array(kj::fwd<T>(array)) {}
577 578 579 580 581 582 583 584
  template <typename Func>
  auto operator*(Func&& func) -> Array<decltype(func(*array.begin()))> {
    auto builder = heapArrayBuilder<decltype(func(*array.begin()))>(array.size());
    for (auto iter = array.begin(); iter != array.end(); ++iter) {
      builder.add(func(*iter));
    }
    return builder.finish();
  }
585
  typedef decltype(*kj::instance<T>().begin()) Element;
586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
};

template <typename T, size_t s>
struct Mapper<T(&)[s]> {
  T* array;
  Mapper(T* array): array(array) {}
  template <typename Func>
  auto operator*(Func&& func) -> Array<decltype(func(*array))> {
    auto builder = heapArrayBuilder<decltype(func(*array))>(s);
    for (size_t i = 0; i < s; i++) {
      builder.add(func(array[i]));
    }
    return builder.finish();
  }
  typedef decltype(*array)& Element;
601 602 603 604
};

}  // namespace _ (private)

605
// =======================================================================================
Kenton Varda's avatar
Kenton Varda committed
606 607 608 609 610 611
// Inline implementation details

template <typename T>
struct ArrayDisposer::Dispose_<T, true> {
  static void dispose(T* firstElement, size_t elementCount, size_t capacity,
                      const ArrayDisposer& disposer) {
612 613
    disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
                         sizeof(T), elementCount, capacity, nullptr);
Kenton Varda's avatar
Kenton Varda committed
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632
  }
};
template <typename T>
struct ArrayDisposer::Dispose_<T, false> {
  static void destruct(void* ptr) {
    kj::dtor(*reinterpret_cast<T*>(ptr));
  }

  static void dispose(T* firstElement, size_t elementCount, size_t capacity,
                      const ArrayDisposer& disposer) {
    disposer.disposeImpl(firstElement, sizeof(T), elementCount, capacity, &destruct);
  }
};

template <typename T>
void ArrayDisposer::dispose(T* firstElement, size_t elementCount, size_t capacity) const {
  Dispose_<T>::dispose(firstElement, elementCount, capacity, *this);
}

633
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675

template <typename T>
struct HeapArrayDisposer::Allocate_<T, true, true> {
  static T* allocate(size_t elementCount, size_t capacity) {
    return reinterpret_cast<T*>(allocateImpl(
        sizeof(T), elementCount, capacity, nullptr, nullptr));
  }
};
template <typename T>
struct HeapArrayDisposer::Allocate_<T, false, true> {
  static void construct(void* ptr) {
    kj::ctor(*reinterpret_cast<T*>(ptr));
  }
  static T* allocate(size_t elementCount, size_t capacity) {
    return reinterpret_cast<T*>(allocateImpl(
        sizeof(T), elementCount, capacity, &construct, nullptr));
  }
};
template <typename T>
struct HeapArrayDisposer::Allocate_<T, false, false> {
  static void construct(void* ptr) {
    kj::ctor(*reinterpret_cast<T*>(ptr));
  }
  static void destruct(void* ptr) {
    kj::dtor(*reinterpret_cast<T*>(ptr));
  }
  static T* allocate(size_t elementCount, size_t capacity) {
    return reinterpret_cast<T*>(allocateImpl(
        sizeof(T), elementCount, capacity, &construct, &destruct));
  }
};

template <typename T>
T* HeapArrayDisposer::allocate(size_t count) {
  return Allocate_<T>::allocate(count, count);
}

template <typename T>
T* HeapArrayDisposer::allocateUninitialized(size_t count) {
  return Allocate_<T, true, true>::allocate(0, count);
}

676
template <typename Element, typename Iterator, bool move, bool = canMemcpy<Element>()>
Kenton Varda's avatar
Kenton Varda committed
677 678
struct CopyConstructArray_;

679 680
template <typename T, bool move>
struct CopyConstructArray_<T, T*, move, true> {
Kenton Varda's avatar
Kenton Varda committed
681
  static inline T* apply(T* __restrict__ pos, T* start, T* end) {
682 683 684
    if (end != start) {
      memcpy(pos, start, reinterpret_cast<byte*>(end) - reinterpret_cast<byte*>(start));
    }
Kenton Varda's avatar
Kenton Varda committed
685 686 687 688 689
    return pos + (end - start);
  }
};

template <typename T>
690
struct CopyConstructArray_<T, const T*, false, true> {
Kenton Varda's avatar
Kenton Varda committed
691
  static inline T* apply(T* __restrict__ pos, const T* start, const T* end) {
692 693 694
    if (end != start) {
      memcpy(pos, start, reinterpret_cast<const byte*>(end) - reinterpret_cast<const byte*>(start));
    }
Kenton Varda's avatar
Kenton Varda committed
695 696 697 698
    return pos + (end - start);
  }
};

699 700
template <typename T, typename Iterator, bool move>
struct CopyConstructArray_<T, Iterator, move, true> {
Kenton Varda's avatar
Kenton Varda committed
701 702 703 704 705 706 707 708 709 710 711 712
  static inline T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
    // Since both the copy constructor and assignment operator are trivial, we know that assignment
    // is equivalent to copy-constructing.  So we can make this case somewhat easier for the
    // compiler to optimize.
    while (start != end) {
      *pos++ = *start++;
    }
    return pos;
  }
};

template <typename T, typename Iterator>
713
struct CopyConstructArray_<T, Iterator, false, false> {
Kenton Varda's avatar
Kenton Varda committed
714 715 716 717
  struct ExceptionGuard {
    T* start;
    T* pos;
    inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
718
    ~ExceptionGuard() noexcept(false) {
Kenton Varda's avatar
Kenton Varda committed
719 720 721 722 723 724 725
      while (pos > start) {
        dtor(*--pos);
      }
    }
  };

  static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
726 727 728 729
    // Verify that T can be *implicitly* constructed from the source values.
    if (false) implicitCast<T>(*start);

    if (noexcept(T(*start))) {
Kenton Varda's avatar
Kenton Varda committed
730
      while (start != end) {
731
        ctor(*pos++, *start++);
Kenton Varda's avatar
Kenton Varda committed
732 733 734 735 736 737
      }
      return pos;
    } else {
      // Crap.  This is complicated.
      ExceptionGuard guard(pos);
      while (start != end) {
738
        ctor(*guard.pos, *start++);
Kenton Varda's avatar
Kenton Varda committed
739 740 741 742 743 744 745 746 747
        ++guard.pos;
      }
      guard.start = guard.pos;
      return guard.pos;
    }
  }
};

template <typename T, typename Iterator>
748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782
struct CopyConstructArray_<T, Iterator, true, false> {
  // Actually move-construct.

  struct ExceptionGuard {
    T* start;
    T* pos;
    inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
    ~ExceptionGuard() noexcept(false) {
      while (pos > start) {
        dtor(*--pos);
      }
    }
  };

  static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
    // Verify that T can be *implicitly* constructed from the source values.
    if (false) implicitCast<T>(kj::mv(*start));

    if (noexcept(T(kj::mv(*start)))) {
      while (start != end) {
        ctor(*pos++, kj::mv(*start++));
      }
      return pos;
    } else {
      // Crap.  This is complicated.
      ExceptionGuard guard(pos);
      while (start != end) {
        ctor(*guard.pos, kj::mv(*start++));
        ++guard.pos;
      }
      guard.start = guard.pos;
      return guard.pos;
    }
  }
};
Kenton Varda's avatar
Kenton Varda committed
783

784
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
785 786

template <typename T>
787
template <typename Iterator, bool move>
Kenton Varda's avatar
Kenton Varda committed
788
void ArrayBuilder<T>::addAll(Iterator start, Iterator end) {
789
  pos = _::CopyConstructArray_<RemoveConst<T>, Decay<Iterator>, move>::apply(pos, start, end);
Kenton Varda's avatar
Kenton Varda committed
790 791
}

Kenton Varda's avatar
Kenton Varda committed
792 793 794 795 796 797 798
template <typename T>
Array<T> heapArray(const T* content, size_t size) {
  ArrayBuilder<T> builder = heapArrayBuilder<T>(size);
  builder.addAll(content, content + size);
  return builder.finish();
}

799 800 801 802 803 804 805
template <typename T>
Array<T> heapArray(T* content, size_t size) {
  ArrayBuilder<T> builder = heapArrayBuilder<T>(size);
  builder.addAll(content, content + size);
  return builder.finish();
}

806 807 808 809 810 811 812
template <typename T>
Array<T> heapArray(ArrayPtr<T> content) {
  ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size());
  builder.addAll(content);
  return builder.finish();
}

Kenton Varda's avatar
Kenton Varda committed
813 814 815 816 817 818 819 820 821 822 823 824 825 826
template <typename T>
Array<T> heapArray(ArrayPtr<const T> content) {
  ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size());
  builder.addAll(content);
  return builder.finish();
}

template <typename T, typename Iterator> Array<T>
heapArray(Iterator begin, Iterator end) {
  ArrayBuilder<T> builder = heapArrayBuilder<T>(end - begin);
  builder.addAll(begin, end);
  return builder.finish();
}

827 828 829 830 831
template <typename T>
inline Array<T> heapArray(std::initializer_list<T> init) {
  return heapArray<T>(init.begin(), init.end());
}

832 833 834 835 836 837 838 839 840
#if __cplusplus > 201402L
template <typename T, typename... Params>
inline Array<Decay<T>> arr(T&& param1, Params&&... params) {
  ArrayBuilder<Decay<T>> builder = heapArrayBuilder<Decay<T>>(sizeof...(params) + 1);
  (builder.add(kj::fwd<T>(param1)), ... , builder.add(kj::fwd<Params>(params)));
  return builder.finish();
}
#endif

841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872
namespace _ {  // private

template <typename... T>
struct ArrayDisposableOwnedBundle final: public ArrayDisposer, public OwnedBundle<T...> {
  ArrayDisposableOwnedBundle(T&&... values): OwnedBundle<T...>(kj::fwd<T>(values)...) {}
  void disposeImpl(void*, size_t, size_t, size_t, void (*)(void*)) const override { delete this; }
};

}  // namespace _ (private)

template <typename T>
template <typename... Attachments>
Array<T> Array<T>::attach(Attachments&&... attachments) {
  T* ptrCopy = ptr;

  KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");

  // HACK: If someone accidentally calls .attach() on a null pointer in opt mode, try our best to
  //   accomplish reasonable behavior: We turn the pointer non-null but still invalid, so that the
  //   disposer will still be called when the pointer goes out of scope.
  if (ptrCopy == nullptr) ptrCopy = reinterpret_cast<T*>(1);

  auto bundle = new _::ArrayDisposableOwnedBundle<Array<T>, Attachments...>(
      kj::mv(*this), kj::fwd<Attachments>(attachments)...);
  return Array<T>(ptrCopy, size_, *bundle);
}

template <typename T>
template <typename... Attachments>
Array<T> ArrayPtr<T>::attach(Attachments&&... attachments) const {
  T* ptrCopy = ptr;

873
  KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");
874 875 876 877 878 879 880 881

  // HACK: If someone accidentally calls .attach() on a null pointer in opt mode, try our best to
  //   accomplish reasonable behavior: We turn the pointer non-null but still invalid, so that the
  //   disposer will still be called when the pointer goes out of scope.
  if (ptrCopy == nullptr) ptrCopy = reinterpret_cast<T*>(1);

  auto bundle = new _::ArrayDisposableOwnedBundle<Attachments...>(
      kj::fwd<Attachments>(attachments)...);
882
  return Array<T>(ptrCopy, size_, *bundle);
883 884
}

885
}  // namespace kj