From e3a1b18bc3e213c318107b84b07543d945b48514 Mon Sep 17 00:00:00 2001
From: Erik Verbruggen <erik.verbruggen@qt.io>
Date: Tue, 24 Apr 2018 13:41:28 +0200
Subject: ItemModels: search for the child index in 2 directions

Previously, the search for the index of a child was done by searching
forwards (minus 2) from the last search, and subsequently backwards when
it wasn't found. This would cause quite some searching in models with
lots of items, and where the child lay before the last search.

We still assume that subsequent searches for children are "nearby" the
previous search, but instead of first searching forwards and then
backwards, do the search in both directions.

Task-number: QTBUG-61368
Change-Id: Idb549c2d02840632cd658f906816ce911f3ff8bc
Reviewed-by: David Faure <david.faure@kdab.com>
---
 src/gui/itemmodels/qstandarditemmodel_p.h | 36 +++++++++++++++++++++++++------
 1 file changed, 29 insertions(+), 7 deletions(-)

(limited to 'src')

diff --git a/src/gui/itemmodels/qstandarditemmodel_p.h b/src/gui/itemmodels/qstandarditemmodel_p.h
index d3ff2787a5..4589a62223 100644
--- a/src/gui/itemmodels/qstandarditemmodel_p.h
+++ b/src/gui/itemmodels/qstandarditemmodel_p.h
@@ -114,7 +114,7 @@ public:
           rows(0),
           columns(0),
           q_ptr(0),
-          lastIndexOf(2)
+          lastIndexOf(-1)
         { }
 
     inline int childIndex(int row, int column) const {
@@ -124,11 +124,33 @@ public:
         }
         return (row * columnCount()) + column;
     }
-    inline int childIndex(const QStandardItem *child) {
-        int start = qMax(0, lastIndexOf -2);
-        lastIndexOf = children.indexOf(const_cast<QStandardItem*>(child), start);
-        if (lastIndexOf == -1 && start != 0)
-            lastIndexOf = children.lastIndexOf(const_cast<QStandardItem*>(child), start);
+    inline int childIndex(const QStandardItem *child) const {
+        const int lastChild = children.size() - 1;
+        if (lastIndexOf == -1)
+            lastIndexOf = lastChild / 2;
+        // assuming the item is in the vicinity of the last search, iterate forwards and
+        // backwards through the children
+        int backwardIter = lastIndexOf - 1;
+        int forwardIter = lastIndexOf;
+        Q_FOREVER {
+            if (forwardIter <= lastChild) {
+                if (children.at(forwardIter) == child) {
+                    lastIndexOf = forwardIter;
+                    break;
+                }
+                ++forwardIter;
+            } else if (backwardIter < 0) {
+                lastIndexOf = -1;
+                break;
+            }
+            if (backwardIter >= 0) {
+                if (children.at(backwardIter) == child) {
+                    lastIndexOf = backwardIter;
+                    break;
+                }
+                --backwardIter;
+            }
+        }
         return lastIndexOf;
     }
     QPair<int, int> position() const;
@@ -170,7 +192,7 @@ public:
 
     QStandardItem *q_ptr;
 
-    int lastIndexOf;
+    mutable int lastIndexOf;
 };
 
 class QStandardItemModelPrivate : public QAbstractItemModelPrivate
-- 
cgit v1.2.3