array.h 29.4 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
  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);
      }
    }
  }

423 424 425 426 427 428 429 430 431 432
  void clear() {
    if (__has_trivial_destructor(T)) {
      pos = ptr;
    } else {
      while (pos > ptr) {
        kj::dtor(*--pos);
      }
    }
  }

433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
  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);
        }
      }
    }
  }

458
  Array<T> finish() {
459 460 461 462 463 464
    // 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
465
    KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely.");
466
    Array<T> result(reinterpret_cast<T*>(ptr), pos - ptr, *disposer);
467 468 469
    ptr = nullptr;
    pos = nullptr;
    endPtr = nullptr;
470
    return result;
471 472
  }

473 474 475 476
  inline bool isFull() const {
    return pos == endPtr;
  }

477
private:
Kenton Varda's avatar
Kenton Varda committed
478
  T* ptr;
479
  RemoveConst<T>* pos;
Kenton Varda's avatar
Kenton Varda committed
480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
  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);
    }
  }
496 497
};

Kenton Varda's avatar
Kenton Varda committed
498 499 500 501 502
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()`.

503 504
  return ArrayBuilder<T>(_::HeapArrayDisposer::allocateUninitialized<RemoveConst<T>>(size),
                         size, _::HeapArrayDisposer::instance);
Kenton Varda's avatar
Kenton Varda committed
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 533 534 535 536 537 538 539 540 541 542
// 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:
543
  inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {}
544 545 546
  inline explicit constexpr CappedArray(size_t s): currentSize(s) {}

  inline size_t size() const { return currentSize; }
547
  inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; }
548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567
  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];
};

568
// =======================================================================================
569
// KJ_MAP
570

571
#define KJ_MAP(elementName, array) \
572 573
  ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>(array) * \
  [&](typename ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>::Element elementName)
574 575 576 577
// Applies some function to every element of an array, returning an Array of the results,  with
// nice syntax.  Example:
//
//     StringPtr foo = "abcd";
578
//     Array<char> bar = KJ_MAP(c, foo) -> char { return c + 1; };
579 580 581 582 583 584 585
//     KJ_ASSERT(str(bar) == "bcde");

namespace _ {  // private

template <typename T>
struct Mapper {
  T array;
Kenton Varda's avatar
Kenton Varda committed
586
  Mapper(T&& array): array(kj::fwd<T>(array)) {}
587 588 589 590 591 592 593 594
  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();
  }
595
  typedef decltype(*kj::instance<T>().begin()) Element;
596 597 598 599 600 601 602 603 604 605 606 607 608 609 610
};

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;
611 612 613 614
};

}  // namespace _ (private)

615
// =======================================================================================
Kenton Varda's avatar
Kenton Varda committed
616 617 618 619 620 621
// 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) {
622 623
    disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
                         sizeof(T), elementCount, capacity, nullptr);
Kenton Varda's avatar
Kenton Varda committed
624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642
  }
};
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);
}

643
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
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 676 677 678 679 680 681 682 683 684 685

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);
}

686
template <typename Element, typename Iterator, bool move, bool = canMemcpy<Element>()>
Kenton Varda's avatar
Kenton Varda committed
687 688
struct CopyConstructArray_;

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

template <typename T>
700
struct CopyConstructArray_<T, const T*, false, true> {
Kenton Varda's avatar
Kenton Varda committed
701
  static inline T* apply(T* __restrict__ pos, const T* start, const T* end) {
702 703 704
    if (end != start) {
      memcpy(pos, start, reinterpret_cast<const byte*>(end) - reinterpret_cast<const byte*>(start));
    }
Kenton Varda's avatar
Kenton Varda committed
705 706 707 708
    return pos + (end - start);
  }
};

709 710
template <typename T, typename Iterator, bool move>
struct CopyConstructArray_<T, Iterator, move, true> {
Kenton Varda's avatar
Kenton Varda committed
711 712 713 714 715 716 717 718 719 720 721 722
  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>
723
struct CopyConstructArray_<T, Iterator, false, false> {
Kenton Varda's avatar
Kenton Varda committed
724 725 726 727
  struct ExceptionGuard {
    T* start;
    T* pos;
    inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
728
    ~ExceptionGuard() noexcept(false) {
Kenton Varda's avatar
Kenton Varda committed
729 730 731 732 733 734 735
      while (pos > start) {
        dtor(*--pos);
      }
    }
  };

  static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
736 737 738 739
    // 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
740
      while (start != end) {
741
        ctor(*pos++, *start++);
Kenton Varda's avatar
Kenton Varda committed
742 743 744 745 746 747
      }
      return pos;
    } else {
      // Crap.  This is complicated.
      ExceptionGuard guard(pos);
      while (start != end) {
748
        ctor(*guard.pos, *start++);
Kenton Varda's avatar
Kenton Varda committed
749 750 751 752 753 754 755 756 757
        ++guard.pos;
      }
      guard.start = guard.pos;
      return guard.pos;
    }
  }
};

template <typename T, typename Iterator>
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 783 784 785 786 787 788 789 790 791 792
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
793

794
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
795 796

template <typename T>
797
template <typename Iterator, bool move>
Kenton Varda's avatar
Kenton Varda committed
798
void ArrayBuilder<T>::addAll(Iterator start, Iterator end) {
799
  pos = _::CopyConstructArray_<RemoveConst<T>, Decay<Iterator>, move>::apply(pos, start, end);
Kenton Varda's avatar
Kenton Varda committed
800 801
}

Kenton Varda's avatar
Kenton Varda committed
802 803 804 805 806 807 808
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();
}

809 810 811 812 813 814 815
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();
}

816 817 818 819 820 821 822
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
823 824 825 826 827 828 829 830 831 832 833 834 835 836
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();
}

837 838 839 840 841
template <typename T>
inline Array<T> heapArray(std::initializer_list<T> init) {
  return heapArray<T>(init.begin(), init.end());
}

842 843 844 845 846 847 848 849 850
#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

851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882
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;

883
  KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");
884 885 886 887 888 889 890 891

  // 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)...);
892
  return Array<T>(ptrCopy, size_, *bundle);
893 894
}

895
}  // namespace kj