nxt.array_help source code

1 module nxt.array_help;
2 
3 import core.internal.traits : Unqual;
4 
5 @safe:
6 
7 /** Returns: statically (stack) allocated array with elements of type `T` of
8  * length `n`.
9  *
10  * For more convenient usage alias it as `s' together with UFCS for the
11  * following convenient notation:
12  *
13  * const x = [1, 2, 3].s;
14  *
15  * TODO: Replace with Phobos `staticArray` when dmd automatically does move for uncopyable `T`.
16  *
17  * TODO: Fix problems discussed here: http://forum.dlang.org/post/otrsanpgmokzpzqmfyvx@forum.dlang.org
18  * TODO: File a bug report: http://forum.dlang.org/post/otrsanpgmokzpzqmfyvx@forum.dlang.org
19  *
20  * TODO: fix compiler so that move kicks in here automatically and remove
21  * special case on `isCopyable`
22  *
23  * See_Also: http://dpaste.dzfl.pl/d0059e6e6c09
24  * See_Also: http://forum.dlang.org/post/oq0cd1$2ji3$1@digitalmars.com
25  */
26 Unqual!T[n] staticArray(T, size_t n)(T[n] x...) @trusted
27 {
28     static if (__traits(isCopyable, T))  // TODO: remove when compiler does move for us
29         return x[];
30     else                      // TODO: remove `move` when compiler does it for us
31     {
32         // TODO: remove `move` when compiler does it for us:
33         T[n] y = void;        // initialized below
34         import core.internal.traits : hasElaborateDestructor;
35         static if (hasElaborateDestructor!T)
36         {
37             import core.lifetime : move;
38             /* NOTE: moveEmplaceAll doesn't support uncopyable elements
39              * import std.algorithm.mutation : moveEmplaceAll;
40              * moveEmplaceAll(x[], y[]);
41              */
42             foreach (const ix, ref value; x)
43                 move(value, y[ix]);
44         }
45         else
46         {
47             import core.stdc.string : memcpy;
48             memcpy(y.ptr, x.ptr, n*T.sizeof); // fast
49         }
50         return y;
51     }
52 }
53 alias s = staticArray;
54 
55 @safe pure unittest
56 {
57     // assert([].staticArray.ptr == null);
58     assert([].s.length == 0);
59 }
60 
61 version(none)
62 @safe pure unittest
63 {
64     import std.array : staticArray;
65     assert([].staticArray.ptr !is null);
66     assert([].staticArray.length == 0);
67 }
68 
69 /** Make a static array. */
70 version(none)
71 auto staticArrayAlternative() @safe
72 {
73     static struct _staticArray
74     {
75         T[n] s(T, size_t n)(auto ref T[n] values) @safe @property { return values; }
76 
77         T[0][n] opIndex(size_t n = T.length, T...)(T items)
78         {
79             typeof(return) arr;
80             foreach (index,item; items)
81                 arr[index] = item;
82 
83             return (values) { return values; } (arr);//s!(T[0], n)(arr);
84         }
85     }
86     return _staticArray();
87 }
88 
89 version(unittest)
90 {
91     static struct US
92     {
93         @disable this(this);
94         int x;
95         void f() { x = 42; }
96     }
97 }
98 
99 ///
100 @safe pure nothrow @nogc unittest
101 {
102     auto a = [1, 2, 3].staticArray;
103     static assert(is(typeof(a) == int[a.length]));
104     static assert(is(typeof([1, 2, 3].staticArray) == int[a.length]));
105 
106     auto b = "hello".s;
107     static assert(is(typeof(b) == char[5]));
108 
109     auto x = s!ubyte(1, 2, 3);
110     static assert(is(typeof(x) == ubyte[3]));
111 }
112 
113 /// non-copyable element type in static array
114 @safe pure nothrow @nogc unittest
115 {
116     auto b = [US(42)].s;
117     static assert(b.length == 1);
118 }
119 
120 ///
121 @safe pure nothrow @nogc unittest
122 {
123     auto x = [1, 2, 3].staticArray;
124 
125     static assert(is(typeof(x) == int[x.length]));
126     static assert(is(typeof([1, 2, 3].staticArray) == int[x.length]));
127 
128     static assert(!__traits(compiles,
129                             {
130                                 static int[] doNotDoThat() { return [1, 2, 3].s; }
131                             }
132                       ));
133 }
134 
135 /** Returns: `x` as a static array of unsigned bytes. */
136 @property ubyte[T.sizeof] toUbytes(T)(in T x) @trusted pure nothrow @nogc // TODO: endian-dependent
137 	=> (cast(ubyte*)(&x))[0 .. x.sizeof];
138 
139 /** Returns: `x` as a static array with elements of type `E`. */
140 @property ref inout(E)[T.sizeof] asN(E, T)(inout ref T x) @trusted pure nothrow @nogc // TODO: endian-dependent
141 if (T.sizeof % E.sizeof == 0)
142 	=> (cast(E*)(&x))[0 .. x.sizeof];
143 
144 ///
145 @safe pure nothrow @nogc unittest
146 {
147     immutable ushort x = 17;
148     auto y = x.asN!ubyte;
149     version(LittleEndian)
150         assert(y == [17, 0].s);
151 }
152 
153 /// Number of bytes in a word.
154 private enum wordBytes = size_t.sizeof;
155 
156 /// Number of bits in a word.
157 private enum wordBits = 8*wordBytes;
158 
159 /** Returns: number of words (`size_t`) needed to represent
160  * `bitCount` bits.
161  */
162 static size_t wordCountOfBitCount(size_t bitCount) @safe pure nothrow @nogc
163 	=> ((bitCount / wordBits) +
164 	(bitCount % wordBits != 0 ? 1 : 0));
165 
166 static size_t binBlockBytes(size_t bitCount) @safe pure nothrow @nogc
167 	=> wordBytes*wordCountOfBitCount(bitCount);
168 
169 /** Returns: an uninitialized bit-array containing `bitCount` number of bits. */
170 size_t* makeUninitializedBitArray(alias Allocator)(size_t bitCount) @trusted pure nothrow @nogc
171 	=> cast(typeof(return))Allocator.instance.allocate(binBlockBytes(bitCount));
172 
173 /** Returns: an zero-initialized bit-array containing `bitCount` number of bits. */
174 size_t* makeZeroedBitArray(alias Allocator)(size_t bitCount) @trusted pure nothrow @nogc
175 {
176     version(D_Coverage) {} else pragma(inline, true);
177 	const numBytes = binBlockBytes(bitCount);
178     static if (__traits(hasMember, Allocator, "allocateZeroed"))
179         return cast(typeof(return))Allocator.instance.allocateZeroed(numBytes);
180     else
181 	{
182 		import core.stdc.string : memset;
183 		auto result = allocator.allocate(numBytes).ptr;
184 		memset(result, 0, numBytes);
185 		return cast(typeof(return))result;
186 	}
187 }
188 
189 /** Returns: `input` reallocated to contain `newBitCount` number of bits. New bits
190  * are default-initialized to zero.
191  */
192 size_t* makeReallocatedBitArrayZeroPadded(alias Allocator)(size_t* input,
193                                                            const size_t currentBitCount,
194                                                            const size_t newBitCount) @system
195 if (__traits(hasMember, Allocator, "reallocate"))
196 {
197     assert(currentBitCount < newBitCount, "no use reallocate to same size");
198 
199     immutable currentWordCount = wordCountOfBitCount(currentBitCount);
200     immutable newWordCount = wordCountOfBitCount(newBitCount);
201 
202     auto rawArray = cast(void[])(input[0 .. currentWordCount]);
203 
204     const ok = Allocator.instance.reallocate(rawArray, newWordCount*wordBytes);
205     assert(ok, "couldn't reallocate input");
206     input = cast(size_t*)rawArray.ptr;
207 
208     // See: https://forum.dlang.org/post/puolgthmxgacveqasqkk@forum.dlang.org
209     input[currentWordCount .. newWordCount] = 0;
210 
211     return input;
212 }
213 
214 ///
215 @trusted pure nothrow @nogc unittest
216 {
217     enum bitCount = 8*size_t.sizeof + 1;
218 
219     size_t* x = makeUninitializedBitArray!(Allocator)(bitCount);
220     Allocator.instance.deallocate(cast(void[])(x[0 .. wordCountOfBitCount(bitCount)]));
221 }
222 
223 ///
224 @trusted pure nothrow @nogc unittest
225 {
226     size_t bitCount = 1;
227     size_t* y = makeZeroedBitArray!(Allocator)(bitCount); // start empty
228     while (bitCount < 100_000)
229     {
230         const newBitCount = bitCount*2;
231         y = makeReallocatedBitArrayZeroPadded!(Allocator)(y, bitCount, newBitCount);
232         bitCount = newBitCount;
233 
234         // check contents
235         foreach (immutable bitIndex; 0 .. bitCount)
236             assert(bt(y, bitIndex) == 0);
237     }
238     Allocator.instance.deallocate(cast(void[])(y[0 .. wordCountOfBitCount(bitCount)]));
239 }
240 
241 version(unittest)
242 {
243     import core.bitop : bt;
244     import nxt.my_mallocator : Allocator = Mallocator;
245 }