From 02135be18f3c4b1d1525aff6dfe96c9c8521084d Mon Sep 17 00:00:00 2001
From: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
Date: Tue, 16 Feb 2010 15:44:41 +0100
Subject: avoid double reallocations in appending 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).

Reviewed-by: joao
Reviewed-by: denis
---
 src/corelib/tools/qlist.cpp | 18 ++++++++++++++++++
 src/corelib/tools/qlist.h   | 28 ++++++++++++++++++++++++----
 2 files changed, 42 insertions(+), 4 deletions(-)

diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index ac0dc46..a468c77 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -154,6 +154,19 @@ QListData::Data *QListData::detach(int alloc)
 }
 
 /*!
+ *  Detaches the QListData by allocating new memory for a list which will be bigger
+ *  than the copied one and is expected to grow further.
+ *  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 alloc)
+{
+    return detach(grow(alloc));
+}
+
+/*!
  *  Detaches the QListData by reallocating new memory.
  *  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.
@@ -596,6 +609,11 @@ void **QListData::erase(void **xi)
     \internal
 */
 
+/*! \fn void QList::detach_grow(int alloc)
+
+    \internal
+*/
+
 /*! \fn void QList::detachShared()
 
     \internal
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 8c75c98..1edac03 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -73,6 +73,7 @@ struct Q_CORE_EXPORT QListData {
     enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };
 
     Data *detach(int alloc);
+    Data *detach_grow(int alloc);
     Data *detach(); // remove in 5.0
     Data *detach2(); // remove in 5.0
     Data *detach3(); // remove in 5.0
@@ -121,6 +122,7 @@ public:
     inline int size() const { return p.size(); }
 
     inline void detach() { if (d->ref != 1) detach_helper(); }
+    inline void detach_grow(int by) { if (d->ref != 1) detach_helper_grow(d->end - d->begin + by); }
 
     inline void detachShared()
     {
@@ -333,6 +335,7 @@ public:
 #endif
 
 private:
+    void detach_helper_grow(int alloc);
     void detach_helper(int alloc);
     void detach_helper();
     void free(QListData::Data *d);
@@ -480,7 +483,7 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc)
 template <typename T>
 Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
 {
-    detach();
+    detach_grow(1);
     if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.append());
         QT_TRY {
@@ -504,7 +507,7 @@ Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
 template <typename T>
 inline void QList<T>::prepend(const T &t)
 {
-    detach();
+    detach_grow(1);
     if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.prepend());
         QT_TRY {
@@ -528,7 +531,7 @@ inline void QList<T>::prepend(const T &t)
 template <typename T>
 inline void QList<T>::insert(int i, const T &t)
 {
-    detach();
+    detach_grow(1);
     if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.insert(i));
         QT_TRY {
@@ -622,6 +625,23 @@ Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const
 }
 
 template <typename T>
+Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper_grow(int alloc)
+{
+    Node *n = reinterpret_cast<Node *>(p.begin());
+    QListData::Data *x = p.detach_grow(alloc);
+    QT_TRY {
+        node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
+    } QT_CATCH(...) {
+        qFree(d);
+        d = x;
+        QT_RETHROW;
+    }
+
+    if (!x->ref.deref())
+        free(x);
+}
+
+template <typename T>
 Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc)
 {
     Node *n = reinterpret_cast<Node *>(p.begin());
@@ -730,7 +750,7 @@ 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();
+    detach_grow(l.size());
     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()));
-- 
cgit v0.12