Introduce a new class QStringBuilder to speed up the creation of

QString objects from smaller chunks.

The QStringBuilder class:

QStringBuilder uses expression templates (using the '%' operator)
to postpone any actual concatenation until it is assigned to an
actual QString. At that time it knows the exact sizes of all chunks,
can compute the required space, allocates once a QString of
appriopriate size and then copies over the chunk data one-by-one.

In addition, QLatin1Literal is a drop-in replacement for QLatin1String
(which we can't change for compatibility reasons) that knows its
size, therefore saving a few cycles when computing the size of the
resulting string.

Some further saved cycles stem from inlining and reduced reference
counting logic (the QString created from a QStringBuilder has typically
ref count equal to 1, while QString::append() needs an extra test)

Minor changes to the existing QString class:

- Introduce QString constructor to create an uninitialized QString of a given size.
This particular constructor is used by QStringBuilder class.

- Introduce a QT_USE_FAST_CONCATENATION macro to disable the existing
overloads of operator+() and helps finding the places where they are used in code.

- Introduce QT_USE_FAST_OPERATOR_PLUS.  This also disables the existing
overloads of operator+() and creates a new templated operator+() with
identical implementation of operator%().  This allows code that is compilable
QT_CAST_{TO,FROM}_ASCII to use QStringBuilder almost transparently. The only
case that is not covered is creating objects like QUrl that are implicitly
constructible from a QString from a QStringBuilder result.  This needs to be
converted explicitly to a QString first, e.g. by using QUrl
url(QString(QLatin1String("http://") + hostName));

Reviewed-by: MariusSO

5 files changed, 373 insertions, 3 deletions

diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index 29509c5..c64e1d6 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -944,6 +944,23 @@ QString::QString(int size, QChar ch)
     }
 }
 
+/*!
+    Constructs a string of the given \a size without initializing the
+    characters. This is only used in \c QStringBuilder::toString().
+
+    \internal
+*/
+
+QString::QString(int size, Uninitialized)
+{
+    d = (Data*) qMalloc(sizeof(Data)+size*sizeof(QChar));
+    d->ref = 1;
+    d->alloc = d->size = size;
+    d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
+    d->data = d->array;
+    d->array[size] = '\0';
+}
+
 /*! \fn QString::QString(const QLatin1String &str)
 
     Constructs a copy of the Latin-1 string \a str.
diff --git a/src/corelib/tools/qstring.h b/src/corelib/tools/qstring.h
index 69c4f2f..7c0d6a3 100644
--- a/src/corelib/tools/qstring.h
+++ b/src/corelib/tools/qstring.h
@@ -579,6 +579,9 @@ public:
     bool isSimpleText() const { if (!d->clean) updateProperties(); return d->simpletext; }
     bool isRightToLeft() const { if (!d->clean) updateProperties(); return d->righttoleft; }
 
+    struct Uninitialized {};
+    QString(int size, Uninitialized);
+
 private:
 #if defined(QT_NO_CAST_FROM_ASCII) && !defined(Q_NO_DECLARED_NOT_DEFINED)
     QString &operator+=(const char *s);
@@ -1001,13 +1004,15 @@ inline int QByteArray::findRev(const QString &s, int from) const
 #  endif // QT3_SUPPORT
 #endif // QT_NO_CAST_TO_ASCII
 
+#ifndef QT_USE_FAST_OPERATOR_PLUS
+# ifndef QT_USE_FAST_CONCATENATION
 inline const QString operator+(const QString &s1, const QString &s2)
 { QString t(s1); t += s2; return t; }
 inline const QString operator+(const QString &s1, QChar s2)
 { QString t(s1); t += s2; return t; }
 inline const QString operator+(QChar s1, const QString &s2)
 { QString t(s1); t += s2; return t; }
-#ifndef QT_NO_CAST_FROM_ASCII
+#  ifndef QT_NO_CAST_FROM_ASCII
 inline QT_ASCII_CAST_WARN const QString operator+(const QString &s1, const char *s2)
 { QString t(s1); t += QString::fromAscii(s2); return t; }
 inline QT_ASCII_CAST_WARN const QString operator+(const char *s1, const QString &s2)
@@ -1020,7 +1025,9 @@ inline QT_ASCII_CAST_WARN const QString operator+(const QByteArray &ba, const QS
 { QString t = QString::fromAscii(ba.constData(), qstrnlen(ba.constData(), ba.size())); t += s; return t; }
 inline QT_ASCII_CAST_WARN const QString operator+(const QString &s, const QByteArray &ba)
 { QString t(s); t += QString::fromAscii(ba.constData(), qstrnlen(ba.constData(), ba.size())); return t; }
-#endif
+#  endif // QT_NO_CAST_FROM_ASCII
+# endif // QT_USE_FAST_CONCATENATION
+#endif // QT_USE_FAST_OPERATOR_PLUS
 
 #ifndef QT_NO_STL
 inline std::string QString::toStdString() const
@@ -1229,6 +1236,8 @@ inline int QStringRef::localeAwareCompare(const QStringRef &s1, const QStringRef
 
 QT_END_NAMESPACE
 
-QT_END_HEADER
+#ifdef QT_USE_FAST_CONCATENATION
+#include <QtCore/qstringbuilder.h>
+#endif
 
 #endif // QSTRING_H
diff --git a/src/corelib/tools/qstringbuilder.cpp b/src/corelib/tools/qstringbuilder.cpp
new file mode 100644
index 0000000..b807a89
--- /dev/null
+++ b/src/corelib/tools/qstringbuilder.cpp
@@ -0,0 +1,135 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial Usage
+** Licensees holding valid Qt Commercial licenses may use this file in
+** accordance with the Qt Commercial License Agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Nokia.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qstringbuilder.h"
+
+/*!
+    \class QLatin1Literal
+    \reentrant
+    \since 4.6
+
+    \brief The QLatin1Literal class provides a thin wrapper around string
+    literals used in source code.
+
+    \ingroup tools
+    \ingroup shared
+    \ingroup text
+    \mainclass
+
+    Unlike \c QLatin1String, a \c QLatin1Literal can retrieve its size
+    without iterating over the literal.
+
+    The main use of \c QLatin1Literal is in conjunction with \c QStringBuilder
+    to reduce the number of reallocations needed to build up a string from
+    smaller chunks.
+
+    \sa QStringBuilder, QLatin1String, QString, QStringRef
+*/
+
+/*! \fn QLatin1Literal::QLatin1Literal(const char(&string)[])
+ 
+    Constructs a new literal from the given \a string.
+*/
+
+/*! \fn int QLatin1Literal::size() const
+ 
+    Returns the number of characters in the literal \i{excluding} the trailing
+    NUL char.
+*/
+
+/*! \fn char *QLatin1Literal::data() const
+ 
+    Returns a pointer to the first character of the string literal.
+    The string literal is terminated by a NUL character.
+*/
+
+/*! \fn QLatin1Literal::operator QString() const
+ 
+    Converts the \c QLatin1Literal into a \c QString object.
+*/
+
+
+
+/*!
+    \class QStringBuilder
+    \reentrant
+    \since 4.6
+
+    \brief QStringBuilder is a template class that provides a facility to build
+    up QStrings from smaller chunks.
+
+    \ingroup tools
+    \ingroup shared
+    \ingroup text
+    \mainclass
+
+    When creating strings from smaller chunks, typically \c QString::operator+()
+    is used, resulting in \i{n - 1} reallocations when operating on \i{n} chunks.
+
+    QStringBuilder uses expression templates to collect the individual parts,
+    compute the total size, allocate memory for the resulting QString object,
+    and copy the contents of the chunks into the result.
+
+    The QStringBuilder class is not to be used explicitly in user code.
+    Instances of the class are created as return values of the operator%()
+    function, acting on objects of type \c QString, \c QLatin1String,
+    \c QLatin1Literal, \c \QStringRef, \c QChar,
+    \c QLatin1Char, and \c char.
+
+    Concatenating strings with operator%() generally yields better
+    performance then using \c QString::operator+() on the same chunks
+    if there are three or more of them, and performs equally well in other
+    cases.
+
+    \sa QLatin1Literal, QString
+*/
+
+/* !fn template <class A, class B> QStringBuilder<A, B> operator%(const A &a, const B &b)
+
+    Returns a \c QStringBuilder object that is converted to a QString object
+    when assigned to a variable of QString type or passed to a function that
+    takes a QString parameter.
+
+    This function is usable with arguments of type \c QString,
+    \c QLatin1String, \c QLatin1Literal, \c QStringRef, 
+    \c QChar, \c QLatin1Char, and \c char.
+*/
+
diff --git a/src/corelib/tools/qstringbuilder.h b/src/corelib/tools/qstringbuilder.h
new file mode 100644
index 0000000..1e67b7d
--- /dev/null
+++ b/src/corelib/tools/qstringbuilder.h
@@ -0,0 +1,207 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial Usage
+** Licensees holding valid Qt Commercial licenses may use this file in
+** accordance with the Qt Commercial License Agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Nokia.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QSTRINGBUILDER_H
+#define QSTRINGBUILDER_H
+
+#include <QtCore/qstring.h>
+
+#include <string.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Core)
+
+// ### Qt 5: merge with QLatin1String
+class QLatin1Literal
+{
+public:
+    template <int N>
+    QLatin1Literal(const char (&str)[N]) : m_size(N - 1), m_data(str) {}
+
+    inline int size() const { return m_size; }
+    inline const char *data() const { return m_data; }
+
+private:
+    const int m_size;
+    const char *m_data;
+};
+
+
+template <typename T> class QConcatenable {};
+
+template <typename A, typename B>
+class QStringBuilder
+{
+public:
+    QStringBuilder(const A &a_, const B &b_) : a(a_), b(b_) {}
+
+    operator QString() const
+    {
+        QString s(QConcatenable< QStringBuilder<A, B> >::size(*this),
+            QString::Uninitialized());
+        
+        QChar *d = s.data();
+        QConcatenable< QStringBuilder<A, B> >::appendTo(*this, d);
+        return s;
+    }
+    QByteArray toLatin1() const { return QString(*this).toLatin1(); }
+
+    const A &a;
+    const B &b;
+};
+
+
+template <> struct QConcatenable<char>
+{
+    typedef char type;
+    static int size(const char) { return 1; }
+    static inline void appendTo(const char c, QChar *&out)
+    {
+        *out++ = QLatin1Char(c);
+    }
+};
+
+template <> struct QConcatenable<QLatin1Char>
+{
+    typedef QLatin1Char type;
+    static int size(const QLatin1Char) { return 1; }
+    static inline void appendTo(const QLatin1Char c, QChar *&out)
+    {
+        *out++ = c;
+    }
+};
+
+template <> struct QConcatenable<QChar>
+{
+    typedef QChar type;
+    static int size(const QChar) { return 1; }
+    static inline void appendTo(const QChar c, QChar *&out)
+    {
+        *out++ = c;
+    }
+};
+
+template <> struct QConcatenable<QLatin1String>
+{
+    typedef QLatin1String type;
+    static int size(const QLatin1String &a) { return qstrlen(a.latin1()); }
+    static inline void appendTo(const QLatin1String &a, QChar *&out)
+    {
+        for (const char *s = a.latin1(); *s; )
+            *out++ = QLatin1Char(*s++);
+    }
+
+};
+
+template <> struct QConcatenable<QLatin1Literal>
+{
+    typedef QLatin1Literal type;
+    static int size(const QLatin1Literal &a) { return a.size(); }
+    static inline void appendTo(const QLatin1Literal &a, QChar *&out)
+    {
+        for (const char *s = a.data(); *s; )
+            *out++ = QLatin1Char(*s++);
+    }
+};
+
+template <> struct QConcatenable<QString>
+{
+    typedef QString type;
+    static int size(const QString &a) { return a.size(); }
+    static inline void appendTo(const QString &a, QChar *&out)
+    {
+        const int n = a.size();
+        memcpy(out, (char*)a.constData(), sizeof(QChar) * n);
+        out += n; 
+    }
+};
+
+template <> struct QConcatenable<QStringRef>
+{
+    typedef QStringRef type;
+    static int size(const QStringRef &a) { return a.size(); }
+    static inline void appendTo(QStringRef a, QChar *&out)
+    {
+        const int n = a.size();
+        memcpy(out, (char*)a.constData(), sizeof(QChar) * n);
+        out += n; 
+    }
+};
+
+template <typename A, typename B>
+struct QConcatenable< QStringBuilder<A, B> >
+{
+    typedef QStringBuilder<A, B> type;
+    static int size(const type &p) 
+    {
+        return QConcatenable<A>::size(p.a) + QConcatenable<B>::size(p.b);
+    }
+    static inline void appendTo(const QStringBuilder<A, B> &p, QChar *&out)
+    {
+        QConcatenable<A>::appendTo(p.a, out);
+        QConcatenable<B>::appendTo(p.b, out);
+    }
+};
+
+template <typename A, typename B>
+QStringBuilder<typename QConcatenable<A>::type, typename QConcatenable<B>::type>
+operator%(const A &a, const B &b)
+{
+   return QStringBuilder<A, B>(a, b);
+}
+
+#ifdef QT_USE_FAST_OPERATOR_PLUS
+template <typename A, typename B>
+QStringBuilder<typename QConcatenable<A>::type, typename QConcatenable<B>::type>
+operator+(const A &a, const B &b)
+{
+   return QStringBuilder<A, B>(a, b);
+}
+#endif
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif // QSTRINGBUILDER_H
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index 90287cb..aea0c6c 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -32,6 +32,7 @@ HEADERS +=  \
         tools/qsize.h \
 	tools/qstack.h \
 	tools/qstring.h \
+	tools/qstringbuilder.h \
 	tools/qstringlist.h \
 	tools/qstringmatcher.h \
 	tools/qtextboundaryfinder.h \
@@ -62,6 +63,7 @@ SOURCES += \
 	tools/qsharedpointer.cpp \
         tools/qsize.cpp \
 	tools/qstring.cpp \
+	tools/qstringbuilder.cpp \
 	tools/qstringlist.cpp \
 	tools/qtextboundaryfinder.cpp \
 	tools/qtimeline.cpp \