summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorDimitar Asenov <dimitar.asenov@gmail.com>2014-06-07 03:53:51 -0700
committerIsmo Haataja <ismo.haataja@digia.com>2014-06-16 09:58:58 +0200
commitbf2ec0183cb62034f2a4e700b7ab741371fcb106 (patch)
tree9a5e9d4e3f4485e23d8d034f52f530e6cb79a21d /src
parent4e7baaaa91ce663b0b5c315e5b049d1574aef73f (diff)
Speed up the removal of items from a QGraphicsScene
When using a linear index, all items in a scene are stored in a QList. While adding new items is a constant operation, removal requires a traversal through the entire list. This is especially problematic when the scene contains millions of items and many of them are removed, which requires a linear search for each item, resulting in a very slow operation. Moreover, this behavior is actually inconsistent with the current documentation which states for the linear index: "Adding, moving and removing items, however, is done in constant time." Instead of removing items from the list in the index, this patch just marks the list as invalid. The next time the list is required it will be rebuilt from scratch by traversing all items from the scene. This new behavior more accurately matches the documentation. Testing this change in a scene with over 1 million objects, resulted in a massive speed up, effectively eliminating the overhead of item removal. [ChangeLog][QtWidgets][QGraphicsScene] Speed up the removal of items when using the linear index. Change-Id: I95c7b90b9f1fe426018695b6429138530e6d2f3e Reviewed-by: Andreas Aardal Hanssen <andreas@hanssen.name>
Diffstat (limited to 'src')
-rw-r--r--src/widgets/graphicsview/qgraphicsscene.h1
-rw-r--r--src/widgets/graphicsview/qgraphicsscenelinearindex_p.h45
2 files changed, 39 insertions, 7 deletions
diff --git a/src/widgets/graphicsview/qgraphicsscene.h b/src/widgets/graphicsview/qgraphicsscene.h
index ba47d45d63..d95237baef 100644
--- a/src/widgets/graphicsview/qgraphicsscene.h
+++ b/src/widgets/graphicsview/qgraphicsscene.h
@@ -313,6 +313,7 @@ private:
friend class QGraphicsEffect;
friend class QGraphicsSceneIndex;
friend class QGraphicsSceneIndexPrivate;
+ friend class QGraphicsSceneLinearIndex;
friend class QGraphicsSceneBspTreeIndex;
friend class QGraphicsSceneBspTreeIndexPrivate;
friend class QGraphicsItemEffectSourcePrivate;
diff --git a/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h b/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
index 7debcfb501..baf3de3755 100644
--- a/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/widgets/graphicsview/qgraphicsscenelinearindex_p.h
@@ -70,31 +70,62 @@ class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex
Q_OBJECT
public:
- QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0) : QGraphicsSceneIndex(scene)
+ QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0) : QGraphicsSceneIndex(scene), m_itemsIsValid(true)
{ }
QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const
- { Q_UNUSED(order); return m_items; }
+ {
+ Q_UNUSED(order);
+ return validList();
+ }
virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const
{
Q_UNUSED(rect);
Q_UNUSED(order);
- return m_items;
+ return validList();
}
protected :
virtual void clear()
- { m_items.clear(); }
+ {
+ m_items.clear();
+ m_itemsIsValid = true;
+ }
virtual void addItem(QGraphicsItem *item)
- { m_items << item; }
+ {
+ if (m_itemsIsValid)
+ m_items << item;
+ }
virtual void removeItem(QGraphicsItem *item)
- { m_items.removeOne(item); }
+ {
+ Q_UNUSED(item);
+ m_itemsIsValid = false;
+ }
private:
- QList<QGraphicsItem*> m_items;
+ mutable QList<QGraphicsItem*> m_items;
+ mutable bool m_itemsIsValid;
+
+ QList<QGraphicsItem*>& validList() const
+ {
+ if (!m_itemsIsValid)
+ {
+ m_items.clear();
+
+ QList<QGraphicsItem*> stack = scene()->d_func()->topLevelItems;
+ m_items << stack;
+ while (!stack.isEmpty())
+ {
+ m_items << stack.last()->childItems();
+ stack << stack.takeLast()->childItems();
+ }
+ m_itemsIsValid = true;
+ }
+ return m_items;
+ }
};
#endif // QT_NO_GRAPHICSVIEW