array.h (31745B)
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 = __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(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 = __has_trivial_constructor(T), 289 bool hasNothrowConstructor = __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 (__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 (__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 (__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 (__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 __cplusplus > 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