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 }