Speedup item-lookup in Graphics View.

We don't have to do a stable sort anymore because the lessThan operator
now accounts for the insertion order. This also means we don't have to
sort all top-level items to preserve the insertion order in
QGraphicsScenePrivate::topLevelItemsInStackingOrder.

Reviewed-by: Andreas

7 files changed, 65 insertions, 52 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index 002eab9..9a27ef5 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -4310,6 +4310,7 @@ void QGraphicsItemPrivate::resolveDepth(int parentDepth)
 void QGraphicsItemPrivate::addChild(QGraphicsItem *child)
 {
     needSortChildren = 1;
+    child->d_ptr->siblingIndex = children.size();
     children.append(child);
 }
 
@@ -4319,6 +4320,10 @@ void QGraphicsItemPrivate::addChild(QGraphicsItem *child)
 void QGraphicsItemPrivate::removeChild(QGraphicsItem *child)
 {
     children.removeOne(child);
+    // NB! Do not use children.removeAt(child->d_ptr->siblingIndex) because
+    // the child is not guaranteed to be at the index after the list is sorted.
+    // (see ensureSortedChildren()).
+    child->d_ptr->siblingIndex = -1;
 }
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index a4b2c25..99865b0 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -126,6 +126,7 @@ public:
         parent(0),
         transformData(0),
         index(-1),
+        siblingIndex(-1),
         depth(0),
         acceptedMouseButtons(0x1f),
         visible(1),
@@ -386,6 +387,7 @@ public:
     }
 
     inline QTransform transformToParent() const;
+    inline void ensureSortedChildren();
 
     QPainterPath cachedClipPath;
     QRectF childrenBoundingRect;
@@ -401,6 +403,7 @@ public:
     TransformData *transformData;
     QTransform sceneTransform;
     int index;
+    int siblingIndex;
     int depth;
 
     inline QGestureExtraData* extraGestures() const
@@ -517,6 +520,12 @@ struct QGraphicsItemPrivate::TransformData {
     }
 };
 
+/*!
+    \internal
+*/
+static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{ return qt_closestLeaf(item2, item1); }
+
 /*
    return the full transform of the item to the parent.  This include the position and all the transform data
 */
@@ -527,6 +536,14 @@ inline QTransform QGraphicsItemPrivate::transformToParent() const
     return matrix;
 }
 
+inline void QGraphicsItemPrivate::ensureSortedChildren()
+{
+    if (needSortChildren) {
+        qSort(children.begin(), children.end(), qt_notclosestLeaf);
+        needSortChildren = 0;
+    }
+}
+
 QT_END_NAMESPACE
 
 #endif // QT_NO_GRAPHICSVIEW
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 8a032f4..3b1c8ad 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -375,6 +375,7 @@ void QGraphicsScenePrivate::_q_emitUpdated()
 void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 {
     needSortTopLevelItems = true;
+    item->d_ptr->siblingIndex = topLevelItems.size();
     topLevelItems.append(item);
 }
 
@@ -384,6 +385,10 @@ void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)
 {
     topLevelItems.removeOne(item);
+    // NB! Do not use topLevelItems.removeAt(item->d_ptr->siblingIndex) because
+    // the item is not guaranteed to be at the index after the list is sorted
+    // (see ensureSortedTopLevelItems()).
+    item->d_ptr->siblingIndex = -1;
 }
 
 /*!
@@ -1084,37 +1089,29 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const
                                                                            const QRectF &sceneRect)
 {
     if (indexMethod == QGraphicsScene::NoIndex || sceneRect.isNull()) {
-        if (needSortTopLevelItems) {
-            needSortTopLevelItems = false;
-            qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
-        }
+        ensureSortedTopLevelItems();
         return topLevelItems;
     }
 
-    QList<QGraphicsItem *> tmp = index->estimateItems(sceneRect, Qt::SortOrder(-1),
-                                                      viewTransform ? *viewTransform : QTransform());
-    for (int i = 0; i < tmp.size(); ++i)
-        tmp.at(i)->topLevelItem()->d_ptr->itemDiscovered = 1;
-
-    // Sort if the toplevel list is unsorted.
-    if (needSortTopLevelItems) {
-        needSortTopLevelItems = false;
-        qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
-    }
-
+    const QList<QGraphicsItem *> tmp = index->estimateItems(sceneRect, Qt::SortOrder(-1),
+                                                            viewTransform ? *viewTransform : QTransform());
+    // estimateItems returns a list of *all* items, but we are only interested
+    // in the top-levels (those that are within the rect themselves and those that
+    // have descendants within the rect).
+    // ### Look into how we can add this feature to the BSP.
     QList<QGraphicsItem *> tli;
-    for (int i = 0; i < topLevelItems.size(); ++i) {
-        // ### Investigate smarter ways. Looping through all top level
-        // items is not optimal. If the BSP tree is to have maximum
-        // effect, it should be possible to sort the subset of items
-        // quickly. We must use this approach for now, as it's the only
-        // current way to keep the stable sorting order (insertion order).
-        QGraphicsItem *item = topLevelItems.at(i);
-        if (item->d_ptr->itemDiscovered) {
-            item->d_ptr->itemDiscovered = 0;
-            tli << item;
+    for (int i = 0; i < tmp.size(); ++i) {
+        QGraphicsItem *topLevelItem = tmp.at(i)->topLevelItem();
+        if (!topLevelItem->d_ptr->itemDiscovered) {
+            tli << topLevelItem;
+            topLevelItem->d_ptr->itemDiscovered = 1;
         }
     }
+    // Reset discovered bit.
+    for (int i = 0; i < tli.size(); ++i)
+        tli.at(i)->d_ptr->itemDiscovered = 0;
+
+    qSort(tli.begin(), tli.end(), qt_notclosestLeaf);
     return tli;
 }
 
@@ -4283,10 +4280,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
 
     int i = 0;
     if (itemHasChildren) {
-        if (item->d_ptr->needSortChildren) {
-            item->d_ptr->needSortChildren = 0;
-            qStableSort(item->d_ptr->children.begin(), item->d_ptr->children.end(), qt_notclosestLeaf);
-        }
+        item->d_ptr->ensureSortedChildren();
 
         if (itemClipsChildrenToShape) {
             painter->save();
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 4842e72..23b0dd5 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -234,6 +234,14 @@ public:
         item->d_ptr->ignoreOpacity = 0;
     }
 
+    inline void ensureSortedTopLevelItems()
+    {
+        if (needSortTopLevelItems) {
+            qSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
+            needSortTopLevelItems = false;
+        }
+    }
+
     QStyle *style;
     QFont font;
     void setFont_helper(const QFont &font);
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
index c8d755e..0688cb1 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
@@ -242,7 +242,7 @@ void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stac
 {
     if (!item->d_ptr->children.isEmpty()) {
         QList<QGraphicsItem *> childList = item->d_ptr->children;
-        qStableSort(childList.begin(), childList.end(), qt_closestLeaf);
+        qSort(childList.begin(), childList.end(), qt_closestLeaf);
         for (int i = 0; i < childList.size(); ++i) {
             QGraphicsItem *item = childList.at(i);
             if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
@@ -281,7 +281,7 @@ void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
             topLevels << item;
     }
 
-    qStableSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
+    qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
     for (int i = 0; i < topLevels.size(); ++i)
         climbTree(topLevels.at(i), &stackingOrder);
 }
@@ -446,15 +446,15 @@ void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemLi
 {
     if (sortCacheEnabled) {
         if (order == Qt::AscendingOrder) {
-            qStableSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
+            qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
         } else if (order == Qt::DescendingOrder) {
-            qStableSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
+            qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
         }
     } else {
         if (order == Qt::AscendingOrder) {
-            qStableSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
+            qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
         } else if (order == Qt::DescendingOrder) {
-            qStableSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
+            qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
         }
     }
 }
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
index 7b431e6..437b17d 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -173,21 +173,13 @@ inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item
     const QGraphicsItemPrivate *d2 = item2->d_ptr;
     bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
     bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
-    if (f1 != f2) return f2;
-    qreal z1 = d1->z;
-    qreal z2 = d2->z;
-    return z1 > z2;
+    if (f1 != f2)
+        return f2;
+    if (d1->z != d2->z)
+        return d1->z > d2->z;
+    return d1->siblingIndex > d2->siblingIndex;
 }
 
-/*!
-    \internal
-*/
-static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return qt_closestLeaf(item2, item1);
-}
-
-
 static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
 {
     qreal xp = s.left();
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index b317e8e..d6281e2 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -266,10 +266,7 @@ void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QRe
     int i = 0;
     if (itemHasChildren) {
         // Sort children.
-        if (item->d_ptr->needSortChildren) {
-            item->d_ptr->needSortChildren = 0;
-            qStableSort(item->d_ptr->children.begin(), item->d_ptr->children.end(), qt_notclosestLeaf);
-        }
+        item->d_ptr->ensureSortedChildren();
 
         // Clip to shape.
         if (itemClipsChildrenToShape)