Mercurial > projects > qtd

comparison qt/core/QList.d @ 291:0d2094800bdb signals

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
QList native implementation
author eldar
date Mon, 09 Nov 2009 20:49:26 +0000
parents
children 19498f420252
comparison
equal deleted inserted replaced
290:dcc2b22d1f55 291:0d2094800bdb
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);