Fix quadratic behavior when converting from QVariant

The old code called insert for each item, leading to constant
reallocation of the data structure. Instead rely on the fact
that a QVariantMap (as well as the variant list) is sorted, so
we can convert to the QJson data structure in one go without
lots of reallocations.

Task-number: QTBUG-44737
Change-Id: Id2d38d278fb9afa5e062c7353b4d4215bdfb993c
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 39 insertions, 2 deletions

diff --git a/src/corelib/json/qjsonarray.cpp b/src/corelib/json/qjsonarray.cpp
index e8d54b5b87..dc8851e8e7 100644
--- a/src/corelib/json/qjsonarray.cpp
+++ b/src/corelib/json/qjsonarray.cpp
@@ -256,8 +256,45 @@ QJsonArray QJsonArray::fromStringList(const QStringList &list)
 QJsonArray QJsonArray::fromVariantList(const QVariantList &list)
 {
     QJsonArray array;
-    for (QVariantList::const_iterator it = list.constBegin(); it != list.constEnd(); ++it)
-        array.append(QJsonValue::fromVariant(*it));
+    if (list.isEmpty())
+        return array;
+
+    array.detach2(1024);
+
+    QVector<QJsonPrivate::Value> values;
+    values.resize(list.size());
+    QJsonPrivate::Value *valueData = values.data();
+    uint currentOffset = sizeof(QJsonPrivate::Base);
+
+    for (int i = 0; i < list.size(); ++i) {
+        QJsonValue val = QJsonValue::fromVariant(list.at(i));
+
+        bool latinOrIntValue;
+        int valueSize = QJsonPrivate::Value::requiredStorage(val, &latinOrIntValue);
+
+        if (!array.detach2(valueSize))
+            return QJsonArray();
+
+        QJsonPrivate::Value *v = valueData + i;
+        v->type = (val.t == QJsonValue::Undefined ? QJsonValue::Null : val.t);
+        v->latinOrIntValue = latinOrIntValue;
+        v->latinKey = false;
+        v->value = QJsonPrivate::Value::valueToStore(val, currentOffset);
+        if (valueSize)
+            QJsonPrivate::Value::copyData(val, (char *)array.a + currentOffset, latinOrIntValue);
+
+        currentOffset += valueSize;
+        array.a->size = currentOffset;
+    }
+
+    // write table
+    array.a->tableOffset = currentOffset;
+    if (!array.detach2(sizeof(QJsonPrivate::offset)*values.size()))
+        return QJsonArray();
+    memcpy(array.a->table(), values.constData(), values.size()*sizeof(uint));
+    array.a->length = values.size();
+    array.a->size = currentOffset + sizeof(QJsonPrivate::offset)*values.size();
+
     return array;
 }