Remove siblingIndex and use stable sorting instead.

To avoid sorting siblings in real-time, ensure we lazily sort the list
in place when needed.

Reviewed-by: bnilsen

4 files changed, 24 insertions, 28 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index c3744b2..9159381 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -1997,15 +1997,16 @@ qreal QGraphicsItem::effectiveOpacity() const
     if (!d_ptr->parent)
         return d_ptr->opacity;
 
-    QGraphicsItem::GraphicsItemFlags myFlags = flags();
-    QGraphicsItem::GraphicsItemFlags parentFlags = d_ptr->parent ? d_ptr->parent->flags() : QGraphicsItem::GraphicsItemFlags(0);
+    int myFlags = d_ptr->flags;
+    int parentFlags = d_ptr->parent ? d_ptr->parent->d_ptr->flags : 0;
 
     // If I have a parent, and I don't ignore my parent's opacity, and my
     // parent propagates to me, then combine my local opacity with my parent's
     // effective opacity into my effective opacity.
     if (!(myFlags & QGraphicsItem::ItemIgnoresParentOpacity)
-        && !(parentFlags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren))
+        && !(parentFlags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren)) {
         return d_ptr->opacity * d_ptr->parent->effectiveOpacity();
+    }
 
     return d_ptr->opacity;
 }
@@ -3793,7 +3794,7 @@ void QGraphicsItemPrivate::resolveDepth(int parentDepth)
 */
 void QGraphicsItemPrivate::addChild(QGraphicsItem *child)
 {
-    child->d_ptr->siblingIndex = children.size();
+    needSortChildren = 1;
     children.append(child);
 }
 
@@ -3802,14 +3803,7 @@ void QGraphicsItemPrivate::addChild(QGraphicsItem *child)
 */
 void QGraphicsItemPrivate::removeChild(QGraphicsItem *child)
 {
-    int idx = child->d_ptr->siblingIndex;
-    int size = children.size();
-    for (int i = idx; i < size - 1; ++i) {
-        QGraphicsItem *p = children[i + 1];
-        children[i] = p;
-        p->d_ptr->siblingIndex = i;
-    }
-    children.removeLast();
+    children.removeOne(child);
 }
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index deaf30f..80b1fb4 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -116,7 +116,6 @@ public:
         scene(0),
         parent(0),
         transform(0),
-        siblingIndex(-1),
         index(-1),
         depth(0),
         acceptedMouseButtons(0x1f),
@@ -141,6 +140,7 @@ public:
         dirtyClipPath(1),
         emptyClipPath(0),
         inSetPosHelper(0),
+        needSortChildren(1),
         flags(0),
         dirtyChildrenBoundingRect(1),
         inDirtyList(0),
@@ -312,7 +312,6 @@ public:
     QList<QGraphicsItem *> children;
     QTransform *transform;
     QTransform deviceTransform;
-    int siblingIndex;
     int index;
     int depth;
 
@@ -339,7 +338,8 @@ public:
     quint32 dirtyClipPath : 1;
     quint32 emptyClipPath : 1;
     quint32 inSetPosHelper : 1;
-    quint32 unused : 3;
+    quint32 needSortChildren : 1;
+    quint32 unused : 2;
 
     // New 32 bits
     quint32 flags : 11;
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 434cc8e..52dc152 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -339,6 +339,7 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       calledEmitUpdated(false),
       processDirtyItemsEmitted(false),
       selectionChanging(0),
+      needSortTopLevelItems(true),
       regenerateIndex(true),
       purgePending(false),
       indexTimerId(0),
@@ -631,7 +632,7 @@ void QGraphicsScenePrivate::_q_emitUpdated()
 */
 void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 {
-    item->d_ptr->siblingIndex = topLevelItems.size();
+    needSortTopLevelItems = true;
     topLevelItems.append(item);
 }
 
@@ -640,14 +641,7 @@ void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 */
 void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)
 {
-    int idx = item->d_ptr->siblingIndex;
-    int size = topLevelItems.size();
-    for (int i = idx; i < size - 1; ++i) {
-        QGraphicsItem *p = topLevelItems[i + 1];
-        topLevelItems[i] = p;
-        p->d_ptr->siblingIndex = i;
-    }
-    topLevelItems.removeLast();
+    topLevelItems.removeOne(item);
 }
 
 /*!
@@ -1910,7 +1904,7 @@ inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item
     if (f1 != f2) return f2;
     qreal z1 = d1->z;
     qreal z2 = d2->z;
-    return z1 != z2 ? z1 > z2 : d1->siblingIndex > d2->siblingIndex;
+    return z1 > z2;
 }
 
 static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
@@ -5100,9 +5094,16 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     }
 
     // Find and sort children.
-    QList<QGraphicsItem *> children = item ? item->d_ptr->children : topLevelItems;
-    if (!dontDrawChildren)
-        qSort(children.begin(), children.end(), qt_notclosestLeaf);
+    QList<QGraphicsItem *> &children = item ? item->d_ptr->children : topLevelItems;
+    if (!dontDrawChildren) {
+        if (item && item->d_ptr->needSortChildren) {
+            item->d_ptr->needSortChildren = 0;
+            qStableSort(children.begin(), children.end(), qt_notclosestLeaf);
+        } else if (!item && needSortTopLevelItems) {
+            needSortTopLevelItems = false;
+            qStableSort(children.begin(), children.end(), qt_notclosestLeaf);
+        }
+    }
 
     // Draw children behind
     int i;
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 50c716c..e7e96f5 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -116,6 +116,7 @@ public:
     QList<QGraphicsItem *> pendingUpdateItems;
     QList<QGraphicsItem *> unpolishedItems;
     QList<QGraphicsItem *> topLevelItems;
+    bool needSortTopLevelItems;
     QMap<QGraphicsItem *, QPointF> movingItemsInitialPositions;
     void registerTopLevelItem(QGraphicsItem *item);
     void unregisterTopLevelItem(QGraphicsItem *item);