Speed up QSortFilterProxyModel filtering

Speed up the QSortFilterProxyModel filtering by only updating the
source_to_proxy entries which are really changed - When proxy intervals
are added or removed, it is not needed to update the proxy_to_source
indexes which were not touched.

Change-Id: I35459ff1b04f4610ec74f4b01d58a71832a9ae22
Reviewed-by: David Faure <david.faure@kdab.com>

3 files changed, 113 insertions, 8 deletions

diff --git a/src/corelib/itemmodels/qsortfilterproxymodel.cpp b/src/corelib/itemmodels/qsortfilterproxymodel.cpp
index a620e25f13..6ed4c942d8 100644
--- a/src/corelib/itemmodels/qsortfilterproxymodel.cpp
+++ b/src/corelib/itemmodels/qsortfilterproxymodel.cpp
@@ -403,8 +403,8 @@ public:
         QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
         int proxy_start, int proxy_end, const QModelIndex &proxy_parent,
         Qt::Orientation orient, bool emit_signal = true);
-    void build_source_to_proxy_mapping(
-        const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy) const;
+    static inline void build_source_to_proxy_mapping(
+        const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy, int start = 0);
     void source_items_inserted(const QModelIndex &source_parent,
                                int start, int end, Qt::Orientation orient);
     void source_items_about_to_be_removed(const QModelIndex &source_parent,
@@ -798,9 +798,11 @@ void QSortFilterProxyModelPrivate::remove_proxy_interval(
     }
 
     // Remove items from proxy-to-source mapping
+    for (int i = proxy_start; i <= proxy_end; ++i)
+        source_to_proxy[proxy_to_source.at(i)] = -1;
     proxy_to_source.remove(proxy_start, proxy_end - proxy_start + 1);
 
-    build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
+    build_source_to_proxy_mapping(proxy_to_source, source_to_proxy, proxy_start);
 
     if (emit_signal) {
         if (orient == Qt::Vertical)
@@ -926,7 +928,7 @@ void QSortFilterProxyModelPrivate::insert_source_items(
         for (int i = 0; i < source_items.size(); ++i)
             proxy_to_source.insert(proxy_start + i, source_items.at(i));
 
-        build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
+        build_source_to_proxy_mapping(proxy_to_source, source_to_proxy, proxy_start);
 
         if (emit_signal) {
             if (orient == Qt::Vertical)
@@ -1208,11 +1210,12 @@ void QSortFilterProxyModelPrivate::proxy_item_range(
   \internal
 */
 void QSortFilterProxyModelPrivate::build_source_to_proxy_mapping(
-    const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy) const
+    const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy, int start)
 {
-    source_to_proxy.fill(-1);
-    int proxy_count = proxy_to_source.size();
-    for (int i = 0; i < proxy_count; ++i)
+    if (start == 0)
+        source_to_proxy.fill(-1);
+    const int proxy_count = proxy_to_source.size();
+    for (int i = start; i < proxy_count; ++i)
         source_to_proxy[proxy_to_source.at(i)] = i;
 }
 
diff --git a/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.cpp b/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.cpp
index a01f5bcf46..6f032d2696 100644
--- a/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.cpp
+++ b/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.cpp
@@ -4940,6 +4940,107 @@ void tst_QSortFilterProxyModel::filterAndInsertRow()
     }
 }
 
+
+namespace CheckFilteredIndexes {
+class TableModel : public QAbstractTableModel
+{
+    Q_OBJECT
+public:
+    static const int s_rowCount = 1000;
+    static const int s_columnCount = 1;
+    TableModel(QObject *parent = nullptr) : QAbstractTableModel(parent)
+    {
+        m_data.resize(s_rowCount);
+        for (int r = 0; r < s_rowCount; ++r) {
+            auto &curRow = m_data[r];
+            curRow.resize(s_columnCount);
+            for (int c = 0; c < s_columnCount; ++c) {
+                curRow[c] = QVariant(QString::number(r % 100) +
+                                     QLatin1Char('_') + QString::number(r / 100) +
+                                     QString::number(c));
+            }
+        }
+    }
+    int rowCount(const QModelIndex &parent = QModelIndex()) const override
+    {
+        return parent.isValid() ? 0 : s_rowCount;
+    }
+    int columnCount(const QModelIndex &parent = QModelIndex()) const override
+    {
+        return parent.isValid() ? 0 : s_columnCount;
+    }
+    QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const override
+    {
+        if (role != Qt::DisplayRole || !index.isValid())
+            return QVariant();
+        return m_data[index.row()][index.column()];
+    }
+    QVector<QVector<QVariant>> m_data;
+};
+
+class SortFilterProxyModel final : public QSortFilterProxyModel
+{
+    Q_OBJECT
+public:
+    using QSortFilterProxyModel::QSortFilterProxyModel;
+    using QSortFilterProxyModel::invalidateFilter;
+
+    void setSourceModel(QAbstractItemModel *m) override
+    {
+        m_sourceModel = qobject_cast<TableModel*>(m);
+        QSortFilterProxyModel::setSourceModel(m);
+    }
+    bool lessThan(const QModelIndex &left, const QModelIndex &right) const override
+    {
+        if (!left.isValid() || !right.isValid() || !m_sourceModel)
+            return QSortFilterProxyModel::lessThan(left, right);
+        return m_sourceModel->m_data.at(left.row()).at(left.column()).toString() <
+               m_sourceModel->m_data.at(right.row()).at(right.column()).toString();
+    }
+    bool filterAcceptsRow(int source_row, const QModelIndex &source_parent) const override
+    {
+        if (m_filteredRows == 0 || source_parent.isValid())
+            return true;
+        return (source_row % m_filteredRows) != 0;
+    }
+
+    TableModel *m_sourceModel = nullptr;
+    int m_filteredRows = 0;
+    bool m_bInverseFilter = false;
+};
+}
+
+void tst_QSortFilterProxyModel::checkFilteredIndexes()
+{
+    using namespace CheckFilteredIndexes;
+    auto checkIndexes = [](const SortFilterProxyModel &s)
+    {
+        for (int r = 0; r < s.rowCount(); ++r) {
+            const QModelIndex idxSFPM = s.index(r, 0);
+            const QModelIndex idxTM = s.mapToSource(idxSFPM);
+            QVERIFY(idxTM.isValid());
+            QVERIFY(idxTM.row() % s.m_filteredRows != 0);
+        }
+    };
+
+    TableModel m;
+    SortFilterProxyModel s;
+    s.m_filteredRows = 2; // every 2nd row is filtered
+    s.setSourceModel(&m);
+    s.sort(0);
+
+    s.invalidateFilter();
+    checkIndexes(s);
+
+    s.m_filteredRows = 5; // every 5th row is filtered
+    s.invalidateFilter();
+    checkIndexes(s);
+
+    s.m_filteredRows = 3; // every 3rd row is filtered
+    s.invalidateFilter();
+    checkIndexes(s);
+}
+
 void tst_QSortFilterProxyModel::invalidateColumnsOrRowsFilter()
 {
     class FilterProxy : public QSortFilterProxyModel
diff --git a/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.h b/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.h
index 703f168cdb..68c00318fe 100644
--- a/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.h
+++ b/tests/auto/corelib/itemmodels/qsortfilterproxymodel_common/tst_qsortfilterproxymodel.h
@@ -159,6 +159,7 @@ private slots:
     void removeIntervals_data();
     void removeIntervals();
 
+    void checkFilteredIndexes();
     void invalidateColumnsOrRowsFilter();
 
 protected: