QStringBuilder: fix quadratic behavior in op+=

QByteArray and QString honor a reserve(n) faithfully, meaning that if
n > capacity(), then capacity() == n after the reserve() call.

This is expected behavior, and also what libstdc++'s std::vector does.

The problem is QStringBuilder's op+=, which calls reserve()
unconditionally to ensure capacity for its resize-after-append
magic. If a user builds up a string by repeatedly appending
string-builder expressions, these repeated minimal-progress reserve
calls destroy the string's natural geometric capacity growth, turning
it linear instead, and hence the whole construction becomes quadratic.

Fix by calling reserve() only when necessary, and for a maximum of
O(logN) times, N being the separate calls to QStringBuilder's op+=.

This guarantees amortized-linear runtime of string building again.

Need to insert an explicit detach() call in reserve()'s stead, lest a
detach() in the following data() would reset capacity() to size().

Copied a useful comment from the QByteArray case to the QString case.

[ChangeLog][QtCore][QStringBuilder] Fixed quadratic behavior when
repeatedly appending string-builder expressions (using operator+=) to
QString/QByteArray objects.

Pick-to: 6.3 6.2
Change-Id: I1c210a8d0026c227e55e5e30a46fb747660bb66e
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Anton Kudryavtsev <antkudr@mail.ru>

0 files changed, 0 insertions, 0 deletions