optimize qstring::simplified()

- avoid detaching if the string is already simplified
- avoid calling isSpace() multiple times on the same character

Reviewed-by: joao

2 files changed, 109 insertions, 23 deletions

diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index cce313b..ac1bee7 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -3995,24 +3995,74 @@ QString QString::simplified() const
 {
     if (d->size == 0)
         return *this;
-    QString result(d->size, Qt::Uninitialized);
-    const QChar *from = (const QChar*) d->data;
-    const QChar *fromend = (const QChar*) from+d->size;
-    int outc=0;
-    QChar *to   = (QChar*) result.d->data;
-    for (;;) {
-        while (from!=fromend && from->isSpace())
-            from++;
-        while (from!=fromend && !from->isSpace())
-            to[outc++] = *from++;
-        if (from!=fromend)
-            to[outc++] = QLatin1Char(' ');
-        else
+
+    const QChar * const start = reinterpret_cast<QChar *>(d->data);
+    const QChar *from = start;
+    const QChar *fromEnd = start + d->size;
+    forever {
+        QChar ch = *from;
+        if (!ch.isSpace())
+            break;
+        if (++from == fromEnd) {
+            // All-whitespace string
+            shared_empty.ref.ref();
+            return QString(&shared_empty, 0);
+        }
+    }
+    // This loop needs no underflow check, as we already determined that
+    // the string contains non-whitespace. If the string has exactly one
+    // non-whitespace, it will be checked twice - we can live with that.
+    while (fromEnd[-1].isSpace())
+        fromEnd--;
+    // The rest of the function depends on the fact that we already know
+    // that the last character in the source is no whitespace.
+    const QChar *copyFrom = from;
+    int copyCount;
+    forever {
+        if (++from == fromEnd) {
+            // Only leading and/or trailing whitespace, if any at all
+            return mid(copyFrom - start, from - copyFrom);
+        }
+        QChar ch = *from;
+        if (!ch.isSpace())
+            continue;
+        if (ch != QLatin1Char(' ')) {
+            copyCount = from - copyFrom;
             break;
+        }
+        ch = *++from;
+        if (ch.isSpace()) {
+            copyCount = from - copyFrom - 1;
+            break;
+        }
+    }
+    // 'from' now points at the non-trailing whitespace which made the
+    // string not simplified in the first place. 'copyCount' is the number
+    // of already simplified characters - at least one, obviously -
+    // without a trailing space.
+    QString result((fromEnd - from) + copyCount, Qt::Uninitialized);
+    QChar *to = reinterpret_cast<QChar *>(result.d->data);
+    ::memcpy(to, copyFrom, copyCount * 2);
+    to += copyCount;
+    fromEnd--;
+    QChar ch;
+    forever {
+        *to++ = QLatin1Char(' ');
+        do {
+            ch = *++from;
+        } while (ch.isSpace());
+        if (from == fromEnd)
+            break;
+        do {
+            *to++ = ch;
+            ch = *++from;
+            if (from == fromEnd)
+                goto done;
+        } while (!ch.isSpace());
     }
-    if (outc > 0 && to[outc-1] == QLatin1Char(' '))
-        outc--;
-    result.truncate(outc);
+  done:
+    *to++ = ch;
+    result.truncate(to - reinterpret_cast<QChar *>(result.d->data));
     return result;
 }
 
diff --git a/tests/auto/qstring/tst_qstring.cpp b/tests/auto/qstring/tst_qstring.cpp
index c9b3436..9c9524a 100644
--- a/tests/auto/qstring/tst_qstring.cpp
+++ b/tests/auto/qstring/tst_qstring.cpp
@@ -120,6 +120,7 @@ private slots:
     void operator_eqeq_nullstring();
     void operator_smaller();
     void insert();
+    void simplified_data();
     void simplified();
     void trimmed();
     void toLower();
@@ -1592,16 +1593,51 @@ void tst_QString::trimmed()
     QCOMPARE(a.trimmed(),(QString)"a");
 }
 
+void tst_QString::simplified_data()
+{
+    QTest::addColumn<QString>("full" );
+    QTest::addColumn<QString>("simple" );
+
+    QTest::newRow("null") << QString() << QString();
+    QTest::newRow("empty") << "" << "";
+    QTest::newRow("one char") << "a" << "a";
+    QTest::newRow("one word") << "foo" << "foo";
+    QTest::newRow("chars trivial") << "a b" << "a b";
+    QTest::newRow("words trivial") << "foo bar" << "foo bar";
+    QTest::newRow("allspace") << "  \t\v " << "";
+    QTest::newRow("char trailing") << "a " << "a";
+    QTest::newRow("char trailing tab") << "a\t" << "a";
+    QTest::newRow("char multitrailing") << "a   " << "a";
+    QTest::newRow("char multitrailing tab") << "a   \t" << "a";
+    QTest::newRow("char leading") << " a" << "a";
+    QTest::newRow("char leading tab") << "\ta" << "a";
+    QTest::newRow("char multileading") << "   a" << "a";
+    QTest::newRow("char multileading tab") << "\t   a" << "a";
+    QTest::newRow("chars apart") << "a  b" << "a b";
+    QTest::newRow("words apart") << "foo  bar" << "foo bar";
+    QTest::newRow("enclosed word") << "   foo \t " << "foo";
+    QTest::newRow("enclosed chars apart") << " a   b " << "a b";
+    QTest::newRow("enclosed words apart") << " foo   bar " << "foo bar";
+    QTest::newRow("chars apart posttab") << "a \tb" << "a b";
+    QTest::newRow("chars apart pretab") << "a\t b" << "a b";
+    QTest::newRow("many words") << "  just some    random\ttext here" << "just some random text here";
+}
+
 void tst_QString::simplified()
 {
-    QString j;
-    j.simplified();
+    QFETCH(QString, full);
+    QFETCH(QString, simple);
 
-    QString a;
-    a = "a ";
-    QCOMPARE(a.simplified(),(QString)"a");
-    a=" a   b ";
-    QCOMPARE(a.simplified(),(QString)"a b");
+    QString result = full.simplified();
+    if (simple.isNull()) {
+        QVERIFY2(result.isNull(), qPrintable("'" + full + "' did not yield null: " + result));
+    } else if (simple.isEmpty()) {
+        QVERIFY2(result.isEmpty() && !result.isNull(), qPrintable("'" + full + "' did not yield empty: " + result));
+    } else {
+        QCOMPARE(result, simple);
+        if (full == simple)
+            QVERIFY(result.isSharedWith(full));
+    }
 }
 
 void tst_QString::insert()