QFileSystemWatcher: fix quadratic loop by porting away from QMutableListIterator

QMutableListIterator::remove() is linear, so called in a loop, the
loop potentially becomes quadratic.

Fix by porting to std::remove_if. In this case, since the old code
unconditionally detached, anyway, we use remove_copy_if to build a new
list. That's still more efficient than the old code, even if nothing
is removed. It also prepares the code for when Java-style iterators
will be deprecated.

Since the same code appears in two different functions, do an Extract
Method into a file-static function.

Lastly, restore NRVO for most compilers by returning the same object
from all return statements of the function.

Change-Id: I6909c6483d8f7acfd1bf381828f020038b04e431
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
 
 
 
 
 
 
 

1 files changed, 15 insertions, 18 deletions

diff --git a/src/corelib/io/qfilesystemwatcher.cpp b/src/corelib/io/qfilesystemwatcher.cpp
index 9b47b27f5c..e3e4433a6b 100644
--- a/src/corelib/io/qfilesystemwatcher.cpp
+++ b/src/corelib/io/qfilesystemwatcher.cpp
@@ -311,6 +311,17 @@ bool QFileSystemWatcher::addPath(const QString &path)
     return paths.isEmpty();
 }
 
+static QStringList empty_paths_pruned(const QStringList &paths)
+{
+    QStringList p;
+    p.reserve(paths.size());
+    const auto isEmpty = [](const QString &s) { return s.isEmpty(); };
+    std::remove_copy_if(paths.begin(), paths.end(),
+                        std::back_inserter(p),
+                        isEmpty);
+    return p;
+}
+
 /*!
     Adds each path in \a paths to the file system watcher. Paths are
     not added if they not exist, or if they are already being
@@ -338,18 +349,11 @@ QStringList QFileSystemWatcher::addPaths(const QStringList &paths)
 {
     Q_D(QFileSystemWatcher);
 
-    QStringList p = paths;
-    QMutableListIterator<QString> it(p);
-
-    while (it.hasNext()) {
-        const QString &path = it.next();
-        if (path.isEmpty())
-            it.remove();
-    }
+    QStringList p = empty_paths_pruned(paths);
 
     if (p.isEmpty()) {
         qWarning("QFileSystemWatcher::addPaths: list is empty");
-        return QStringList();
+        return p;
     }
 
     const auto selectEngine = [this, d]() -> QFileSystemWatcherEngine* {
@@ -421,18 +425,11 @@ QStringList QFileSystemWatcher::removePaths(const QStringList &paths)
 {
     Q_D(QFileSystemWatcher);
 
-    QStringList p = paths;
-    QMutableListIterator<QString> it(p);
-
-    while (it.hasNext()) {
-        const QString &path = it.next();
-        if (path.isEmpty())
-            it.remove();
-    }
+    QStringList p = empty_paths_pruned(paths);
 
     if (p.isEmpty()) {
         qWarning("QFileSystemWatcher::removePaths: list is empty");
-        return QStringList();
+        return p;
     }
 
     if (d->native)