summaryrefslogtreecommitdiffstats
path: root/src/corelib
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib')
-rw-r--r--src/corelib/tools/qlist.cpp47
-rw-r--r--src/corelib/tools/qlist.h131
2 files changed, 143 insertions, 35 deletions
diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index 249b8d1..6f5bb9b 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -66,6 +66,53 @@ static int grow(int size)
return x;
}
+/*!
+ * Detaches the QListData by allocating new memory for a list which will be bigger
+ * than the copied one and is expected to grow further.
+ * *idx is the desired insertion point and is clamped to the actual size of the list.
+ * num is the number of new elements to insert at the insertion point.
+ * Returns the old (shared) data, it is up to the caller to deref() and free().
+ * For the new data node_copy needs to be called.
+ *
+ * \internal
+ */
+QListData::Data *QListData::detach_grow(int *idx, int num)
+{
+ Data *x = d;
+ int l = x->end - x->begin;
+ int nl = l + num;
+ int alloc = grow(nl);
+ Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
+ Q_CHECK_PTR(t);
+
+ t->ref = 1;
+ t->sharable = true;
+ t->alloc = alloc;
+ // The space reservation algorithm's optimization is biased towards appending:
+ // Something which looks like an append will put the data at the beginning,
+ // while something which looks like a prepend will put it in the middle
+ // instead of at the end. That's based on the assumption that prepending
+ // is uncommon and even an initial prepend will eventually be followed by
+ // at least some appends.
+ int bg;
+ if (*idx < 0) {
+ *idx = 0;
+ bg = (alloc - nl) >> 1;
+ } else if (*idx > l) {
+ *idx = l;
+ bg = 0;
+ } else if (*idx < (l >> 1)) {
+ bg = (alloc - nl) >> 1;
+ } else {
+ bg = 0;
+ }
+ t->begin = bg;
+ t->end = bg + nl;
+ d = t;
+
+ return x;
+}
+
#if QT_VERSION >= 0x050000
# error "Remove QListData::detach(), it is only required for binary compatibility for 4.0.x to 4.2.x"
#endif
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index b79011e..3a29e13 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
@@ -73,6 +74,7 @@ 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(); // remove in 5.0
@@ -353,6 +355,7 @@ public:
#endif
private:
+ Node *detach_helper_grow(int i, int n);
void detach_helper(int alloc);
void detach_helper();
void free(QListData::Data *d);
@@ -500,9 +503,8 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int 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(...) {
@@ -510,14 +512,24 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
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 {
- node_construct(n, *reinterpret_cast<const T *>(&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 {
+ node_construct(n, *reinterpret_cast<const T *>(&cpy));
+ } QT_CATCH(...) {
+ --d->end;
+ QT_RETHROW;
+ }
}
}
}
@@ -525,9 +537,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(...) {
@@ -535,14 +546,24 @@ inline void QList<T>::prepend(const T &t)
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 {
- node_construct(n, *reinterpret_cast<const T *>(&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 {
+ node_construct(n, *reinterpret_cast<const T *>(&cpy));
+ } QT_CATCH(...) {
+ ++d->begin;
+ QT_RETHROW;
+ }
}
}
}
@@ -550,9 +571,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(...) {
@@ -560,14 +580,24 @@ inline void QList<T>::insert(int i, const T &t)
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 {
- node_construct(n, *reinterpret_cast<const T *>(&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 {
+ node_construct(n, *reinterpret_cast<const T *>(&cpy));
+ } QT_CATCH(...) {
+ p.remove(i);
+ QT_RETHROW;
+ }
}
}
}
@@ -640,6 +670,36 @@ Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const
}
template <typename T>
+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.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());
@@ -748,8 +808,9 @@ 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));
+ 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(...) {
generated by cgit v0.12 at 2024-12-29 05:16:06 (GMT)