1 /** Structure of arrays similar to a feature present in the Jai programming language.
2  *
3  * Initially a builtin feature in the Jai programming language that later was
4  * made into a library solution.
5  *
6  * See_Also: https://maikklein.github.io/post/soa-d/
7  * See_Also: http://forum.dlang.org/post/wvulryummkqtskiwrusb@forum.dlang.org
8  * See_Also: https://forum.dlang.org/post/purhollnapramxczmcka@forum.dlang.org
9  */
10 module nxt.soa;
11 
12 /** Structure of arrays similar to members of `S`.
13  */
14 struct SOA(S)
15 if (is(S == struct))        // TODO extend to `isAggregate!S`?
16 {
17     import nxt.pure_mallocator : PureMallocator;
18 
19     private alias toType(string s) = typeof(__traits(getMember, S, s));
20     private alias Types = typeof(S.tupleof);
21 
22     this(size_t initialCapacity)
23     {
24         _capacity = initialCapacity;
25         allocate(initialCapacity);
26     }
27 
28     auto opDispatch(string name)()
29     {
30         static foreach (index, memberSymbol; S.tupleof)
31         {
32             static if (name == memberSymbol.stringof)
33             {
34                 return getArray!index;
35             }
36         }
37         // TODO static assert(0, S.stringof ~ " has no field named " ~ name);
38     }
39 
40     /// Push element (struct) `value` to back of array.
41     void insertBack()(S value) @trusted // template-lazy
42     {
43         import core.lifetime : moveEmplace;
44         reserveOneExtra();
45         static foreach (const index, memberSymbol; S.tupleof)
46         {
47             moveEmplace(__traits(getMember, value, memberSymbol.stringof),
48                         getArray!index[_length]); // TODO assert that
49         }
50         ++_length;
51     }
52 
53     /// Push element (struct) `value` to back of array using its data members `members`.
54     void insertBackMembers()(Types members) @trusted // template-lazy
55     {
56         import core.lifetime : moveEmplace;
57         reserveOneExtra();
58         // move each member to its position respective array
59         static foreach (const index, _; members)
60         {
61             moveEmplace(members[index], getArray!index[_length]); // same as `getArray!index[_length] = members[index];`
62         }
63         ++_length;
64     }
65 
66     void opOpAssign(string op, S)(S value)
67         if (op == "~")
68     {
69         pragma(inline, true);
70         insertBack(value);
71     }
72 
73     /// Length of this array.
74     @property size_t length() const @safe pure nothrow @nogc
75     {
76         return _length;
77     }
78 
79     /// Capacity of this array.
80     @property size_t capacity() const @safe pure nothrow @nogc
81     {
82         return _capacity;
83     }
84 
85     ~this() @trusted @nogc
86     {
87         import std.experimental.allocator : dispose;
88         static foreach (const index, _; S.tupleof)
89         {
90             PureMallocator.instance.dispose(getArray!index);
91         }
92     }
93 
94     /** Index operator. */
95     inout(SOAElementRef!S) opIndex()(size_t elementIndex) inout return // template-lazy
96     {
97         assert(elementIndex < _length);
98         return typeof(return)(&this, elementIndex);
99     }
100 
101     /** Slice operator. */
102     inout(SOASlice!S) opSlice()() inout return // template-lazy
103     {
104         return typeof(return)(&this);
105     }
106 
107 private:
108 
109     // generate array definitions
110     static foreach (index, Type; Types)
111     {
112         mixin(Type.stringof ~ `[] _container` ~ index.stringof ~ ";");
113     }
114 
115     /// Get array of all fields at aggregate field index `index`.
116     ref inout(Types[index][]) getArray(size_t index)() inout return
117     {
118         mixin(`return _container` ~ index.stringof ~ ";");
119     }
120 
121     size_t _length = 0;         ///< Current length.
122     size_t _capacity = 0;       ///< Current capacity.
123     enum _growthFactor = 2;     ///< Growth factor.
124 
125     void allocate(size_t newCapacity) @trusted
126     {
127         // if (_alloc is null)
128         // {
129         //     _alloc = allocatorObject(Mallocator.instance);
130         // }
131         import std.experimental.allocator : makeArray;
132         static foreach (const index, _; S.tupleof)
133         {
134             getArray!index = PureMallocator.instance.makeArray!(Types[index])(newCapacity);
135         }
136     }
137 
138     void grow() @trusted
139     {
140         import std.algorithm.comparison : max;
141         const newCapacity = max(1, _capacity * _growthFactor);
142         const expandSize = newCapacity - _capacity;
143 
144         if (_capacity is 0)
145         {
146             allocate(newCapacity);
147         }
148         else
149         {
150             import std.experimental.allocator : expandArray;
151             static foreach (const index, _; S.tupleof)
152             {
153                 PureMallocator.instance.expandArray(getArray!index, expandSize);
154             }
155         }
156         _capacity = newCapacity;
157     }
158 
159     void reserveOneExtra()
160     {
161         if (_length == _capacity) { grow(); }
162     }
163 }
164 alias StructArrays = SOA;
165 
166 /// Reference to element in `soaPtr` at index `elementIndex`.
167 private struct SOAElementRef(S)
168 if (is(S == struct))        // TODO extend to `isAggregate!S`?
169 {
170     SOA!S* soaPtr;
171     size_t elementIndex;
172 
173     @disable this(this);
174 
175     /// Access member name `memberName`.
176     auto ref opDispatch(string memberName)()
177         @trusted return scope
178     {
179         mixin(`return ` ~ `(*soaPtr).` ~ memberName ~ `[elementIndex];`);
180     }
181 }
182 
183 /// Reference to slice in `soaPtr`.
184 private struct SOASlice(S)
185     if (is(S == struct))        // TODO extend to `isAggregate!S`?
186 {
187     SOA!S* soaPtr;
188 
189     @disable this(this);
190 
191     /// Access aggregate at `index`.
192     inout(S) opIndex(size_t index) inout @trusted return scope
193     {
194         S s = void;
195         static foreach (memberIndex, memberSymbol; S.tupleof)
196         {
197             mixin(`s.` ~ memberSymbol.stringof ~ `= (*soaPtr).getArray!` ~ memberIndex.stringof ~ `[index];`);
198         }
199         return s;
200     }
201 }
202 
203 @safe:
204 
205 @safe pure nothrow @nogc unittest
206 {
207     import nxt.dip_traits : isDIP1000;
208 
209     struct S { int i; float f; }
210 
211     auto x = SOA!S();
212 
213     static assert(is(typeof(x.getArray!0()) == int[]));
214     static assert(is(typeof(x.getArray!1()) == float[]));
215 
216     assert(x.length == 0);
217 
218     x.insertBack(S.init);
219     assert(x.length == 1);
220 
221     x ~= S.init;
222     assert(x.length == 2);
223 
224     x.insertBackMembers(42, 43f);
225     assert(x.length == 3);
226     assert(x.i[2] == 42);
227     assert(x.f[2] == 43f);
228 
229     // uses opDispatch
230     assert(x[2].i == 42);
231     assert(x[2].f == 43f);
232 
233     const x3 = SOA!S(3);
234     assert(x3.length == 0);
235     assert(x3.capacity == 3);
236 
237     // TODO make foreach work
238     // foreach (_; x[])
239     // {
240     // }
241 
242     static if (isDIP1000)
243     {
244         static assert(!__traits(compiles,
245                                 {
246                                     ref int testScope() @safe
247                                     {
248                                         auto y = SOA!S(1);
249                                         y ~= S(42, 43f);
250                                         return y[0].i;
251                                     }
252                                 }));
253     }
254 }