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