QString: fix quadratic behavior in QString::remove(QString)

Calling linear-complexity remove(int, int) in a loop is O(N²).

Fix by implementing a remove_if()-like algorithm which ensures each
character is written at most once, which is linear.

[ChangeLog][QtCore][QString] Fixed quadratic worst-case complexity of
remove(QString). The function now has linear complexity in all cases.

Change-Id: I12f70fbc83fb5da4a9aae4bd02f525d7657cc940
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
(cherry picked from commit 49e69827d2be045751ded48645904b4349115212)
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 24 insertions, 10 deletions

diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp
index 3e8e12a59c..c09beceefb 100644
--- a/src/corelib/text/qstring.cpp
+++ b/src/corelib/text/qstring.cpp
@@ -2862,16 +2862,30 @@ QString &QString::remove(int pos, int len)
 template<typename T>
 static void removeStringImpl(QString &s, const T &needle, Qt::CaseSensitivity cs)
 {
-    const int needleSize = needle.size();
-    if (needleSize) {
-        if (needleSize == 1) {
-            s.remove(needle.front(), cs);
-        } else {
-            int i = 0;
-            while ((i = s.indexOf(needle, i, cs)) != -1)
-                s.remove(i, needleSize);
-        }
-    }
+    const auto needleSize = needle.size();
+    if (!needleSize)
+        return;
+
+    // avoid detach if nothing to do:
+    int i = s.indexOf(needle, 0, cs);
+    if (i < 0)
+        return;
+
+    const auto beg = s.begin(); // detaches
+    auto dst = beg + i;
+    auto src = beg + i + needleSize;
+    const auto end = s.end();
+    // loop invariant: [beg, dst[ is partial result
+    //                 [src, end[ still to be checked for needles
+    while (src < end) {
+        const auto i = s.indexOf(needle, src - beg, cs);
+        const auto hit = i == -1 ? end : beg + i;
+        const auto skipped = hit - src;
+        memmove(dst, src, skipped * sizeof(QChar));
+        dst += skipped;
+        src = hit + needleSize;
+    }
+    s.truncate(dst - beg);
 }
 
 /*!