1 module nxt.dynamic_array; 2 3 // version = debugCtors; 4 5 import core.internal.traits : Unqual; 6 import nxt.my_mallocator : Mallocator; 7 import nxt.allocator_traits : isAllocator; 8 9 /** Array type with deterministic control of memory. The memory allocated for 10 the array is reclaimed as soon as possible; there is no reliance on the 11 garbage collector. Array uses malloc, realloc and free for managing its own 12 memory. 13 14 A null `Allocator` means means to qcmeman functions. TODO use `Mallocator` by default 15 16 TODO Generalize to bucket array either via specialized allocator to by extra 17 Storage class given as template type parameter. Integrate `nxt.bucket_array` for 18 details. 19 20 TODO: Use `std.bitmanip.BitArray` for array container storing boolean 21 values. 22 23 TODO: Add OutputRange.writer support as 24 https://github.com/burner/StringBuffer/blob/master/source/stringbuffer.d#L45 25 26 TODO: Use `std.traits.areCopyCompatibleArrays` 27 28 See also https://github.com/izabera/s 29 */ 30 @safe struct DynamicArray(T, Allocator = Mallocator, Capacity = size_t) 31 if (!is(Unqual!T == bool) && // use `BitArray` instead 32 (is(Capacity == ulong) || // 3 64-bit words 33 is(Capacity == uint)) && 34 isAllocator!Allocator) // 2 64-bit words 35 { 36 /** Growth factor P/Q. 37 https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling 38 Use 1.5 like Facebook's `fbvector` does. 39 */ 40 enum _growthP = 3; // numerator 41 /// ditto 42 enum _growthQ = 2; // denominator 43 44 // import core.exception : onOutOfMemoryError; 45 import core.stdc.string : memset; 46 import core.internal.traits : hasElaborateDestructor; 47 import std.experimental.allocator : makeArray; 48 import std.range.primitives : isInputRange, ElementType, hasLength, hasSlicing, isInfinite; 49 import std.traits : hasIndirections, hasAliasing, 50 isMutable, TemplateOf, isArray, isAssignable, isType, hasFunctionAttributes, isIterable, isPointer; 51 import core.lifetime : emplace, move, moveEmplace; 52 53 import nxt.qcmeman : malloc, calloc, realloc, free, gc_addRange, gc_removeRange; 54 import nxt.container_traits : mustAddGCRange, needsMove; 55 56 /// Mutable element type. 57 private alias MutableE = Unqual!T; 58 59 /// Is `true` if `U` can be assign to the element type `T` of `this`. 60 enum isElementAssignable(U) = isAssignable!(MutableE, U); 61 62 pragma(inline): 63 64 /// Returns: an array of length `initialLength` with all elements default-initialized to `ElementType.init`. 65 static typeof(this) withLength()(size_t initialLength) // template-lazy 66 { 67 version(D_Coverage) {} else pragma(inline, true); 68 return withCapacityLengthZero(initialLength, initialLength, true); 69 } 70 71 /// Returns: an array with initial capacity `initialCapacity`. 72 static typeof(this) withCapacity()(size_t initialCapacity) // template-lazy 73 { 74 version(D_Coverage) {} else pragma(inline, true); 75 return withCapacityLengthZero(initialCapacity, 0, false); 76 } 77 78 static if (__traits(isCopyable, T)) 79 { 80 /** Construct using 81 * - initial length `length`, 82 * - and value of all elements `elementValue`. 83 */ 84 static typeof(this) withLengthElementValue()(size_t length, T elementValue) 85 in(length <= Capacity.max) 86 { 87 version(D_Coverage) {} else pragma(inline, true); 88 return typeof(return)(Store(typeof(this).allocateWithValue(length, move(elementValue)), 89 cast(Capacity)length, 90 cast(Capacity)length)); 91 } 92 } 93 94 /** Construct using 95 - initial capacity `capacity`, 96 - initial length `length`, 97 - and default-flag `initFlag`. 98 */ 99 private static typeof(this) withCapacityLengthZero()(size_t capacity, size_t length, bool initFlag) @trusted // template-lazy 100 in(capacity >= length) 101 in(capacity <= Capacity.max) 102 { 103 version(LDC) pragma(inline, true); 104 return typeof(return)(Store(typeof(this).allocate(capacity, initFlag), 105 cast(Capacity)capacity, 106 cast(Capacity)length)); 107 } 108 109 /** Emplace `thatPtr` with elements moved from `elements`. */ 110 static ref typeof(this) emplaceWithMovedElements()(typeof(this)* thatPtr, T[] elements) @system // template-lazy 111 { 112 immutable length = elements.length; 113 thatPtr._store.ptr = typeof(this).allocate(length, false); 114 thatPtr._store.capacity = cast(Capacity)length; 115 thatPtr._store.length = cast(Capacity)length; 116 foreach (immutable i, ref e; elements[]) 117 moveEmplace(e, thatPtr._mptr[i]); 118 return *thatPtr; 119 } 120 121 /** Emplace `thatPtr` with elements copied from `elements`. */ 122 static ref typeof(this) emplaceWithCopiedElements()(typeof(this)* thatPtr, const(T)[] elements) @system // template-lazy 123 if (__traits(isCopyable, T)) 124 { 125 immutable length = elements.length; 126 thatPtr._store.ptr = typeof(this).allocate(length, false); 127 thatPtr._store.capacity = cast(Capacity)length; 128 thatPtr._store.length = cast(Capacity)length; 129 foreach (immutable i, ref e; elements[]) 130 thatPtr._mptr[i] = cast(T)e; // TODO: restrict this function using a 131 // T-trait where this cast can be @trusted 132 return *thatPtr; 133 } 134 135 private this(Store store) 136 { 137 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(store)); 138 _store = store; 139 } 140 141 /// Construct from uncopyable element `value`. 142 this()(T value) @trusted // template-lazy 143 if (!__traits(isCopyable, T)) 144 { 145 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(value)); 146 _store.ptr = typeof(this).allocate(1, false); 147 _store.capacity = 1; 148 _store.length = 1; 149 moveEmplace(value, _mptr[0]); // TODO: remove `moveEmplace` when compiler does it for us 150 } 151 152 /// Construct from copyable element `value`. 153 this(U)(U value) @trusted 154 if (__traits(isCopyable, U) && 155 isElementAssignable!U) 156 { 157 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(value)); 158 _store.ptr = typeof(this).allocate(1, false); 159 _store.capacity = 1; 160 _store.length = 1; 161 emplace(&_mptr[0], value); 162 } 163 164 static if (__traits(isCopyable, T) && 165 !is(T == union)) // forbid copying of unions such as `HybridBin` in hashmap.d 166 { 167 static typeof(this) withElements()(const T[] elements) @trusted // template-lazy 168 { 169 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(elements)); 170 immutable length = elements.length; 171 auto ptr = typeof(this).allocate(length, false); 172 173 foreach (immutable i, const element; elements[]) 174 // TODO: be more strict 175 // static if (hasIndirections!T) 176 // { 177 // ptr[i] = element; 178 // } 179 // else 180 // { 181 // ptr[i] = *cast(MutableE*)&element; 182 // } 183 ptr[i] = *cast(MutableE*)&element; 184 185 // ptr[0 .. length] = elements[]; 186 return typeof(return)(Store(ptr, 187 cast(Capacity)length, 188 cast(Capacity)length)); 189 } 190 191 /// Returns: shallow duplicate of `this`. 192 @property DynamicArray!(Unqual!T, Allocator, Capacity) dup()() const @trusted // template-lazy 193 { 194 version(D_Coverage) {} else pragma(inline, true); 195 return typeof(this).withElements(this[]); 196 } 197 } 198 199 /// Construct from the element(s) of the dynamic array `values`. 200 this(U)(U[] values) @trusted 201 if (isElementAssignable!(U)) 202 { 203 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(values)); 204 // TODO: use import emplace_all instead 205 206 _store.ptr = allocate(values.length, false); 207 static if (!is(Capacity == size_t)) 208 assert(values.length <= Capacity.max, 209 "Minimum capacity doesn't fit in capacity type."); 210 _store.capacity = cast(Capacity)values.length; 211 212 foreach (index; 0 .. values.length) 213 static if (needsMove!(T)) 214 move(values[index], _mptr[index]); 215 else 216 _mptr[index] = values[index]; 217 218 setLengthChecked(values.length); 219 } 220 221 /// Construct from the `n` number of element(s) in the static array `values`. 222 this(uint n, U)(U[n] values) @trusted 223 if (isElementAssignable!(U)) 224 { 225 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(values)); 226 // TODO: use import emplace_all instead 227 228 _store.ptr = allocate(values.length, false); 229 static assert(values.length <= Capacity.max); 230 _store.capacity = cast(Capacity)values.length; 231 232 static foreach (index; 0 .. values.length) 233 static if (needsMove!(T)) 234 move(values[index], _mptr[index]); 235 else 236 _mptr[index] = values[index]; 237 238 setLengthChecked(values.length); 239 } 240 /// ditto 241 this(R)(scope R values) @trusted 242 if (// isRefIterable!R && 243 isElementAssignable!(ElementType!R) && 244 !isArray!R) 245 { 246 version(debugCtors) pragma(msg, __FILE_FULL_PATH__, ":", __LINE__, ": info: ", typeof(values)); 247 static if (hasLength!R) 248 { 249 reserve(values.length); 250 size_t index = 0; 251 foreach (ref value; values) 252 _mptr[index++] = value; 253 setLengthChecked(values.length); 254 } 255 else 256 foreach (ref value; values) 257 insertBack1(value); 258 } 259 260 /** Is `true` iff the iterable container `C` can be insert to `this`. 261 */ 262 private enum isInsertableContainer(C) = (is(C == struct) && // exclude class ranges for aliasing control 263 isRefIterable!C && // elements may be non-copyable 264 !isInfinite!C && 265 isElementAssignable!(ElementType!C)); 266 267 /// Construct from the elements `values`. 268 static typeof(this) withElementsOfRange_untested(R)(R values) @trusted 269 if (isInsertableContainer!R) 270 { 271 typeof(this) result; 272 273 static if (hasLength!R) 274 result.reserve(values.length); 275 276 static if (hasLength!R && 277 hasSlicing!R && 278 !needsMove!(ElementType!R)) 279 { 280 import std.algorithm.mutation : copy; 281 copy(values[0 .. values.length], 282 result._mptr[0 .. values.length]); // TODO: better to use foreach instead? 283 result.setLengthChecked(values.length); 284 } 285 else 286 { 287 static if (hasLength!R) 288 { 289 size_t i = 0; 290 foreach (ref value; move(values)) // TODO: remove `move` when compiler does it for us 291 static if (needsMove!(typeof(value))) 292 moveEmplace(value, result._mptr[i++]); 293 else 294 result._mptr[i++] = value; 295 result.setLengthChecked(values.length); 296 } 297 else 298 { 299 // import std.algorithm.mutation : moveEmplaceAll; 300 /* TODO: optimize with `moveEmplaceAll` that does a raw copy and 301 * zeroing of values */ 302 foreach (ref value; move(values)) // TODO: remove `move` when compiler does it for us 303 static if (needsMove!(ElementType!R)) 304 result.insertBackMove(value); // steal element 305 else 306 result.insertBack(value); 307 } 308 } 309 return result; 310 } 311 312 /// No default copying. 313 @disable this(this); 314 315 // TODO: this gives error in insertBack. why? 316 // void opAssign()(typeof(this) rhs) @trusted pure nothrow @nogc // template-lazy 317 // { 318 // move(rhs, this); 319 // } 320 321 /** Destruct. 322 * 323 * TODO: what effect does have here? 324 * See_Also: https://github.com/atilaneves/automem/blob/master/source/automem/vector.d#L92 325 */ 326 ~this() @nogc /*TODO: scope*/ 327 { 328 releaseElementsStore(); 329 } 330 331 /// Empty. 332 void clear() @nogc 333 { 334 releaseElementsStore(); 335 resetInternalData(); 336 } 337 338 /// Release elements and internal store. 339 private void releaseElementsStore() @nogc @trusted 340 { 341 foreach (immutable index; 0 .. _store.length) 342 static if (hasElaborateDestructor!T) 343 .destroy(_mptr[index]); 344 else static if (is(T == class) || isPointer!T || hasIndirections!T) 345 _mptr[index] = T.init; // nullify any pointers 346 freeStore(); 347 } 348 349 /// Free internal store. 350 private void freeStore() @trusted 351 { 352 static if (mustAddGCRange!T) 353 gc_removeRange(_mptr); 354 free(_mptr); 355 } 356 357 /// Reset internal data. 358 private void resetInternalData() @nogc 359 { 360 version(D_Coverage) {} else pragma(inline, true); 361 _store.ptr = null; 362 _store.capacity = 0; 363 _store.length = 0; 364 } 365 366 /** Allocate heap region with `initialCapacity` number of elements of type `T`. 367 * 368 * If `initFlag` is `true` elements will be initialized 369 */ 370 private static MutableE* allocate(size_t initialCapacity, bool initFlag) @trusted 371 { 372 immutable size_t numBytes = initialCapacity * T.sizeof; 373 374 typeof(return) ptr = null; 375 if (initFlag) 376 { 377 static if (__traits(isZeroInit, T) && 378 __traits(hasMember, Allocator, "allocateZeroed") && 379 is(typeof(allocator.allocateZeroed(numBytes)) == void[])) 380 ptr = cast(typeof(return))(allocator.allocateZeroed(numBytes).ptr); 381 else 382 { 383 ptr = cast(typeof(return))(allocator.allocate(numBytes).ptr); 384 static if (__traits(isZeroInit, T)) 385 memset(ptr, 0, numBytes); 386 else 387 foreach (i; 0 .. initialCapacity) 388 ptr[i] = MutableE.init; 389 } 390 } 391 else 392 ptr = cast(typeof(return))(allocator.allocate(numBytes).ptr); 393 394 if (ptr is null && 395 initialCapacity >= 1 ) 396 // TODO: onOutOfMemoryError(); 397 return null; 398 399 static if (mustAddGCRange!T) 400 gc_addRange(ptr, numBytes); 401 402 return ptr; 403 } 404 405 static if (__traits(isCopyable, T)) 406 { 407 /** Allocate heap region with `initialCapacity` number of elements of type `T` all set to `elementValue`. 408 */ 409 private static MutableE* allocateWithValue(size_t initialCapacity, T elementValue) @trusted 410 { 411 immutable size_t numBytes = initialCapacity * T.sizeof; 412 413 typeof(return) ptr = null; 414 ptr = allocator.makeArray!MutableE(initialCapacity, elementValue).ptr; // TODO: set length 415 if (ptr is null && 416 initialCapacity >= 1) 417 // TODO: onOutOfMemoryError(); 418 return null; 419 420 static if (mustAddGCRange!T) 421 gc_addRange(ptr, numBytes); 422 423 return ptr; 424 } 425 } 426 427 /** Comparison for equality. */ 428 bool opEquals()(const scope auto ref typeof(this) rhs) const scope // template-lazy 429 { 430 version(D_Coverage) {} else pragma(inline, true); 431 return opSlice() == rhs.opSlice(); 432 } 433 /// ditto 434 bool opEquals(U)(const scope U[] rhs) const scope 435 if (is(typeof(T[].init == U[].init))) 436 { 437 version(D_Coverage) {} else pragma(inline, true); 438 return opSlice() == rhs; 439 } 440 441 /// Calculate D associative array (AA) key hash. 442 hash_t toHash()() const scope @trusted // template-lazy 443 { 444 import core.internal.hash : hashOf; 445 static if (__traits(isCopyable, T)) 446 return hashOf(this.length) ^ hashOf(opSlice()); 447 else 448 { 449 typeof(return) hash = hashOf(this.length); 450 foreach (immutable index; 0 .. this.length) 451 hash ^= this.ptr[index].hashOf; 452 return hash; 453 } 454 } 455 456 static if (__traits(isCopyable, T)) 457 { 458 /** Construct a string representation of `this` at `sink`. 459 */ 460 void toString()(scope void delegate(scope const(char)[]) sink) const scope // template-lazy 461 { 462 sink("["); 463 foreach (immutable index, ref value; opSlice()) 464 { 465 import std.conv : to; 466 sink(to!string(value)); 467 if (index + 1 < length) { sink(", "); } // separator 468 } 469 sink("]"); 470 } 471 } 472 473 /// Check if empty. 474 @property bool empty()() const scope // template-lazy 475 { 476 version(D_Coverage) {} else pragma(inline, true); 477 return _store.length == 0; 478 } 479 480 /// Get length. 481 @property size_t length() const scope // can't be template-lazy 482 { 483 version(D_Coverage) {} else pragma(inline, true); 484 return _store.length; 485 } 486 alias opDollar = length; /// ditto 487 488 /** Set length to `newLength`. 489 * 490 * If `newLength` < `length` elements are truncate. 491 * If `newLength` > `length` default-initialized elements are appended. 492 */ 493 @property void length(size_t newLength) @trusted scope // can't template-lazy 494 { 495 if (newLength < length) // if truncatation 496 { 497 static if (hasElaborateDestructor!T) 498 foreach (immutable index; newLength .. _store.length) 499 .destroy(_mptr[index]); 500 else static if (mustAddGCRange!T) 501 foreach (immutable index; newLength .. _store.length) 502 _mptr[index] = T.init; // avoid GC mark-phase dereference 503 } 504 else 505 { 506 reserve(newLength); 507 static if (hasElaborateDestructor!T) 508 // TODO: remove when compiler does it for us 509 foreach (immutable index; _store.length .. newLength) 510 { 511 // TODO: remove when compiler does it for us: 512 static if (__traits(isCopyable, T)) 513 emplace(&_mptr[index], T.init); 514 else 515 { 516 auto _ = T.init; 517 moveEmplace(_, _mptr[index]); 518 } 519 } 520 else 521 _mptr[_store.length .. newLength] = T.init; 522 } 523 524 setLengthChecked(newLength); 525 } 526 527 /// Set capacity, checking for overflow when `Capacity` is not `size_t`. 528 private void setLengthChecked(size_t newLength) scope 529 { 530 static if (!is(Capacity == size_t)) 531 assert(newLength <= Capacity.max, 532 "New length doesn't fit in capacity type."); 533 _store.length = cast(Capacity)newLength; 534 } 535 536 /// Get capacity. 537 @property size_t capacity() const scope // can't be template-lazy 538 { 539 version(D_Coverage) {} else pragma(inline, true); 540 return _store.capacity; 541 } 542 543 /** Ensures sufficient capacity to accommodate for minimumCapacity number of 544 elements. If `minimumCapacity` < `capacity`, this method does nothing. 545 */ 546 void reserve(size_t minimumCapacity) @trusted scope pure nothrow @nogc 547 { 548 static if (!is(Capacity == size_t)) 549 assert(minimumCapacity <= Capacity.max, 550 "Minimum capacity doesn't fit in capacity type."); 551 552 if (minimumCapacity <= capacity) 553 return; 554 555 reallocateAndSetCapacity(_growthP * minimumCapacity / _growthQ); 556 // static if (__VERSION__ >= 2098) import std.math.algebraic : nextPow2; else import std.math : nextPow2; 557 // reallocateAndSetCapacity(minimumCapacity.nextPow2); 558 } 559 560 /// Reallocate storage. 561 private void reallocateAndSetCapacity()(size_t newCapacity) @trusted // template-lazy 562 { 563 static if (!is(Capacity == size_t)) 564 assert(newCapacity <= Capacity.max, 565 "New capacity doesn't fit in capacity type."); 566 567 static if (mustAddGCRange!T) 568 gc_removeRange(_store.ptr); 569 570 _store.capacity = cast(Capacity)newCapacity; 571 _store.ptr = cast(T*)realloc(_mptr, T.sizeof * _store.capacity); 572 573 if (_store.ptr is null && 574 newCapacity >= 1) 575 // TODO: onOutOfMemoryError(); 576 return; 577 578 static if (mustAddGCRange!T) 579 gc_addRange(_store.ptr, _store.capacity * T.sizeof); 580 } 581 582 /// Index support. 583 ref inout(T) opIndex()(size_t i) inout return scope // template-lazy 584 { 585 version(D_Coverage) {} else pragma(inline, true); 586 return opSlice()[i]; 587 } 588 589 /// Slice support. 590 inout(T)[] opSlice()(size_t i, size_t j) inout return scope // template-lazy 591 { 592 version(D_Coverage) {} else pragma(inline, true); 593 return opSlice()[i .. j]; 594 } 595 /// ditto 596 inout(T)[] opSlice()() inout return @trusted scope // template-lazy 597 { 598 version(D_Coverage) {} else pragma(inline, true); 599 return _store.ptr[0 .. _store.length]; 600 } 601 602 /// Index assignment support. 603 ref T opIndexAssign(U)(scope U value, size_t i) @trusted return scope 604 { 605 static if (needsMove!T) 606 { 607 move(*(cast(MutableE*)(&value)), _mptr[i]); // TODO: is this correct? 608 return opSlice()[i]; 609 } 610 else static if ((is(T == class) || isPointer!T || hasIndirections!T) && 611 !isMutable!T) 612 static assert("Cannot modify constant elements with indirections"); 613 else 614 return opSlice()[i] = value; 615 } 616 617 /// Slice assignment support. 618 T[] opSliceAssign(U)(scope U value) return scope 619 { 620 version(D_Coverage) {} else pragma(inline, true); 621 return opSlice()[] = value; 622 } 623 /// ditto 624 T[] opSliceAssign(U)(scope U value, size_t i, size_t j) return scope 625 { 626 version(D_Coverage) {} else pragma(inline, true); 627 return opSlice()[i .. j] = value; 628 } 629 630 /// Get reference to front element. 631 @property ref inout(T) front()() inout return scope // template-lazy 632 { 633 version(D_Coverage) {} else pragma(inline, true); 634 return opSlice()[0]; // range-checked by default 635 } 636 637 /// Get reference to back element. 638 @property ref inout(T) back()() inout return scope // template-lazy 639 { 640 version(D_Coverage) {} else pragma(inline, true); 641 return opSlice()[_store.length - 1]; // range-checked by default 642 643 } 644 645 /** Move `value` into the end of the array. 646 */ 647 void insertBackMove()(ref T value) @trusted // template-lazy 648 { 649 version(LDC) pragma(inline, true); 650 reserve(_store.length + 1); 651 moveEmplace(value, _mptr[_store.length]); 652 _store.length += 1; 653 } 654 655 /** Insert `value` into the end of the array. 656 */ 657 void insertBack()(T value) @trusted // template-lazy 658 { 659 static if (needsMove!T) 660 insertBackMove(*cast(MutableE*)(&value)); 661 else 662 { 663 reserve(_store.length + 1); 664 _mptr[_store.length] = value; 665 _store.length += 1; 666 } 667 } 668 669 alias put = insertBack; 670 671 /** Insert the elements `values` into the end of the array. 672 */ 673 void insertBack(U)(U[] values...) @trusted 674 if (isElementAssignable!U && 675 __traits(isCopyable, U)) // prevent accidental move of l-value `values` 676 { 677 if (values.length == 1) // TODO: branch should be detected at compile-time 678 // twice as fast as array assignment below 679 return insertBack(values[0]); 680 681 static if (is(T == immutable(T))) 682 { 683 /* An array of immutable values cannot overlap with the `this` 684 mutable array container data, which entails no need to check for 685 overlap. 686 */ 687 reserve(_store.length + values.length); 688 _mptr[_store.length .. _store.length + values.length] = values; 689 } 690 else 691 { 692 import nxt.overlapping : overlaps; 693 if (_store.ptr == values.ptr) // called for instances as: `this ~= this` 694 { 695 reserve(2*_store.length); // invalidates `values.ptr` 696 foreach (immutable i; 0 .. _store.length) 697 { 698 _mptr[_store.length + i] = _store.ptr[i]; 699 } 700 } 701 else if (overlaps(this[], values[])) 702 assert(0, `TODO: Handle overlapping arrays`); 703 else 704 { 705 reserve(_store.length + values.length); 706 _mptr[_store.length .. _store.length + values.length] = values; 707 } 708 } 709 _store.length += values.length; 710 } 711 712 /** Insert the elements `elements` into the end of the array. 713 */ 714 void insertBack(R)(scope R elements) @trusted 715 if (isInsertableContainer!R) 716 { 717 import std.range.primitives : hasLength; 718 static if (isInputRange!R && 719 hasLength!R) 720 { 721 reserve(_store.length + elements.length); 722 import std.algorithm.mutation : copy; 723 copy(elements, _mptr[_store.length .. _store.length + elements.length]); 724 _store.length += elements.length; 725 } 726 else 727 { 728 foreach (ref element; move(elements)) // TODO: remove `move` when compiler does it for us 729 static if (__traits(isCopyable, ElementType!R)) 730 insertBack(element); 731 else 732 insertBackMove(element); 733 } 734 } 735 /// ditto 736 alias put = insertBack; 737 738 /** Remove last value fromm the end of the array. 739 */ 740 void popBack()() @trusted // template-lazy 741 in(!empty) 742 { 743 version(D_Coverage) {} else pragma(inline, true); 744 _store.length -= 1; 745 static if (hasElaborateDestructor!T) 746 .destroy(_mptr[_store.length]); 747 else static if (mustAddGCRange!T) 748 _mptr[_store.length] = T.init; // avoid GC mark-phase dereference 749 } 750 751 /** Rmove `n` last values from the end of the array. 752 753 See_Also: http://mir-algorithm.libmir.org/mir_appender.html#.ScopedBuffer.popBackN 754 */ 755 void popBackN()(size_t n) @trusted // template-lazy 756 in(length >= n) 757 { 758 _store.length -= n; 759 static if (hasElaborateDestructor!T) 760 foreach (immutable index; 0 .. n) 761 .destroy(_mptr[_store.length + index]); 762 else static if (mustAddGCRange!T) 763 foreach (immutable index; 0 .. n) 764 _mptr[_store.length + index] = T.init; // avoid GC mark-phase dereference 765 } 766 767 /** Pop back element and return it. 768 769 This is well-missed feature of C++'s `std::vector` because of problems 770 with exception handling. For more details see 771 https://stackoverflow.com/questions/12600330/pop-back-return-value. 772 */ 773 T backPop()() @trusted // template-lazy 774 in(!empty) 775 { 776 version(D_Coverage) {} else pragma(inline, true); 777 _store.length -= 1; 778 static if (needsMove!T) 779 return move(_mptr[_store.length]); 780 else static if (is(T == class) || isPointer!T || hasIndirections!T) // fast, medium, slow path 781 { 782 T e = void; 783 moveEmplace(_mptr[_store.length], e); // reset any pointers at `back` 784 return e; 785 } 786 else 787 return _mptr[_store.length]; 788 } 789 790 /** Pop element at `index`. */ 791 void popAt()(size_t index) @trusted @("complexity", "O(length)") // template-lazy 792 in(index < this.length) 793 { 794 static if (hasElaborateDestructor!T) 795 .destroy(_mptr[index]); 796 else static if (mustAddGCRange!T) 797 _mptr[index] = T.init; // avoid GC mark-phase dereference 798 shiftToFrontAt(index); 799 _store.length -= 1; 800 } 801 802 /** Move element at `index` to return. */ 803 T moveAt()(size_t index) @trusted @("complexity", "O(length)") // template-lazy 804 in(index < this.length) 805 { 806 auto value = move(_mptr[index]); 807 shiftToFrontAt(index); 808 _store.length -= 1; 809 return move(value); // TODO: remove `move` when compiler does it for us 810 } 811 812 /** Move element at front. */ 813 T frontPop()() // template-lazy 814 @("complexity", "O(length)") 815 { 816 version(D_Coverage) {} else pragma(inline, true); 817 return moveAt(0); 818 } 819 820 private void shiftToFrontAt()(size_t index) @trusted // template-lazy 821 { 822 // TODO: use this instead: 823 // immutable si = index + 1; // source index 824 // immutable ti = index; // target index 825 // immutable restLength = this.length - (index + 1); 826 // import std.algorithm.mutation : moveEmplaceAll; 827 // moveEmplaceAll(_mptr[si .. si + restLength], 828 // _mptr[ti .. ti + restLength]); 829 foreach (immutable i; 0 .. this.length - (index + 1)) // each element index that needs to be moved 830 { 831 immutable si = index + i + 1; // source index 832 immutable ti = index + i; // target index 833 moveEmplace(_mptr[si], // TODO: remove `move` when compiler does it for us 834 _mptr[ti]); 835 } 836 } 837 838 /** Forwards to $(D insertBack(values)). 839 */ 840 void opOpAssign(string op)(T value) 841 if (op == "~") 842 { 843 version(D_Coverage) {} else pragma(inline, true); 844 insertBackMove(value); 845 } 846 /// ditto 847 void opOpAssign(string op, U)(U[] values...) @trusted 848 if (op == "~" && 849 isElementAssignable!U && 850 __traits(isCopyable, U)) // prevent accidental move of l-value `values` 851 { 852 version(D_Coverage) {} else pragma(inline, true); 853 insertBack(values); 854 } 855 /// ditto 856 void opOpAssign(string op, R)(R values) 857 if (op == "~" && 858 isInputRange!R && 859 !isInfinite!R && 860 !isArray!R && 861 isElementAssignable!(ElementType!R)) 862 { 863 version(D_Coverage) {} else pragma(inline, true); 864 insertBack(values); 865 } 866 867 void opOpAssign(string op)(auto ref typeof(this) values) 868 if (op == "~") 869 { 870 version(D_Coverage) {} else pragma(inline, true); 871 insertBack(values[]); 872 } 873 874 // typeof(this) opBinary(string op, R)(R values) 875 // if (op == "~") 876 // { 877 // // TODO: optimize 878 // typeof(this) result; 879 // result ~= this[]; 880 // assert(result.length == length); 881 // result ~= values[]; 882 // return result; 883 // } 884 885 /// Unsafe access to pointer. 886 inout(T)* ptr()() inout return @system // template-lazy 887 { 888 version(D_Coverage) {} else pragma(inline, true); 889 return _store.ptr; 890 } 891 892 /// Mutable pointer. 893 private MutableE* _mptr() const return @trusted 894 { 895 version(D_Coverage) {} else pragma(inline, true); 896 return cast(typeof(return))_store.ptr; 897 } 898 899 private: 900 import nxt.allocator_traits : AllocatorState; 901 mixin AllocatorState!Allocator; // put first as emsi-containers do 902 903 /** For more convenient construction. */ 904 struct Store 905 { 906 static if (hasFunctionAttributes!(Allocator.allocate, "@nogc")) 907 { 908 import nxt.gc_traits : NoGc; 909 @NoGc T* ptr; // non-GC-allocated store pointer 910 } 911 else 912 T* ptr; // GC-allocated store pointer 913 914 Capacity capacity; // store capacity 915 Capacity length; // store length 916 } 917 918 Store _store; 919 } 920 921 import std.traits : isInstanceOf; 922 import std.functional : unaryFun; 923 924 /** Remove all elements matching `predicate`. 925 926 Returns: number of elements that were removed. 927 928 TODO: implement version that doesn't use a temporary array `tmp`, which is 929 probably faster for small arrays. 930 */ 931 size_t remove(alias predicate, C)(ref C c) @trusted 932 @("complexity", "O(length)") 933 if (isInstanceOf!(DynamicArray, C) && 934 is(typeof(unaryFun!predicate(C.init[0])))) 935 { 936 C tmp; 937 size_t count = 0; 938 foreach (immutable i; 0 .. c.length) 939 { 940 if (unaryFun!predicate(c[i])) 941 { 942 count += 1; 943 import core.internal.traits : hasElaborateDestructor; 944 import nxt.container_traits : mustAddGCRange; 945 alias T = typeof(c[i]); 946 static if (hasElaborateDestructor!(T)) 947 .destroy(c[i]); 948 else static if (mustAddGCRange!(T)) 949 c[i] = T.init; // avoid GC mark-phase dereference 950 } 951 else 952 tmp.insertBackMove(c[i]); // TODO: remove unnecessary clearing of `_mptr[i]` 953 } 954 955 c.freeStore(); 956 957 import core.lifetime : moveEmplace; 958 moveEmplace(tmp, c); 959 960 return count; 961 } 962 963 /// construct and append from slices 964 @safe pure nothrow @nogc unittest 965 { 966 alias T = int; 967 alias A = DynamicArray!(T, Mallocator, uint); 968 static if (size_t.sizeof == 8) // only 64-bit 969 static assert(A.sizeof == 2 * size_t.sizeof); // only two words 970 971 auto a = A([10, 11, 12].s); 972 973 a ~= a[]; 974 assert(a[] == [10, 11, 12, 975 10, 11, 12].s); 976 977 a ~= false; 978 assert(a[] == [10, 11, 12, 979 10, 11, 12, 0].s); 980 } 981 982 /// 983 @safe pure nothrow @nogc unittest 984 { 985 alias T = int; 986 alias A = DynamicArray!(T); 987 988 A a; 989 990 a.length = 1; 991 assert(a.length == 1); 992 assert(a.capacity >= 1); 993 994 a[0] = 10; 995 996 a.insertBack(11, 12); 997 998 a ~= T.init; 999 a.insertBack([3].s); 1000 assert(a[] == [10, 11, 12, 0, 3].s); 1001 1002 import std.algorithm.iteration : filter; 1003 1004 a.insertBack([42].s[].filter!(_ => _ is 42)); 1005 assert(a[] == [10, 11, 12, 0, 3, 42].s); 1006 1007 a.insertBack([42].s[].filter!(_ => _ !is 42)); 1008 assert(a[] == [10, 11, 12, 0, 3, 42].s); 1009 1010 a ~= a[]; 1011 assert(a[] == [10, 11, 12, 0, 3, 42, 1012 10, 11, 12, 0, 3, 42].s); 1013 } 1014 1015 /// 1016 @safe pure nothrow @nogc unittest 1017 { 1018 alias T = int; 1019 alias A = DynamicArray!(T); 1020 1021 A a; // default construction allowed 1022 assert(a.empty); 1023 assert(a.length == 0); 1024 assert(a.capacity == 0); 1025 assert(a[] == []); 1026 1027 auto b = DynamicArray!int.withLength(3); 1028 assert(!b.empty); 1029 assert(b.length == 3); 1030 assert(b.capacity == 3); 1031 b[0] = 1; 1032 b[1] = 2; 1033 b[2] = 3; 1034 assert(b[] == [1, 2, 3].s); 1035 1036 b[] = [4, 5, 6].s; 1037 assert(b[] == [4, 5, 6].s); 1038 1039 const c = DynamicArray!int.withCapacity(3); 1040 assert(c.empty); 1041 assert(c.capacity == 3); 1042 assert(c[] == []); 1043 1044 // TODO: this should fail with -dip1000 1045 auto f() @safe 1046 { 1047 A a; 1048 return a[]; 1049 } 1050 auto _d = f(); 1051 1052 const e = DynamicArray!int([1, 2, 3, 4].s); 1053 assert(e.length == 4); 1054 assert(e[] == [1, 2, 3, 4].s); 1055 } 1056 1057 /// 1058 @trusted pure nothrow @nogc unittest 1059 { 1060 alias T = int; 1061 alias A = DynamicArray!(T); 1062 1063 auto a = A([1, 2, 3].s); 1064 A b = a.dup; // copy construction enabled 1065 1066 assert(a[] == b[]); // same content 1067 assert(&a[0] !is &b[0]); // but not the same 1068 1069 assert(b[] == [1, 2, 3].s); 1070 assert(b.length == 3); 1071 1072 b ~= 4; 1073 assert(a != b); 1074 a.clear(); 1075 assert(a != b); 1076 b.clear(); 1077 assert(a == b); 1078 1079 auto _c = A([1, 2, 3].s); 1080 } 1081 1082 /// DIP-1000 return ref escape analysis 1083 @safe pure nothrow @nogc unittest 1084 { 1085 alias T = int; 1086 alias A = DynamicArray!T; 1087 1088 T[] leakSlice() @safe pure nothrow @nogc 1089 { 1090 A a; 1091 return a[]; // TODO: shouldn't compile with -dip1000 1092 } 1093 1094 T* leakPointer() @safe pure nothrow @nogc 1095 { 1096 A a; 1097 return a._store.ptr; // TODO: shouldn't compile with -dip1000 1098 } 1099 1100 auto _lp = leakPointer(); // TODO: shouldn't compile with -dip1000 1101 auto _ls = leakSlice(); // TODO: shouldn't compile with -dip1000 1102 } 1103 1104 version(unittest) 1105 { 1106 private static struct SomeUncopyable 1107 { 1108 @disable this(this); 1109 int _x; 1110 } 1111 } 1112 1113 /// construct and insert from non-copyable element type passed by value 1114 @safe pure nothrow /*@nogc*/ unittest 1115 { 1116 alias A = DynamicArray!(SomeUncopyable); 1117 1118 A a = A(SomeUncopyable(17)); 1119 assert(a[] == [SomeUncopyable(17)]); 1120 1121 a.insertBack(SomeUncopyable(18)); 1122 assert(a[] == [SomeUncopyable(17), 1123 SomeUncopyable(18)]); 1124 1125 a ~= SomeUncopyable(19); 1126 assert(a[] == [SomeUncopyable(17), 1127 SomeUncopyable(18), 1128 SomeUncopyable(19)]); 1129 } 1130 1131 /// construct from slice of uncopyable type 1132 @safe pure nothrow @nogc unittest 1133 { 1134 alias _A = DynamicArray!(SomeUncopyable); 1135 // TODO: can we safely support this?: A a = [SomeUncopyable(17)]; 1136 } 1137 1138 // construct from array with uncopyable elements 1139 @safe pure nothrow @nogc unittest 1140 { 1141 alias A = DynamicArray!(SomeUncopyable); 1142 1143 A a; 1144 assert(a.empty); 1145 1146 // TODO: a.insertBack(A.init); 1147 assert(a.empty); 1148 } 1149 1150 // construct from ranges of uncopyable elements 1151 @safe pure nothrow @nogc unittest 1152 { 1153 alias T = SomeUncopyable; 1154 alias A = DynamicArray!T; 1155 1156 A a; 1157 assert(a.empty); 1158 1159 // import std.algorithm.iteration : map, filter; 1160 1161 // const b = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => T(_^^2))); // hasLength 1162 // assert(b.length == 3); 1163 // assert(b == [T(100), T(400), T(900)].s); 1164 1165 // const c = A.withElementsOfRange_untested([10, 20, 30].s[].filter!(_ => _ == 30).map!(_ => T(_^^2))); // !hasLength 1166 // assert(c.length == 1); 1167 // assert(c[0].x == 900); 1168 } 1169 1170 // construct from ranges of copyable elements 1171 @safe pure nothrow @nogc unittest 1172 { 1173 alias T = int; 1174 alias A = DynamicArray!T; 1175 1176 A a; 1177 assert(a.empty); 1178 1179 import std.algorithm.iteration : map, filter; 1180 1181 const b = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => T(_^^2))); // hasLength 1182 assert(b.length == 3); 1183 assert(b == [T(100), T(400), T(900)].s); 1184 1185 () @trusted { // TODO: remove @trusted 1186 const c = A.withElementsOfRange_untested([10, 20, 30].s[].filter!(_ => _ == 30).map!(_ => T(_^^2))); // !hasLength 1187 assert(c == [T(900)].s); 1188 } (); 1189 } 1190 1191 /// construct with string as element type that needs GC-range 1192 @safe pure nothrow @nogc unittest 1193 { 1194 alias T = string; 1195 alias A = DynamicArray!(T); 1196 1197 A a; 1198 a ~= `alpha`; 1199 a ~= `beta`; 1200 a ~= [`gamma`, `delta`].s; 1201 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`].s); 1202 1203 const b = [`epsilon`].s; 1204 1205 a.insertBack(b); 1206 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`, `epsilon`].s); 1207 1208 a ~= b; 1209 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`, `epsilon`, `epsilon`].s); 1210 } 1211 1212 /// convert to string 1213 version(none) // TODO: make this work 1214 unittest 1215 { 1216 alias T = int; 1217 alias A = DynamicArray!(T); 1218 1219 DynamicArray!char sink; 1220 A([1, 2, 3]).toString(sink.put); 1221 } 1222 1223 /// iteration over mutable elements 1224 @safe pure nothrow @nogc unittest 1225 { 1226 alias T = int; 1227 alias A = DynamicArray!(T); 1228 1229 auto a = A([1, 2, 3].s); 1230 1231 foreach (immutable i, const e; a) 1232 { 1233 assert(i + 1 == e); 1234 } 1235 } 1236 1237 /// iteration over `const`ant elements 1238 @safe pure nothrow @nogc unittest 1239 { 1240 alias T = const(int); 1241 alias A = DynamicArray!(T); 1242 1243 auto a = A([1, 2, 3].s); 1244 1245 foreach (immutable i, const e; a) 1246 { 1247 assert(i + 1 == e); 1248 } 1249 } 1250 1251 /// iteration over immutable elements 1252 @safe pure nothrow @nogc unittest 1253 { 1254 alias T = immutable(int); 1255 alias A = DynamicArray!(T); 1256 1257 auto a = A([1, 2, 3].s); 1258 1259 foreach (immutable i, const e; a) 1260 { 1261 assert(i + 1 == e); 1262 } 1263 } 1264 1265 /// removal 1266 @safe pure nothrow @nogc unittest 1267 { 1268 alias T = int; 1269 alias A = DynamicArray!(T); 1270 1271 auto a = A([1, 2, 3].s); 1272 assert(a == [1, 2, 3].s); 1273 1274 assert(a.frontPop() == 1); 1275 assert(a == [2, 3].s); 1276 1277 a.popAt(1); 1278 assert(a == [2].s); 1279 1280 a.popAt(0); 1281 assert(a == []); 1282 1283 a.insertBack(11); 1284 assert(a == [11].s); 1285 1286 assert(a.backPop == 11); 1287 1288 a.insertBack(17); 1289 assert(a == [17].s); 1290 a.popBack(); 1291 assert(a.empty); 1292 1293 a.insertBack([11, 12, 13, 14, 15].s[]); 1294 a.popAt(2); 1295 assert(a == [11, 12, 14, 15].s); 1296 a.popAt(0); 1297 assert(a == [12, 14, 15].s); 1298 a.popAt(2); 1299 1300 assert(a == [12, 14].s); 1301 1302 a ~= a; 1303 } 1304 1305 /// removal 1306 @safe pure nothrow unittest 1307 { 1308 import nxt.container_traits : mustAddGCRange; 1309 1310 size_t mallocCount = 0; 1311 size_t freeCount = 0; 1312 1313 struct S 1314 { 1315 @safe pure nothrow @nogc: 1316 1317 alias E = int; 1318 1319 import nxt.qcmeman : malloc, free; 1320 1321 this(E x) @trusted 1322 { 1323 _ptr = cast(E*)malloc(E.sizeof); 1324 mallocCount += 1; 1325 *_ptr = x; 1326 } 1327 1328 @disable this(this); 1329 1330 ~this() @trusted @nogc 1331 { 1332 free(_ptr); 1333 freeCount += 1; 1334 } 1335 1336 import nxt.gc_traits : NoGc; 1337 @NoGc E* _ptr; 1338 } 1339 1340 /* D compilers cannot currently move stuff efficiently when using 1341 std.algorithm.mutation.move. A final dtor call to the cleared sourced is 1342 always done. 1343 */ 1344 size_t extraDtor = 1; 1345 1346 alias A = DynamicArray!(S); 1347 static assert(!mustAddGCRange!A); 1348 alias AA = DynamicArray!(A); 1349 static assert(!mustAddGCRange!AA); 1350 1351 assert(mallocCount == 0); 1352 1353 { 1354 A a; 1355 a.insertBack(S(11)); 1356 assert(mallocCount == 1); 1357 assert(freeCount == extraDtor + 0); 1358 } 1359 1360 assert(freeCount == extraDtor + 1); 1361 1362 // assert(a.front !is S(11)); 1363 // assert(a.back !is S(11)); 1364 // a.insertBack(S(12)); 1365 } 1366 1367 /// test `OutputRange` behaviour with std.format 1368 version(none) // TODO: replace with other exercise of std.format 1369 @safe pure /*TODO: nothrow @nogc*/ unittest 1370 { 1371 import std.format : formattedWrite; 1372 const x = "42"; 1373 alias A = DynamicArray!(char); 1374 A a; 1375 a.formattedWrite!("x : %s")(x); 1376 assert(a == "x : 42"); 1377 } 1378 1379 /// test emplaceWithMovedElements 1380 @trusted pure nothrow @nogc unittest 1381 { 1382 alias A = DynamicArray!(char); 1383 1384 auto ae = ['a', 'b'].s; 1385 1386 A a = void; 1387 A.emplaceWithMovedElements(&a, ae[]); 1388 1389 assert(a.length == ae.length); 1390 assert(a.capacity == ae.length); 1391 assert(a[] == ae); 1392 } 1393 1394 /// test emplaceWithCopiedElements 1395 @trusted pure nothrow @nogc unittest 1396 { 1397 alias A = DynamicArray!(char); 1398 1399 auto ae = ['a', 'b'].s; 1400 1401 A a = void; 1402 A.emplaceWithCopiedElements(&a, ae[]); 1403 1404 assert(a.length == ae.length); 1405 assert(a.capacity == ae.length); 1406 assert(a[] == ae); 1407 } 1408 1409 @safe pure nothrow @nogc unittest 1410 { 1411 alias T = int; 1412 alias A = DynamicArray!(T, Mallocator, uint); 1413 const a = A(17); 1414 assert(a[] == [17].s); 1415 } 1416 1417 /// check duplication via `dup` 1418 @trusted pure nothrow @nogc unittest 1419 { 1420 alias T = int; 1421 alias A = DynamicArray!(T); 1422 1423 static assert(!__traits(compiles, { A b = a; })); // copying disabled 1424 1425 auto a = A([10, 11, 12].s); 1426 auto b = a.dup; 1427 assert(a == b); 1428 assert(&a[0] !is &b[0]); 1429 } 1430 1431 /// element type is a class 1432 @safe pure nothrow unittest 1433 { 1434 class T 1435 { 1436 this (int x) 1437 { 1438 this.x = x; 1439 } 1440 ~this() @nogc { x = 42; } 1441 int x; 1442 } 1443 alias A = DynamicArray!(T); 1444 auto a = A([new T(10), 1445 new T(11), 1446 new T(12)].s); 1447 assert(a.length == 3); 1448 a.remove!(_ => _.x == 12); 1449 assert(a.length == 2); 1450 } 1451 1452 /// check filtered removal via `remove` 1453 @safe pure nothrow @nogc unittest 1454 { 1455 struct T 1456 { 1457 int value; 1458 } 1459 1460 alias A = DynamicArray!(T); 1461 1462 static assert(!__traits(compiles, { A b = a; })); // copying disabled 1463 1464 auto a = A([T(10), T(11), T(12)].s); 1465 1466 assert(a.remove!"a.value == 13" == 0); 1467 assert(a[] == [T(10), T(11), T(12)].s); 1468 1469 assert(a.remove!"a.value >= 12" == 1); 1470 assert(a[] == [T(10), T(11)].s); 1471 1472 assert(a.remove!(_ => _.value == 10) == 1); 1473 assert(a[] == [T(11)].s); 1474 1475 assert(a.remove!(_ => _.value == 11) == 1); 1476 assert(a.empty); 1477 } 1478 1479 /// construct from map range 1480 @safe pure nothrow unittest 1481 { 1482 import std.algorithm.iteration : map; 1483 alias T = int; 1484 alias A = DynamicArray!(T); 1485 1486 A a = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => _^^2)); 1487 assert(a[] == [100, 400, 900].s); 1488 a.popBackN(2); 1489 assert(a.length == 1); 1490 a.popBackN(1); 1491 assert(a.empty); 1492 1493 A b = A([10, 20, 30].s[].map!(_ => _^^2)); 1494 assert(b[] == [100, 400, 900].s); 1495 b.popBackN(2); 1496 assert(b.length == 1); 1497 b.popBackN(1); 1498 assert(b.empty); 1499 1500 A c = A([10, 20, 30].s[]); 1501 assert(c[] == [10, 20, 30].s); 1502 } 1503 1504 /// construct from map range 1505 @trusted pure nothrow unittest 1506 { 1507 alias T = int; 1508 alias A = DynamicArray!(T); 1509 1510 import std.typecons : RefCounted; 1511 RefCounted!A x; 1512 1513 auto z = [1, 2, 3].s; 1514 x ~= z[]; 1515 1516 auto y = x; 1517 assert(y[] == z); 1518 1519 auto _ = x.toHash; 1520 } 1521 1522 /// construct from static array 1523 @trusted pure nothrow @nogc unittest 1524 { 1525 alias T = uint; 1526 alias A = DynamicArray!(T); 1527 1528 ushort[3] a = [1, 2, 3]; 1529 1530 auto x = A(a); 1531 assert(x == a); 1532 assert(x == a[]); 1533 } 1534 1535 /// construct from static array slice 1536 @trusted pure nothrow @nogc unittest 1537 { 1538 alias T = uint; 1539 alias A = DynamicArray!(T); 1540 1541 ushort[3] a = [1, 2, 3]; 1542 ushort[] b = a[]; 1543 1544 auto y = A(b); // cannot construct directly from `a[]` because its type is `ushort[3]` 1545 assert(y == a); 1546 assert(y == a[]); 1547 } 1548 1549 /// GCAllocator 1550 @trusted pure nothrow unittest 1551 { 1552 import std.experimental.allocator.gc_allocator : GCAllocator; 1553 alias T = int; 1554 alias A = DynamicArray!(T, GCAllocator); 1555 A a; 1556 assert(a.length == 0); 1557 } 1558 1559 /// construct with slices as element types 1560 @trusted pure nothrow unittest 1561 { 1562 alias A = DynamicArray!(string); 1563 A a; 1564 assert(a.length == 0); 1565 alias B = DynamicArray!(char[]); 1566 B b; 1567 assert(b.length == 0); 1568 } 1569 1570 /** Variant of `DynamicArray` with copy construction (postblit) enabled. 1571 * 1572 * See_Also: suppressing.d 1573 * See_Also: http://forum.dlang.org/post/eitlbtfbavdphbvplnrk@forum.dlang.org 1574 */ 1575 struct BasicCopyableArray 1576 { 1577 /** TODO: implement using instructions at: 1578 * http://forum.dlang.org/post/eitlbtfbavdphbvplnrk@forum.dlang.org 1579 */ 1580 } 1581 1582 /// TODO: Move to Phobos. 1583 private enum bool isRefIterable(T) = is(typeof({ foreach (ref elem; T.init) {} })); 1584 1585 version(unittest) 1586 { 1587 import nxt.array_help : s; 1588 }