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 `move` when compiler does it for us
29     {
30         return x[];
31     }
32     else                      // TODO remove `move` when compiler does it for us
33     {
34         // TODO remove `move` when compiler does it for us:
35         T[n] y = void;        // initialized below
36         import core.internal.traits : hasElaborateDestructor;
37         static if (hasElaborateDestructor!T)
38         {
39             /* NOTE: moveEmplaceAll doesn't support uncopyable elements
40              * import std.algorithm.mutation : moveEmplaceAll;
41              * moveEmplaceAll(x[], y[]);
42              */
43             foreach (const ix, ref value; x)
44             {
45                 import core.lifetime : move;
46                 move(value, y[ix]);
47             }
48         }
49         else
50         {
51             import core.stdc..string : memcpy;
52             memcpy(y.ptr, x.ptr, n*T.sizeof); // fast
53         }
54         return y;
55     }
56 }
57 alias s = staticArray;
58 
59 @safe pure unittest
60 {
61     // assert([].staticArray.ptr == null);
62     assert([].s.length == 0);
63 }
64 
65 version(none)
66 @safe pure unittest
67 {
68     import std.array : staticArray;
69     assert([].staticArray.ptr !is null);
70     assert([].staticArray.length == 0);
71 }
72 
73 /** Make a static array. */
74 version(none)
75 auto staticArrayAlternative() @property @safe
76 {
77     static struct _staticArray
78     {
79         T[n] s(T, size_t n)(auto ref T[n] values) @safe @property { return values; }
80 
81         T[0][n] opIndex(size_t n = T.length, T...)(T items)
82         {
83             typeof(return) arr;
84             foreach (index,item; items)
85                 arr[index] = item;
86 
87             return (values) { return values; }(arr);//s!(T[0], n)(arr);
88         }
89     }
90     return _staticArray();
91 }
92 
93 version(unittest)
94 {
95     private static struct US
96     {
97         @disable this(this);
98         int x;
99     }
100 }
101 
102 ///
103 @safe pure nothrow @nogc unittest
104 {
105     auto a = [1, 2, 3].staticArray;
106     static assert(is(typeof(a) == int[a.length]));
107     static assert(is(typeof([1, 2, 3].staticArray) == int[a.length]));
108 
109     auto b = "hello".s;
110     static assert(is(typeof(b) == char[5]));
111 
112     auto x = s!ubyte(1, 2, 3);
113     static assert(is(typeof(x) == ubyte[3]));
114 }
115 
116 /// non-copyable element type in static array
117 @safe pure nothrow @nogc unittest
118 {
119     auto b = [US(42)].s;
120 }
121 
122 ///
123 @safe pure nothrow @nogc unittest
124 {
125     auto x = [1, 2, 3].staticArray;
126 
127     static assert(is(typeof(x) == int[x.length]));
128     static assert(is(typeof([1, 2, 3].staticArray) == int[x.length]));
129 
130     static assert(!__traits(compiles,
131                             {
132                                 static int[] doNotDoThat() { return [1, 2, 3].s; }
133                             }
134                       ));
135 }
136 
137 /** Returns: `x` as a static array of unsigned bytes. */
138 @property ubyte[T.sizeof] toUbytes(T)(in T x)
139     @trusted pure nothrow @nogc // TODO endian-dependent
140 {
141     version(D_Coverage) {} else pragma(inline, true);
142     return (cast(ubyte*)(&x))[0 .. x.sizeof];
143 }
144 
145 /** Returns: `x` as a static array with elements of type `E`. */
146 @property ref E[T.sizeof] asN(E, T)(in ref T x)
147     @trusted pure nothrow @nogc // TODO endian-dependent
148 if (T.sizeof % E.sizeof == 0)
149 {
150     version(D_Coverage) {} else pragma(inline, true);
151     return (cast(E*)(&x))[0 .. x.sizeof];
152 }
153 
154 @safe pure nothrow @nogc unittest
155 {
156     immutable ushort x = 17;
157     auto y = x.asN!ubyte;
158     version(LittleEndian)
159     {
160         assert(y == [17, 0].s);
161     }
162 }
163 
164 private enum wordBytes = size_t.sizeof;
165 private enum wordBits = 8*wordBytes;
166 
167 /** Returns: number of words (`size_t`) needed to represent
168  * `bitCount` bits.
169  */
170 static size_t wordCountOfBitCount(size_t bitCount)
171     @safe pure nothrow @nogc
172 {
173     version(D_Coverage) {} else pragma(inline, true);
174     return ((bitCount / wordBits) +
175             (bitCount % wordBits != 0 ? 1 : 0));
176 }
177 
178 static size_t binBlockBytes(size_t bitCount)
179     @safe pure nothrow @nogc
180 {
181     version(D_Coverage) {} else pragma(inline, true);
182     return wordBytes*wordCountOfBitCount(bitCount);
183 }
184 
185 /** Returns: an uninitialized bit-array containing `bitCount` number of bits. */
186 size_t* makeUninitializedBitArray(alias Allocator)(size_t bitCount)
187     @trusted pure nothrow @nogc
188 {
189     version(D_Coverage) {} else pragma(inline, true);
190     immutable byteCount = binBlockBytes(bitCount);
191     return cast(typeof(return))Allocator.instance.allocate(byteCount);
192 }
193 
194 /** Returns: an zero-initialized bit-array containing `bitCount` number of bits. */
195 size_t* makeZeroedBitArray(alias Allocator)(size_t bitCount)
196     @trusted pure nothrow @nogc
197 {
198     version(D_Coverage) {} else pragma(inline, true);
199     static if (__traits(hasMember, Allocator, "allocateZeroed"))
200     {
201         immutable byteCount = binBlockBytes(bitCount);
202         return cast(typeof(return))Allocator.instance.allocateZeroed(byteCount);
203     }
204     else
205     {
206         static assert(0, "use allocate plus memset");
207     }
208 }
209 
210 /** Returns: `input` reallocated to contain `newBitCount` number of bits. New bits
211  * are default-initialized to zero.
212  */
213 size_t* makeReallocatedBitArrayZeroPadded(alias Allocator)(size_t* input,
214                                                            const size_t currentBitCount,
215                                                            const size_t newBitCount)
216     @system
217 if (__traits(hasMember, Allocator, "reallocate"))
218 {
219     assert(currentBitCount < newBitCount, "no use reallocate to same size");
220 
221     immutable currentWordCount = wordCountOfBitCount(currentBitCount);
222     immutable newWordCount = wordCountOfBitCount(newBitCount);
223 
224     auto rawArray = cast(void[])(input[0 .. currentWordCount]);
225 
226     const ok = Allocator.instance.reallocate(rawArray, newWordCount*wordBytes);
227     assert(ok, "couldn't reallocate input");
228     input = cast(size_t*)rawArray.ptr;
229 
230     // See: https://forum.dlang.org/post/puolgthmxgacveqasqkk@forum.dlang.org
231     input[currentWordCount .. newWordCount] = 0;
232 
233     return input;
234 }
235 
236 @trusted pure nothrow @nogc unittest
237 {
238     enum bitCount = 8*size_t.sizeof + 1;
239 
240     size_t* x = makeUninitializedBitArray!(Allocator)(bitCount);
241     Allocator.instance.deallocate(cast(void[])(x[0 .. wordCountOfBitCount(bitCount)]));
242 }
243 
244 @trusted pure nothrow @nogc unittest
245 {
246     size_t bitCount = 1;
247     size_t* y = makeZeroedBitArray!(Allocator)(bitCount); // start empty
248     while (bitCount < 100_000)
249     {
250         const newBitCount = bitCount*2;
251         y = makeReallocatedBitArrayZeroPadded!(Allocator)(y, bitCount, newBitCount);
252         bitCount = newBitCount;
253 
254         // check contents
255         foreach (immutable bitIndex; 0 .. bitCount)
256         {
257             assert(bt(y, bitIndex) == 0);
258         }
259     }
260     Allocator.instance.deallocate(cast(void[])(y[0 .. wordCountOfBitCount(bitCount)]));
261 }
262 
263 version(unittest)
264 {
265     import core.bitop : bt;
266     import nxt.pure_mallocator : Allocator = PureMallocator;
267     import nxt.dbgio;
268 }