array.h 23.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 23 24

#ifndef KJ_ARRAY_H_
#define KJ_ARRAY_H_

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

29 30
#include "common.h"
#include <string.h>
31
#include <initializer_list>
32 33 34

namespace kj {

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

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

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

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

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

105 106 107 108 109 110 111 112
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;
};

113 114 115 116 117 118 119 120 121 122 123
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;
};

124 125 126 127 128
// =======================================================================================
// Array

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

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

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

  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
161 162 163
  inline ArrayPtr<const T> asPtr() const {
    return ArrayPtr<T>(ptr, size_);
  }
164 165 166

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

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

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

189 190 191 192 193
  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(); }

194 195 196 197
  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
198
    dispose();
199 200 201 202
    return *this;
  }

  inline Array& operator=(Array&& other) {
Kenton Varda's avatar
Kenton Varda committed
203
    dispose();
204 205
    ptr = other.ptr;
    size_ = other.size_;
Kenton Varda's avatar
Kenton Varda committed
206
    disposer = other.disposer;
207 208 209 210 211 212 213 214
    other.ptr = nullptr;
    other.size_ = 0;
    return *this;
  }

private:
  T* ptr;
  size_t size_;
Kenton Varda's avatar
Kenton Varda committed
215 216 217 218 219 220 221 222 223 224 225 226 227
  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);
    }
  }
228 229 230

  template <typename U>
  friend class Array;
Kenton Varda's avatar
Kenton Varda committed
231 232
};

233
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
234 235 236 237 238 239 240

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

Kenton Varda's avatar
Kenton Varda committed
242 243 244
  static const HeapArrayDisposer instance;

private:
Kenton Varda's avatar
Kenton Varda committed
245 246 247 248 249 250 251 252
  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
253 254 255
  template <typename T, bool hasTrivialConstructor = __has_trivial_constructor(T),
                        bool hasNothrowConstructor = __has_nothrow_constructor(T)>
  struct Allocate_;
256 257
};

258
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
259

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

264 265
  return Array<T>(_::HeapArrayDisposer::allocate<T>(size), size,
                  _::HeapArrayDisposer::instance);
266 267
}

Kenton Varda's avatar
Kenton Varda committed
268
template <typename T> Array<T> heapArray(const T* content, size_t size);
269
template <typename T> Array<T> heapArray(ArrayPtr<T> content);
Kenton Varda's avatar
Kenton Varda committed
270 271
template <typename T> Array<T> heapArray(ArrayPtr<const T> content);
template <typename T, typename Iterator> Array<T> heapArray(Iterator begin, Iterator end);
272 273
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
274

275 276 277 278 279
template <typename T, typename Container>
Array<T> heapArrayFromIterable(Container&& a) { return heapArray(a.begin(), a.end()); }
template <typename T>
Array<T> heapArrayFromIterable(Array<T>&& a) { return mv(a); }

280 281 282 283 284
// =======================================================================================
// ArrayBuilder

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

public:
Kenton Varda's avatar
Kenton Varda committed
289 290
  ArrayBuilder(): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
  ArrayBuilder(decltype(nullptr)): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
291 292
  explicit ArrayBuilder(RemoveConst<T>* firstElement, size_t capacity,
                        const ArrayDisposer& disposer)
Kenton Varda's avatar
Kenton Varda committed
293 294 295 296 297 298 299 300 301
      : 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;
  }
  KJ_DISALLOW_COPY(ArrayBuilder);
302
  inline ~ArrayBuilder() noexcept(false) { dispose(); }
Kenton Varda's avatar
Kenton Varda committed
303 304 305 306 307 308 309 310 311 312

  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);
  }
313 314 315
  inline ArrayPtr<const T> asPtr() const {
    return arrayPtr(ptr, pos);
  }
Kenton Varda's avatar
Kenton Varda committed
316 317 318 319

  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
320
    KJ_IREQUIRE(index < implicitCast<size_t>(pos - ptr), "Out-of-bounds Array access.");
Kenton Varda's avatar
Kenton Varda committed
321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
    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;
347 348 349
  }

  template <typename... Params>
Kenton Varda's avatar
Kenton Varda committed
350
  T& add(Params&&... params) {
Kenton Varda's avatar
Kenton Varda committed
351
    KJ_IREQUIRE(pos < endPtr, "Added too many elements to ArrayBuilder.");
Kenton Varda's avatar
Kenton Varda committed
352
    ctor(*pos, kj::fwd<Params>(params)...);
Kenton Varda's avatar
Kenton Varda committed
353
    return *pos++;
354 355 356 357
  }

  template <typename Container>
  void addAll(Container&& container) {
Kenton Varda's avatar
Kenton Varda committed
358
    addAll(container.begin(), container.end());
359 360
  }

Kenton Varda's avatar
Kenton Varda committed
361 362 363
  template <typename Iterator>
  void addAll(Iterator start, Iterator end);

364 365 366 367 368
  void removeLast() {
    KJ_IREQUIRE(pos > ptr, "No elements present to remove.");
    kj::dtor(*--pos);
  }

369
  Array<T> finish() {
370 371 372 373 374 375
    // 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
376
    KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely.");
377
    Array<T> result(reinterpret_cast<T*>(ptr), pos - ptr, *disposer);
378 379 380 381 382 383
    ptr = nullptr;
    pos = nullptr;
    endPtr = nullptr;
    return result;
  }

384 385 386 387
  inline bool isFull() const {
    return pos == endPtr;
  }

388
private:
Kenton Varda's avatar
Kenton Varda committed
389
  T* ptr;
390
  RemoveConst<T>* pos;
Kenton Varda's avatar
Kenton Varda committed
391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406
  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);
    }
  }
407 408
};

Kenton Varda's avatar
Kenton Varda committed
409 410 411 412 413
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()`.

414 415
  return ArrayBuilder<T>(_::HeapArrayDisposer::allocateUninitialized<RemoveConst<T>>(size),
                         size, _::HeapArrayDisposer::instance);
Kenton Varda's avatar
Kenton Varda committed
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 448 449 450 451 452 453
// 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:
454
  inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {}
455 456 457
  inline explicit constexpr CappedArray(size_t s): currentSize(s) {}

  inline size_t size() const { return currentSize; }
458
  inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; }
459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478
  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];
};

479
// =======================================================================================
480
// KJ_MAP
481

482
#define KJ_MAP(elementName, array) \
Kenton Varda's avatar
Kenton Varda committed
483
  ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>(array) * [&](decltype(*(array).begin()) elementName)
484 485 486 487
// Applies some function to every element of an array, returning an Array of the results,  with
// nice syntax.  Example:
//
//     StringPtr foo = "abcd";
488
//     Array<char> bar = KJ_MAP(c, foo) -> char { return c + 1; };
489 490 491 492 493 494 495
//     KJ_ASSERT(str(bar) == "bcde");

namespace _ {  // private

template <typename T>
struct Mapper {
  T array;
Kenton Varda's avatar
Kenton Varda committed
496
  Mapper(T&& array): array(kj::fwd<T>(array)) {}
497 498 499 500 501 502 503 504 505 506 507 508
  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();
  }
};

}  // namespace _ (private)

509
// =======================================================================================
Kenton Varda's avatar
Kenton Varda committed
510 511 512 513 514 515
// 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) {
516 517
    disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
                         sizeof(T), elementCount, capacity, nullptr);
Kenton Varda's avatar
Kenton Varda committed
518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
  }
};
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);
}

537
namespace _ {  // private
Kenton Varda's avatar
Kenton Varda committed
538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579

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

580
template <typename Element, typename Iterator, bool = canMemcpy<Element>()>
Kenton Varda's avatar
Kenton Varda committed
581 582 583 584 585
struct CopyConstructArray_;

template <typename T>
struct CopyConstructArray_<T, T*, true> {
  static inline T* apply(T* __restrict__ pos, T* start, T* end) {
586
    memcpy(pos, start, reinterpret_cast<byte*>(end) - reinterpret_cast<byte*>(start));
Kenton Varda's avatar
Kenton Varda committed
587 588 589 590 591 592 593
    return pos + (end - start);
  }
};

template <typename T>
struct CopyConstructArray_<T, const T*, true> {
  static inline T* apply(T* __restrict__ pos, const T* start, const T* end) {
594
    memcpy(pos, start, reinterpret_cast<const byte*>(end) - reinterpret_cast<const byte*>(start));
Kenton Varda's avatar
Kenton Varda committed
595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
    return pos + (end - start);
  }
};

template <typename T, typename Iterator>
struct CopyConstructArray_<T, Iterator, true> {
  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>
struct CopyConstructArray_<T, Iterator, false> {
  struct ExceptionGuard {
    T* start;
    T* pos;
    inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
618
    ~ExceptionGuard() noexcept(false) {
Kenton Varda's avatar
Kenton Varda committed
619 620 621 622 623 624 625
      while (pos > start) {
        dtor(*--pos);
      }
    }
  };

  static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
626 627 628 629
    // 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
630
      while (start != end) {
631
        ctor(*pos++, *start++);
Kenton Varda's avatar
Kenton Varda committed
632 633 634 635 636 637
      }
      return pos;
    } else {
      // Crap.  This is complicated.
      ExceptionGuard guard(pos);
      while (start != end) {
638
        ctor(*guard.pos, *start++);
Kenton Varda's avatar
Kenton Varda committed
639 640 641 642 643 644 645 646 647 648
        ++guard.pos;
      }
      guard.start = guard.pos;
      return guard.pos;
    }
  }
};

template <typename T, typename Iterator>
inline T* copyConstructArray(T* dst, Iterator start, Iterator end) {
649
  return CopyConstructArray_<T, Decay<Iterator>>::apply(dst, start, end);
Kenton Varda's avatar
Kenton Varda committed
650 651
}

652
}  // namespace _ (private)
Kenton Varda's avatar
Kenton Varda committed
653 654 655 656

template <typename T>
template <typename Iterator>
void ArrayBuilder<T>::addAll(Iterator start, Iterator end) {
657
  pos = _::copyConstructArray(pos, start, end);
Kenton Varda's avatar
Kenton Varda committed
658 659
}

Kenton Varda's avatar
Kenton Varda committed
660 661 662 663 664 665 666
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();
}

667 668 669 670 671 672 673
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();
}

674 675 676 677 678 679 680
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
681 682 683 684 685 686 687 688 689 690 691 692 693 694
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();
}

695 696 697 698 699
template <typename T>
inline Array<T> heapArray(std::initializer_list<T> init) {
  return heapArray<T>(init.begin(), init.end());
}

700 701 702
}  // namespace kj

#endif  // KJ_ARRAY_H_