array.h 29.8 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
#include "memory.h"
25
#include <string.h>
26
#include <initializer_list>
27

28 29
KJ_BEGIN_HEADER

30 31
namespace kj {

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

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

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

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

63 64 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
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*);
};

102 103 104 105 106 107 108 109
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;
};

110 111 112 113 114 115 116 117 118 119 120
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;
};

121 122 123 124 125
// =======================================================================================
// Array

template <typename T>
class Array {
Kenton Varda's avatar
Kenton Varda committed
126 127 128
  // 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.
129 130

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

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

  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
158 159 160
  inline ArrayPtr<const T> asPtr() const {
    return ArrayPtr<T>(ptr, size_);
  }
161 162

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

Kenton Varda's avatar
Kenton Varda committed
172 173 174 175 176 177 178 179
  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); }
180

181 182 183 184 185
  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; }

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

195 196 197 198 199
  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(); }

200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
  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;
  }

221 222 223 224
  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
225
    dispose();
226 227 228 229
    return *this;
  }

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

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

243 244 245
private:
  T* ptr;
  size_t size_;
Kenton Varda's avatar
Kenton Varda committed
246 247 248 249 250 251 252 253 254 255 256 257 258
  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);
    }
  }
259 260 261

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

266 267
static_assert(!canMemcpy<Array<char>>(), "canMemcpy<>() is broken");

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

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

Kenton Varda's avatar
Kenton Varda committed
277 278 279
  static const HeapArrayDisposer instance;

private:
Kenton Varda's avatar
Kenton Varda committed
280 281 282 283 284 285 286 287
  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
288 289 290
  template <typename T, bool hasTrivialConstructor = __has_trivial_constructor(T),
                        bool hasNothrowConstructor = __has_nothrow_constructor(T)>
  struct Allocate_;
291 292
};

293
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
294

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

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

Kenton Varda's avatar
Kenton Varda committed
303
template <typename T> Array<T> heapArray(const T* content, size_t size);
304
template <typename T> Array<T> heapArray(ArrayPtr<T> content);
Kenton Varda's avatar
Kenton Varda committed
305 306
template <typename T> Array<T> heapArray(ArrayPtr<const T> content);
template <typename T, typename Iterator> Array<T> heapArray(Iterator begin, Iterator end);
307 308
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
309

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

315 316 317 318 319
// =======================================================================================
// ArrayBuilder

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

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

  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);
  }
355 356 357
  inline ArrayPtr<const T> asPtr() const {
    return arrayPtr(ptr, pos);
  }
Kenton Varda's avatar
Kenton Varda committed
358 359 360

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

  template <typename... Params>
Kenton Varda's avatar
Kenton Varda committed
396
  T& add(Params&&... params) {
Kenton Varda's avatar
Kenton Varda committed
397
    KJ_IREQUIRE(pos < endPtr, "Added too many elements to ArrayBuilder.");
Kenton Varda's avatar
Kenton Varda committed
398
    ctor(*pos, kj::fwd<Params>(params)...);
Kenton Varda's avatar
Kenton Varda committed
399
    return *pos++;
400 401 402 403
  }

  template <typename Container>
  void addAll(Container&& container) {
404 405
    addAll<decltype(container.begin()), !isReference<Container>()>(
        container.begin(), container.end());
406 407
  }

408
  template <typename Iterator, bool move = false>
Kenton Varda's avatar
Kenton Varda committed
409 410
  void addAll(Iterator start, Iterator end);

411 412 413 414 415
  void removeLast() {
    KJ_IREQUIRE(pos > ptr, "No elements present to remove.");
    kj::dtor(*--pos);
  }

416 417 418 419 420 421 422 423 424 425 426 427 428
  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);
      }
    }
  }

429 430 431 432 433 434 435 436 437 438
  void clear() {
    if (__has_trivial_destructor(T)) {
      pos = ptr;
    } else {
      while (pos > ptr) {
        kj::dtor(*--pos);
      }
    }
  }

439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
  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);
        }
      }
    }
  }

464
  Array<T> finish() {
465
    // We could safely remove this check if we assume that the disposer implementation doesn't
466
    // need to know the original capacity, as is the case with HeapArrayDisposer since it uses
467 468 469 470
    // 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
471
    KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely.");
472
    Array<T> result(reinterpret_cast<T*>(ptr), pos - ptr, *disposer);
473 474 475
    ptr = nullptr;
    pos = nullptr;
    endPtr = nullptr;
476
    return result;
477 478
  }

479 480 481 482
  inline bool isFull() const {
    return pos == endPtr;
  }

483
private:
Kenton Varda's avatar
Kenton Varda committed
484
  T* ptr;
485
  RemoveConst<T>* pos;
Kenton Varda's avatar
Kenton Varda committed
486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501
  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);
    }
  }
502 503
};

Kenton Varda's avatar
Kenton Varda committed
504 505 506 507 508
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()`.

509 510
  return ArrayBuilder<T>(_::HeapArrayDisposer::allocateUninitialized<RemoveConst<T>>(size),
                         size, _::HeapArrayDisposer::instance);
Kenton Varda's avatar
Kenton Varda committed
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 543 544 545 546 547 548
// 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:
549
  inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {}
550 551 552
  inline explicit constexpr CappedArray(size_t s): currentSize(s) {}

  inline size_t size() const { return currentSize; }
553
  inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; }
554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573
  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];
};

574
// =======================================================================================
575
// KJ_MAP
576

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

namespace _ {  // private

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

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;
617 618 619 620
};

}  // namespace _ (private)

621
// =======================================================================================
Kenton Varda's avatar
Kenton Varda committed
622 623 624 625 626 627
// 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) {
628 629
    disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
                         sizeof(T), elementCount, capacity, nullptr);
Kenton Varda's avatar
Kenton Varda committed
630 631 632 633 634 635 636 637 638 639
  }
};
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) {
640 641
    disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
                         sizeof(T), elementCount, capacity, &destruct);
Kenton Varda's avatar
Kenton Varda committed
642 643 644 645 646 647 648 649
  }
};

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

650
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
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 686 687 688 689 690 691 692

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

693
template <typename Element, typename Iterator, bool move, bool = canMemcpy<Element>()>
Kenton Varda's avatar
Kenton Varda committed
694 695
struct CopyConstructArray_;

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

template <typename T>
707
struct CopyConstructArray_<T, const T*, false, true> {
Kenton Varda's avatar
Kenton Varda committed
708
  static inline T* apply(T* __restrict__ pos, const T* start, const T* end) {
709 710 711
    if (end != start) {
      memcpy(pos, start, reinterpret_cast<const byte*>(end) - reinterpret_cast<const byte*>(start));
    }
Kenton Varda's avatar
Kenton Varda committed
712 713 714 715
    return pos + (end - start);
  }
};

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

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

template <typename T, typename Iterator>
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 793 794 795 796 797 798 799
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
800

801
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
802 803

template <typename T>
804
template <typename Iterator, bool move>
Kenton Varda's avatar
Kenton Varda committed
805
void ArrayBuilder<T>::addAll(Iterator start, Iterator end) {
806
  pos = _::CopyConstructArray_<RemoveConst<T>, Decay<Iterator>, move>::apply(pos, start, end);
Kenton Varda's avatar
Kenton Varda committed
807 808
}

Kenton Varda's avatar
Kenton Varda committed
809 810 811 812 813 814 815
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();
}

816 817 818 819 820 821 822
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();
}

823 824 825 826 827 828 829
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
830 831 832 833 834 835 836 837 838 839 840 841 842 843
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();
}

844 845 846 847 848
template <typename T>
inline Array<T> heapArray(std::initializer_list<T> init) {
  return heapArray<T>(init.begin(), init.end());
}

849 850 851 852 853 854 855 856 857
#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

858 859 860 861 862 863 864 865 866 867 868 869 870 871
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;
872
  auto sizeCopy = size_;
873 874 875 876 877 878 879 880 881 882

  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)...);
883
  return Array<T>(ptrCopy, sizeCopy, *bundle);
884 885 886 887 888 889 890
}

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

891
  KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");
892 893 894 895 896 897 898 899

  // 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)...);
900
  return Array<T>(ptrCopy, size_, *bundle);
901 902
}

903
}  // namespace kj
904 905

KJ_END_HEADER