From d34287af6fc1c7558e8ed15dbb29c0e6b58b7b00 Mon Sep 17 00:00:00 2001 From: Stephen Bowline Date: Mon, 16 Aug 2010 14:38:11 -0700 Subject: QAbstractItemView: optimize handling of editors for view with large numbers of editors. This change improves algorithmic time complexity for item views during operations which directly (or indirectly such as layout) require bi-directional lookups between model indices and persistent editor widgets. The previous implementation scaled as O(n^2) due to the unordered search through a QVector. Implementations that use large numbers of persistent editors are most dramatically improved. In one "real world" test case with 648 persistent editors, profiling indicates an improvement of layout from 45 seconds to 8 seconds with this change alone. Reviewed-by: Olivier Goffart Merge-Request: 2452 --- src/gui/itemviews/qabstractitemview.cpp | 122 +++++++++++++++++--------------- src/gui/itemviews/qabstractitemview_p.h | 29 ++++---- src/gui/itemviews/qtableview.cpp | 4 +- src/gui/itemviews/qtreeview.cpp | 14 ++-- 4 files changed, 87 insertions(+), 82 deletions(-) diff --git a/src/gui/itemviews/qabstractitemview.cpp b/src/gui/itemviews/qabstractitemview.cpp index 12add05..a5630ec 100644 --- a/src/gui/itemviews/qabstractitemview.cpp +++ b/src/gui/itemviews/qabstractitemview.cpp @@ -1037,10 +1037,10 @@ void QAbstractItemView::reset() { Q_D(QAbstractItemView); d->delayedReset.stop(); //make sure we stop the timer - QList::const_iterator it = d->editors.constBegin(); - for (; it != d->editors.constEnd(); ++it) - d->releaseEditor(it->editor); - d->editors.clear(); + for (QEditorIndexHash::iterator it = d->editorIndexHash.begin(); it != d->editorIndexHash.end(); ++it) + d->releaseEditor(it.key()); + d->editorIndexHash.clear(); + d->indexEditorHash.clear(); d->persistent.clear(); d->currentIndexSet = false; setState(NoState); @@ -2519,7 +2519,7 @@ bool QAbstractItemView::edit(const QModelIndex &index, EditTrigger trigger, QEve if (!d->isIndexValid(index)) return false; - if (QWidget *w = (d->persistent.isEmpty() ? static_cast(0) : d->editorForIndex(index).editor.data())) { + if (QWidget *w = (d->persistent.isEmpty() ? static_cast(0) : d->editorForIndex(index).widget.data())) { if (w->focusPolicy() == Qt::NoFocus) return false; w->setFocus(); @@ -2579,15 +2579,15 @@ void QAbstractItemView::updateEditorData() void QAbstractItemView::updateEditorGeometries() { Q_D(QAbstractItemView); - if(d->editors.isEmpty()) + if(d->editorIndexHash.isEmpty()) return; QStyleOptionViewItemV4 option = d->viewOptionsV4(); - QList::iterator it = d->editors.begin(); + QEditorIndexHash::iterator it = d->editorIndexHash.begin(); QWidgetList editorsToRelease; QWidgetList editorsToHide; - while (it != d->editors.end()) { - QModelIndex index = it->index; - QWidget *editor = it->editor; + while (it != d->editorIndexHash.end()) { + QModelIndex index = it.value(); + QWidget *editor = it.key(); if (index.isValid() && editor) { option.rect = visualRect(index); if (option.rect.isValid()) { @@ -2600,7 +2600,8 @@ void QAbstractItemView::updateEditorGeometries() } ++it; } else { - it = d->editors.erase(it); + d->indexEditorHash.remove(it.value()); + it = d->editorIndexHash.erase(it); editorsToRelease << editor; } } @@ -2957,7 +2958,7 @@ int QAbstractItemView::sizeHintForRow(int row) const QModelIndex index; for (int c = 0; c < colCount; ++c) { index = d->model->index(row, c, d->root); - if (QWidget *editor = d->editorForIndex(index).editor) + if (QWidget *editor = d->editorForIndex(index).widget.data()) height = qMax(height, editor->height()); int hint = d->delegateForIndex(index)->sizeHint(option, index).height(); height = qMax(height, hint); @@ -2988,7 +2989,7 @@ int QAbstractItemView::sizeHintForColumn(int column) const QModelIndex index; for (int r = 0; r < rows; ++r) { index = d->model->index(r, column, d->root); - if (QWidget *editor = d->editorForIndex(index).editor) + if (QWidget *editor = d->editorForIndex(index).widget.data()) width = qMax(width, editor->sizeHint().width()); int hint = d->delegateForIndex(index)->sizeHint(option, index).width(); width = qMax(width, hint); @@ -3024,8 +3025,7 @@ void QAbstractItemView::openPersistentEditor(const QModelIndex &index) void QAbstractItemView::closePersistentEditor(const QModelIndex &index) { Q_D(QAbstractItemView); - QWidget *editor = d->editorForIndex(index).editor; - if (editor) { + if (QWidget *editor = d->editorForIndex(index).widget.data()) { if (index == selectionModel()->currentIndex()) closeEditor(editor, QAbstractItemDelegate::RevertModelCache); d->persistent.remove(editor); @@ -3089,9 +3089,11 @@ void QAbstractItemView::setIndexWidget(const QModelIndex &index, QWidget *widget QWidget* QAbstractItemView::indexWidget(const QModelIndex &index) const { Q_D(const QAbstractItemView); - if (!d->isIndexValid(index)) - return 0; - return d->editorForIndex(index).editor; + if (d->isIndexValid(index)) + if (QWidget *editor = d->editorForIndex(index).widget.data()) + return editor; + + return 0; } /*! @@ -3153,12 +3155,12 @@ void QAbstractItemView::dataChanged(const QModelIndex &topLeft, const QModelInde // Single item changed Q_D(QAbstractItemView); if (topLeft == bottomRight && topLeft.isValid()) { - const QEditorInfo editorInfo = d->editorForIndex(topLeft); + const QEditorInfo &editorInfo = d->editorForIndex(topLeft); //we don't update the edit data if it is static - if (!editorInfo.isStatic && editorInfo.editor) { + if (!editorInfo.isStatic && editorInfo.widget) { QAbstractItemDelegate *delegate = d->delegateForIndex(topLeft); if (delegate) { - delegate->setEditorData(editorInfo.editor, topLeft); + delegate->setEditorData(editorInfo.widget.data(), topLeft); } } if (isVisible() && !d->delayedPendingLayout) { @@ -3232,12 +3234,16 @@ void QAbstractItemView::rowsAboutToBeRemoved(const QModelIndex &parent, int star } // Remove all affected editors; this is more efficient than waiting for updateGeometries() to clean out editors for invalid indexes - for (int i = d->editors.size() - 1; i >= 0; --i) { - const QModelIndex index = d->editors.at(i).index; - QWidget *editor = d->editors.at(i).editor; + QEditorIndexHash::iterator i = d->editorIndexHash.begin(); + while (i != d->editorIndexHash.end()) { + const QModelIndex index = i.value(); if (index.row() >= start && index.row() <= end && d->model->parent(index) == parent) { - d->editors.removeAt(i); + QWidget *editor = i.key(); + d->indexEditorHash.remove(index); + i = d->editorIndexHash.erase(i); d->releaseEditor(editor); + } else { + ++i; } } } @@ -3294,17 +3300,19 @@ void QAbstractItemViewPrivate::_q_columnsAboutToBeRemoved(const QModelIndex &par } // Remove all affected editors; this is more efficient than waiting for updateGeometries() to clean out editors for invalid indexes - QList::iterator it = editors.begin(); - while (it != editors.end()) { - QModelIndex index = it->index; + QEditorIndexHash::iterator it = editorIndexHash.begin(); + while (it != editorIndexHash.end()) { + QModelIndex index = it.value(); if (index.column() <= start && index.column() >= end && model->parent(index) == parent) { - QWidget *editor = it->editor; - it = editors.erase(it); + QWidget *editor = it.key(); + indexEditorHash.remove(it.value()); + it = editorIndexHash.erase(it); releaseEditor(editor); } else { ++it; } } + } /*! @@ -3386,7 +3394,7 @@ void QAbstractItemView::currentChanged(const QModelIndex ¤t, const QModelI if (previous.isValid()) { QModelIndex buddy = d->model->buddy(previous); - QWidget *editor = d->editorForIndex(buddy).editor; + QWidget *editor = d->editorForIndex(buddy).widget.data(); if (editor && !d->persistent.contains(editor)) { commitData(editor); if (current.row() != previous.row()) @@ -3912,7 +3920,7 @@ QWidget *QAbstractItemViewPrivate::editor(const QModelIndex &index, const QStyleOptionViewItem &options) { Q_Q(QAbstractItemView); - QWidget *w = editorForIndex(index).editor; + QWidget *w = editorForIndex(index).widget.data(); if (!w) { QAbstractItemDelegate *delegate = delegateForIndex(index); if (!delegate) @@ -3943,6 +3951,7 @@ QWidget *QAbstractItemViewPrivate::editor(const QModelIndex &index, #endif } } + return w; } @@ -3951,11 +3960,11 @@ void QAbstractItemViewPrivate::updateEditorData(const QModelIndex &tl, const QMo // we are counting on having relatively few editors const bool checkIndexes = tl.isValid() && br.isValid(); const QModelIndex parent = tl.parent(); - QList::const_iterator it = editors.constBegin(); - for (; it != editors.constEnd(); ++it) { - QWidget *editor = it->editor; - const QModelIndex index = it->index; - if (it->isStatic || editor == 0 || !index.isValid() || + QIndexEditorHash::const_iterator it = indexEditorHash.constBegin(); + for (; it != indexEditorHash.constEnd(); ++it) { + QWidget *editor = it.value().widget.data(); + const QModelIndex index = it.key(); + if (it.value().isStatic || !editor || !index.isValid() || (checkIndexes && (index.row() < tl.row() || index.row() > br.row() || index.column() < tl.column() || index.column() > br.column() @@ -4028,41 +4037,40 @@ void QAbstractItemViewPrivate::checkPersistentEditorFocus() } -QEditorInfo QAbstractItemViewPrivate::editorForIndex(const QModelIndex &index) const +const QEditorInfo & QAbstractItemViewPrivate::editorForIndex(const QModelIndex &index) const { - QList::const_iterator it = editors.constBegin(); - for (; it != editors.constEnd(); ++it) { - if (it->index == index) - return *it; - } + static QEditorInfo nullInfo; + + QIndexEditorHash::const_iterator it = indexEditorHash.find(index); + if (it == indexEditorHash.end()) + return nullInfo; - return QEditorInfo(); + return it.value(); } QModelIndex QAbstractItemViewPrivate::indexForEditor(QWidget *editor) const { - QList::const_iterator it = editors.constBegin(); - for (; it != editors.constEnd(); ++it) { - if (it->editor == editor) - return it->index; - } - return QModelIndex(); + QEditorIndexHash::const_iterator it = editorIndexHash.find(editor); + if (it == editorIndexHash.end()) + return QModelIndex(); + + return it.value(); } void QAbstractItemViewPrivate::removeEditor(QWidget *editor) { - QList::iterator it = editors.begin(); - for (; it != editors.end(); ) { - if (it->editor == editor) - it = editors.erase(it); - else - ++it; + QEditorIndexHash::iterator it = editorIndexHash.find(editor); + if (it != editorIndexHash.end()) + { + indexEditorHash.remove(it.value()); + editorIndexHash.erase(it); } } void QAbstractItemViewPrivate::addEditor(const QModelIndex &index, QWidget *editor, bool isStatic) { - editors.append(QEditorInfo(index, editor, isStatic)); + editorIndexHash.insert(editor, index); + indexEditorHash.insert(index, QEditorInfo(editor, isStatic)); } bool QAbstractItemViewPrivate::sendDelegateEvent(const QModelIndex &index, QEvent *event) const diff --git a/src/gui/itemviews/qabstractitemview_p.h b/src/gui/itemviews/qabstractitemview_p.h index 969553a..03b413a 100644 --- a/src/gui/itemviews/qabstractitemview_p.h +++ b/src/gui/itemviews/qabstractitemview_p.h @@ -70,22 +70,18 @@ QT_BEGIN_NAMESPACE -struct QEditorInfo -{ - QEditorInfo() : isStatic(false) - { - } - - QEditorInfo(const QPersistentModelIndex &i, QWidget *e, bool b) : index(i), editor(e), isStatic(b) - { - } - - QPersistentModelIndex index; - QPointer editor; - bool isStatic; //true when called from setIndexWidget +struct QEditorInfo { + QEditorInfo(QWidget *e, bool s): widget(QWeakPointer(e)), isStatic(s) {} + QEditorInfo(): isStatic(false) {} + QWeakPointer widget; + bool isStatic; }; +// Fast associativity between Persistent editors and indices. +typedef QHash QEditorIndexHash; +typedef QHash QIndexEditorHash; + typedef QPair QItemViewPaintPair; typedef QList QItemViewPaintPairs; @@ -248,9 +244,9 @@ public: : q->horizontalOffset(), q->verticalOffset()); } - QEditorInfo editorForIndex(const QModelIndex &index) const; + const QEditorInfo &editorForIndex(const QModelIndex &index) const; inline bool hasEditor(const QModelIndex &index) const { - return editorForIndex(index).editor != 0; + return indexEditorHash.find(index) != indexEditorHash.constEnd(); } QModelIndex indexForEditor(QWidget *editor) const; @@ -353,7 +349,8 @@ public: QAbstractItemView::SelectionMode selectionMode; QAbstractItemView::SelectionBehavior selectionBehavior; - QList editors; + QEditorIndexHash editorIndexHash; + QIndexEditorHash indexEditorHash; QSet persistent; QWidget *currentlyCommittingEditor; diff --git a/src/gui/itemviews/qtableview.cpp b/src/gui/itemviews/qtableview.cpp index e9e2e38..d8fef55 100644 --- a/src/gui/itemviews/qtableview.cpp +++ b/src/gui/itemviews/qtableview.cpp @@ -2159,7 +2159,7 @@ int QTableView::sizeHintForRow(int row) const option.rect.setWidth(columnWidth(index.column())); } - QWidget *editor = d->editorForIndex(index).editor; + QWidget *editor = d->editorForIndex(index).widget.data(); if (editor && d->persistent.contains(editor)) { hint = qMax(hint, editor->sizeHint().height()); int min = editor->minimumSize().height(); @@ -2212,7 +2212,7 @@ int QTableView::sizeHintForColumn(int column) const continue; index = d->model->index(logicalRow, column, d->root); - QWidget *editor = d->editorForIndex(index).editor; + QWidget *editor = d->editorForIndex(index).widget.data(); if (editor && d->persistent.contains(editor)) { hint = qMax(hint, editor->sizeHint().width()); int min = editor->minimumSize().width(); diff --git a/src/gui/itemviews/qtreeview.cpp b/src/gui/itemviews/qtreeview.cpp index ccc8e00..e393902 100644 --- a/src/gui/itemviews/qtreeview.cpp +++ b/src/gui/itemviews/qtreeview.cpp @@ -1493,7 +1493,7 @@ void QTreeView::drawRow(QPainter *painter, const QStyleOptionViewItem &option, // when the row contains an index widget which has focus, // we want to paint the entire row as active bool indexWidgetHasFocus = false; - if ((current.row() == index.row()) && !d->editors.isEmpty()) { + if ((current.row() == index.row()) && !d->editorIndexHash.isEmpty()) { const int r = index.row(); QWidget *fw = QApplication::focusWidget(); for (int c = 0; c < header->count(); ++c) { @@ -2388,7 +2388,7 @@ void QTreeView::scrollContentsBy(int dx, int dy) int viewCount = d->viewport->height() / itemHeight; int maxDeltaY = qMin(d->viewItems.count(), viewCount); // no need to do a lot of work if we are going to redraw the whole thing anyway - if (qAbs(dy) > qAbs(maxDeltaY) && d->editors.isEmpty()) { + if (qAbs(dy) > qAbs(maxDeltaY) && d->editorIndexHash.isEmpty()) { verticalScrollBar()->update(); d->viewport->update(); return; @@ -2718,7 +2718,7 @@ int QTreeView::sizeHintForColumn(int column) const continue; // we have no good size hint QModelIndex index = viewItems.at(i).index; index = index.sibling(index.row(), column); - QWidget *editor = d->editorForIndex(index).editor; + QWidget *editor = d->editorForIndex(index).widget.data(); if (editor && d->persistent.contains(editor)) { w = qMax(w, editor->sizeHint().width()); int min = editor->minimumSize().width(); @@ -2782,7 +2782,7 @@ int QTreeView::indexRowSizeHint(const QModelIndex &index) const continue; QModelIndex idx = d->model->index(index.row(), logicalColumn, parent); if (idx.isValid()) { - QWidget *editor = d->editorForIndex(idx).editor; + QWidget *editor = d->editorForIndex(idx).widget.data(); if (editor && d->persistent.contains(editor)) { height = qMax(height, editor->sizeHint().height()); int min = editor->minimumSize().height(); @@ -3031,9 +3031,9 @@ QPixmap QTreeViewPrivate::renderTreeToPixmapForAnimation(const QRect &rect) cons //and now let's render the editors the editors QStyleOptionViewItemV4 option = viewOptionsV4(); - for (QList::const_iterator it = editors.constBegin(); it != editors.constEnd(); ++it) { - QWidget *editor = it->editor; - QModelIndex index = it->index; + for (QEditorIndexHash::const_iterator it = editorIndexHash.constBegin(); it != editorIndexHash.constEnd(); ++it) { + QWidget *editor = it.key(); + const QModelIndex &index = it.value(); option.rect = q->visualRect(index); if (option.rect.isValid()) { -- cgit v0.12