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

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<QEditorInfo>::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<QWidget*>(0) : d->editorForIndex(index).editor.data())) {
+    if (QWidget *w = (d->persistent.isEmpty() ? static_cast<QWidget*>(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<QEditorInfo>::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<QEditorInfo>::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 &current, 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<QEditorInfo>::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<QEditorInfo>::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<QEditorInfo>::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<QEditorInfo>::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<QWidget> editor;
-    bool isStatic; //true when called from setIndexWidget
+struct QEditorInfo {
+    QEditorInfo(QWidget *e, bool s): widget(QWeakPointer<QWidget>(e)), isStatic(s) {}
+    QEditorInfo(): isStatic(false) {}
 
+    QWeakPointer<QWidget> widget;
+    bool isStatic;
 };
 
+//  Fast associativity between Persistent editors and indices.
+typedef QHash<QWidget *, QPersistentModelIndex> QEditorIndexHash;
+typedef QHash<QPersistentModelIndex, QEditorInfo> QIndexEditorHash;
+
 typedef QPair<QRect, QModelIndex> QItemViewPaintPair;
 typedef QList<QItemViewPaintPair> 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<QEditorInfo> editors;
+    QEditorIndexHash editorIndexHash;
+    QIndexEditorHash indexEditorHash;
     QSet<QWidget*> 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<QEditorInfo>::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()) {