1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22#pragma once
23
24#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
25#pragma GCC system_header
26#endif
27
28#include "memory.h"
29#include <string.h>
30#include <initializer_list>
31
32namespace kj {
33
34// =======================================================================================
35// ArrayDisposer -- Implementation details.
36
37class ArrayDisposer {
38 // Much like Disposer from memory.h.
39
40protected:
41 // Do not declare a destructor, as doing so will force a global initializer for
42 // HeapArrayDisposer::instance.
43
44 virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
45 size_t capacity, void (*destroyElement)(void*)) const = 0;
46 // Disposes of the array. `destroyElement` invokes the destructor of each element, or is nullptr
47 // if the elements have trivial destructors. `capacity` is the amount of space that was
48 // allocated while `elementCount` is the number of elements that were actually constructed;
49 // these are always the same number for Array<T> but may be different when using ArrayBuilder<T>.
50
51public:
52
53 template <typename T>
54 void dispose(T* firstElement, size_t elementCount, size_t capacity) const;
55 // Helper wrapper around disposeImpl().
56 //
57 // Callers must not call dispose() on the same array twice, even if the first call throws
58 // an exception.
59
60private:
61 template <typename T, bool hasTrivialDestructor = __has_trivial_destructor(T)>
62 struct Dispose_;
63};
64
65class ExceptionSafeArrayUtil {
66 // Utility class that assists in constructing or destroying elements of an array, where the
67 // constructor or destructor could throw exceptions. In case of an exception,
68 // ExceptionSafeArrayUtil's destructor will call destructors on all elements that have been
69 // constructed but not destroyed. Remember that destructors that throw exceptions are required
70 // to use UnwindDetector to detect unwind and avoid exceptions in this case. Therefore, no more
71 // than one exception will be thrown (and the program will not terminate).
72
73public:
74 inline ExceptionSafeArrayUtil(void* ptr, size_t elementSize, size_t constructedElementCount,
75 void (*destroyElement)(void*))
76 : pos(reinterpret_cast<byte*>(ptr) + elementSize * constructedElementCount),
77 elementSize(elementSize), constructedElementCount(constructedElementCount),
78 destroyElement(destroyElement) {}
79 KJ_DISALLOW_COPY(ExceptionSafeArrayUtil);
80
81 inline ~ExceptionSafeArrayUtil() noexcept(false) {
82 if (constructedElementCount > 0) destroyAll();
83 }
84
85 void construct(size_t count, void (*constructElement)(void*));
86 // Construct the given number of elements.
87
88 void destroyAll();
89 // Destroy all elements. Call this immediately before ExceptionSafeArrayUtil goes out-of-scope
90 // to ensure that one element throwing an exception does not prevent the others from being
91 // destroyed.
92
93 void release() { constructedElementCount = 0; }
94 // Prevent ExceptionSafeArrayUtil's destructor from destroying the constructed elements.
95 // Call this after you've successfully finished constructing.
96
97private:
98 byte* pos;
99 size_t elementSize;
100 size_t constructedElementCount;
101 void (*destroyElement)(void*);
102};
103
104class DestructorOnlyArrayDisposer: public ArrayDisposer {
105public:
106 static const DestructorOnlyArrayDisposer instance;
107
108 void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
109 size_t capacity, void (*destroyElement)(void*)) const override;
110};
111
112class NullArrayDisposer: public ArrayDisposer {
113 // An ArrayDisposer that does nothing. Can be used to construct a fake Arrays that doesn't
114 // actually own its content.
115
116public:
117 static const NullArrayDisposer instance;
118
119 void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
120 size_t capacity, void (*destroyElement)(void*)) const override;
121};
122
123// =======================================================================================
124// Array
125
126template <typename T>
127class Array {
128 // An owned array which will automatically be disposed of (using an ArrayDisposer) in the
129 // destructor. Can be moved, but not copied. Much like Own<T>, but for arrays rather than
130 // single objects.
131
132public:
133 inline Array(): ptr(nullptr), size_(0), disposer(nullptr) {}
134 inline Array(decltype(nullptr)): ptr(nullptr), size_(0), disposer(nullptr) {}
135 inline Array(Array&& other) noexcept
136 : ptr(other.ptr), size_(other.size_), disposer(other.disposer) {
137 other.ptr = nullptr;
138 other.size_ = 0;
139 }
140 inline Array(Array<RemoveConstOrDisable<T>>&& other) noexcept
141 : ptr(other.ptr), size_(other.size_), disposer(other.disposer) {
142 other.ptr = nullptr;
143 other.size_ = 0;
144 }
145 inline Array(T* firstElement, size_t size, const ArrayDisposer& disposer)
146 : ptr(firstElement), size_(size), disposer(&disposer) {}
147
148 KJ_DISALLOW_COPY(Array);
149 inline ~Array() noexcept { dispose(); }
150
151 inline operator ArrayPtr<T>() {
152 return ArrayPtr<T>(ptr, size_);
153 }
154 inline operator ArrayPtr<const T>() const {
155 return ArrayPtr<T>(ptr, size_);
156 }
157 inline ArrayPtr<T> asPtr() {
158 return ArrayPtr<T>(ptr, size_);
159 }
160 inline ArrayPtr<const T> asPtr() const {
161 return ArrayPtr<T>(ptr, size_);
162 }
163
164 inline size_t size() const { return size_; }
165 inline T& operator[](size_t index) const {
166 KJ_IREQUIRE(index < size_, "Out-of-bounds Array access.");
167 return ptr[index];
168 }
169
170 inline const T* begin() const { return ptr; }
171 inline const T* end() const { return ptr + size_; }
172 inline const T& front() const { return *ptr; }
173 inline const T& back() const { return *(ptr + size_ - 1); }
174 inline T* begin() { return ptr; }
175 inline T* end() { return ptr + size_; }
176 inline T& front() { return *ptr; }
177 inline T& back() { return *(ptr + size_ - 1); }
178
179 template <typename U>
180 inline bool operator==(const U& other) const { return asPtr() == other; }
181 template <typename U>
182 inline bool operator!=(const U& other) const { return asPtr() != other; }
183
184 inline ArrayPtr<T> slice(size_t start, size_t end) {
185 KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice().");
186 return ArrayPtr<T>(ptr + start, end - start);
187 }
188 inline ArrayPtr<const T> slice(size_t start, size_t end) const {
189 KJ_IREQUIRE(start <= end && end <= size_, "Out-of-bounds Array::slice().");
190 return ArrayPtr<const T>(ptr + start, end - start);
191 }
192
193 inline ArrayPtr<const byte> asBytes() const { return asPtr().asBytes(); }
194 inline ArrayPtr<PropagateConst<T, byte>> asBytes() { return asPtr().asBytes(); }
195 inline ArrayPtr<const char> asChars() const { return asPtr().asChars(); }
196 inline ArrayPtr<PropagateConst<T, char>> asChars() { return asPtr().asChars(); }
197
198 inline Array<PropagateConst<T, byte>> releaseAsBytes() {
199 // Like asBytes() but transfers ownership.
200 static_assert(sizeof(T) == sizeof(byte),
201 "releaseAsBytes() only possible on arrays with byte-size elements (e.g. chars).");
202 Array<PropagateConst<T, byte>> result(
203 reinterpret_cast<PropagateConst<T, byte>*>(ptr), size_, *disposer);
204 ptr = nullptr;
205 size_ = 0;
206 return result;
207 }
208 inline Array<PropagateConst<T, char>> releaseAsChars() {
209 // Like asChars() but transfers ownership.
210 static_assert(sizeof(T) == sizeof(PropagateConst<T, char>),
211 "releaseAsChars() only possible on arrays with char-size elements (e.g. bytes).");
212 Array<PropagateConst<T, char>> result(
213 reinterpret_cast<PropagateConst<T, char>*>(ptr), size_, *disposer);
214 ptr = nullptr;
215 size_ = 0;
216 return result;
217 }
218
219 inline bool operator==(decltype(nullptr)) const { return size_ == 0; }
220 inline bool operator!=(decltype(nullptr)) const { return size_ != 0; }
221
222 inline Array& operator=(decltype(nullptr)) {
223 dispose();
224 return *this;
225 }
226
227 inline Array& operator=(Array&& other) {
228 dispose();
229 ptr = other.ptr;
230 size_ = other.size_;
231 disposer = other.disposer;
232 other.ptr = nullptr;
233 other.size_ = 0;
234 return *this;
235 }
236
237 template <typename... Attachments>
238 Array<T> attach(Attachments&&... attachments) KJ_WARN_UNUSED_RESULT;
239 // Like Own<T>::attach(), but attaches to an Array.
240
241private:
242 T* ptr;
243 size_t size_;
244 const ArrayDisposer* disposer;
245
246 inline void dispose() {
247 // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly
248 // dispose again.
249 T* ptrCopy = ptr;
250 size_t sizeCopy = size_;
251 if (ptrCopy != nullptr) {
252 ptr = nullptr;
253 size_ = 0;
254 disposer->dispose(ptrCopy, sizeCopy, sizeCopy);
255 }
256 }
257
258 template <typename U>
259 friend class Array;
260 template <typename U>
261 friend class ArrayBuilder;
262};
263
264static_assert(!canMemcpy<Array<char>>(), "canMemcpy<>() is broken");
265
266namespace _ { // private
267
268class HeapArrayDisposer final: public ArrayDisposer {
269public:
270 template <typename T>
271 static T* allocate(size_t count);
272 template <typename T>
273 static T* allocateUninitialized(size_t count);
274
275 static const HeapArrayDisposer instance;
276
277private:
278 static void* allocateImpl(size_t elementSize, size_t elementCount, size_t capacity,
279 void (*constructElement)(void*), void (*destroyElement)(void*));
280 // Allocates and constructs the array. Both function pointers are null if the constructor is
281 // trivial, otherwise destroyElement is null if the constructor doesn't throw.
282
283 virtual void disposeImpl(void* firstElement, size_t elementSize, size_t elementCount,
284 size_t capacity, void (*destroyElement)(void*)) const override;
285
286 template <typename T, bool hasTrivialConstructor = __has_trivial_constructor(T),
287 bool hasNothrowConstructor = __has_nothrow_constructor(T)>
288 struct Allocate_;
289};
290
291} // namespace _ (private)
292
293template <typename T>
294inline Array<T> heapArray(size_t size) {
295 // Much like `heap<T>()` from memory.h, allocates a new array on the heap.
296
297 return Array<T>(_::HeapArrayDisposer::allocate<T>(size), size,
298 _::HeapArrayDisposer::instance);
299}
300
301template <typename T> Array<T> heapArray(const T* content, size_t size);
302template <typename T> Array<T> heapArray(ArrayPtr<T> content);
303template <typename T> Array<T> heapArray(ArrayPtr<const T> content);
304template <typename T, typename Iterator> Array<T> heapArray(Iterator begin, Iterator end);
305template <typename T> Array<T> heapArray(std::initializer_list<T> init);
306// Allocate a heap array containing a copy of the given content.
307
308template <typename T, typename Container>
309Array<T> heapArrayFromIterable(Container&& a) { return heapArray<T>(a.begin(), a.end()); }
310template <typename T>
311Array<T> heapArrayFromIterable(Array<T>&& a) { return mv(a); }
312
313// =======================================================================================
314// ArrayBuilder
315
316template <typename T>
317class ArrayBuilder {
318 // Class which lets you build an Array<T> specifying the exact constructor arguments for each
319 // element, rather than starting by default-constructing them.
320
321public:
322 ArrayBuilder(): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
323 ArrayBuilder(decltype(nullptr)): ptr(nullptr), pos(nullptr), endPtr(nullptr) {}
324 explicit ArrayBuilder(RemoveConst<T>* firstElement, size_t capacity,
325 const ArrayDisposer& disposer)
326 : ptr(firstElement), pos(firstElement), endPtr(firstElement + capacity),
327 disposer(&disposer) {}
328 ArrayBuilder(ArrayBuilder&& other)
329 : ptr(other.ptr), pos(other.pos), endPtr(other.endPtr), disposer(other.disposer) {
330 other.ptr = nullptr;
331 other.pos = nullptr;
332 other.endPtr = nullptr;
333 }
334 ArrayBuilder(Array<T>&& other)
335 : ptr(other.ptr), pos(other.ptr + other.size_), endPtr(pos), disposer(other.disposer) {
336 // Create an already-full ArrayBuilder from an Array of the same type. This constructor
337 // primarily exists to enable Vector<T> to be constructed from Array<T>.
338 other.ptr = nullptr;
339 other.size_ = 0;
340 }
341 KJ_DISALLOW_COPY(ArrayBuilder);
342 inline ~ArrayBuilder() noexcept(false) { dispose(); }
343
344 inline operator ArrayPtr<T>() {
345 return arrayPtr(ptr, pos);
346 }
347 inline operator ArrayPtr<const T>() const {
348 return arrayPtr(ptr, pos);
349 }
350 inline ArrayPtr<T> asPtr() {
351 return arrayPtr(ptr, pos);
352 }
353 inline ArrayPtr<const T> asPtr() const {
354 return arrayPtr(ptr, pos);
355 }
356
357 inline size_t size() const { return pos - ptr; }
358 inline size_t capacity() const { return endPtr - ptr; }
359 inline T& operator[](size_t index) const {
360 KJ_IREQUIRE(index < implicitCast<size_t>(pos - ptr), "Out-of-bounds Array access.");
361 return ptr[index];
362 }
363
364 inline const T* begin() const { return ptr; }
365 inline const T* end() const { return pos; }
366 inline const T& front() const { return *ptr; }
367 inline const T& back() const { return *(pos - 1); }
368 inline T* begin() { return ptr; }
369 inline T* end() { return pos; }
370 inline T& front() { return *ptr; }
371 inline T& back() { return *(pos - 1); }
372
373 ArrayBuilder& operator=(ArrayBuilder&& other) {
374 dispose();
375 ptr = other.ptr;
376 pos = other.pos;
377 endPtr = other.endPtr;
378 disposer = other.disposer;
379 other.ptr = nullptr;
380 other.pos = nullptr;
381 other.endPtr = nullptr;
382 return *this;
383 }
384 ArrayBuilder& operator=(decltype(nullptr)) {
385 dispose();
386 return *this;
387 }
388
389 template <typename... Params>
390 T& add(Params&&... params) {
391 KJ_IREQUIRE(pos < endPtr, "Added too many elements to ArrayBuilder.");
392 ctor(*pos, kj::fwd<Params>(params)...);
393 return *pos++;
394 }
395
396 template <typename Container>
397 void addAll(Container&& container) {
398 addAll<decltype(container.begin()), !isReference<Container>()>(
399 container.begin(), container.end());
400 }
401
402 template <typename Iterator, bool move = false>
403 void addAll(Iterator start, Iterator end);
404
405 void removeLast() {
406 KJ_IREQUIRE(pos > ptr, "No elements present to remove.");
407 kj::dtor(*--pos);
408 }
409
410 void truncate(size_t size) {
411 KJ_IREQUIRE(size <= this->size(), "can't use truncate() to expand");
412
413 T* target = ptr + size;
414 if (__has_trivial_destructor(T)) {
415 pos = target;
416 } else {
417 while (pos > target) {
418 kj::dtor(*--pos);
419 }
420 }
421 }
422
423 void clear() {
424 if (__has_trivial_destructor(T)) {
425 pos = ptr;
426 } else {
427 while (pos > ptr) {
428 kj::dtor(*--pos);
429 }
430 }
431 }
432
433 void resize(size_t size) {
434 KJ_IREQUIRE(size <= capacity(), "can't resize past capacity");
435
436 T* target = ptr + size;
437 if (target > pos) {
438 // expand
439 if (__has_trivial_constructor(T)) {
440 pos = target;
441 } else {
442 while (pos < target) {
443 kj::ctor(*pos++);
444 }
445 }
446 } else {
447 // truncate
448 if (__has_trivial_destructor(T)) {
449 pos = target;
450 } else {
451 while (pos > target) {
452 kj::dtor(*--pos);
453 }
454 }
455 }
456 }
457
458 Array<T> finish() {
459 // We could safely remove this check if we assume that the disposer implementation doesn't
460 // need to know the original capacity, as is thes case with HeapArrayDisposer since it uses
461 // operator new() or if we created a custom disposer for ArrayBuilder which stores the capacity
462 // in a prefix. But that would make it hard to write cleverer heap allocators, and anyway this
463 // check might catch bugs. Probably people should use Vector if they want to build arrays
464 // without knowing the final size in advance.
465 KJ_IREQUIRE(pos == endPtr, "ArrayBuilder::finish() called prematurely.");
466 Array<T> result(reinterpret_cast<T*>(ptr), pos - ptr, *disposer);
467 ptr = nullptr;
468 pos = nullptr;
469 endPtr = nullptr;
470 return result;
471 }
472
473 inline bool isFull() const {
474 return pos == endPtr;
475 }
476
477private:
478 T* ptr;
479 RemoveConst<T>* pos;
480 T* endPtr;
481 const ArrayDisposer* disposer;
482
483 inline void dispose() {
484 // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly
485 // dispose again.
486 T* ptrCopy = ptr;
487 T* posCopy = pos;
488 T* endCopy = endPtr;
489 if (ptrCopy != nullptr) {
490 ptr = nullptr;
491 pos = nullptr;
492 endPtr = nullptr;
493 disposer->dispose(ptrCopy, posCopy - ptrCopy, endCopy - ptrCopy);
494 }
495 }
496};
497
498template <typename T>
499inline ArrayBuilder<T> heapArrayBuilder(size_t size) {
500 // Like `heapArray<T>()` but does not default-construct the elements. You must construct them
501 // manually by calling `add()`.
502
503 return ArrayBuilder<T>(_::HeapArrayDisposer::allocateUninitialized<RemoveConst<T>>(size),
504 size, _::HeapArrayDisposer::instance);
505}
506
507// =======================================================================================
508// Inline Arrays
509
510template <typename T, size_t fixedSize>
511class FixedArray {
512 // A fixed-width array whose storage is allocated inline rather than on the heap.
513
514public:
515 inline size_t size() const { return fixedSize; }
516 inline T* begin() { return content; }
517 inline T* end() { return content + fixedSize; }
518 inline const T* begin() const { return content; }
519 inline const T* end() const { return content + fixedSize; }
520
521 inline operator ArrayPtr<T>() {
522 return arrayPtr(content, fixedSize);
523 }
524 inline operator ArrayPtr<const T>() const {
525 return arrayPtr(content, fixedSize);
526 }
527
528 inline T& operator[](size_t index) { return content[index]; }
529 inline const T& operator[](size_t index) const { return content[index]; }
530
531private:
532 T content[fixedSize];
533};
534
535template <typename T, size_t fixedSize>
536class CappedArray {
537 // Like `FixedArray` but can be dynamically resized as long as the size does not exceed the limit
538 // specified by the template parameter.
539 //
540 // TODO(someday): Don't construct elements past currentSize?
541
542public:
543 inline KJ_CONSTEXPR() CappedArray(): currentSize(fixedSize) {}
544 inline explicit constexpr CappedArray(size_t s): currentSize(s) {}
545
546 inline size_t size() const { return currentSize; }
547 inline void setSize(size_t s) { KJ_IREQUIRE(s <= fixedSize); currentSize = s; }
548 inline T* begin() { return content; }
549 inline T* end() { return content + currentSize; }
550 inline const T* begin() const { return content; }
551 inline const T* end() const { return content + currentSize; }
552
553 inline operator ArrayPtr<T>() {
554 return arrayPtr(content, currentSize);
555 }
556 inline operator ArrayPtr<const T>() const {
557 return arrayPtr(content, currentSize);
558 }
559
560 inline T& operator[](size_t index) { return content[index]; }
561 inline const T& operator[](size_t index) const { return content[index]; }
562
563private:
564 size_t currentSize;
565 T content[fixedSize];
566};
567
568// =======================================================================================
569// KJ_MAP
570
571#define KJ_MAP(elementName, array) \
572 ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>(array) * \
573 [&](typename ::kj::_::Mapper<KJ_DECLTYPE_REF(array)>::Element elementName)
574// Applies some function to every element of an array, returning an Array of the results, with
575// nice syntax. Example:
576//
577// StringPtr foo = "abcd";
578// Array<char> bar = KJ_MAP(c, foo) -> char { return c + 1; };
579// KJ_ASSERT(str(bar) == "bcde");
580
581namespace _ { // private
582
583template <typename T>
584struct Mapper {
585 T array;
586 Mapper(T&& array): array(kj::fwd<T>(array)) {}
587 template <typename Func>
588 auto operator*(Func&& func) -> Array<decltype(func(*array.begin()))> {
589 auto builder = heapArrayBuilder<decltype(func(*array.begin()))>(array.size());
590 for (auto iter = array.begin(); iter != array.end(); ++iter) {
591 builder.add(func(*iter));
592 }
593 return builder.finish();
594 }
595 typedef decltype(*kj::instance<T>().begin()) Element;
596};
597
598template <typename T, size_t s>
599struct Mapper<T(&)[s]> {
600 T* array;
601 Mapper(T* array): array(array) {}
602 template <typename Func>
603 auto operator*(Func&& func) -> Array<decltype(func(*array))> {
604 auto builder = heapArrayBuilder<decltype(func(*array))>(s);
605 for (size_t i = 0; i < s; i++) {
606 builder.add(func(array[i]));
607 }
608 return builder.finish();
609 }
610 typedef decltype(*array)& Element;
611};
612
613} // namespace _ (private)
614
615// =======================================================================================
616// Inline implementation details
617
618template <typename T>
619struct ArrayDisposer::Dispose_<T, true> {
620 static void dispose(T* firstElement, size_t elementCount, size_t capacity,
621 const ArrayDisposer& disposer) {
622 disposer.disposeImpl(const_cast<RemoveConst<T>*>(firstElement),
623 sizeof(T), elementCount, capacity, nullptr);
624 }
625};
626template <typename T>
627struct ArrayDisposer::Dispose_<T, false> {
628 static void destruct(void* ptr) {
629 kj::dtor(*reinterpret_cast<T*>(ptr));
630 }
631
632 static void dispose(T* firstElement, size_t elementCount, size_t capacity,
633 const ArrayDisposer& disposer) {
634 disposer.disposeImpl(firstElement, sizeof(T), elementCount, capacity, &destruct);
635 }
636};
637
638template <typename T>
639void ArrayDisposer::dispose(T* firstElement, size_t elementCount, size_t capacity) const {
640 Dispose_<T>::dispose(firstElement, elementCount, capacity, *this);
641}
642
643namespace _ { // private
644
645template <typename T>
646struct HeapArrayDisposer::Allocate_<T, true, true> {
647 static T* allocate(size_t elementCount, size_t capacity) {
648 return reinterpret_cast<T*>(allocateImpl(
649 sizeof(T), elementCount, capacity, nullptr, nullptr));
650 }
651};
652template <typename T>
653struct HeapArrayDisposer::Allocate_<T, false, true> {
654 static void construct(void* ptr) {
655 kj::ctor(*reinterpret_cast<T*>(ptr));
656 }
657 static T* allocate(size_t elementCount, size_t capacity) {
658 return reinterpret_cast<T*>(allocateImpl(
659 sizeof(T), elementCount, capacity, &construct, nullptr));
660 }
661};
662template <typename T>
663struct HeapArrayDisposer::Allocate_<T, false, false> {
664 static void construct(void* ptr) {
665 kj::ctor(*reinterpret_cast<T*>(ptr));
666 }
667 static void destruct(void* ptr) {
668 kj::dtor(*reinterpret_cast<T*>(ptr));
669 }
670 static T* allocate(size_t elementCount, size_t capacity) {
671 return reinterpret_cast<T*>(allocateImpl(
672 sizeof(T), elementCount, capacity, &construct, &destruct));
673 }
674};
675
676template <typename T>
677T* HeapArrayDisposer::allocate(size_t count) {
678 return Allocate_<T>::allocate(count, count);
679}
680
681template <typename T>
682T* HeapArrayDisposer::allocateUninitialized(size_t count) {
683 return Allocate_<T, true, true>::allocate(0, count);
684}
685
686template <typename Element, typename Iterator, bool move, bool = canMemcpy<Element>()>
687struct CopyConstructArray_;
688
689template <typename T, bool move>
690struct CopyConstructArray_<T, T*, move, true> {
691 static inline T* apply(T* __restrict__ pos, T* start, T* end) {
692 if (end != start) {
693 memcpy(pos, start, reinterpret_cast<byte*>(end) - reinterpret_cast<byte*>(start));
694 }
695 return pos + (end - start);
696 }
697};
698
699template <typename T>
700struct CopyConstructArray_<T, const T*, false, true> {
701 static inline T* apply(T* __restrict__ pos, const T* start, const T* end) {
702 if (end != start) {
703 memcpy(pos, start, reinterpret_cast<const byte*>(end) - reinterpret_cast<const byte*>(start));
704 }
705 return pos + (end - start);
706 }
707};
708
709template <typename T, typename Iterator, bool move>
710struct CopyConstructArray_<T, Iterator, move, true> {
711 static inline T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
712 // Since both the copy constructor and assignment operator are trivial, we know that assignment
713 // is equivalent to copy-constructing. So we can make this case somewhat easier for the
714 // compiler to optimize.
715 while (start != end) {
716 *pos++ = *start++;
717 }
718 return pos;
719 }
720};
721
722template <typename T, typename Iterator>
723struct CopyConstructArray_<T, Iterator, false, false> {
724 struct ExceptionGuard {
725 T* start;
726 T* pos;
727 inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
728 ~ExceptionGuard() noexcept(false) {
729 while (pos > start) {
730 dtor(*--pos);
731 }
732 }
733 };
734
735 static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
736 // Verify that T can be *implicitly* constructed from the source values.
737 if (false) implicitCast<T>(*start);
738
739 if (noexcept(T(*start))) {
740 while (start != end) {
741 ctor(*pos++, *start++);
742 }
743 return pos;
744 } else {
745 // Crap. This is complicated.
746 ExceptionGuard guard(pos);
747 while (start != end) {
748 ctor(*guard.pos, *start++);
749 ++guard.pos;
750 }
751 guard.start = guard.pos;
752 return guard.pos;
753 }
754 }
755};
756
757template <typename T, typename Iterator>
758struct CopyConstructArray_<T, Iterator, true, false> {
759 // Actually move-construct.
760
761 struct ExceptionGuard {
762 T* start;
763 T* pos;
764 inline explicit ExceptionGuard(T* pos): start(pos), pos(pos) {}
765 ~ExceptionGuard() noexcept(false) {
766 while (pos > start) {
767 dtor(*--pos);
768 }
769 }
770 };
771
772 static T* apply(T* __restrict__ pos, Iterator start, Iterator end) {
773 // Verify that T can be *implicitly* constructed from the source values.
774 if (false) implicitCast<T>(kj::mv(*start));
775
776 if (noexcept(T(kj::mv(*start)))) {
777 while (start != end) {
778 ctor(*pos++, kj::mv(*start++));
779 }
780 return pos;
781 } else {
782 // Crap. This is complicated.
783 ExceptionGuard guard(pos);
784 while (start != end) {
785 ctor(*guard.pos, kj::mv(*start++));
786 ++guard.pos;
787 }
788 guard.start = guard.pos;
789 return guard.pos;
790 }
791 }
792};
793
794} // namespace _ (private)
795
796template <typename T>
797template <typename Iterator, bool move>
798void ArrayBuilder<T>::addAll(Iterator start, Iterator end) {
799 pos = _::CopyConstructArray_<RemoveConst<T>, Decay<Iterator>, move>::apply(pos, start, end);
800}
801
802template <typename T>
803Array<T> heapArray(const T* content, size_t size) {
804 ArrayBuilder<T> builder = heapArrayBuilder<T>(size);
805 builder.addAll(content, content + size);
806 return builder.finish();
807}
808
809template <typename T>
810Array<T> heapArray(T* content, size_t size) {
811 ArrayBuilder<T> builder = heapArrayBuilder<T>(size);
812 builder.addAll(content, content + size);
813 return builder.finish();
814}
815
816template <typename T>
817Array<T> heapArray(ArrayPtr<T> content) {
818 ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size());
819 builder.addAll(content);
820 return builder.finish();
821}
822
823template <typename T>
824Array<T> heapArray(ArrayPtr<const T> content) {
825 ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size());
826 builder.addAll(content);
827 return builder.finish();
828}
829
830template <typename T, typename Iterator> Array<T>
831heapArray(Iterator begin, Iterator end) {
832 ArrayBuilder<T> builder = heapArrayBuilder<T>(end - begin);
833 builder.addAll(begin, end);
834 return builder.finish();
835}
836
837template <typename T>
838inline Array<T> heapArray(std::initializer_list<T> init) {
839 return heapArray<T>(init.begin(), init.end());
840}
841
842#if __cplusplus > 201402L
843template <typename T, typename... Params>
844inline Array<Decay<T>> arr(T&& param1, Params&&... params) {
845 ArrayBuilder<Decay<T>> builder = heapArrayBuilder<Decay<T>>(sizeof...(params) + 1);
846 (builder.add(kj::fwd<T>(param1)), ... , builder.add(kj::fwd<Params>(params)));
847 return builder.finish();
848}
849#endif
850
851namespace _ { // private
852
853template <typename... T>
854struct ArrayDisposableOwnedBundle final: public ArrayDisposer, public OwnedBundle<T...> {
855 ArrayDisposableOwnedBundle(T&&... values): OwnedBundle<T...>(kj::fwd<T>(values)...) {}
856 void disposeImpl(void*, size_t, size_t, size_t, void (*)(void*)) const override { delete this; }
857};
858
859} // namespace _ (private)
860
861template <typename T>
862template <typename... Attachments>
863Array<T> Array<T>::attach(Attachments&&... attachments) {
864 T* ptrCopy = ptr;
865 auto sizeCopy = size_;
866
867 KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");
868
869 // HACK: If someone accidentally calls .attach() on a null pointer in opt mode, try our best to
870 // accomplish reasonable behavior: We turn the pointer non-null but still invalid, so that the
871 // disposer will still be called when the pointer goes out of scope.
872 if (ptrCopy == nullptr) ptrCopy = reinterpret_cast<T*>(1);
873
874 auto bundle = new _::ArrayDisposableOwnedBundle<Array<T>, Attachments...>(
875 kj::mv(*this), kj::fwd<Attachments>(attachments)...);
876 return Array<T>(ptrCopy, sizeCopy, *bundle);
877}
878
879template <typename T>
880template <typename... Attachments>
881Array<T> ArrayPtr<T>::attach(Attachments&&... attachments) const {
882 T* ptrCopy = ptr;
883
884 KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");
885
886 // HACK: If someone accidentally calls .attach() on a null pointer in opt mode, try our best to
887 // accomplish reasonable behavior: We turn the pointer non-null but still invalid, so that the
888 // disposer will still be called when the pointer goes out of scope.
889 if (ptrCopy == nullptr) ptrCopy = reinterpret_cast<T*>(1);
890
891 auto bundle = new _::ArrayDisposableOwnedBundle<Attachments...>(
892 kj::fwd<Attachments>(attachments)...);
893 return Array<T>(ptrCopy, size_, *bundle);
894}
895
896} // namespace kj
897