avoid double reallocations in inserting operations

operator+=() and co. would first detach, and then realloc if they found
the reservation too small. in particular, appending anything to an empty
list would trigger this double reallocation (first copy shared_null,
then grow the copy).

entirely rewritten take 3, this time without memory corruption or
exhaustion ... :)

Reviewed-by: joao

1 files changed, 96 insertions, 35 deletions

diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index b79011e95f..3a29e13ff4 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(...) {