From c4ae87721e011fe44f301c4039f0651a05394162 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B8rn=20Erik=20Nilsen?= Date: Thu, 2 Jul 2009 14:59:51 +0200 Subject: 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 --- src/gui/graphicsview/qgraphicsitem.cpp | 5 +++ src/gui/graphicsview/qgraphicsitem_p.h | 17 +++++++ src/gui/graphicsview/qgraphicsscene.cpp | 52 ++++++++++------------ src/gui/graphicsview/qgraphicsscene_p.h | 8 ++++ .../graphicsview/qgraphicsscenebsptreeindex.cpp | 12 ++--- .../graphicsview/qgraphicsscenebsptreeindex_p.h | 18 +++----- src/gui/graphicsview/qgraphicssceneindex.cpp | 5 +-- 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 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 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 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 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 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 *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) -- cgit v0.12