Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/array.h @ 69:33d812a61356

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