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

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(...) {