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