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() @property @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 {
138     version(D_Coverage) {} else pragma(inline, true);
139     return (cast(ubyte*)(&x))[0 .. x.sizeof];
140 }
141 
142 /** Returns: `x` as a static array with elements of type `E`. */
143 @property ref inout(E)[T.sizeof] asN(E, T)(inout ref T x) @trusted pure nothrow @nogc // TODO: endian-dependent
144 if (T.sizeof % E.sizeof == 0)
145 {
146     version(D_Coverage) {} else pragma(inline, true);
147     return (cast(E*)(&x))[0 .. x.sizeof];
148 }
149 
150 ///
151 @safe pure nothrow @nogc unittest
152 {
153     immutable ushort x = 17;
154     auto y = x.asN!ubyte;
155     version(LittleEndian)
156         assert(y == [17, 0].s);
157 }
158 
159 private enum wordBytes = size_t.sizeof;
160 private enum wordBits = 8*wordBytes;
161 
162 /** Returns: number of words (`size_t`) needed to represent
163  * `bitCount` bits.
164  */
165 static size_t wordCountOfBitCount(size_t bitCount) @safe pure nothrow @nogc
166 {
167     version(D_Coverage) {} else pragma(inline, true);
168     return ((bitCount / wordBits) +
169             (bitCount % wordBits != 0 ? 1 : 0));
170 }
171 
172 static size_t binBlockBytes(size_t bitCount) @safe pure nothrow @nogc
173 {
174     version(D_Coverage) {} else pragma(inline, true);
175     return wordBytes*wordCountOfBitCount(bitCount);
176 }
177 
178 /** Returns: an uninitialized bit-array containing `bitCount` number of bits. */
179 size_t* makeUninitializedBitArray(alias Allocator)(size_t bitCount) @trusted pure nothrow @nogc
180 {
181     version(D_Coverage) {} else pragma(inline, true);
182     immutable byteCount = binBlockBytes(bitCount);
183     return cast(typeof(return))Allocator.instance.allocate(byteCount);
184 }
185 
186 /** Returns: an zero-initialized bit-array containing `bitCount` number of bits. */
187 size_t* makeZeroedBitArray(alias Allocator)(size_t bitCount) @trusted pure nothrow @nogc
188 {
189     version(D_Coverage) {} else pragma(inline, true);
190     static if (__traits(hasMember, Allocator, "allocateZeroed"))
191     {
192         immutable byteCount = binBlockBytes(bitCount);
193         return cast(typeof(return))Allocator.instance.allocateZeroed(byteCount);
194     }
195     else
196         static assert(0, "use allocate plus memset");
197 }
198 
199 /** Returns: `input` reallocated to contain `newBitCount` number of bits. New bits
200  * are default-initialized to zero.
201  */
202 size_t* makeReallocatedBitArrayZeroPadded(alias Allocator)(size_t* input,
203                                                            const size_t currentBitCount,
204                                                            const size_t newBitCount) @system
205 if (__traits(hasMember, Allocator, "reallocate"))
206 {
207     assert(currentBitCount < newBitCount, "no use reallocate to same size");
208 
209     immutable currentWordCount = wordCountOfBitCount(currentBitCount);
210     immutable newWordCount = wordCountOfBitCount(newBitCount);
211 
212     auto rawArray = cast(void[])(input[0 .. currentWordCount]);
213 
214     const ok = Allocator.instance.reallocate(rawArray, newWordCount*wordBytes);
215     assert(ok, "couldn't reallocate input");
216     input = cast(size_t*)rawArray.ptr;
217 
218     // See: https://forum.dlang.org/post/puolgthmxgacveqasqkk@forum.dlang.org
219     input[currentWordCount .. newWordCount] = 0;
220 
221     return input;
222 }
223 
224 ///
225 @trusted pure nothrow @nogc unittest
226 {
227     enum bitCount = 8*size_t.sizeof + 1;
228 
229     size_t* x = makeUninitializedBitArray!(Allocator)(bitCount);
230     Allocator.instance.deallocate(cast(void[])(x[0 .. wordCountOfBitCount(bitCount)]));
231 }
232 
233 ///
234 @trusted pure nothrow @nogc unittest
235 {
236     size_t bitCount = 1;
237     size_t* y = makeZeroedBitArray!(Allocator)(bitCount); // start empty
238     while (bitCount < 100_000)
239     {
240         const newBitCount = bitCount*2;
241         y = makeReallocatedBitArrayZeroPadded!(Allocator)(y, bitCount, newBitCount);
242         bitCount = newBitCount;
243 
244         // check contents
245         foreach (immutable bitIndex; 0 .. bitCount)
246             assert(bt(y, bitIndex) == 0);
247     }
248     Allocator.instance.deallocate(cast(void[])(y[0 .. wordCountOfBitCount(bitCount)]));
249 }
250 
251 version(unittest)
252 {
253     import core.bitop : bt;
254     import nxt.my_mallocator : Allocator = Mallocator;
255 }