From 26fec96a813b8d1c4955b394794c66e5e830e4c4 Mon Sep 17 00:00:00 2001
From: Ahmad Samir <a.samirh78@gmail.com>
Date: Tue, 17 Jan 2023 14:13:38 +0200
Subject: QString, QByteArray: don't detach in removeIf/erase/eraseif()

If the object is shared, instead of detaching, copy characters from
"this" to a new object except for the chacters that would be erased,
this is more efficient than detaching (which would copy the whole data
then erase).

- Extend tst_QString::removeIf() to catch a corner-case (that I saw
  with tst_QByteArray::removeIf()).

- Add q_uninitialized_remove_copy_if, which works like
  std::remove_copy_if but for uninitialized memory like
  q_uninitialized_relocate_n (but copies rather than relocates/moves).
  With the same static_assert from q_relocate_overlap_n that the type
  destructor is non-throwing.

Added q_uninitialized_remove_copy_if in this commit rather than a
separate one so that it's unittested by its usage in eraseIf().

[ChangeLog][QtCore][QString, QByteArray] Removing characters from a
currently shared string or byte array is now done more efficiently

Task-number: QTBUG-106181
Task-number: QTBUG-106183
Change-Id: Icc0ed31633cef71d482b97e0d2d20d763163d383
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
---
 src/corelib/text/qbytearray.h | 17 ++++++++++++++---
 src/corelib/text/qstring.h    | 17 ++++++++++++++---
 2 files changed, 28 insertions(+), 6 deletions(-)

(limited to 'src/corelib/text')

diff --git a/src/corelib/text/qbytearray.h b/src/corelib/text/qbytearray.h
index c2e456fc29..2f7070d539 100644
--- a/src/corelib/text/qbytearray.h
+++ b/src/corelib/text/qbytearray.h
@@ -247,7 +247,7 @@ public:
     template <typename Predicate>
     QByteArray &removeIf(Predicate pred)
     {
-        QtPrivate::sequential_erase_if(*this, pred);
+        removeIf_helper(pred);
         return *this;
     }
 
@@ -478,9 +478,20 @@ private:
     static QByteArray trimmed_helper(QByteArray &a);
     static QByteArray simplified_helper(const QByteArray &a);
     static QByteArray simplified_helper(QByteArray &a);
+    template <typename Predicate>
+    qsizetype removeIf_helper(Predicate pred)
+    {
+        const qsizetype result = d->eraseIf(pred);
+        if (result > 0)
+            d.data()[d.size] = '\0';
+        return result;
+    }
 
     friend class QString;
     friend Q_CORE_EXPORT QByteArray qUncompress(const uchar *data, qsizetype nbytes);
+
+    template <typename T> friend qsizetype erase(QByteArray &ba, const T &t);
+    template <typename Predicate> friend qsizetype erase_if(QByteArray &ba, Predicate pred);
 };
 
 Q_DECLARE_OPERATORS_FOR_FLAGS(QByteArray::Base64Options)
@@ -662,13 +673,13 @@ Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray::FromBase64Resu
 template <typename T>
 qsizetype erase(QByteArray &ba, const T &t)
 {
-    return QtPrivate::sequential_erase(ba, t);
+    return ba.removeIf_helper([&t](const auto &e) { return t == e; });
 }
 
 template <typename Predicate>
 qsizetype erase_if(QByteArray &ba, Predicate pred)
 {
-    return QtPrivate::sequential_erase_if(ba, pred);
+    return ba.removeIf_helper(pred);
 }
 
 //
diff --git a/src/corelib/text/qstring.h b/src/corelib/text/qstring.h
index 7063ac7f82..d4f9e6bc63 100644
--- a/src/corelib/text/qstring.h
+++ b/src/corelib/text/qstring.h
@@ -406,9 +406,10 @@ public:
     template <typename Predicate>
     QString &removeIf(Predicate pred)
     {
-        QtPrivate::sequential_erase_if(*this, pred);
+        removeIf_helper(pred);
         return *this;
     }
+
     QString &replace(qsizetype i, qsizetype len, QChar after);
     QString &replace(qsizetype i, qsizetype len, const QChar *s, qsizetype slen);
     QString &replace(qsizetype i, qsizetype len, const QString &after);
@@ -865,10 +866,20 @@ private:
     static qsizetype toUcs4_helper(const char16_t *uc, qsizetype length, char32_t *out);
     static qlonglong toIntegral_helper(QStringView string, bool *ok, int base);
     static qulonglong toIntegral_helper(QStringView string, bool *ok, uint base);
+    template <typename Predicate>
+    qsizetype removeIf_helper(Predicate pred)
+    {
+        const qsizetype result = d->eraseIf(pred);
+        if (result > 0)
+            d.data()[d.size] = u'\0';
+        return result;
+    }
 
     friend class QStringView;
     friend class QByteArray;
     friend struct QAbstractConcatenable;
+    template <typename T> friend qsizetype erase(QString &s, const T &t);
+    template <typename Predicate> friend qsizetype erase_if(QString &s, Predicate pred);
 
     template <typename T> static
     T toIntegral_helper(QStringView string, bool *ok, int base)
@@ -1345,13 +1356,13 @@ QString QLatin1StringView::arg(Args &&...args) const
 template <typename T>
 qsizetype erase(QString &s, const T &t)
 {
-    return QtPrivate::sequential_erase(s, t);
+    return s.removeIf_helper([&t](const auto &e) { return t == e; });
 }
 
 template <typename Predicate>
 qsizetype erase_if(QString &s, Predicate pred)
 {
-    return QtPrivate::sequential_erase_if(s, pred);
+    return s.removeIf_helper(pred);
 }
 
 namespace Qt {
-- 
cgit v1.2.3