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, 47 insertions, 4 deletions

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;
 }