Mercurial > projects > qtd
diff d2/qt/core/QList.d @ 344:96a75b1e5b26
project structure changes
author | Max Samukha <maxter@spambox.com> |
---|---|
date | Fri, 14 May 2010 12:14:37 +0300 |
parents | qt/core/QList.d@5896535a03cd |
children | 970332a88b72 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/d2/qt/core/QList.d Fri May 14 12:14:37 2010 +0300 @@ -0,0 +1,627 @@ +module qt.core.QList; + +import qt.QGlobal; +import qt.core.QTypeInfo; +import qt.core.QString; +import qtd.QtdObject; +import qtd.Atomic; +import qtd.MetaMarshall; + +import core.stdc.stdlib : qRealloc = realloc, qFree = free, qMalloc = malloc; +import core.stdc.string : memcpy, memmove; + +import std.traits; + +enum INT_MAX = int.max; + +bool isComplex(T)() + if (is(T.QTypeInfo)) +{ + return T.QTypeInfo.isComplex; +} + +bool isStatic(T)() + if (is(T.QTypeInfo)) +{ + return T.QTypeInfo.isStatic; +} + +bool isLarge(T)() + if (is(T.QTypeInfo)) +{ + return T.QTypeInfo.isLarge; +} + +template isQtReference(T) +{ + enum isQtReference = isQObjectType!T || isObjectType!T || isValueType!T || is(T == string); +} + +int qAllocMore(int alloc, int extra) +{ + if (alloc == 0 && extra == 0) + return 0; + const int page = 1 << 12; + int nalloc; + alloc += extra; + if (alloc < 1<<6) { + nalloc = (1<<3) + ((alloc >>3) << 3); + } else { + // don't do anything if the loop will overflow signed int. + if (alloc >= INT_MAX/2) + return INT_MAX; + nalloc = (alloc < page) ? 1 << 3 : page; + while (nalloc < alloc) { + if (nalloc <= 0) + return INT_MAX; + nalloc *= 2; + } + } + return nalloc - extra; +} + +void q_new_at(T)(T* ptr, const ref T t) +{ + memcpy(ptr, &t, T.sizeof); +/* static if (__traits(compiles, ptr.__postblit())) DMD bug #3539 + ptr.__postblit();*/ +} + +T* q_new(T)(const ref T t) +{ + T* ptr = cast(T*) qMalloc(T.sizeof); + q_new_at!T(ptr, t); + return ptr; +} + +void q_delete(T)(T* t) +{ + static if (__traits(compiles, t.__dtor())) + t.__dtor(); + qFree(t); +} + +private int grow(int size) +{ + // dear compiler: don't optimize me out. +// synchronized { + int x = qAllocMore(size * (void*).sizeof, QListData.DataHeaderSize) / (void*).sizeof; + return x; +// } +} + +struct QListData { +private: + struct Data { + Atomic!int ref_; + int alloc, begin, end; + uint sharable; + void*[1] array; + } + + enum { DataHeaderSize = Data.sizeof - (void*).sizeof } + + static Data shared_null; + Data *d; + + static this() + { + shared_null = Data(Atomic!int(1), 0, 0, 0, true, [null]); + } + + +// Data *detach(); // remove in 5.0 + + Data* detach2() + { + Data* x = d; + d = cast(Data*)(qMalloc(DataHeaderSize + x.alloc * (void*).sizeof)); + if (!d) + qFatal("QList: Out of memory"); + + memcpy(d, x, DataHeaderSize + x.alloc * (void*).sizeof); + d.alloc = x.alloc; + d.ref_.store(1); + d.sharable = true; + if (!d.alloc) + d.begin = d.end = 0; + + return x; + } + + void realloc(int alloc) + { +// assert(d.ref_ == 1); + Data* x = cast(Data*)(qRealloc(d, DataHeaderSize + alloc * (void*).sizeof)); + if (!x) + qFatal("QList: Out of memory"); + + d = x; + d.alloc = alloc; + if (!alloc) + d.begin = d.end = 0; + } + + void** append() + { +// #TODO Q_ASSERT(d.ref_ == 1); + if (d.end == d.alloc) { + int n = d.end - d.begin; + if (d.begin > 2 * d.alloc / 3) { + memcpy(d.array.ptr + n, d.array.ptr + d.begin, n * (void*).sizeof); + d.begin = n; + d.end = n * 2; + } else { + realloc(grow(d.alloc + 1)); + } + } + return d.array.ptr + d.end++; + } + + void **append(const ref QListData l) + { +// Q_ASSERT(d.ref_ == 1); + int e = d.end; + int n = l.d.end - l.d.begin; + if (n) { + if (e + n > d.alloc) + realloc(grow(e + l.d.end - l.d.begin)); + memcpy(d.array.ptr + d.end, l.d.array.ptr + l.d.begin, n * (void*).sizeof); + d.end += n; + } + return d.array.ptr + e; + } + + void **prepend() + { +// Q_ASSERT(d.ref_ == 1); + if (d.begin == 0) { + if (d.end >= d.alloc / 3) + realloc(grow(d.alloc + 1)); + + if (d.end < d.alloc / 3) + d.begin = d.alloc - 2 * d.end; + else + d.begin = d.alloc - d.end; + + memmove(d.array.ptr + d.begin, d.array.ptr, d.end * (void*).sizeof); + d.end += d.begin; + } + return d.array.ptr + --d.begin; + } + + void **insert(int i) + { +// Q_ASSERT(d.ref_ == 1); + if (i <= 0) + return prepend(); + if (i >= d.end - d.begin) + return append(); + + bool leftward = false; + int size = d.end - d.begin; + + if (d.begin == 0) { + if (d.end == d.alloc) { + // If the array is full, we expand it and move some items rightward + realloc(grow(d.alloc + 1)); + } else { + // If there is free space at the end of the array, we move some items rightward + } + } else { + if (d.end == d.alloc) { + // If there is free space at the beginning of the array, we move some items leftward + leftward = true; + } else { + // If there is free space at both ends, we move as few items as possible + leftward = (i < size - i); + } + } + + if (leftward) { + --d.begin; + memmove(d.array.ptr + d.begin, d.array.ptr + d.begin + 1, i * (void*).sizeof); + } else { + memmove(d.array.ptr + d.begin + i + 1, d.array.ptr + d.begin + i, + (size - i) * (void*).sizeof); + ++d.end; + } + return d.array.ptr + d.begin + i; + } + + void remove(int i) + { +// Q_ASSERT(d.ref_ == 1); + i += d.begin; + if (i - d.begin < d.end - i) { + if (int offset = i - d.begin) + memmove(d.array.ptr + d.begin + 1, d.array.ptr + d.begin, offset * (void*).sizeof); + d.begin++; + } else { + if (int offset = d.end - i - 1) + memmove(d.array.ptr + i, d.array.ptr + i + 1, offset * (void*).sizeof); + d.end--; + } + } + + void remove(int i, int n) + { +// Q_ASSERT(d.ref_ == 1); + i += d.begin; + int middle = i + n/2; + if (middle - d.begin < d.end - middle) { + memmove(d.array.ptr + d.begin + n, d.array.ptr + d.begin, + (i - d.begin) * (void*).sizeof); + d.begin += n; + } else { + memmove(d.array.ptr + i, d.array.ptr + i + n, + (d.end - i - n) * (void*).sizeof); + d.end -= n; + } + } + + void move(int from, int to) + { +// Q_ASSERT(d.ref_ == 1); + if (from == to) + return; + + from += d.begin; + to += d.begin; + void *t = d.array.ptr[from]; + + if (from < to) { + if (d.end == d.alloc || 3 * (to - from) < 2 * (d.end - d.begin)) { + memmove(d.array.ptr + from, d.array.ptr + from + 1, (to - from) * (void*).sizeof); + } else { + // optimization + if (int offset = from - d.begin) + memmove(d.array.ptr + d.begin + 1, d.array.ptr + d.begin, offset * (void*).sizeof); + if (int offset = d.end - (to + 1)) + memmove(d.array.ptr + to + 2, d.array.ptr + to + 1, offset * (void*).sizeof); + ++d.begin; + ++d.end; + ++to; + } + } else { + if (d.begin == 0 || 3 * (from - to) < 2 * (d.end - d.begin)) { + memmove(d.array.ptr + to + 1, d.array.ptr + to, (from - to) * (void*).sizeof); + } else { + // optimization + if (int offset = to - d.begin) + memmove(d.array.ptr + d.begin - 1, d.array.ptr + d.begin, offset * (void*).sizeof); + if (int offset = d.end - (from + 1)) + memmove(d.array.ptr + from, d.array.ptr + from + 1, offset * (void*).sizeof); + --d.begin; + --d.end; + --to; + } + } + d.array.ptr[to] = t; + } + + void **erase(void **xi) + { +// Q_ASSERT(d.ref_ == 1); + int i = xi - (d.array.ptr + d.begin); + remove(i); + return d.array.ptr + d.begin + i; + } + + int size() const { return d.end - d.begin; } + bool isEmpty() const { return d.end == d.begin; } + const (void*)* at(int i) const { return d.array.ptr + d.begin + i; } + const (void*)* begin() const { return d.array.ptr + d.begin; } + const (void*)* end() const { return d.array.ptr + d.end; } +} + +import std.stdio; +import std.conv; + +alias void Dummy; // DMD bug #3538 + +struct QList(T, alias Default = Dummy) +{ + static if (is(Default == Dummy)) + alias QTypeInfo!T TI; + else + alias Default TI; + + struct Node + { + void *v; + + static if (isQObjectType!T || isObjectType!T || isValueType!T || is(T == string)) // binded Qt types + { + T t() + { + static if(is(T == string)) + { + void* ptr = cast(void*)(TI.isLarge || TI.isStatic ? v : &this); + return QStringUtil.toNativeString(ptr); + } + else static if (isValueType!T) + { + void* ptr = cast(void*)(isLarge!T() || isStatic!T() ? v : &this); + return new T(ptr, QtdObjectFlags.nativeOwnership); + } + else + { + return T.__getObject( *cast(void**)(&this) ); + } + } + } + else // native types + { + ref T t() + { + static if(TI.isLarge || TI.isStatic) + return *cast(T*)(this.v); + else + return *cast(T*)(&this); + } + } + } + + union { + QListData p; + QListData.Data* d; + } + +public: + /* + void output() + { + writeln("QList atomic ", d.ref_.load()); + } + */ + + static QList!T opCall() + { + QList!T res; +// writeln("QList opCall"); + + res.d = &QListData.shared_null; + res.d.ref_.increment(); + + return res; + } + + this(this) + { +// writeln("QList postblit"); + d.ref_.increment(); + if (!d.sharable) + detach_helper(); + } + + ~this() + { +// writeln("QList ~this"); + if (d && !d.ref_.decrement()) + free(d); + } + + ref QList!T opAssign(const ref QList!T l) + { +// writeln("QList opAssign"); + if (d != l.d) { + QListData.Data* nd = cast(QListData.Data*)l.d; + nd.ref_.increment(); + if (!d.ref_.decrement()) + free(d); + d = nd; + if (!d.sharable) + detach_helper(); + } + return this; + } + + int length() const { return p.size(); } + int size() const { return length; } + + void detach() { if (d.ref_.load() != 1) detach_helper(); } + + private void detach_helper() + { + Node *n = cast(Node*)(p.begin()); + QListData.Data* x = p.detach2(); + node_copy(cast(Node*)(p.begin()), cast(Node*)(p.end()), n); + if (!x.ref_.decrement()) + free(x); + } + + void append(const T t) // fix to const ref for complex types TODO + { + detach(); + static if (isQObjectType!T || isObjectType!T || isValueType!T) + { + node_construct(cast(Node*)(p.append()), t); + } + else + { + const T cpy = t; + node_construct(cast(Node*)(p.append()), cpy); + } + } + + alias append opCatAssign; + + static if (isQObjectType!T || isObjectType!T || isValueType!T || is(T == string)) + { + T at(int i) const + { + assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range"); + return (cast(Node*)(p.at(i))).t(); + } + T opIndex(int i) + { + assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range"); + return (cast(Node*)(p.at(i))).t(); + } + } + else + { + const (T) at(int i) const // DMD BUG + { + assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range"); + return (cast(Node*)(p.at(i))).t(); + } + ref T opIndex(int i) + { + assert(i >= 0 && i < p.size(), "QList!T.at(): index out of range"); + return (cast(Node*)(p.at(i))).t(); + } + } + + static if (isQObjectType!T || isObjectType!T || isValueType!T) //binded types + void node_construct(Node *n, const T t) + { + static if (isValueType!T) + { + if (isLarge!T() || isStatic!T()) // TODO should be static if + n.v = T.__constructNativeCopy(t.__nativeId); // n.v = new T(t); + else if (isComplex!T()) + T.__constructPlacedNativeCopy(t.__nativeId, n); // new (n) T(t); + else + T.__constructPlacedNativeCopy(t.__nativeId, n); // TODO should be *cast(T*)(n) = cast(T)(t); as it is a primitive type. fix when they are implemented with structs + } + else // in case of QObject or Object Qt types we place a pointer to a native object in the node + n = cast(Node*) t.__nativeId; + } + else static if (is(T == string)) + { + void node_construct(Node *n, T t) + { + QString.__constructPlacedQString(n, t); + } + } + else // native types + void node_construct(Node *n, const ref T t) + { + static if (TI.isLarge || TI.isStatic) + n.v = q_new!T(t); // n.v = new T(t); + else static if (TI.isComplex) + q_new_at(n, t); // new (n) T(t); + else + *cast(T*)(n) = cast(T)(t); + } + + void node_copy(Node *from, Node *to, Node *src) + { +// writeln("QList node_copy"); + static if (isQObjectType!T || isObjectType!T) + {} // ensure to do nothing. copying only a pointer + else static if(is(T == string)) + { + while(from != to) // TODO when porting to Qt 5 ensure that QTypeInfo<QString>.isLarge and .isStatic == false + QString.__constructPlacedNativeCopy(src++, from++); // new (from++) T(*reinterpret_cast<T*>(src++)); + } + else static if (isValueType!T) + { + if (TI.isLarge || TI.isStatic) // TODO should be static if + while(from != to) + (from++).v = T.__constructNativeCopy((src++).v); // (from++)->v = new T(*reinterpret_cast<T*>((src++)->v)); + else if (TI.isComplex) + while(from != to) + T.__constructPlacedNativeCopy(src++, from++); // new (from++) T(*reinterpret_cast<T*>(src++)); + } + else static if (TI.isLarge || TI.isStatic) + while(from != to) + (from++).v = q_new!T(*cast(T*)((src++).v)); + else static if (TI.isComplex) + while(from != to) + q_new_at(from++, *cast(T*)(src++)); + } + + T[] toArray() + { + T[] res; + res.length = this.length; + for(int i = 0; i < res.length; ++i) + { + static if (isValueType!T) + res[i] = new T(T.__constructNativeCopy(this.at(i).__nativeId)); // Node should probably provide a ptr method to directly extract pointer to the native value stored in the list to avoid creating a dummy D object in t() + else + res[i] = this.opIndex(i); + } + return res; + } + + void free(QListData.Data* data) + { +// writeln("QList data destroyed"); + node_destruct(cast(Node*)(data.array.ptr + data.begin), + cast(Node*)(data.array.ptr + data.end)); + if (data.ref_.load() == 0) + qFree(data); + } + + void node_destruct(Node *from, Node *to) + { + static if (isQObjectType!T || isObjectType!T) //binded types + {} // removing just pointers, do nothing + else static if (is(T == string)) + { + while (from != to) + --to, QString.__callNativeDestructor(to); + } + else static if (isValueType!T) //binded value types + { + if (isLarge!T() || isStatic!T()) // TODO should be static if + while (from != to) + --to, T.__deleteNativeObject(to.v); + else if (isComplex!T()) + while (from != to) + --to, T.__callNativeDestructor(to); + } + else + { + static if (TI.isLarge || TI.isStatic) + while (from != to) --to, q_delete(cast(T*)(to.v)); + else static if (TI.isComplex) + while (from != to) --to, cast(T*)(to).__dtor(); + } + } + + //iteration support + int opApply(int delegate(ref T) dg) + { + int result = 0; + int sz = this.length; + for (int i = 0; i < sz; i++) + { + static if (isQtReference!T) + { + T t = this[i]; // hack to avoid "is not an lvalue" error, since dg accepts ref T + result = dg(t); + } + else + result = dg(this[i]); + + if (result) + break; + } + return result; + } +} + +alias QList!string QStringList; + +QList!T toQList(T)(T[] src) +{ + auto res = QList!T.opCall(); + foreach(elem; src) + res.append(elem); + return res; +} + +QList!T qList(T)() +{ + return QList!T.opCall(); +} + +extern(C) void qtd_create_QList(void *nativeId); +extern(C) void qtd_create_QList_double(void *nativeId); + +extern(C) void qtd_create_QList_QObject(void *nativeId);