/** * This module provides an `Array` type with deterministic memory usage not * reliant on the GC, as an alternative to the built-in arrays. * * This module is a submodule of $(MREF std, container). * * Source: $(PHOBOSSRC std/container/array.d) * * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. * * License: Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP * boost.org/LICENSE_1_0.txt)). * * Authors: $(HTTP erdani.com, Andrei Alexandrescu) * * $(SCRIPT inhibitQuickIndex = 1;) */module std.container.array; import core.exception : RangeError;import std.range.primitives;import std.traits; public import std.container.util; pure @system unittest{ // We test multiple array lengths in order to ensure that the "a1.capacity == a0.length" test is meaningful // for the version in which the constructor uses insertBack // (because for some lengths, the test passes even without reserve). for (size_t n = 0; n < 100; ++n) { float[] a0; { import std.range : iota; import std.array : array; import std.algorithm.iteration : map; a0 = iota (0, n).map!(i => i * 1.1f).array; } auto a1 = Array!float(a0); // We check that a1 has the same length and contents as a0: { assert(a1.length == a0.length); // I wish that I could write "assert(a1[] == a0[]);", // but the compiler complains: "Error: incompatible types for `(a1.opSlice()) == (a0[])`: `RangeT!(Array!float)` and `float[]`". import std.algorithm.comparison : equal; assert(equal(a1[], a0[])); } // We check that a1's constructor has called reserve (to maintain good performance): assert(a1.capacity == a0.length); }} pure @system unittest{ // To avoid bad performance, we check that an Array constructed from an empty range // does not initialize its RefCountedStore object, even after a call to "reserve(0)". { Array!float a1; assert(! a1._data.refCountedStore.isInitialized); a1.reserve(0); assert(! a1._data.refCountedStore.isInitialized); } { float[] a0 = []; Array!float a1 = a0; // [2021-09-26] TODO: Investigate RefCounted. //assert(! a1._data.refCountedStore.isInitialized); a1.reserve(0); // [2021-09-26] TODO: Investigate RefCounted. //assert(! a1._data.refCountedStore.isInitialized); }} ///pure @system unittest{ auto arr = Array!int(0, 2, 3); assert(arr[0] == 0); assert(arr.front == 0); assert(arr.back == 3); // reserve space arr.reserve(1000); assert(arr.length == 3); assert(arr.capacity >= 1000); // insertion arr.insertBefore(arr[1..$], 1); assert(arr.front == 0); assert(arr.length == 4); arr.insertBack(4); assert(arr.back == 4); assert(arr.length == 5); // set elements arr[1] *= 42; assert(arr[1] == 42);} ///pure @system unittest{ import std.algorithm.comparison : equal; auto arr = Array!int(1, 2, 3); // concat auto b = Array!int(11, 12, 13); arr ~= b; assert(arr.length == 6); // slicing assert(arr[1 .. 3].equal([2, 3])); // remove arr.linearRemove(arr[1 .. 3]); assert(arr[0 .. 2].equal([1, 11]));} /// `Array!bool` packs together values efficiently by allocating one bit per elementpure @system unittest{ auto arr = Array!bool([true, true, false, true, false]); assert(arr.length == 5);} private struct RangeT(A){ /* Workaround for https://issues.dlang.org/show_bug.cgi?id=13629 See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org */ private A[1] _outer_; private @property ref inout(A) _outer() inout { return _outer_[0]; } private size_t _a, _b; /* E is different from T when A is more restrictively qualified than T: immutable(Array!int) => T == int, E = immutable(int) */ alias E = typeof(_outer_[0]._data._payload[0]); private this(ref A data, size_t a, size_t b) { _outer_ = data; _a = a; _b = b; } @property RangeT save() { return this; } @property bool empty() @safe pure nothrow const { return _a >= _b; } @property size_t length() @safe pure nothrow const { return _b - _a; } alias opDollar = length; @property ref inout(E) front() inout { assert(!empty, "Attempting to access the front of an empty Array"); return _outer[_a]; } @property ref inout(E) back() inout { assert(!empty, "Attempting to access the back of an empty Array"); return _outer[_b - 1]; } void popFront() @safe @nogc pure nothrow { assert(!empty, "Attempting to popFront an empty Array"); ++_a; } void popBack() @safe @nogc pure nothrow { assert(!empty, "Attempting to popBack an empty Array"); --_b; } static if (isMutable!A) { import std.algorithm.mutation : move; E moveFront() { assert(!empty, "Attempting to moveFront an empty Array"); assert(_a < _outer.length, "Attempting to moveFront using an out of bounds low index on an Array"); return move(_outer._data._payload[_a]); } E moveBack() { assert(!empty, "Attempting to moveBack an empty Array"); assert(_b - 1 < _outer.length, "Attempting to moveBack using an out of bounds high index on an Array"); return move(_outer._data._payload[_b - 1]); } E moveAt(size_t i) { assert(_a + i < _b, "Attempting to moveAt using an out of bounds index on an Array"); assert(_a + i < _outer.length, "Cannot move past the end of the array"); return move(_outer._data._payload[_a + i]); } } ref inout(E) opIndex(size_t i) inout { assert(_a + i < _b, "Attempting to fetch using an out of bounds index on an Array"); return _outer[_a + i]; } RangeT opSlice() { return typeof(return)(_outer, _a, _b); } RangeT opSlice(size_t i, size_t j) { assert(i <= j && _a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); return typeof(return)(_outer, _a + i, _a + j); } RangeT!(const(A)) opSlice() const { return typeof(return)(_outer, _a, _b); } RangeT!(const(A)) opSlice(size_t i, size_t j) const { assert(i <= j && _a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); return typeof(return)(_outer, _a + i, _a + j); } static if (isMutable!A) { void opSliceAssign(E value) { assert(_b <= _outer.length, "Attempting to assign using an out of bounds indices on an Array"); _outer[_a .. _b] = value; } void opSliceAssign(E value, size_t i, size_t j) { assert(_a + j <= _b, "Attempting to slice assign using an out of bounds indices on an Array"); _outer[_a + i .. _a + j] = value; } void opSliceUnary(string op)() if (op == "++" || op == "--") { assert(_b <= _outer.length, "Attempting to slice using an out of bounds indices on an Array"); mixin(op~"_outer[_a .. _b];"); } void opSliceUnary(string op)(size_t i, size_t j) if (op == "++" || op == "--") { assert(_a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); mixin(op~"_outer[_a + i .. _a + j];"); } void opSliceOpAssign(string op)(E value) { assert(_b <= _outer.length, "Attempting to slice using an out of bounds indices on an Array"); mixin("_outer[_a .. _b] "~op~"= value;"); } void opSliceOpAssign(string op)(E value, size_t i, size_t j) { assert(_a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); mixin("_outer[_a + i .. _a + j] "~op~"= value;"); } }} @system unittest{ enum : bool { display = false } static if (display) { import std.stdio; enum { nDigitsForPointer = 2 * size_t.sizeof, nDigitsForNObjects = 4 } } static struct S { static size_t s_nConstructed; static size_t s_nDestroyed; static void throwIfTooMany() { if (s_nConstructed >= 7) throw new Exception ("Ka-boom !"); } uint _i; ~this() { static if (display) writefln("@%*Xh: Destroying.", nDigitsForPointer, &this); ++s_nDestroyed; } this(uint i) { static if (display) writefln("@%*Xh: Constructing.", nDigitsForPointer, &this); _i = i; ++s_nConstructed; throwIfTooMany(); } this(this) { static if (display) writefln("@%*Xh: Copying.", nDigitsForPointer, &this); ++s_nConstructed; throwIfTooMany(); } } try { auto a = Array!S (S(0), S(1), S(2), S(3)); static if (display) writefln("@%*Xh: This is where the array elements are.", nDigitsForPointer, &a [0]); } catch (Exception e) { static if (display) writefln("Exception caught !"); } static if (display) { writefln("s_nConstructed %*Xh.", nDigitsForNObjects, S.s_nConstructed); writefln("s_nDestroyed %*Xh.", nDigitsForNObjects, S.s_nDestroyed); writefln("s_nConstructed should be equal to s_nDestroyed."); writefln(""); } assert(S.s_nDestroyed == S.s_nConstructed);} /** * _Array type with deterministic control of memory. The memory allocated * for the array is reclaimed as soon as possible; there is no reliance * on the garbage collector. `Array` uses `malloc`, `realloc` and `free` * for managing its own memory. * * This means that pointers to elements of an `Array` will become * dangling as soon as the element is removed from the `Array`. On the other hand * the memory allocated by an `Array` will be scanned by the GC and * GC managed objects referenced from an `Array` will be kept alive. * * Note: * * When using `Array` with range-based functions like those in `std.algorithm`, * `Array` must be sliced to get a range (for example, use `array[].map!` * instead of `array.map!`). The container itself is not a range. */struct Array(T)if (!is(immutable T == immutable bool)){ import core.memory : free = pureFree; import std.internal.memory : enforceMalloc, enforceRealloc; import core.stdc.string : memcpy, memmove, memset; import core.memory : GC; import std.exception : enforce; import std.typecons : RefCounted, RefCountedAutoInitialize; // This structure is not copyable. private struct Payload { size_t _capacity; T[] _payload; this(T[] p) { _capacity = p.length; _payload = p; } // Destructor releases array memory ~this() { // Warning: destroy would destroy also class instances. // The hasElaborateDestructor protects us here. static if (hasElaborateDestructor!T) foreach (ref e; _payload) .destroy(e); static if (hasIndirections!T) GC.removeRange(cast(void*) _payload.ptr); free(cast(void*) _payload.ptr); } this(this) @disable; void opAssign(Payload rhs) @disable; @property size_t length() const { return _payload.length; } @property void length(size_t newLength) { if (length >= newLength) { // shorten static if (hasElaborateDestructor!T) foreach (ref e; _payload.ptr[newLength .. _payload.length]) .destroy(e); _payload = _payload.ptr[0 .. newLength]; return; } static if (__traits(compiles, { static T _; })) { import std.algorithm.mutation : initializeAll; immutable startEmplace = length; reserve(newLength); initializeAll(_payload.ptr[startEmplace .. newLength]); _payload = _payload.ptr[0 .. newLength]; } else { assert(0, "Cannot add elements to array because `" ~ fullyQualifiedName!T ~ ".this()` is annotated with " ~ "`@disable`."); } } @property size_t capacity() const { return _capacity; } void reserve(size_t elements) { if (elements <= capacity) return; static if (T.sizeof == 1) { const sz = elements; } else { import core.checkedint : mulu; bool overflow; const sz = mulu(elements, T.sizeof, overflow); if (overflow) assert(false, "Overflow"); } static if (hasIndirections!T) { /* Because of the transactional nature of this * relative to the garbage collector, ensure no * threading bugs by using malloc/copy/free rather * than realloc. */ immutable oldLength = length; auto newPayloadPtr = cast(T*) enforceMalloc(sz); auto newPayload = newPayloadPtr[0 .. oldLength]; // copy old data over to new array memcpy(cast(void*) newPayload.ptr, cast(void*) _payload.ptr, T.sizeof * oldLength); // Zero out unused capacity to prevent gc from seeing false pointers memset( cast(void*) (newPayload.ptr + oldLength), 0, (elements - oldLength) * T.sizeof); GC.addRange(cast(void*) newPayload.ptr, sz); GC.removeRange(cast(void*) _payload.ptr); free(cast(void*) _payload.ptr); _payload = newPayload;Lines 1–500 of 2795. Load more
/** * This module provides an `Array` type with deterministic memory usage not * reliant on the GC, as an alternative to the built-in arrays. * * This module is a submodule of $(MREF std, container). * * Source: $(PHOBOSSRC std/container/array.d) * * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. * * License: Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP * boost.org/LICENSE_1_0.txt)). * * Authors: $(HTTP erdani.com, Andrei Alexandrescu) * * $(SCRIPT inhibitQuickIndex = 1;) */ module std.container.array; import core.exception : RangeError; import std.range.primitives; import std.traits; public import std.container.util; pure @system unittest { // We test multiple array lengths in order to ensure that the "a1.capacity == a0.length" test is meaningful // for the version in which the constructor uses insertBack // (because for some lengths, the test passes even without reserve). for (size_t n = 0; n < 100; ++n) { float[] a0; { import std.range : iota; import std.array : array; import std.algorithm.iteration : map; a0 = iota (0, n).map!(i => i * 1.1f).array; } auto a1 = Array!float(a0); // We check that a1 has the same length and contents as a0: { assert(a1.length == a0.length); // I wish that I could write "assert(a1[] == a0[]);", // but the compiler complains: "Error: incompatible types for `(a1.opSlice()) == (a0[])`: `RangeT!(Array!float)` and `float[]`". import std.algorithm.comparison : equal; assert(equal(a1[], a0[])); } // We check that a1's constructor has called reserve (to maintain good performance): assert(a1.capacity == a0.length); } } pure @system unittest { // To avoid bad performance, we check that an Array constructed from an empty range // does not initialize its RefCountedStore object, even after a call to "reserve(0)". { Array!float a1; assert(! a1._data.refCountedStore.isInitialized); a1.reserve(0); assert(! a1._data.refCountedStore.isInitialized); } { float[] a0 = []; Array!float a1 = a0; // [2021-09-26] TODO: Investigate RefCounted. //assert(! a1._data.refCountedStore.isInitialized); a1.reserve(0); // [2021-09-26] TODO: Investigate RefCounted. //assert(! a1._data.refCountedStore.isInitialized); } } /// pure @system unittest { auto arr = Array!int(0, 2, 3); assert(arr[0] == 0); assert(arr.front == 0); assert(arr.back == 3); // reserve space arr.reserve(1000); assert(arr.length == 3); assert(arr.capacity >= 1000); // insertion arr.insertBefore(arr[1..$], 1); assert(arr.front == 0); assert(arr.length == 4); arr.insertBack(4); assert(arr.back == 4); assert(arr.length == 5); // set elements arr[1] *= 42; assert(arr[1] == 42); } /// pure @system unittest { import std.algorithm.comparison : equal; auto arr = Array!int(1, 2, 3); // concat auto b = Array!int(11, 12, 13); arr ~= b; assert(arr.length == 6); // slicing assert(arr[1 .. 3].equal([2, 3])); // remove arr.linearRemove(arr[1 .. 3]); assert(arr[0 .. 2].equal([1, 11])); } /// `Array!bool` packs together values efficiently by allocating one bit per element pure @system unittest { auto arr = Array!bool([true, true, false, true, false]); assert(arr.length == 5); } private struct RangeT(A) { /* Workaround for https://issues.dlang.org/show_bug.cgi?id=13629 See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org */ private A[1] _outer_; private @property ref inout(A) _outer() inout { return _outer_[0]; } private size_t _a, _b; /* E is different from T when A is more restrictively qualified than T: immutable(Array!int) => T == int, E = immutable(int) */ alias E = typeof(_outer_[0]._data._payload[0]); private this(ref A data, size_t a, size_t b) { _outer_ = data; _a = a; _b = b; } @property RangeT save() { return this; } @property bool empty() @safe pure nothrow const { return _a >= _b; } @property size_t length() @safe pure nothrow const { return _b - _a; } alias opDollar = length; @property ref inout(E) front() inout { assert(!empty, "Attempting to access the front of an empty Array"); return _outer[_a]; } @property ref inout(E) back() inout { assert(!empty, "Attempting to access the back of an empty Array"); return _outer[_b - 1]; } void popFront() @safe @nogc pure nothrow { assert(!empty, "Attempting to popFront an empty Array"); ++_a; } void popBack() @safe @nogc pure nothrow { assert(!empty, "Attempting to popBack an empty Array"); --_b; } static if (isMutable!A) { import std.algorithm.mutation : move; E moveFront() { assert(!empty, "Attempting to moveFront an empty Array"); assert(_a < _outer.length, "Attempting to moveFront using an out of bounds low index on an Array"); return move(_outer._data._payload[_a]); } E moveBack() { assert(!empty, "Attempting to moveBack an empty Array"); assert(_b - 1 < _outer.length, "Attempting to moveBack using an out of bounds high index on an Array"); return move(_outer._data._payload[_b - 1]); } E moveAt(size_t i) { assert(_a + i < _b, "Attempting to moveAt using an out of bounds index on an Array"); assert(_a + i < _outer.length, "Cannot move past the end of the array"); return move(_outer._data._payload[_a + i]); } } ref inout(E) opIndex(size_t i) inout { assert(_a + i < _b, "Attempting to fetch using an out of bounds index on an Array"); return _outer[_a + i]; } RangeT opSlice() { return typeof(return)(_outer, _a, _b); } RangeT opSlice(size_t i, size_t j) { assert(i <= j && _a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); return typeof(return)(_outer, _a + i, _a + j); } RangeT!(const(A)) opSlice() const { return typeof(return)(_outer, _a, _b); } RangeT!(const(A)) opSlice(size_t i, size_t j) const { assert(i <= j && _a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); return typeof(return)(_outer, _a + i, _a + j); } static if (isMutable!A) { void opSliceAssign(E value) { assert(_b <= _outer.length, "Attempting to assign using an out of bounds indices on an Array"); _outer[_a .. _b] = value; } void opSliceAssign(E value, size_t i, size_t j) { assert(_a + j <= _b, "Attempting to slice assign using an out of bounds indices on an Array"); _outer[_a + i .. _a + j] = value; } void opSliceUnary(string op)() if (op == "++" || op == "--") { assert(_b <= _outer.length, "Attempting to slice using an out of bounds indices on an Array"); mixin(op~"_outer[_a .. _b];"); } void opSliceUnary(string op)(size_t i, size_t j) if (op == "++" || op == "--") { assert(_a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); mixin(op~"_outer[_a + i .. _a + j];"); } void opSliceOpAssign(string op)(E value) { assert(_b <= _outer.length, "Attempting to slice using an out of bounds indices on an Array"); mixin("_outer[_a .. _b] "~op~"= value;"); } void opSliceOpAssign(string op)(E value, size_t i, size_t j) { assert(_a + j <= _b, "Attempting to slice using an out of bounds indices on an Array"); mixin("_outer[_a + i .. _a + j] "~op~"= value;"); } } } @system unittest { enum : bool { display = false } static if (display) { import std.stdio; enum { nDigitsForPointer = 2 * size_t.sizeof, nDigitsForNObjects = 4 } } static struct S { static size_t s_nConstructed; static size_t s_nDestroyed; static void throwIfTooMany() { if (s_nConstructed >= 7) throw new Exception ("Ka-boom !"); } uint _i; ~this() { static if (display) writefln("@%*Xh: Destroying.", nDigitsForPointer, &this); ++s_nDestroyed; } this(uint i) { static if (display) writefln("@%*Xh: Constructing.", nDigitsForPointer, &this); _i = i; ++s_nConstructed; throwIfTooMany(); } this(this) { static if (display) writefln("@%*Xh: Copying.", nDigitsForPointer, &this); ++s_nConstructed; throwIfTooMany(); } } try { auto a = Array!S (S(0), S(1), S(2), S(3)); static if (display) writefln("@%*Xh: This is where the array elements are.", nDigitsForPointer, &a [0]); } catch (Exception e) { static if (display) writefln("Exception caught !"); } static if (display) { writefln("s_nConstructed %*Xh.", nDigitsForNObjects, S.s_nConstructed); writefln("s_nDestroyed %*Xh.", nDigitsForNObjects, S.s_nDestroyed); writefln("s_nConstructed should be equal to s_nDestroyed."); writefln(""); } assert(S.s_nDestroyed == S.s_nConstructed); } /** * _Array type with deterministic control of memory. The memory allocated * for the array is reclaimed as soon as possible; there is no reliance * on the garbage collector. `Array` uses `malloc`, `realloc` and `free` * for managing its own memory. * * This means that pointers to elements of an `Array` will become * dangling as soon as the element is removed from the `Array`. On the other hand * the memory allocated by an `Array` will be scanned by the GC and * GC managed objects referenced from an `Array` will be kept alive. * * Note: * * When using `Array` with range-based functions like those in `std.algorithm`, * `Array` must be sliced to get a range (for example, use `array[].map!` * instead of `array.map!`). The container itself is not a range. */ struct Array(T) if (!is(immutable T == immutable bool)) { import core.memory : free = pureFree; import std.internal.memory : enforceMalloc, enforceRealloc; import core.stdc.string : memcpy, memmove, memset; import core.memory : GC; import std.exception : enforce; import std.typecons : RefCounted, RefCountedAutoInitialize; // This structure is not copyable. private struct Payload { size_t _capacity; T[] _payload; this(T[] p) { _capacity = p.length; _payload = p; } // Destructor releases array memory ~this() { // Warning: destroy would destroy also class instances. // The hasElaborateDestructor protects us here. static if (hasElaborateDestructor!T) foreach (ref e; _payload) .destroy(e); static if (hasIndirections!T) GC.removeRange(cast(void*) _payload.ptr); free(cast(void*) _payload.ptr); } this(this) @disable; void opAssign(Payload rhs) @disable; @property size_t length() const { return _payload.length; } @property void length(size_t newLength) { if (length >= newLength) { // shorten static if (hasElaborateDestructor!T) foreach (ref e; _payload.ptr[newLength .. _payload.length]) .destroy(e); _payload = _payload.ptr[0 .. newLength]; return; } static if (__traits(compiles, { static T _; })) { import std.algorithm.mutation : initializeAll; immutable startEmplace = length; reserve(newLength); initializeAll(_payload.ptr[startEmplace .. newLength]); _payload = _payload.ptr[0 .. newLength]; } else { assert(0, "Cannot add elements to array because `" ~ fullyQualifiedName!T ~ ".this()` is annotated with " ~ "`@disable`."); } } @property size_t capacity() const { return _capacity; } void reserve(size_t elements) { if (elements <= capacity) return; static if (T.sizeof == 1) { const sz = elements; } else { import core.checkedint : mulu; bool overflow; const sz = mulu(elements, T.sizeof, overflow); if (overflow) assert(false, "Overflow"); } static if (hasIndirections!T) { /* Because of the transactional nature of this * relative to the garbage collector, ensure no * threading bugs by using malloc/copy/free rather * than realloc. */ immutable oldLength = length; auto newPayloadPtr = cast(T*) enforceMalloc(sz); auto newPayload = newPayloadPtr[0 .. oldLength]; // copy old data over to new array memcpy(cast(void*) newPayload.ptr, cast(void*) _payload.ptr, T.sizeof * oldLength); // Zero out unused capacity to prevent gc from seeing false pointers memset( cast(void*) (newPayload.ptr + oldLength), 0, (elements - oldLength) * T.sizeof); GC.addRange(cast(void*) newPayload.ptr, sz); GC.removeRange(cast(void*) _payload.ptr); free(cast(void*) _payload.ptr); _payload = newPayload;