From 26c367b9b9e220056af3a47eced366d6d187a890 Mon Sep 17 00:00:00 2001 From: Oswald Buddenhagen Date: Thu, 18 Feb 2010 16:03:22 +0100 Subject: optimize qstring::simplified() - avoid detaching if the string is already simplified - avoid calling isSpace() multiple times on the same character Reviewed-by: joao --- src/corelib/tools/qstring.cpp | 82 ++++++++++++++++++++++++++++++-------- tests/auto/qstring/tst_qstring.cpp | 50 +++++++++++++++++++---- 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(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(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(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("full" ); + QTest::addColumn("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() -- cgit v0.12