From 4889269ff0fb37130b332863e82dd7c19564116c Mon Sep 17 00:00:00 2001
From: Lars Knoll <lars.knoll@theqtcompany.com>
Date: Wed, 18 Mar 2015 08:49:09 +0100
Subject: 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>
---
 src/corelib/json/qjsonarray.cpp  | 41 ++++++++++++++++++++++++++++++--
 src/corelib/json/qjsonobject.cpp | 51 ++++++++++++++++++++++++++++++++++++----
 2 files changed, 86 insertions(+), 6 deletions(-)

(limited to 'src')

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;
 }
 
diff --git a/src/corelib/json/qjsonobject.cpp b/src/corelib/json/qjsonobject.cpp
index 8b45dd196b..b83c8dd19a 100644
--- a/src/corelib/json/qjsonobject.cpp
+++ b/src/corelib/json/qjsonobject.cpp
@@ -197,11 +197,54 @@ QJsonObject &QJsonObject::operator =(const QJsonObject &other)
  */
 QJsonObject QJsonObject::fromVariantMap(const QVariantMap &map)
 {
-    // ### this is implemented the trivial way, not the most efficient way
-
     QJsonObject object;
-    for (QVariantMap::const_iterator it = map.constBegin(); it != map.constEnd(); ++it)
-        object.insert(it.key(), QJsonValue::fromVariant(it.value()));
+    if (map.isEmpty())
+        return object;
+
+    object.detach2(1024);
+
+    QVector<QJsonPrivate::offset> offsets;
+    QJsonPrivate::offset currentOffset;
+    currentOffset = sizeof(QJsonPrivate::Base);
+
+    // the map is already sorted, so we can simply append one entry after the other and
+    // write the offset table at the end
+    for (QVariantMap::const_iterator it = map.constBegin(); it != map.constEnd(); ++it) {
+        QString key = it.key();
+        QJsonValue val = QJsonValue::fromVariant(it.value());
+
+        bool latinOrIntValue;
+        int valueSize = QJsonPrivate::Value::requiredStorage(val, &latinOrIntValue);
+
+        bool latinKey = QJsonPrivate::useCompressed(key);
+        int valueOffset = sizeof(QJsonPrivate::Entry) + QJsonPrivate::qStringSize(key, latinKey);
+        int requiredSize = valueOffset + valueSize;
+
+        if (!object.detach2(requiredSize + sizeof(QJsonPrivate::offset))) // offset for the new index entry
+            return QJsonObject();
+
+        QJsonPrivate::Entry *e = reinterpret_cast<QJsonPrivate::Entry *>(reinterpret_cast<char *>(object.o) + currentOffset);
+        e->value.type = val.t;
+        e->value.latinKey = latinKey;
+        e->value.latinOrIntValue = latinOrIntValue;
+        e->value.value = QJsonPrivate::Value::valueToStore(val, (char *)e - (char *)object.o + valueOffset);
+        QJsonPrivate::copyString((char *)(e + 1), key, latinKey);
+        if (valueSize)
+            QJsonPrivate::Value::copyData(val, (char *)e + valueOffset, latinOrIntValue);
+
+        offsets << currentOffset;
+        currentOffset += requiredSize;
+        object.o->size = currentOffset;
+    }
+
+    // write table
+    object.o->tableOffset = currentOffset;
+    if (!object.detach2(sizeof(QJsonPrivate::offset)*offsets.size()))
+        return QJsonObject();
+    memcpy(object.o->table(), offsets.constData(), offsets.size()*sizeof(uint));
+    object.o->length = offsets.size();
+    object.o->size = currentOffset + sizeof(QJsonPrivate::offset)*offsets.size();
+
     return object;
 }
 
-- 
cgit v1.2.3