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 | |
32 | namespace kj { |
33 | |
34 | // ======================================================================================= |
35 | // ArrayDisposer -- Implementation details. |
36 | |
37 | class ArrayDisposer { |
38 | // Much like Disposer from memory.h. |
39 | |
40 | protected: |
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 | |
51 | public: |
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 | |
60 | private: |
61 | template <typename T, bool hasTrivialDestructor = __has_trivial_destructor(T)> |
62 | struct Dispose_; |
63 | }; |
64 | |
65 | class 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 | |
73 | public: |
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 | |
97 | private: |
98 | byte* pos; |
99 | size_t elementSize; |
100 | size_t constructedElementCount; |
101 | void (*destroyElement)(void*); |
102 | }; |
103 | |
104 | class DestructorOnlyArrayDisposer: public ArrayDisposer { |
105 | public: |
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 | |
112 | class 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 | |
116 | public: |
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 | |
126 | template <typename T> |
127 | class 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 | |
132 | public: |
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 | |
241 | private: |
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 | |
264 | static_assert(!canMemcpy<Array<char>>(), "canMemcpy<>() is broken" ); |
265 | |
266 | namespace _ { // private |
267 | |
268 | class HeapArrayDisposer final: public ArrayDisposer { |
269 | public: |
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 | |
277 | private: |
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 | |
293 | template <typename T> |
294 | inline 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 | |
301 | template <typename T> Array<T> heapArray(const T* content, size_t size); |
302 | template <typename T> Array<T> heapArray(ArrayPtr<T> content); |
303 | template <typename T> Array<T> heapArray(ArrayPtr<const T> content); |
304 | template <typename T, typename Iterator> Array<T> heapArray(Iterator begin, Iterator end); |
305 | template <typename T> Array<T> heapArray(std::initializer_list<T> init); |
306 | // Allocate a heap array containing a copy of the given content. |
307 | |
308 | template <typename T, typename Container> |
309 | Array<T> heapArrayFromIterable(Container&& a) { return heapArray<T>(a.begin(), a.end()); } |
310 | template <typename T> |
311 | Array<T> heapArrayFromIterable(Array<T>&& a) { return mv(a); } |
312 | |
313 | // ======================================================================================= |
314 | // ArrayBuilder |
315 | |
316 | template <typename T> |
317 | class 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 | |
321 | public: |
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 | |
477 | private: |
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 | |
498 | template <typename T> |
499 | inline 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 | |
510 | template <typename T, size_t fixedSize> |
511 | class FixedArray { |
512 | // A fixed-width array whose storage is allocated inline rather than on the heap. |
513 | |
514 | public: |
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 | |
531 | private: |
532 | T content[fixedSize]; |
533 | }; |
534 | |
535 | template <typename T, size_t fixedSize> |
536 | class 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 | |
542 | public: |
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 | |
563 | private: |
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 | |
581 | namespace _ { // private |
582 | |
583 | template <typename T> |
584 | struct 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 | |
598 | template <typename T, size_t s> |
599 | struct 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 | |
618 | template <typename T> |
619 | struct 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 | }; |
626 | template <typename T> |
627 | struct 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 | |
638 | template <typename T> |
639 | void ArrayDisposer::dispose(T* firstElement, size_t elementCount, size_t capacity) const { |
640 | Dispose_<T>::dispose(firstElement, elementCount, capacity, *this); |
641 | } |
642 | |
643 | namespace _ { // private |
644 | |
645 | template <typename T> |
646 | struct 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 | }; |
652 | template <typename T> |
653 | struct 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 | }; |
662 | template <typename T> |
663 | struct 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 | |
676 | template <typename T> |
677 | T* HeapArrayDisposer::allocate(size_t count) { |
678 | return Allocate_<T>::allocate(count, count); |
679 | } |
680 | |
681 | template <typename T> |
682 | T* HeapArrayDisposer::allocateUninitialized(size_t count) { |
683 | return Allocate_<T, true, true>::allocate(0, count); |
684 | } |
685 | |
686 | template <typename Element, typename Iterator, bool move, bool = canMemcpy<Element>()> |
687 | struct CopyConstructArray_; |
688 | |
689 | template <typename T, bool move> |
690 | struct 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 | |
699 | template <typename T> |
700 | struct 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 | |
709 | template <typename T, typename Iterator, bool move> |
710 | struct 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 | |
722 | template <typename T, typename Iterator> |
723 | struct 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 | |
757 | template <typename T, typename Iterator> |
758 | struct 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 | |
796 | template <typename T> |
797 | template <typename Iterator, bool move> |
798 | void ArrayBuilder<T>::addAll(Iterator start, Iterator end) { |
799 | pos = _::CopyConstructArray_<RemoveConst<T>, Decay<Iterator>, move>::apply(pos, start, end); |
800 | } |
801 | |
802 | template <typename T> |
803 | Array<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 | |
809 | template <typename T> |
810 | Array<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 | |
816 | template <typename T> |
817 | Array<T> heapArray(ArrayPtr<T> content) { |
818 | ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size()); |
819 | builder.addAll(content); |
820 | return builder.finish(); |
821 | } |
822 | |
823 | template <typename T> |
824 | Array<T> heapArray(ArrayPtr<const T> content) { |
825 | ArrayBuilder<T> builder = heapArrayBuilder<T>(content.size()); |
826 | builder.addAll(content); |
827 | return builder.finish(); |
828 | } |
829 | |
830 | template <typename T, typename Iterator> Array<T> |
831 | heapArray(Iterator begin, Iterator end) { |
832 | ArrayBuilder<T> builder = heapArrayBuilder<T>(end - begin); |
833 | builder.addAll(begin, end); |
834 | return builder.finish(); |
835 | } |
836 | |
837 | template <typename T> |
838 | inline Array<T> heapArray(std::initializer_list<T> init) { |
839 | return heapArray<T>(init.begin(), init.end()); |
840 | } |
841 | |
842 | #if __cplusplus > 201402L |
843 | template <typename T, typename... Params> |
844 | inline 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 | |
851 | namespace _ { // private |
852 | |
853 | template <typename... T> |
854 | struct 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 | |
861 | template <typename T> |
862 | template <typename... Attachments> |
863 | Array<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 | |
879 | template <typename T> |
880 | template <typename... Attachments> |
881 | Array<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 | |