QTreeView: Optimise QTreeViewPrivate::viewIndex

... by first looking around the last find item.

This was already done, but only for the 4 closest item. Now start
searching from the last index and continue.

Reviewed-by: Gabriel
Task-number: QTBUG-8886

1 files changed, 27 insertions, 35 deletions

diff --git a/src/gui/itemviews/qtreeview.cpp b/src/gui/itemviews/qtreeview.cpp
index 18ee5d3..4135ba0 100644
--- a/src/gui/itemviews/qtreeview.cpp
+++ b/src/gui/itemviews/qtreeview.cpp
@@ -2407,9 +2407,9 @@ void QTreeView::reexpand()
 
 /*!
   \internal
+  This function assume that left is a (grand-)child of the parent of left.
 */
-static bool treeViewItemLessThan(const QTreeViewItem &left,
-                                 const QTreeViewItem &right)
+static bool treeViewItemLessThanInInsert(const QTreeViewItem &left, const QTreeViewItem &right)
 {
     if (left.level != right.level) {
         Q_ASSERT(left.level > right.level);
@@ -2496,7 +2496,7 @@ void QTreeView::rowsInserted(const QModelIndex &parent, int start, int end)
             QVector<QTreeViewItem>::iterator it;
             it = qLowerBound(d->viewItems.begin() + firstChildItem,
                              d->viewItems.begin() + lastChildItem + 1,
-                             insertedItems.at(0), treeViewItemLessThan);
+                             insertedItems.at(0), treeViewItemLessThanInInsert);
             insertPos = it - d->viewItems.begin();
 
             // update stale model indexes of siblings
@@ -3397,46 +3397,39 @@ int QTreeViewPrivate::viewIndex(const QModelIndex &_index) const
 
     const int totalCount = viewItems.count();
     const QModelIndex index = _index.sibling(_index.row(), 0);
+    const int row = index.row();
+    const quint64 internalId = index.internalId();
 
-
-    // A quick check near the last item to see if we are just incrementing
-    const int start = lastViewedItem > 2 ? lastViewedItem - 2 : 0;
-    const int end = lastViewedItem < totalCount - 2 ? lastViewedItem + 2 : totalCount;
-    int row = index.row();
-    for (int i = start; i < end; ++i) {
-        const QModelIndex &idx = viewItems.at(i).index;
-        if (idx.row() == row) {
-            if (idx.internalId() == index.internalId()) {
-                lastViewedItem = i;
-                return i;
-            }
+    // We start nearest to the lastViewedItem
+    int localCount = qMin(lastViewedItem - 1, totalCount - lastViewedItem);
+    for (int i = 0; i < localCount; ++i) {
+        const QModelIndex &idx1 = viewItems.at(lastViewedItem + i).index;
+        if (idx1.row() == row && idx1.internalId() == internalId) {
+            lastViewedItem = lastViewedItem + i;
+            return lastViewedItem;
+        }
+        const QModelIndex &idx2 = viewItems.at(lastViewedItem - i - 1).index;
+        if (idx2.row() == row && idx2.internalId() == internalId) {
+            lastViewedItem = lastViewedItem - i - 1;
+            return lastViewedItem;
         }
     }
 
-    // NOTE: this function is slow if the item is outside the visible area
-    // search in visible items first and below
-    int t = firstVisibleItem();
-    t = t > 100 ? t - 100 : 0; // start 100 items above the visible area
-
-    for (int i = t; i < totalCount; ++i) {
-        const QModelIndex &idx = viewItems.at(i).index;
-        if (idx.row() == row) {
-            if (idx.internalId() == index.internalId()) {
-                lastViewedItem = i;
-                return i;
-            }
+    for (int j = qMax(0, lastViewedItem + localCount); j < totalCount; ++j) {
+        const QModelIndex &idx = viewItems.at(j).index;
+        if (idx.row() == row && idx.internalId() == internalId) {
+            lastViewedItem = j;
+            return j;
         }
     }
-    // search from top to first visible
-    for (int j = 0; j < t; ++j) {
+    for (int j = qMin(totalCount, lastViewedItem - localCount) - 1; j >= 0; --j) {
         const QModelIndex &idx = viewItems.at(j).index;
-        if (idx.row() == row) {
-            if (idx.internalId() == index.internalId()) {
-                lastViewedItem = j;
-                return j;
-            }
+        if (idx.row() == row && idx.internalId() == internalId) {
+            lastViewedItem = j;
+            return j;
         }
     }
+
     // nothing found
     return -1;
 }
@@ -3761,7 +3754,6 @@ bool QTreeViewPrivate::hasVisibleChildren(const QModelIndex& parent) const
 void QTreeViewPrivate::rowsRemoved(const QModelIndex &parent,
                                    int start, int end, bool after)
 {
-    Q_Q(QTreeView);
     // if we are going to do a complete relayout anyway, there is no need to update
     if (delayedPendingLayout) {
         _q_rowsRemoved(parent, start, end);