From d18eb260d70b75376411fe3f69da82bf46fb503f Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Thu, 27 Sep 2012 11:36:23 +0200 Subject: Use the layout change hint to speed up QItemSelectionModel. The testcase in the bug report takes 370035 ms to sort the rows with Qt 4, and 5646 ms in Qt 5 (when using the extra hints to layout*Changed). That's an improvement of more than 98%. Task-number: QTBUG-17732 Change-Id: If78f972d80c501e0cb39078228086c4f4ac8a65b Reviewed-by: Marc Mutz --- src/corelib/itemmodels/qitemselectionmodel.cpp | 128 ++++++++++++++++++++----- src/corelib/itemmodels/qitemselectionmodel.h | 4 +- src/corelib/itemmodels/qitemselectionmodel_p.h | 6 +- 3 files changed, 110 insertions(+), 28 deletions(-) (limited to 'src/corelib/itemmodels') diff --git a/src/corelib/itemmodels/qitemselectionmodel.cpp b/src/corelib/itemmodels/qitemselectionmodel.cpp index 4b9391d285..d1cbd7f461 100644 --- a/src/corelib/itemmodels/qitemselectionmodel.cpp +++ b/src/corelib/itemmodels/qitemselectionmodel.cpp @@ -284,12 +284,21 @@ QItemSelectionRange QItemSelectionRange::intersected(const QItemSelectionRange & */ -/* - \internal - - utility function for getting the indexes from a range - it avoid concatenating list and works on one - */ +static void rowLengthsFromRange(const QItemSelectionRange &range, QVector > &result) +{ + if (range.isValid() && range.model()) { + const QModelIndex topLeft = range.topLeft(); + const int bottom = range.bottom(); + const uint width = range.width(); + const int column = topLeft.column(); + for (int row = topLeft.row(); row <= bottom; ++row) { + // We don't need to keep track of ItemIsSelectable and ItemIsEnabled here. That is + // required in indexesFromRange() because that method is called from public API + // which requires the limitation. + result.push_back(qMakePair(QPersistentModelIndex(topLeft.sibling(row, column)), width)); + } + } +} template static void indexesFromRange(const QItemSelectionRange &range, ModelIndexContainer &result) @@ -468,6 +477,14 @@ static QVector qSelectionPersistentindexes(const QItemSel return result; } +static QVector > qSelectionPersistentRowLengths(const QItemSelection &sel) +{ + QVector > result; + Q_FOREACH (const QItemSelectionRange &range, sel) + rowLengthsFromRange(range, result); + return result; +} + /*! Merges the \a other selection with this QItemSelection using the \a command given. This method guarantees that no ranges are overlapping. @@ -599,10 +616,10 @@ void QItemSelectionModelPrivate::initModel(QAbstractItemModel *model) q, SLOT(_q_layoutChanged())); QObject::connect(model, SIGNAL(columnsMoved(QModelIndex,int,int,QModelIndex,int)), q, SLOT(_q_layoutChanged())); - QObject::connect(model, SIGNAL(layoutAboutToBeChanged()), - q, SLOT(_q_layoutAboutToBeChanged())); - QObject::connect(model, SIGNAL(layoutChanged()), - q, SLOT(_q_layoutChanged())); + QObject::connect(model, SIGNAL(layoutAboutToBeChanged(QList,QAbstractItemModel::LayoutChangeHint)), + q, SLOT(_q_layoutAboutToBeChanged(QList,QAbstractItemModel::LayoutChangeHint))); + QObject::connect(model, SIGNAL(layoutChanged(QList,QAbstractItemModel::LayoutChangeHint)), + q, SLOT(_q_layoutChanged(QList,QAbstractItemModel::LayoutChangeHint))); } } @@ -812,10 +829,12 @@ void QItemSelectionModelPrivate::_q_rowsAboutToBeInserted(const QModelIndex &par preparation for the layoutChanged() signal, where the indexes can be merged again. */ -void QItemSelectionModelPrivate::_q_layoutAboutToBeChanged() +void QItemSelectionModelPrivate::_q_layoutAboutToBeChanged(const QList &, QAbstractItemModel::LayoutChangeHint hint) { savedPersistentIndexes.clear(); savedPersistentCurrentIndexes.clear(); + savedPersistentRowLengths.clear(); + savedPersistentCurrentRowLengths.clear(); // optimization for when all indexes are selected // (only if there is lots of items (1000) because this is not entirely correct) @@ -836,8 +855,53 @@ void QItemSelectionModelPrivate::_q_layoutAboutToBeChanged() } tableSelected = false; - savedPersistentIndexes = qSelectionPersistentindexes(ranges); - savedPersistentCurrentIndexes = qSelectionPersistentindexes(currentSelection); + if (hint == QAbstractItemModel::VerticalSortHint) { + // Special case when we know we're sorting vertically. We can assume that all indexes for columns + // are displaced the same way, and therefore we only need to track an index from one column per + // row with a QPersistentModelIndex together with the length of items to the right of it + // which are displaced the same way. + // An algorithm which contains the same assumption is used to process layoutChanged. + savedPersistentRowLengths = qSelectionPersistentRowLengths(ranges); + savedPersistentCurrentRowLengths = qSelectionPersistentRowLengths(currentSelection); + } else { + savedPersistentIndexes = qSelectionPersistentindexes(ranges); + savedPersistentCurrentIndexes = qSelectionPersistentindexes(currentSelection); + } +} +/*! + \internal +*/ +static QItemSelection mergeRowLengths(const QVector > &rowLengths) +{ + if (rowLengths.isEmpty()) + return QItemSelection(); + + QItemSelection result; + int i = 0; + while (i < rowLengths.count()) { + const QPersistentModelIndex &tl = rowLengths.at(i).first; + if (!tl.isValid()) { + ++i; + continue; + } + QPersistentModelIndex br = tl; + const uint length = rowLengths.at(i).second; + while (++i < rowLengths.count()) { + const QPersistentModelIndex &next = rowLengths.at(i).first; + if (!next.isValid()) + continue; + const uint nextLength = rowLengths.at(i).second; + if ((nextLength == length) + && (next.row() == br.row() + 1) + && (next.parent() == br.parent())) { + br = next; + } else { + break; + } + } + result.append(QItemSelectionRange(tl, br.sibling(br.row(), length - 1))); + } + return result; } /*! @@ -913,7 +977,7 @@ static QItemSelection mergeIndexes(const QVector &indexes Merge the selected indexes into selection ranges again. */ -void QItemSelectionModelPrivate::_q_layoutChanged() +void QItemSelectionModelPrivate::_q_layoutChanged(const QList &, QAbstractItemModel::LayoutChangeHint hint) { // special case for when all indexes are selected if (tableSelected && tableColCount == model->columnCount(tableParent) @@ -930,26 +994,42 @@ void QItemSelectionModelPrivate::_q_layoutChanged() return; } - if (savedPersistentCurrentIndexes.isEmpty() && savedPersistentIndexes.isEmpty()) { + if ((hint != QAbstractItemModel::VerticalSortHint && savedPersistentCurrentIndexes.isEmpty() && savedPersistentIndexes.isEmpty()) + || (hint == QAbstractItemModel::VerticalSortHint && savedPersistentRowLengths.isEmpty() && savedPersistentCurrentRowLengths.isEmpty())) { // either the selection was actually empty, or we // didn't get the layoutAboutToBeChanged() signal return; } + // clear the "old" selection ranges.clear(); currentSelection.clear(); - // sort the "new" selection, as preparation for merging - qStableSort(savedPersistentIndexes.begin(), savedPersistentIndexes.end()); - qStableSort(savedPersistentCurrentIndexes.begin(), savedPersistentCurrentIndexes.end()); + if (hint != QAbstractItemModel::VerticalSortHint) { + // sort the "new" selection, as preparation for merging + qStableSort(savedPersistentIndexes.begin(), savedPersistentIndexes.end()); + qStableSort(savedPersistentCurrentIndexes.begin(), savedPersistentCurrentIndexes.end()); - // update the selection by merging the individual indexes - ranges = mergeIndexes(savedPersistentIndexes); - currentSelection = mergeIndexes(savedPersistentCurrentIndexes); + // update the selection by merging the individual indexes + ranges = mergeIndexes(savedPersistentIndexes); + currentSelection = mergeIndexes(savedPersistentCurrentIndexes); - // release the persistent indexes - savedPersistentIndexes.clear(); - savedPersistentCurrentIndexes.clear(); + // release the persistent indexes + savedPersistentIndexes.clear(); + savedPersistentCurrentIndexes.clear(); + } else { + // sort the "new" selection, as preparation for merging + qStableSort(savedPersistentRowLengths.begin(), savedPersistentRowLengths.end()); + qStableSort(savedPersistentCurrentRowLengths.begin(), savedPersistentCurrentRowLengths.end()); + + // update the selection by merging the individual indexes + ranges = mergeRowLengths(savedPersistentRowLengths); + currentSelection = mergeRowLengths(savedPersistentCurrentRowLengths); + + // release the persistent indexes + savedPersistentRowLengths.clear(); + savedPersistentCurrentRowLengths.clear(); + } } /*! diff --git a/src/corelib/itemmodels/qitemselectionmodel.h b/src/corelib/itemmodels/qitemselectionmodel.h index 555401e621..79a8a25470 100644 --- a/src/corelib/itemmodels/qitemselectionmodel.h +++ b/src/corelib/itemmodels/qitemselectionmodel.h @@ -222,8 +222,8 @@ private: Q_PRIVATE_SLOT(d_func(), void _q_rowsAboutToBeRemoved(const QModelIndex&, int, int)) Q_PRIVATE_SLOT(d_func(), void _q_columnsAboutToBeInserted(const QModelIndex&, int, int)) Q_PRIVATE_SLOT(d_func(), void _q_rowsAboutToBeInserted(const QModelIndex&, int, int)) - Q_PRIVATE_SLOT(d_func(), void _q_layoutAboutToBeChanged()) - Q_PRIVATE_SLOT(d_func(), void _q_layoutChanged()) + Q_PRIVATE_SLOT(d_func(), void _q_layoutAboutToBeChanged(const QList &parents = QList(), QAbstractItemModel::LayoutChangeHint hint = QAbstractItemModel::NoHint)) + Q_PRIVATE_SLOT(d_func(), void _q_layoutChanged(const QList &parents = QList(), QAbstractItemModel::LayoutChangeHint hint = QAbstractItemModel::NoHint)) }; Q_DECLARE_OPERATORS_FOR_FLAGS(QItemSelectionModel::SelectionFlags) diff --git a/src/corelib/itemmodels/qitemselectionmodel_p.h b/src/corelib/itemmodels/qitemselectionmodel_p.h index cc278346ff..9439bb772b 100644 --- a/src/corelib/itemmodels/qitemselectionmodel_p.h +++ b/src/corelib/itemmodels/qitemselectionmodel_p.h @@ -76,8 +76,8 @@ public: void _q_columnsAboutToBeRemoved(const QModelIndex &parent, int start, int end); void _q_rowsAboutToBeInserted(const QModelIndex &parent, int start, int end); void _q_columnsAboutToBeInserted(const QModelIndex &parent, int start, int end); - void _q_layoutAboutToBeChanged(); - void _q_layoutChanged(); + void _q_layoutAboutToBeChanged(const QList &parents = QList(), QAbstractItemModel::LayoutChangeHint hint = QAbstractItemModel::NoLayoutChangeHint); + void _q_layoutChanged(const QList &parents = QList(), QAbstractItemModel::LayoutChangeHint hint = QAbstractItemModel::NoLayoutChangeHint); inline void remove(QList &r) { @@ -100,6 +100,8 @@ public: QItemSelectionModel::SelectionFlags currentCommand; QVector savedPersistentIndexes; QVector savedPersistentCurrentIndexes; + QVector > savedPersistentRowLengths; + QVector > savedPersistentCurrentRowLengths; // optimization when all indexes are selected bool tableSelected; QPersistentModelIndex tableParent; -- cgit v1.2.3