From fc2ab478989fb4effc14c06aa56fdb29d3143b35 Mon Sep 17 00:00:00 2001 From: Frank Reininghaus Date: Wed, 30 Oct 2013 23:21:09 +0100 Subject: Store the selected items in a more efficient way Since Dolphin 2.0, we have stored the selected items in a QSet, which is neither space-efficient nor particularly fast when inserting many items which are in a consecutive range. This commit replaces the QSet by a new class "KItemSet", which stores the items in a sorted list of ranges. For each range, we only store the first index and the length of the range, so we need a lot less memory for most common selection patterns, and we also save quite a few CPU cycles in many situations, because adding an item to the KItemSet will in many cases not need a memory allocation at all, and it's particularly easy when inserting sorted items into the KItemSet in a row. KItemSet contains a minimal subset of QSet's API which makes it suitable as a drop-in replacement for our needs. It also has iterators, such that the items can be iterated through easily, also with foreach. One advantage of KItemSet compared to QSet is that the items are always iterated through in ascending order. REVIEW: 113488 --- src/tests/kitemlistselectionmanagertest.cpp | 100 ++++++++++++++-------------- 1 file changed, 50 insertions(+), 50 deletions(-) (limited to 'src/tests/kitemlistselectionmanagertest.cpp') diff --git a/src/tests/kitemlistselectionmanagertest.cpp b/src/tests/kitemlistselectionmanagertest.cpp index 302985a5f..af2610d8c 100644 --- a/src/tests/kitemlistselectionmanagertest.cpp +++ b/src/tests/kitemlistselectionmanagertest.cpp @@ -80,7 +80,7 @@ private slots: void testDeleteCurrentItem(); private: - void verifySelectionChange(QSignalSpy& spy, const QSet& currentSelection, const QSet& previousSelection) const; + void verifySelectionChange(QSignalSpy& spy, const KItemSet& currentSelection, const KItemSet& previousSelection) const; KItemListSelectionManager* m_selectionManager; DummyModel* m_model; @@ -127,7 +127,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 5); // Items between current and anchor should be selected now - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Change current item again and check the selection @@ -138,7 +138,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(qvariant_cast(spyCurrent.at(0).at(1)), 4); spyCurrent.takeFirst(); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 2 << 3 << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Inserting items should update current item and anchor item. @@ -155,7 +155,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 8); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 8); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8); QVERIFY(m_selectionManager->hasSelection()); // Removing items should update current item and anchor item. @@ -172,12 +172,12 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 5); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 2 << 3 << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Verify that clearSelection() also clears the anchored selection. m_selectionManager->clearSelection(); - QCOMPARE(m_selectionManager->selectedItems(), QSet()); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet()); QVERIFY(!m_selectionManager->hasSelection()); m_selectionManager->endAnchoredSelection(); @@ -212,7 +212,7 @@ void KItemListSelectionManagerTest::testItemsInserted() { // Select items 10 to 12 m_selectionManager->setSelected(10, 3); - QSet selectedItems = m_selectionManager->selectedItems(); + KItemSet selectedItems = m_selectionManager->selectedItems(); QCOMPARE(selectedItems.count(), 3); QVERIFY(selectedItems.contains(10)); QVERIFY(selectedItems.contains(11)); @@ -242,7 +242,7 @@ void KItemListSelectionManagerTest::testItemsRemoved() { // Select items 10 to 15 m_selectionManager->setSelected(10, 6); - QSet selectedItems = m_selectionManager->selectedItems(); + KItemSet selectedItems = m_selectionManager->selectedItems(); QCOMPARE(selectedItems.count(), 6); for (int i = 10; i <= 15; ++i) { QVERIFY(selectedItems.contains(i)); @@ -276,20 +276,20 @@ void KItemListSelectionManagerTest::testAnchoredSelection() m_selectionManager->setCurrentItem(6); QCOMPARE(m_selectionManager->currentItem(), 6); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6); m_selectionManager->setCurrentItem(4); QCOMPARE(m_selectionManager->currentItem(), 4); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5); m_selectionManager->setCurrentItem(7); QCOMPARE(m_selectionManager->currentItem(), 7); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7); // Ending the anchored selection should not change the selected items. m_selectionManager->endAnchoredSelection(); QVERIFY(!m_selectionManager->isAnchoredSelectionActive()); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7); // Start a new anchored selection that overlaps the previous one m_selectionManager->beginAnchoredSelection(9); @@ -298,15 +298,15 @@ void KItemListSelectionManagerTest::testAnchoredSelection() m_selectionManager->setCurrentItem(6); QCOMPARE(m_selectionManager->currentItem(), 6); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 8 << 9); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8 << 9); m_selectionManager->setCurrentItem(10); QCOMPARE(m_selectionManager->currentItem(), 10); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 9 << 10); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10); m_selectionManager->endAnchoredSelection(); QVERIFY(!m_selectionManager->isAnchoredSelectionActive()); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 9 << 10); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10); } namespace { @@ -320,7 +320,7 @@ namespace { }; } -Q_DECLARE_METATYPE(QSet); +Q_DECLARE_METATYPE(KItemSet); Q_DECLARE_METATYPE(ChangeType); Q_DECLARE_METATYPE(KItemRange); Q_DECLARE_METATYPE(KItemRangeList); @@ -355,86 +355,86 @@ Q_DECLARE_METATYPE(QList); void KItemListSelectionManagerTest::testChangeSelection_data() { - QTest::addColumn >("initialSelection"); + QTest::addColumn("initialSelection"); QTest::addColumn("anchor"); QTest::addColumn("current"); - QTest::addColumn >("expectedSelection"); + QTest::addColumn("expectedSelection"); QTest::addColumn("changeType"); QTest::addColumn >("data"); - QTest::addColumn >("finalSelection"); + QTest::addColumn("finalSelection"); QTest::newRow("No change") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << NoChange << QList() - << (QSet() << 2 << 3 << 5 << 6); + << (KItemSet() << 2 << 3 << 5 << 6); QTest::newRow("Insert Items") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << InsertItems << (QList() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(5, 2) << KItemRange(10, 5))) - << (QSet() << 3 << 4 << 8 << 9); + << (KItemSet() << 3 << 4 << 8 << 9); QTest::newRow("Remove Items") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << RemoveItems << (QList() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(3, 1) << KItemRange(10, 5))) - << (QSet() << 1 << 2 << 3 << 4); + << (KItemSet() << 1 << 2 << 3 << 4); QTest::newRow("Empty Anchored Selection") - << QSet() + << KItemSet() << 2 << 2 - << QSet() + << KItemSet() << EndAnchoredSelection << QList() - << QSet(); + << KItemSet(); QTest::newRow("Toggle selection") - << (QSet() << 1 << 3 << 4) + << (KItemSet() << 1 << 3 << 4) << 6 << 8 - << (QSet() << 1 << 3 << 4 << 6 << 7 << 8) + << (KItemSet() << 1 << 3 << 4 << 6 << 7 << 8) << SetSelected << (QList() << 0 << 10 << QVariant::fromValue(KItemListSelectionManager::Toggle)) - << (QSet() << 0 << 2 << 5 << 9); + << (KItemSet() << 0 << 2 << 5 << 9); // Swap items 2, 3 and 4, 5 QTest::newRow("Move items") - << (QSet() << 0 << 1 << 2 << 3) + << (KItemSet() << 0 << 1 << 2 << 3) << -1 << -1 - << (QSet() << 0 << 1 << 2 << 3) + << (KItemSet() << 0 << 1 << 2 << 3) << MoveItems << (QList() << QVariant::fromValue(KItemRange(2, 4)) << QVariant::fromValue(QList() << 4 << 5 << 2 << 3)) - << (QSet() << 0 << 1 << 4 << 5); + << (KItemSet() << 0 << 1 << 4 << 5); // Revert sort order QTest::newRow("Revert sort order") - << (QSet() << 0 << 1) + << (KItemSet() << 0 << 1) << 3 << 4 - << (QSet() << 0 << 1 << 3 << 4) + << (KItemSet() << 0 << 1 << 3 << 4) << MoveItems << (QList() << QVariant::fromValue(KItemRange(0, 10)) << QVariant::fromValue(QList() << 9 << 8 << 7 << 6 << 5 << 4 << 3 << 2 << 1 << 0)) - << (QSet() << 5 << 6 << 8 << 9); + << (KItemSet() << 5 << 6 << 8 << 9); } void KItemListSelectionManagerTest::testChangeSelection() { - QFETCH(QSet, initialSelection); + QFETCH(KItemSet, initialSelection); QFETCH(int, anchor); QFETCH(int, current); - QFETCH(QSet, expectedSelection); + QFETCH(KItemSet, expectedSelection); QFETCH(ChangeType, changeType); QFETCH(QList, data); - QFETCH(QSet, finalSelection); + QFETCH(KItemSet, finalSelection); - QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(QSet,QSet))); + QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(KItemSet,KItemSet))); // Initial selection should be empty QVERIFY(!m_selectionManager->hasSelection()); @@ -443,7 +443,7 @@ void KItemListSelectionManagerTest::testChangeSelection() // Perform the initial selectiion m_selectionManager->setSelectedItems(initialSelection); - verifySelectionChange(spySelectionChanged, initialSelection, QSet()); + verifySelectionChange(spySelectionChanged, initialSelection, KItemSet()); // Perform an anchored selection. // Note that current and anchor index are equal first because this is the case in typical uses of the @@ -486,7 +486,7 @@ void KItemListSelectionManagerTest::testChangeSelection() // Finally, clear the selection m_selectionManager->clearSelection(); - verifySelectionChange(spySelectionChanged, QSet(), finalSelection); + verifySelectionChange(spySelectionChanged, KItemSet(), finalSelection); } void KItemListSelectionManagerTest::testDeleteCurrentItem_data() @@ -520,8 +520,8 @@ void KItemListSelectionManagerTest::testDeleteCurrentItem() } void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy, - const QSet& currentSelection, - const QSet& previousSelection) const + const KItemSet& currentSelection, + const KItemSet& previousSelection) const { QCOMPARE(m_selectionManager->selectedItems(), currentSelection); QCOMPARE(m_selectionManager->hasSelection(), !currentSelection.isEmpty()); @@ -540,8 +540,8 @@ void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy, else { QCOMPARE(spy.count(), 1); QList arguments = spy.takeFirst(); - QCOMPARE(qvariant_cast >(arguments.at(0)), currentSelection); - QCOMPARE(qvariant_cast >(arguments.at(1)), previousSelection); + QCOMPARE(qvariant_cast(arguments.at(0)), currentSelection); + QCOMPARE(qvariant_cast(arguments.at(1)), previousSelection); } } -- cgit v1.3