more.array source code

1 module more.array;
2 
3 import std.format : format;
4 
5 template isArrayLike(T)
6 {
7     enum isArrayLike =
8            is(typeof(T.init.length))
9         && is(typeof(T.init.ptr))
10         && is(typeof(T.init[0]));
11 }
12 
13 /**
14 TODO move this to mored
15 */
16 pragma(inline) void copyFrom(T,U)(T dst, U src)
17 if (isArrayLike!T && isArrayLike!U && dst[0].sizeof == src[0].sizeof)
18 {
19     assert(dst.length >= src.length, "copyFrom source length larger than destination");
20     import core.stdc..string : memcpy;
21     memcpy(dst.ptr, src.ptr, src.length);
22 }
23 
24 pragma(inline) void setBytes(T,U)(T dst, U value)
25 if (isArrayLike!T && T.init[0].sizeof == 1 && value.sizeof == 1)
26 {
27     import core.stdc..string : memset;
28     memset(dst.ptr, cast(int)value, dst.length);
29 }
30 
31 
32 /**
33 TODO: move this to the mored repository
34 
35 A LimitArray is like an array, except it contains 2 pointers, "ptr" and "limit",
36 instead of a "ptr" and "length".
37 
38 The first pointer, "ptr", points to the beginning (like a normal array) and the
39 second pointer, "limit", points to 1 element past the last element in the array.
40 
41 ```
42 -------------------------------
43 | first | second | ... | last |
44 -------------------------------
45  ^                             ^
46  ptr                           limit
47 ````
48 
49 To get the length of the LimitArray, you can evaluate `limit - ptr`.
50 To check if a LimitArray is empty, you can check if `ptr == limit`.
51 
52 The reason for the existense of the LimitArray structure is that some functionality
53 is more efficient when it uses this representation.  A common example is when processing
54 or parsing an array of elements where the beginning is iteratively "sliced off" as
55 it is being processed, i.e.  array = array[someCount .. $];  This operation is more efficient
56 when using a LimitArray because only the "ptr" field needs to be modified whereas a normal array
57 needs to modify the "ptr" field and the "length" each time. Note that other operations are more
58 efficiently done using a normal array, for example, if the length needs to be evaluated quite
59 often then it might make more sense to use a normal array.
60 
61 In order to support "Element Type Modifiers" on a LimitArray's pointer types, the types are
62 defined using a template. Here is a table of LimitArray types with their equivalent normal array types.
63 
64 | Normal Array        | Limit Array             |
65 |---------------------|-------------------------|
66 | `char[]`            | `LimitArray!char.mutable` `LimitArray!(const(char)).mutable` `LimitArray!(immutable(char)).mutable` |
67 | `const(char)[]`     | `LimitArray!char.const` `LimitArray!(const(char)).const` `LimitArray!(immutable(char)).const` |
68 | `immutable(char)[]` | `LimitArray!char.immutable` `LimitArray!(const(char)).immutable` `LimitArray!(immutable(char)).immutable` |
69 
70 */
71 template LimitArray(T)
72 {
73     static if( !is(T == Unqual!T) )
74     {
75         alias LimitArray = LimitArray!(Unqual!T);
76     }
77     else
78     {
79         enum CommonMixin = q{
80             pragma(inline) @property auto asArray()
81             {
82                 return this.ptr[0 .. limit - ptr];
83             }
84             pragma(inline) auto slice(size_t offset)
85             {
86                 auto newPtr = ptr + offset;
87                 assert(newPtr <= limit, "slice offset range violation");
88                 return typeof(this)(newPtr, limit);
89             }
90             pragma(inline) auto slice(size_t offset, size_t newLimit)
91                 in { assert(newLimit >= offset, "slice offset range violation"); } do
92             {
93                 auto newLimitPtr = ptr + newLimit;
94                 assert(newLimitPtr <= limit, "slice limit range violation");
95                 return typeof(this)(ptr + offset, ptr + newLimit);
96             }
97             pragma(inline) auto ptrSlice(typeof(this.ptr) ptr)
98             {
99                 auto copy = this;
100                 copy.ptr = ptr;
101                 return copy;
102             }
103         };
104 
105         struct mutable
106         {
107             union
108             {
109                 struct
110                 {
111                     T* ptr;
112                     T* limit;
113                 }
114                 const_ constVersion;
115             }
116             // mutable is implicitly convertible to const
117             alias constVersion this;
118 
119             mixin(CommonMixin);
120         }
121         struct immutable_
122         {
123             union
124             {
125                 struct
126                 {
127                     immutable(T)* ptr;
128                     immutable(T)* limit;
129                 }
130                 const_ constVersion;
131             }
132             // immutable is implicitly convertible to const
133             alias constVersion this;
134 
135             mixin(CommonMixin);
136         }
137         struct const_
138         {
139             const(T)* ptr;
140             const(T)* limit;
141             mixin(CommonMixin);
142             auto startsWith(const(T)[] check) const
143             {
144                 return ptr + check.length <= limit &&
145                     0 == memcmp(ptr, check.ptr, check.length);
146             }
147             auto equals(const(T)[] check) const
148             {
149                 return ptr + check.length == limit &&
150                     0 == memcmp(ptr, check.ptr, check.length);
151             }
152         }
153     }
154 }
155 
156 pragma(inline)
157 @property auto asLimitArray(T)(T[] array)
158 {
159     static if( is(T == immutable) )
160     {
161         return LimitArray!T.immutable_(array.ptr, array.ptr + array.length);
162     }
163     else static if( is(T == const) )
164     {
165         return LimitArray!T.const_(array.ptr, array.ptr + array.length);
166     }
167     else
168     {
169         return LimitArray!T.mutable(array.ptr, array.ptr + array.length);
170     }
171 }
172 
173 /**
174 TODO: move this to the mored repo
175 
176 An array type that uses a custom type for the length.
177 */
178 struct LengthArray(T, SizeType)
179 {
180     @property static typeof(this) nullValue() { return typeof(this)(null, 0); }
181 
182     T* ptr;
183     SizeType length;
184 
185     void nullify() { this.ptr = null; this.length = 0; }
186     bool isNull() const { return ptr is null; }
187 
188     pragma(inline) @property auto ref last() const
189         in { assert(length > 0); } do { return ptr[length - 1]; }
190 
191     pragma(inline) auto ref opIndex(SizeType index) inout
192         in { assert(index < length, format("range violation %s >= %s", index, length)); } do
193     {
194         return ptr[index];
195     }
196     static if (size_t.sizeof != SizeType.sizeof)
197     {
198         pragma(inline) auto ref opIndex(size_t index) inout
199             in { assert(index < length, format("range violation %s >= %s", index, length)); } do
200         {
201             return ptr[index];
202         }
203     }
204     pragma(inline) SizeType opDollar() const
205     {
206         return length;
207     }
208     /*
209     pragma(inline) auto ref opSlice(SizeType start, SizeType limit) inout
210         in { assert(limit >= start, "slice range violation"); } do
211     {
212         return inout LengthArray!(T,SizeType)(ptr + start, cast(SizeType)(limit - start));
213     }
214     */
215     pragma(inline) auto ref opSlice(SizeType start, SizeType limit)
216         in { assert(limit >= start, "slice range violation"); } do
217     {
218         return LengthArray!(T,SizeType)(ptr + start, cast(SizeType)(limit - start));
219     }
220 
221     pragma(inline) int opApply(scope int delegate(ref T element) dg) const
222     {
223         int result = 0;
224         for (SizeType i = 0; i < length; i++)
225         {
226             result = dg(*cast(T*)&ptr[i]);
227             if (result)
228                 break;
229         }
230         return result;
231     }
232     pragma(inline) int opApply(scope int delegate(SizeType index, ref T element) dg) const
233     {
234         int result = 0;
235         for (SizeType i = 0; i < length; i++)
236         {
237             result = dg(i, *cast(T*)&ptr[i]);
238             if (result)
239                 break;
240         }
241         return result;
242     }
243 
244     @property auto asArray() { return ptr[0..length]; }
245     //alias toArray this;
246 
247     /*
248     // range functions
249     @property bool empty() { return length == 0; }
250     @property auto front() { return *ptr; }
251     void popFront() {
252         ptr++;
253         length--;
254     }
255     */
256 }
257 pragma(inline) LengthArray!(T, LengthType) asLengthArray(LengthType, T)(T[] array)
258 in {
259     static if (LengthType.sizeof < array.length.sizeof)
260     {
261         assert(array.length <= LengthType.max,
262             format("array length %s exceeded " ~ LengthType.stringof ~ ".max %s", array.length, LengthType.max));
263     }
264 } do
265 {
266     return LengthArray!(T, LengthType)(array.ptr, cast(LengthType)array.length);
267 }
268 
269 pragma(inline) LengthArray!(T, LengthType) asLengthArray(LengthType, T)(T* ptr, LengthType length)
270 {
271     return LengthArray!(T, LengthType)(ptr, length);
272 }
273 
274