1 files changed, 69 insertions, 22 deletions

diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index ac0dc46..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
@@ -180,22 +227,30 @@ void QListData::realloc(int alloc)
         d->begin = d->end = 0;
 }
 
-// ensures that enough space is available to append one element
-void **QListData::append()
+// ensures that enough space is available to append n elements
+void **QListData::append(int n)
 {
     Q_ASSERT(d->ref == 1);
-    if (d->end == d->alloc) {
-        int n = d->end - d->begin;
-        if (d->begin > 2 * d->alloc / 3) {
+    int e = d->end;
+    if (e + n > d->alloc) {
+        int b = d->begin;
+        if (b - n >= 2 * d->alloc / 3) {
             // we have enough space. Just not at the end -> move it.
-            ::memcpy(d->array + n, d->array + d->begin, n * sizeof(void *));
-            d->begin = n;
-            d->end = n * 2;
+            e -= b;
+            ::memcpy(d->array, d->array + b, e * sizeof(void *));
+            d->begin = 0;
         } else {
-            realloc(grow(d->alloc + 1));
+            realloc(grow(d->alloc + n));
         }
     }
-    return d->array + d->end++;
+    d->end = e + n;
+    return d->array + e;
+}
+
+// ensures that enough space is available to append one element
+void **QListData::append()
+{
+    return append(1);
 }
 
 // ensures that enough space is available to append the list
@@ -209,7 +264,7 @@ void **QListData::append(const QListData& l)
     int n = l.d->end - l.d->begin;
     if (n) {
         if (e + n > d->alloc)
-            realloc(grow(e + l.d->end - l.d->begin));
+            realloc(grow(e + n));
         ::memcpy(d->array + d->end, l.d->array + l.d->begin, n*sizeof(void*));
         d->end += n;
     }
@@ -219,15 +274,7 @@ void **QListData::append(const QListData& l)
 // ensures that enough space is available to append the list
 void **QListData::append2(const QListData& l)
 {
-    Q_ASSERT(d->ref == 1);
-    int e = d->end;
-    int n = l.d->end - l.d->begin;
-    if (n) {
-        if (e + n > d->alloc)
-            realloc(grow(e + n));
-        d->end += n;
-    }
-    return d->array + e;
+    return append(l.d->end - l.d->begin);
 }
 
 void **QListData::prepend()
@@ -253,11 +300,11 @@ void **QListData::insert(int i)
     Q_ASSERT(d->ref == 1);
     if (i <= 0)
         return prepend();
-    if (i >= d->end - d->begin)
+    int size = d->end - d->begin;
+    if (i >= size)
         return append();
 
     bool leftward = false;
-    int size = d->end - d->begin;
 
     if (d->begin == 0) {
         if (d->end == d->alloc) {