|
291
|
1 module qt.core.QList;
|
|
|
2
|
|
|
3 import qt.QGlobal;
|
|
293
|
4 import qt.QtdObject;
|
|
291
|
5 import qt.qtd.Atomic;
|
|
293
|
6 import qt.qtd.MetaMarshall;
|
|
292
|
7 //import qt.core.QTypeInfo;
|
|
|
8
|
|
291
|
9 import core.stdc.stdlib : qRealloc = realloc, qFree = free, qMalloc = malloc;
|
|
|
10 import core.stdc.string : memcpy, memmove;
|
|
|
11
|
|
292
|
12 import std.traits;
|
|
|
13
|
|
291
|
14 enum INT_MAX = int.max;
|
|
|
15
|
|
292
|
16 bool isComplex(T)()
|
|
293
|
17 if (is(T.QTypeInfo))
|
|
292
|
18 {
|
|
293
|
19 return T.QTypeInfo.isComplex;
|
|
292
|
20 }
|
|
|
21
|
|
|
22 bool isStatic(T)()
|
|
293
|
23 if (is(T.QTypeInfo))
|
|
292
|
24 {
|
|
293
|
25 return T.QTypeInfo.isStatic;
|
|
292
|
26 }
|
|
|
27
|
|
|
28 bool isLarge(T)()
|
|
293
|
29 if (is(T.QTypeInfo))
|
|
292
|
30 {
|
|
293
|
31 return T.QTypeInfo.isLarge;
|
|
292
|
32 }
|
|
|
33
|
|
291
|
34 int qAllocMore(int alloc, int extra)
|
|
|
35 {
|
|
|
36 if (alloc == 0 && extra == 0)
|
|
|
37 return 0;
|
|
|
38 const int page = 1 << 12;
|
|
|
39 int nalloc;
|
|
|
40 alloc += extra;
|
|
|
41 if (alloc < 1<<6) {
|
|
|
42 nalloc = (1<<3) + ((alloc >>3) << 3);
|
|
|
43 } else {
|
|
|
44 // don't do anything if the loop will overflow signed int.
|
|
|
45 if (alloc >= INT_MAX/2)
|
|
|
46 return INT_MAX;
|
|
|
47 nalloc = (alloc < page) ? 1 << 3 : page;
|
|
|
48 while (nalloc < alloc) {
|
|
|
49 if (nalloc <= 0)
|
|
|
50 return INT_MAX;
|
|
|
51 nalloc *= 2;
|
|
|
52 }
|
|
|
53 }
|
|
|
54 return nalloc - extra;
|
|
|
55 }
|
|
|
56
|
|
|
57 private int grow(int size)
|
|
|
58 {
|
|
|
59 // dear compiler: don't optimize me out.
|
|
292
|
60 // synchronized {
|
|
291
|
61 int x = qAllocMore(size * (void*).sizeof, QListData.DataHeaderSize) / (void*).sizeof;
|
|
|
62 return x;
|
|
292
|
63 // }
|
|
291
|
64 }
|
|
|
65
|
|
|
66 struct QListData {
|
|
|
67 struct Data {
|
|
|
68 Atomic!int ref_;
|
|
|
69 int alloc, begin, end;
|
|
|
70 uint sharable;
|
|
|
71 void*[1] array;
|
|
|
72 }
|
|
|
73
|
|
|
74 enum { DataHeaderSize = Data.sizeof - (void*).sizeof }
|
|
|
75
|
|
|
76 static Data shared_null;
|
|
|
77 Data *d;
|
|
|
78
|
|
|
79 static this()
|
|
|
80 {
|
|
|
81 shared_null = Data(Atomic!int(1), 0, 0, 0, true, [null]);
|
|
|
82 }
|
|
|
83
|
|
|
84
|
|
|
85 // Data *detach(); // remove in 5.0
|
|
|
86
|
|
|
87 Data* detach2()
|
|
|
88 {
|
|
|
89 Data* x = d;
|
|
|
90 d = cast(Data*)(qMalloc(DataHeaderSize + x.alloc * (void*).sizeof));
|
|
|
91 if (!d)
|
|
|
92 qFatal("QList: Out of memory");
|
|
|
93
|
|
|
94 memcpy(d, x, DataHeaderSize + x.alloc * (void*).sizeof);
|
|
|
95 d.alloc = x.alloc;
|
|
|
96 d.ref_.store(1);
|
|
|
97 d.sharable = true;
|
|
|
98 if (!d.alloc)
|
|
|
99 d.begin = d.end = 0;
|
|
|
100
|
|
|
101 return x;
|
|
|
102 }
|
|
|
103
|
|
|
104 void realloc(int alloc)
|
|
|
105 {
|
|
|
106 // assert(d.ref_ == 1);
|
|
|
107 Data* x = cast(Data*)(qRealloc(d, DataHeaderSize + alloc * (void*).sizeof));
|
|
|
108 if (!x)
|
|
|
109 qFatal("QList: Out of memory");
|
|
|
110
|
|
|
111 d = x;
|
|
|
112 d.alloc = alloc;
|
|
|
113 if (!alloc)
|
|
|
114 d.begin = d.end = 0;
|
|
|
115 }
|
|
|
116
|
|
|
117 void** append()
|
|
|
118 {
|
|
|
119 // #TODO Q_ASSERT(d.ref_ == 1);
|
|
|
120 if (d.end == d.alloc) {
|
|
|
121 int n = d.end - d.begin;
|
|
|
122 if (d.begin > 2 * d.alloc / 3) {
|
|
|
123 memcpy(d.array.ptr + n, d.array.ptr + d.begin, n * (void*).sizeof);
|
|
|
124 d.begin = n;
|
|
|
125 d.end = n * 2;
|
|
|
126 } else {
|
|
|
127 realloc(grow(d.alloc + 1));
|
|
|
128 }
|
|
|
129 }
|
|
|
130 return d.array.ptr + d.end++;
|
|
|
131 }
|
|
|
132
|
|
|
133 void **append(const ref QListData l)
|
|
|
134 {
|
|
|
135 // Q_ASSERT(d.ref_ == 1);
|
|
|
136 int e = d.end;
|
|
|
137 int n = l.d.end - l.d.begin;
|
|
|
138 if (n) {
|
|
|
139 if (e + n > d.alloc)
|
|
|
140 realloc(grow(e + l.d.end - l.d.begin));
|
|
|
141 memcpy(d.array.ptr + d.end, l.d.array.ptr + l.d.begin, n * (void*).sizeof);
|
|
|
142 d.end += n;
|
|
|
143 }
|
|
|
144 return d.array.ptr + e;
|
|
|
145 }
|
|
|
146
|
|
|
147 void **prepend()
|
|
|
148 {
|
|
|
149 // Q_ASSERT(d.ref_ == 1);
|
|
|
150 if (d.begin == 0) {
|
|
|
151 if (d.end >= d.alloc / 3)
|
|
|
152 realloc(grow(d.alloc + 1));
|
|
|
153
|
|
|
154 if (d.end < d.alloc / 3)
|
|
|
155 d.begin = d.alloc - 2 * d.end;
|
|
|
156 else
|
|
|
157 d.begin = d.alloc - d.end;
|
|
|
158
|
|
|
159 memmove(d.array.ptr + d.begin, d.array.ptr, d.end * (void*).sizeof);
|
|
|
160 d.end += d.begin;
|
|
|
161 }
|
|
|
162 return d.array.ptr + --d.begin;
|
|
|
163 }
|
|
|
164
|
|
|
165 void **insert(int i)
|
|
|
166 {
|
|
|
167 // Q_ASSERT(d.ref_ == 1);
|
|
|
168 if (i <= 0)
|
|
|
169 return prepend();
|
|
|
170 if (i >= d.end - d.begin)
|
|
|
171 return append();
|
|
|
172
|
|
|
173 bool leftward = false;
|
|
|
174 int size = d.end - d.begin;
|
|
|
175
|
|
|
176 if (d.begin == 0) {
|
|
|
177 if (d.end == d.alloc) {
|
|
|
178 // If the array is full, we expand it and move some items rightward
|
|
|
179 realloc(grow(d.alloc + 1));
|
|
|
180 } else {
|
|
|
181 // If there is free space at the end of the array, we move some items rightward
|
|
|
182 }
|
|
|
183 } else {
|
|
|
184 if (d.end == d.alloc) {
|
|
|
185 // If there is free space at the beginning of the array, we move some items leftward
|
|
|
186 leftward = true;
|
|
|
187 } else {
|
|
|
188 // If there is free space at both ends, we move as few items as possible
|
|
|
189 leftward = (i < size - i);
|
|
|
190 }
|
|
|
191 }
|
|
|
192
|
|
|
193 if (leftward) {
|
|
|
194 --d.begin;
|
|
|
195 memmove(d.array.ptr + d.begin, d.array.ptr + d.begin + 1, i * (void*).sizeof);
|
|
|
196 } else {
|
|
|
197 memmove(d.array.ptr + d.begin + i + 1, d.array.ptr + d.begin + i,
|
|
|
198 (size - i) * (void*).sizeof);
|
|
|
199 ++d.end;
|
|
|
200 }
|
|
|
201 return d.array.ptr + d.begin + i;
|
|
|
202 }
|
|
|
203
|
|
|
204 void remove(int i)
|
|
|
205 {
|
|
|
206 // Q_ASSERT(d.ref_ == 1);
|
|
|
207 i += d.begin;
|
|
|
208 if (i - d.begin < d.end - i) {
|
|
|
209 if (int offset = i - d.begin)
|
|
|
210 memmove(d.array.ptr + d.begin + 1, d.array.ptr + d.begin, offset * (void*).sizeof);
|
|
|
211 d.begin++;
|
|
|
212 } else {
|
|
|
213 if (int offset = d.end - i - 1)
|
|
|
214 memmove(d.array.ptr + i, d.array.ptr + i + 1, offset * (void*).sizeof);
|
|
|
215 d.end--;
|
|
|
216 }
|
|
|
217 }
|
|
|
218
|
|
|
219 void remove(int i, int n)
|
|
|
220 {
|
|
|
221 // Q_ASSERT(d.ref_ == 1);
|
|
|
222 i += d.begin;
|
|
|
223 int middle = i + n/2;
|
|
|
224 if (middle - d.begin < d.end - middle) {
|
|
|
225 memmove(d.array.ptr + d.begin + n, d.array.ptr + d.begin,
|
|
|
226 (i - d.begin) * (void*).sizeof);
|
|
|
227 d.begin += n;
|
|
|
228 } else {
|
|
|
229 memmove(d.array.ptr + i, d.array.ptr + i + n,
|
|
|
230 (d.end - i - n) * (void*).sizeof);
|
|
|
231 d.end -= n;
|
|
|
232 }
|
|
|
233 }
|
|
|
234
|
|
|
235 void move(int from, int to)
|
|
|
236 {
|
|
|
237 // Q_ASSERT(d.ref_ == 1);
|
|
|
238 if (from == to)
|
|
|
239 return;
|
|
|
240
|
|
|
241 from += d.begin;
|
|
|
242 to += d.begin;
|
|
|
243 void *t = d.array.ptr[from];
|
|
|
244
|
|
|
245 if (from < to) {
|
|
|
246 if (d.end == d.alloc || 3 * (to - from) < 2 * (d.end - d.begin)) {
|
|
|
247 memmove(d.array.ptr + from, d.array.ptr + from + 1, (to - from) * (void*).sizeof);
|
|
|
248 } else {
|
|
|
249 // optimization
|
|
|
250 if (int offset = from - d.begin)
|
|
|
251 memmove(d.array.ptr + d.begin + 1, d.array.ptr + d.begin, offset * (void*).sizeof);
|
|
|
252 if (int offset = d.end - (to + 1))
|
|
|
253 memmove(d.array.ptr + to + 2, d.array.ptr + to + 1, offset * (void*).sizeof);
|
|
|
254 ++d.begin;
|
|
|
255 ++d.end;
|
|
|
256 ++to;
|
|
|
257 }
|
|
|
258 } else {
|
|
|
259 if (d.begin == 0 || 3 * (from - to) < 2 * (d.end - d.begin)) {
|
|
|
260 memmove(d.array.ptr + to + 1, d.array.ptr + to, (from - to) * (void*).sizeof);
|
|
|
261 } else {
|
|
|
262 // optimization
|
|
|
263 if (int offset = to - d.begin)
|
|
|
264 memmove(d.array.ptr + d.begin - 1, d.array.ptr + d.begin, offset * (void*).sizeof);
|
|
|
265 if (int offset = d.end - (from + 1))
|
|
|
266 memmove(d.array.ptr + from, d.array.ptr + from + 1, offset * (void*).sizeof);
|
|
|
267 --d.begin;
|
|
|
268 --d.end;
|
|
|
269 --to;
|
|
|
270 }
|
|
|
271 }
|
|
|
272 d.array.ptr[to] = t;
|
|
|
273 }
|
|
|
274
|
|
|
275 void **erase(void **xi)
|
|
|
276 {
|
|
|
277 // Q_ASSERT(d.ref_ == 1);
|
|
|
278 int i = xi - (d.array.ptr + d.begin);
|
|
|
279 remove(i);
|
|
|
280 return d.array.ptr + d.begin + i;
|
|
|
281 }
|
|
|
282
|
|
|
283 int size() const { return d.end - d.begin; }
|
|
|
284 bool isEmpty() const { return d.end == d.begin; }
|
|
|
285 const (void*)* at(int i) const { return d.array.ptr + d.begin + i; }
|
|
|
286 const (void*)* begin() const { return d.array.ptr + d.begin; }
|
|
|
287 const (void*)* end() const { return d.array.ptr + d.end; }
|
|
|
288 }
|
|
|
289
|
|
|
290 import std.stdio;
|
|
|
291
|
|
|
292 struct QList(T)
|
|
|
293 {
|
|
|
294 struct Node
|
|
|
295 {
|
|
|
296 void *v;
|
|
292
|
297
|
|
293
|
298 static if (isQObjectType!T || isObjectType!T || isValueType!T) // binded Qt types
|
|
292
|
299 {
|
|
|
300 T t()
|
|
|
301 {
|
|
293
|
302 static if (isValueType!T)
|
|
|
303 {
|
|
|
304 pragma(msg, "value " ~ T.stringof);
|
|
|
305 void* ptr = cast(void*)(isLarge!T() || isStatic!T() ? v : &this);
|
|
|
306 return new T(ptr, QtdObjectFlags.nativeOwnership);
|
|
|
307 }
|
|
|
308 else
|
|
|
309 {
|
|
|
310 pragma(msg, T.stringof);
|
|
|
311
|
|
|
312 return T.__getObject( *cast(void**)(&this) );
|
|
|
313 }
|
|
292
|
314 }
|
|
|
315 }
|
|
293
|
316 else // native types
|
|
292
|
317 {
|
|
|
318 ref T t()
|
|
|
319 {
|
|
293
|
320 pragma(msg, "native " ~ T.stringof);
|
|
|
321
|
|
292
|
322 return *cast(T*)(&this);
|
|
|
323 }
|
|
|
324 // { return *cast(T*)(QTypeInfo!T.isLarge || QTypeInfo!T.isStatic
|
|
|
325 // ? v : &this); } }
|
|
|
326 }
|
|
291
|
327 }
|
|
|
328
|
|
|
329 union {
|
|
|
330 QListData p;
|
|
|
331 QListData.Data* d;
|
|
|
332 }
|
|
|
333
|
|
|
334 public:
|
|
|
335 void output()
|
|
|
336 {
|
|
|
337 writeln("QList atomic ", d.ref_.load());
|
|
|
338 }
|
|
|
339
|
|
|
340 static QList!T opCall()
|
|
|
341 {
|
|
|
342 QList!T res;
|
|
|
343 writeln("QList opCall");
|
|
|
344
|
|
|
345 res.d = &QListData.shared_null;
|
|
|
346 res.d.ref_.increment();
|
|
|
347
|
|
|
348 return res;
|
|
|
349 }
|
|
|
350
|
|
|
351 this(this)
|
|
|
352 {
|
|
|
353 writeln("QList postblit");
|
|
|
354 d.ref_.increment();
|
|
|
355 if (!d.sharable)
|
|
|
356 detach_helper();
|
|
|
357 }
|
|
|
358
|
|
|
359 ~this()
|
|
|
360 {
|
|
|
361 writeln("QList ~this");
|
|
|
362 if (d && !d.ref_.decrement())
|
|
|
363 free(d);
|
|
|
364 }
|
|
|
365
|
|
|
366 ref QList!T opAssign(const ref QList!T l)
|
|
|
367 {
|
|
|
368 writeln("QList opAssign");
|
|
|
369 if (d != l.d) {
|
|
|
370 l.d.ref_.increment();
|
|
|
371 if (!d.ref_.decrement())
|
|
|
372 free(d);
|
|
|
373 d = cast(QListData.Data*)l.d;
|
|
|
374 if (!d.sharable)
|
|
|
375 detach_helper();
|
|
|
376 }
|
|
|
377 return this;
|
|
|
378 }
|
|
|
379
|
|
292
|
380 int length() const { return p.size(); }
|
|
|
381 int size() const { return length; }
|
|
|
382
|
|
291
|
383 void detach() { if (d.ref_.load() != 1) detach_helper(); }
|
|
|
384
|
|
|
385 private void detach_helper()
|
|
|
386 {
|
|
|
387 Node *n = cast(Node*)(p.begin());
|
|
|
388 QListData.Data* x = p.detach2();
|
|
|
389 node_copy(cast(Node*)(p.begin()), cast(Node*)(p.end()), n);
|
|
|
390 if (!x.ref_.decrement())
|
|
|
391 free(x);
|
|
|
392 }
|
|
|
393
|
|
293
|
394
|
|
291
|
395 void append(const T t) // fix to const ref for complex types TODO
|
|
|
396 {
|
|
|
397 detach();
|
|
293
|
398 static if (isQObjectType!T || isObjectType!T || isValueType!T)
|
|
291
|
399 {
|
|
|
400 node_construct(cast(Node*)(p.append()), t);
|
|
|
401 }
|
|
292
|
402 else
|
|
291
|
403 {
|
|
|
404 const T cpy = t;
|
|
|
405 node_construct(cast(Node*)(p.append()), cpy);
|
|
|
406 }
|
|
|
407 }
|
|
292
|
408
|
|
293
|
409 static if (isQObjectType!T || isObjectType!T || isValueType!T)
|
|
291
|
410 {
|
|
292
|
411 T at(int i) const
|
|
|
412 {
|
|
|
413 assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range");
|
|
|
414 return (cast(Node*)(p.at(i))).t();
|
|
|
415 }
|
|
291
|
416 }
|
|
292
|
417 else
|
|
291
|
418 {
|
|
292
|
419 ref const (T) at(int i) const
|
|
|
420 {
|
|
|
421 assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range");
|
|
|
422 return (cast(Node*)(p.at(i))).t();
|
|
|
423 }
|
|
|
424 }
|
|
|
425
|
|
293
|
426 static if (isQObjectType!T || isObjectType!T || isValueType!T) //binded types
|
|
|
427 void node_construct(Node *n, const T t)
|
|
|
428 {
|
|
|
429 static if (isValueType!T)
|
|
|
430 {
|
|
|
431 if (isLarge!T() || isStatic!T()) // TODO should be static if
|
|
|
432 n.v = T.__constructNativeCopy(t.__nativeId);
|
|
|
433 else if (isComplex!T())
|
|
|
434 T.__constructPlacedNativeCopy(t.__nativeId, n);
|
|
|
435 else
|
|
|
436 T.__constructPlacedNativeCopy(t.__nativeId, n); // TODO should be *cast(T*)(n) = cast(T)(t); as it is a primitive type. not until they are implemented with structs
|
|
|
437 }
|
|
|
438 else // in case of QObject or Object Qt types we place a pointer to a native object in the node
|
|
|
439 n = cast(Node*) t.__nativeId;
|
|
|
440 }
|
|
|
441 else // native types
|
|
292
|
442 void node_construct(Node *n, const ref T t)
|
|
|
443 {
|
|
|
444 /* TODO static if (QTypeInfo!T.isLarge || QTypeInfo!T.isStatic)
|
|
|
445 n.v = new T(t);
|
|
|
446 else static if (QTypeInfo!T.isComplex)
|
|
|
447 new (n) T(t);
|
|
|
448 else*/
|
|
293
|
449 *cast(T*)(n) = cast(T)(t);
|
|
292
|
450 }
|
|
291
|
451
|
|
|
452 void node_copy(Node *from, Node *to, Node *src)
|
|
|
453 {
|
|
|
454 /* TODO if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)
|
|
|
455 while(from != to)
|
|
|
456 (from++)->v = new T(*reinterpret_cast<T*>((src++)->v));
|
|
|
457 else if (QTypeInfo<T>::isComplex)
|
|
|
458 while(from != to)
|
|
|
459 new (from++) T(*reinterpret_cast<T*>(src++));
|
|
|
460 */
|
|
|
461 }
|
|
|
462
|
|
|
463 void free(QListData.Data* data)
|
|
|
464 {
|
|
292
|
465 writeln("QList data destroyed");
|
|
291
|
466 node_destruct(cast(Node*)(data.array.ptr + data.begin),
|
|
|
467 cast(Node*)(data.array.ptr + data.end));
|
|
|
468 if (data.ref_.load() == 0)
|
|
293
|
469 qFree(data);
|
|
291
|
470 }
|
|
|
471
|
|
|
472 void node_destruct(Node *from, Node *to)
|
|
293
|
473 {
|
|
|
474 static if (isQObjectType!T || isObjectType!T) //binded types
|
|
|
475 {} // removing just pointers, do nothing
|
|
|
476 static if (isValueType!T) //binded value types
|
|
|
477 {
|
|
|
478 if (isLarge!T() || isStatic!T()) // TODO should be static if
|
|
|
479 while (from != to)
|
|
|
480 --to, delete cast(T*)(to->v);
|
|
|
481 else if (QTypeInfo!T.isComplex)
|
|
|
482 while (from != to) --to, cast(T*)(to).~T();
|
|
|
483 }
|
|
|
484 else
|
|
|
485 { /*
|
|
|
486 if (QTypeInfo!T.isLarge || QTypeInfo!T.isStatic)
|
|
|
487 while (from != to) --to, delete cast(T*)(to->v);
|
|
|
488 else if (QTypeInfo!T.isComplex)
|
|
|
489 while (from != to) --to, cast(T*)(to).~T();
|
|
291
|
490 */
|
|
293
|
491 }
|
|
291
|
492 }
|
|
|
493 }
|
|
|
494
|
|
|
495 extern(C) void qtd_create_QList(void *nativeId);
|
|
292
|
496 extern(C) void qtd_create_QList_QObject(void *nativeId); |
