add QList::reserve()

while this reserves memory "only" for the pointer list, this still
amounts to 100% of the re-allocs for small simple types. for
big/complex/static types the gain is lower, but still.

Reviewed-by: Denis
Reviewed-by: Joao

2 files changed, 57 insertions, 8 deletions

diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index ce62016..ac0dc46 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -125,22 +125,23 @@ QListData::Data *QListData::detach2()
 }
 
 /*!
- *  Detaches the QListData by reallocating new memory.
+ *  Detaches the QListData by allocating new memory for a list which possibly
+ *  has a different size than the copied one.
  *  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::detach3()
+QListData::Data *QListData::detach(int alloc)
 {
     Data *x = d;
-    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + x->alloc * sizeof(void *)));
+    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
     Q_CHECK_PTR(t);
 
     t->ref = 1;
     t->sharable = true;
-    t->alloc = x->alloc;
-    if (!t->alloc) {
+    t->alloc = alloc;
+    if (!alloc) {
         t->begin = 0;
         t->end = 0;
     } else {
@@ -152,6 +153,21 @@ QListData::Data *QListData::detach3()
     return x;
 }
 
+/*!
+ *  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.
+ *
+ *  \internal
+ */
+#if QT_VERSION >= 0x050000
+#  error "Remove QListData::detach3(), it is only required for binary compatibility for 4.5.x to 4.6.x"
+#endif
+QListData::Data *QListData::detach3()
+{
+    return detach(d->alloc);
+}
+
 void QListData::realloc(int alloc)
 {
     Q_ASSERT(d->ref == 1);
@@ -647,6 +663,19 @@ void **QListData::erase(void **xi)
     Same as at().
 */
 
+/*! \fn QList::reserve(int alloc)
+
+    Reserve space for \a alloc elements.
+
+    If \a alloc is smaller than the current size of the list, nothing will happen.
+
+    Use this function to avoid repetetive reallocation of QList's internal
+    data if you can predict how many elements will be appended.
+    Note that the reservation applies only to the internal pointer array.
+
+    \since 4.7
+*/
+
 /*! \fn void QList::append(const T &value)
 
     Inserts \a value at the end of the list.
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 1d08c41..3b9eefa 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -72,9 +72,10 @@ struct Q_CORE_EXPORT QListData {
     };
     enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };
 
+    Data *detach(int alloc);
     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;
@@ -140,6 +141,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);
@@ -331,6 +333,7 @@ public:
 #endif
 
 private:
+    void detach_helper(int alloc);
     void detach_helper();
     void free(QListData::Data *d);
 
@@ -464,6 +467,17 @@ 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();
@@ -599,10 +613,10 @@ 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 void QList<T>::detach_helper(int alloc)
 {
     Node *n = reinterpret_cast<Node *>(p.begin());
-    QListData::Data *x = p.detach3();
+    QListData::Data *x = p.detach(alloc);
     QT_TRY {
         node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
     } QT_CATCH(...) {
@@ -616,6 +630,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())