1 /************************************************************************************************************************
2 Copyright: Copyright © 2018-2023, Dawid Masiukiewicz, Michał Masiukiewicz
3 License: BSD 3-clause, see LICENSE file in project root folder.
4 */
5 module bubel.ecs.vector;
6
7 import core.bitop;
8
9 //import core.stdc.stdlib : free, malloc;
10 import bubel.ecs.std;
11
12 //import core.stdc.string : memcpy, memset;
13 //import std.algorithm : swap;
14 import std.conv : emplace;
15 import std.traits : hasMember, isCopyable, TemplateOf, Unqual;
16
17 export @nogc @safe nothrow pure size_t nextPow2(size_t num)
18 {
19 return 1 << bsr(num) + 1;
20 }
21
22 export __gshared size_t gVectorsCreated = 0;
23 export __gshared size_t gVectorsDestroyed = 0;
24
25 struct Vector(T)
26 {
27 T[] array;
28 size_t used;
29 public:
30
31 export this()(T t)
32 {
33 add(t);
34 }
35
36 export this(X)(X[] t) if (is(Unqual!X == Unqual!T))
37 {
38 add(t);
39
40 }
41
42 /*static if (isCopyable!T) {
43 export this(this) {
44 T[] tmp = array[0 .. used];
45 array = null;
46 used = 0;
47 add(tmp);
48 }
49 } else {
50 @disable this(this);
51 }*/
52
53 @disable this(this);
54
55 export ~this()
56 {
57 clear();
58 }
59
60 export void clear()
61 {
62 removeAll();
63 }
64
65 export void removeAll()
66 {
67 if (array !is null)
68 {
69 /*foreach (ref el; array[0 .. used]) {
70 destroy(el);
71 }*/
72 //freeData(cast(void[]) array);
73 freeData((cast(void*) array.ptr)[0 .. array.length * T.sizeof]);
74 gVectorsDestroyed++;
75 }
76 array = null;
77 used = 0;
78 }
79
80 export bool empty() const
81 {
82 return (used == 0);
83 }
84
85 export size_t length() const
86 {
87 return used;
88 }
89
90 export void length(size_t newLength)
91 {
92 if (newLength > used)
93 {
94 reserve(newLength);
95 foreach (ref el; array[used .. newLength])
96 {
97 emplace(&el);
98 }
99 }
100 else
101 {
102 foreach (ref el; array[newLength .. used])
103 {
104 //destroy(el);
105 static if (__traits(hasMember, T, "__xdtor"))
106 el.__xdtor();
107 else static if (__traits(hasMember, T, "__dtor"))
108 el.__dtor();
109 }
110 }
111 used = newLength;
112 }
113
114 export void reset()
115 {
116 used = 0;
117 }
118
119 export void reserve(size_t numElements)
120 {
121 if (numElements > array.length)
122 {
123 extend(numElements);
124 }
125 }
126
127 export size_t capacity()
128 {
129 return array.length - used;
130 }
131
132 export void extend(size_t newNumOfElements)
133 {
134 auto oldArray = manualExtend(array, newNumOfElements);
135 if (oldArray !is null)
136 {
137 freeData(oldArray);
138 }
139 }
140
141 export @nogc void freeData(void[] data)
142 {
143 // 0x0F probably invalid value for pointers and other types
144 memset(data.ptr, 0x0F, data.length); // Makes bugs show up xD
145 free(data.ptr);
146 }
147
148 export static void[] manualExtend(ref T[] array, size_t newNumOfElements = 0)
149 {
150 if (newNumOfElements == 0)
151 newNumOfElements = 2;
152 if (array.length == 0)
153 gVectorsCreated++;
154 T[] oldArray = array;
155 size_t oldSize = oldArray.length * T.sizeof;
156 size_t newSize = newNumOfElements * T.sizeof;
157 T* memory = cast(T*) malloc(newSize);
158 memcpy(cast(void*) memory, cast(void*) oldArray.ptr, oldSize);
159 array = memory[0 .. newNumOfElements];
160 //return cast(void[]) oldArray;
161 return (cast(void*) oldArray.ptr)[0 .. oldArray.length * T.sizeof];
162 }
163
164 export Vector!T copy()()
165 {
166 Vector!T duplicate;
167 duplicate.reserve(used);
168 duplicate ~= array[0 .. used];
169 return duplicate;
170 }
171
172 /*export bool canAddWithoutRealloc(uint elemNum = 1)
173 {
174 return used + elemNum <= array.length;
175 }*/
176
177 export void add()(T t)
178 {
179 if (used >= array.length)
180 {
181 extend(nextPow2(used + 1));
182 }
183 emplace(&array[used], t);
184 used++;
185 }
186
187 /// Add element at given position moving others
188 export void add()(T t, size_t pos)
189 {
190 assert(pos <= used);
191 if (used >= array.length)
192 {
193 extend(array.length * 2);
194 }
195 foreach_reverse (size_t i; pos .. used)
196 {
197 //swap(array[i + 1], array[i]);
198 array[i + 1] = array[i];
199 }
200 emplace(&array[pos], t);
201 used++;
202 }
203
204 export void add(X)(X[] t) if (is(Unqual!X == Unqual!T))
205 {
206 if (used + t.length > array.length)
207 {
208 extend(nextPow2(used + t.length));
209 }
210 foreach (i; 0 .. t.length)
211 {
212 emplace(&array[used + i], t[i]);
213 }
214 used += t.length;
215 }
216
217 export void remove(size_t elemNum)
218 {
219 //destroy(array[elemNum]);
220 static if (__traits(hasMember, T, "__xdtor"))
221 array[elemNum].__xdtor();
222 else static if (__traits(hasMember, T, "__dtor"))
223 array[elemNum].__dtor();
224 //swap(array[elemNum], array[used - 1]);
225 array[elemNum] = array[used - 1];
226 used--;
227 }
228
229 export void removeStable()(size_t elemNum)
230 {
231 used--;
232 foreach (i; 0 .. used)
233 {
234 array[i] = array[i + 1];
235 }
236 }
237
238 export bool tryRemoveElement()(T elem)
239 {
240 foreach (i, ref el; array[0 .. used])
241 {
242 if (el == elem)
243 {
244 remove(i);
245 return true;
246 }
247 }
248 return false;
249 }
250
251 export void removeElement()(T elem)
252 {
253 bool ok = tryRemoveElement(elem);
254 assert(ok, "There is no such an element in vector");
255 }
256
257 export ref T opIndex(size_t elemNum) const
258 {
259 //debug assert(elemNum < used, "Range violation [index]");
260 return *cast(T*)&array.ptr[elemNum];
261 }
262
263 export auto opSlice()
264 {
265 return array.ptr[0 .. used];
266 }
267
268 export T[] opSlice(size_t x, size_t y)
269 {
270 assert(y <= used);
271 return array.ptr[x .. y];
272 }
273
274 export size_t opDollar()
275 {
276 return used;
277 }
278
279 export void opAssign(X)(X[] slice)
280 {
281 reset();
282 this ~= slice;
283 }
284
285 export void opOpAssign(string op)(T obj)
286 {
287 //static assert(op == "~");
288 add(obj);
289 }
290
291 export void opOpAssign(string op, X)(X[] obj)
292 {
293 //static assert(op == "~");
294 add(obj);
295 }
296
297 export void opIndexAssign()(T obj, size_t elemNum)
298 {
299 assert(elemNum < used, "Range viloation");
300 array[elemNum] = obj;
301 }
302
303 export void opSliceAssign()(T[] obj, size_t a, size_t b)
304 {
305 assert(b <= used && a <= b, "Range viloation");
306 array.ptr[a .. b] = obj;
307 }
308
309 export bool opEquals()(auto ref const Vector!(T) r) const
310 {
311 return used == r.used && array.ptr[0 .. used] == r.array.ptr[0 .. r.used];
312 }
313 }