summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qlist.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qlist.h')
-rw-r--r--src/corelib/tools/qlist.h225
1 files changed, 172 insertions, 53 deletions
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 120442d..c6dd106 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -52,6 +52,7 @@
#endif
#include <new>
+#include <limits.h>
#include <string.h>
QT_BEGIN_HEADER
@@ -72,13 +73,16 @@ struct Q_CORE_EXPORT QListData {
};
enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };
+ Data *detach(int alloc);
+ Data *detach_grow(int *i, int n);
Data *detach(); // remove in 5.0
Data *detach2(); // remove in 5.0
- Data *detach3();
+ Data *detach3(); // remove in 5.0
void realloc(int alloc);
static Data shared_null;
Data *d;
void **erase(void **xi);
+ void **append(int n);
void **append();
void **append(const QListData &l);
void **append2(const QListData &l); // remove in 5.0
@@ -94,6 +98,25 @@ struct Q_CORE_EXPORT QListData {
inline void **end() const { return d->array + d->end; }
};
+//////////////////////////////////////////////////////////////////////////////////
+//
+// QtPodForSize and QtPodForType are internal and may change or go away any time.
+// We mean it.
+//
+//////////////////////////////////////////////////////////////////////////////////
+template <int N> struct QtPodForSize {
+ // This base type is rather obviously broken and cannot be made
+ // working due to alignment constraints.
+ // This doesn't matter as far as QList is concerned, as we are
+ // using this type only for QTypeInfo<T>::isLarge == false.
+ typedef struct { } Type;
+};
+template <> struct QtPodForSize<1> { typedef quint8 Type; };
+template <> struct QtPodForSize<2> { typedef quint16 Type; };
+template <> struct QtPodForSize<4> { typedef quint32 Type; };
+template <> struct QtPodForSize<8> { typedef quint64 Type; };
+template <class T> struct QtPodForType : QtPodForSize<sizeof(T)> { };
+
template <typename T>
class QList
{
@@ -130,6 +153,7 @@ public:
inline bool isDetached() const { return d->ref == 1; }
inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+ inline bool isSharedWith(const QList<T> &other) const { return d == other.d; }
inline bool isEmpty() const { return p.isEmpty(); }
@@ -139,6 +163,7 @@ public:
const T &operator[](int i) const;
T &operator[](int i);
+ void reserve(int size);
void append(const T &t);
void append(const QList<T> &t);
void prepend(const T &t);
@@ -163,7 +188,7 @@ public:
public:
Node *i;
typedef std::random_access_iterator_tag iterator_category;
- typedef ptrdiff_t difference_type;
+ typedef qptrdiff difference_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
@@ -210,7 +235,7 @@ public:
public:
Node *i;
typedef std::random_access_iterator_tag iterator_category;
- typedef ptrdiff_t difference_type;
+ typedef qptrdiff difference_type;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
@@ -289,7 +314,7 @@ public:
typedef const value_type *const_pointer;
typedef value_type &reference;
typedef const value_type &const_reference;
- typedef ptrdiff_t difference_type;
+ typedef qptrdiff difference_type;
#ifdef QT3_SUPPORT
inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }
@@ -330,6 +355,8 @@ public:
#endif
private:
+ Node *detach_helper_grow(int i, int n);
+ void detach_helper(int alloc);
void detach_helper();
void free(QListData::Data *d);
@@ -463,11 +490,21 @@ inline T QList<T>::takeLast()
{ T t = last(); removeLast(); return t; }
template <typename T>
+Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc)
+{
+ if (d->alloc < alloc) {
+ if (d->ref != 1)
+ detach_helper(alloc);
+ else
+ p.realloc(alloc);
+ }
+}
+
+template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
{
- detach();
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.append());
+ if (d->ref != 1) {
+ Node *n = detach_helper_grow(INT_MAX, 1);
QT_TRY {
node_construct(n, t);
} QT_CATCH(...) {
@@ -475,13 +512,25 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
QT_RETHROW;
}
} else {
- const T cpy(t);
- Node *n = reinterpret_cast<Node *>(p.append());
- QT_TRY {
- node_construct(n, cpy);
- } QT_CATCH(...) {
- --d->end;
- QT_RETHROW;
+ if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
+ Node *n = reinterpret_cast<Node *>(p.append());
+ QT_TRY {
+ node_construct(n, t);
+ } QT_CATCH(...) {
+ --d->end;
+ QT_RETHROW;
+ }
+ } else {
+ typedef typename QtPodForType<T>::Type PodNode;
+ PodNode cpy = *reinterpret_cast<const PodNode *>(&t);
+ Node *n = reinterpret_cast<Node *>(p.append());
+ QT_TRY {
+ void *ptr = &cpy;
+ node_construct(n, *reinterpret_cast<T *>(ptr));
+ } QT_CATCH(...) {
+ --d->end;
+ QT_RETHROW;
+ }
}
}
}
@@ -489,9 +538,8 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
template <typename T>
inline void QList<T>::prepend(const T &t)
{
- detach();
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.prepend());
+ if (d->ref != 1) {
+ Node *n = detach_helper_grow(0, 1);
QT_TRY {
node_construct(n, t);
} QT_CATCH(...) {
@@ -499,13 +547,25 @@ inline void QList<T>::prepend(const T &t)
QT_RETHROW;
}
} else {
- const T cpy(t);
- Node *n = reinterpret_cast<Node *>(p.prepend());
- QT_TRY {
- node_construct(n, cpy);
- } QT_CATCH(...) {
- ++d->begin;
- QT_RETHROW;
+ if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
+ Node *n = reinterpret_cast<Node *>(p.prepend());
+ QT_TRY {
+ node_construct(n, t);
+ } QT_CATCH(...) {
+ ++d->begin;
+ QT_RETHROW;
+ }
+ } else {
+ typedef typename QtPodForType<T>::Type PodNode;
+ PodNode cpy = *reinterpret_cast<const PodNode *>(&t);
+ Node *n = reinterpret_cast<Node *>(p.prepend());
+ QT_TRY {
+ void *ptr = &cpy;
+ node_construct(n, *reinterpret_cast<T *>(ptr));
+ } QT_CATCH(...) {
+ ++d->begin;
+ QT_RETHROW;
+ }
}
}
}
@@ -513,9 +573,8 @@ inline void QList<T>::prepend(const T &t)
template <typename T>
inline void QList<T>::insert(int i, const T &t)
{
- detach();
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.insert(i));
+ if (d->ref != 1) {
+ Node *n = detach_helper_grow(i, 1);
QT_TRY {
node_construct(n, t);
} QT_CATCH(...) {
@@ -523,13 +582,25 @@ inline void QList<T>::insert(int i, const T &t)
QT_RETHROW;
}
} else {
- const T cpy(t);
- Node *n = reinterpret_cast<Node *>(p.insert(i));
- QT_TRY {
- node_construct(n, cpy);
- } QT_CATCH(...) {
- p.remove(i);
- QT_RETHROW;
+ if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
+ Node *n = reinterpret_cast<Node *>(p.insert(i));
+ QT_TRY {
+ node_construct(n, t);
+ } QT_CATCH(...) {
+ p.remove(i);
+ QT_RETHROW;
+ }
+ } else {
+ typedef typename QtPodForType<T>::Type PodNode;
+ PodNode cpy = *reinterpret_cast<const PodNode *>(&t);
+ Node *n = reinterpret_cast<Node *>(p.insert(i));
+ QT_TRY {
+ void *ptr = &cpy;
+ node_construct(n, *reinterpret_cast<T *>(ptr));
+ } QT_CATCH(...) {
+ p.remove(i);
+ QT_RETHROW;
+ }
}
}
}
@@ -539,12 +610,7 @@ inline void QList<T>::replace(int i, const T &t)
{
Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range");
detach();
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- reinterpret_cast<Node *>(p.at(i))->t() = t;
- } else {
- const T cpy(t);
- reinterpret_cast<Node *>(p.at(i))->t() = cpy;
- }
+ reinterpret_cast<Node *>(p.at(i))->t() = t;
}
template <typename T>
@@ -574,11 +640,20 @@ Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const
alength = size() - pos;
if (pos == 0 && alength == size())
return *this;
- QList<T> cpy;
if (pos + alength > size())
alength = size() - pos;
- for (int i = pos; i < pos + alength; ++i)
- cpy += at(i);
+ QList<T> cpy;
+ cpy.reserve(alength);
+ cpy.d->end = alength;
+ QT_TRY {
+ cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()),
+ reinterpret_cast<Node *>(cpy.p.end()),
+ reinterpret_cast<Node *>(p.begin() + pos));
+ } QT_CATCH(...) {
+ // restore the old end
+ cpy.d->end = 0;
+ QT_RETHROW;
+ }
return cpy;
}
@@ -598,10 +673,40 @@ Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const
}
template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
+Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c)
{
Node *n = reinterpret_cast<Node *>(p.begin());
- QListData::Data *x = p.detach3();
+ QListData::Data *x = p.detach_grow(&i, c);
+ QT_TRY {
+ node_copy(reinterpret_cast<Node *>(p.begin()),
+ reinterpret_cast<Node *>(p.begin() + i), n);
+ } QT_CATCH(...) {
+ qFree(d);
+ d = x;
+ QT_RETHROW;
+ }
+ QT_TRY {
+ node_copy(reinterpret_cast<Node *>(p.begin() + i + c),
+ reinterpret_cast<Node *>(p.end()), n + i);
+ } QT_CATCH(...) {
+ node_destruct(reinterpret_cast<Node *>(p.begin()),
+ reinterpret_cast<Node *>(p.begin() + i));
+ qFree(d);
+ d = x;
+ QT_RETHROW;
+ }
+
+ if (!x->ref.deref())
+ free(x);
+
+ return reinterpret_cast<Node *>(p.begin() + i);
+}
+
+template <typename T>
+Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc)
+{
+ Node *n = reinterpret_cast<Node *>(p.begin());
+ QListData::Data *x = p.detach(alloc);
QT_TRY {
node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
} QT_CATCH(...) {
@@ -615,6 +720,12 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
}
template <typename T>
+Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
+{
+ detach_helper(d->alloc);
+}
+
+template <typename T>
Q_OUTOFLINE_TEMPLATE QList<T>::~QList()
{
if (d && !d->ref.deref())
@@ -700,14 +811,22 @@ Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<
template <typename T>
Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l)
{
- detach();
- Node *n = reinterpret_cast<Node *>(p.append2(l.p));
- QT_TRY{
- node_copy(n, reinterpret_cast<Node *>(p.end()), reinterpret_cast<Node *>(l.p.begin()));
- } QT_CATCH(...) {
- // restore the old end
- d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
- QT_RETHROW;
+ if (!l.isEmpty()) {
+ if (isEmpty()) {
+ *this = l;
+ } else {
+ Node *n = (d->ref != 1)
+ ? detach_helper_grow(INT_MAX, l.size())
+ : reinterpret_cast<Node *>(p.append2(l.p));
+ QT_TRY {
+ node_copy(n, reinterpret_cast<Node *>(p.end()),
+ reinterpret_cast<Node *>(l.p.begin()));
+ } QT_CATCH(...) {
+ // restore the old end
+ d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
+ QT_RETHROW;
+ }
+ }
}
return *this;
}
generated by cgit v0.12 at 2025-02-03 14:48:48 (GMT)