Make sure that KItemListSizeHintResolver is always consistent

This was the root cause of bug 317827. The assert tried to make sure
that we never access KItemListSizeHintResolver from
KItemListViewLayouter inside the loop over the item ranges. This would
be dangerous because it might be in an inconsistent state - the removed
item ranges were removed step by step, so accessing the item size hints
before the operation was finished could lead to wrong results.

The solution is to insert/remove all item ranges immediately. A nice
side effect is that there are no sources of O(N^2) complexity in
KItemListSizeHintResolver any more if many item ranges are
inserted/removed.

BUG: 317827
FIXED-IN: 4.11.0
REVIEW: 111382

1 files changed, 65 insertions, 11 deletions

diff --git a/src/kitemviews/private/kitemlistsizehintresolver.cpp b/src/kitemviews/private/kitemlistsizehintresolver.cpp
index e075b46d0..5db87f34d 100644
--- a/src/kitemviews/private/kitemlistsizehintresolver.cpp
+++ b/src/kitemviews/private/kitemlistsizehintresolver.cpp
@@ -20,7 +20,6 @@
 #include "kitemlistsizehintresolver.h"
 
 #include <kitemviews/kitemlistview.h>
-#include <KDebug>
 
 KItemListSizeHintResolver::KItemListSizeHintResolver(const KItemListView* itemListView) :
     m_itemListView(itemListView),
@@ -42,22 +41,77 @@ QSizeF KItemListSizeHintResolver::sizeHint(int index) const
     return size;
 }
 
-void KItemListSizeHintResolver::itemsInserted(int index, int count)
+void KItemListSizeHintResolver::itemsInserted(const KItemRangeList& itemRanges)
 {
+    int insertedCount = 0;
+    foreach (const KItemRange& range, itemRanges) {
+        insertedCount += range.count;
+    }
+
     const int currentCount = m_sizeHintCache.count();
-    m_sizeHintCache.reserve(currentCount + count);
-    while (count > 0) {
-        m_sizeHintCache.insert(index, QSizeF());
-        ++index;
-        --count;
+    m_sizeHintCache.reserve(currentCount + insertedCount);
+
+    // We build the new list from the end to the beginning to mimize the
+    // number of moves.
+    m_sizeHintCache.insert(m_sizeHintCache.end(), insertedCount, QSizeF());
+
+    int sourceIndex = currentCount - 1;
+    int targetIndex = m_sizeHintCache.count() - 1;
+    int itemsToInsertBeforeCurrentRange = insertedCount;
+
+    for (int rangeIndex = itemRanges.count() - 1; rangeIndex >= 0; --rangeIndex) {
+        const KItemRange& range = itemRanges.at(rangeIndex);
+        itemsToInsertBeforeCurrentRange -= range.count;
+
+        // First: move all existing items that must be put behind 'range'.
+        while (targetIndex >= itemsToInsertBeforeCurrentRange + range.index + range.count) {
+            m_sizeHintCache[targetIndex] = m_sizeHintCache[sourceIndex];
+            --sourceIndex;
+            --targetIndex;
+        }
+
+        // Then: insert QSizeF() for the items which are inserted into 'range'.
+        while (targetIndex >= itemsToInsertBeforeCurrentRange + range.index) {
+            m_sizeHintCache[targetIndex] = QSizeF();
+            --targetIndex;
+        }
     }
+
+    Q_ASSERT(m_sizeHintCache.count() == m_itemListView->model()->count());
 }
 
-void KItemListSizeHintResolver::itemsRemoved(int index, int count)
+void KItemListSizeHintResolver::itemsRemoved(const KItemRangeList& itemRanges)
 {
-    const QVector<QSizeF>::iterator begin = m_sizeHintCache.begin() + index;
-    const QVector<QSizeF>::iterator end = begin + count;
-    m_sizeHintCache.erase(begin, end);
+    const QVector<QSizeF>::iterator begin = m_sizeHintCache.begin();
+    const QVector<QSizeF>::iterator end = m_sizeHintCache.end();
+
+    KItemRangeList::const_iterator rangeIt = itemRanges.constBegin();
+    const KItemRangeList::const_iterator rangeEnd = itemRanges.constEnd();
+
+    QVector<QSizeF>::iterator destIt = begin + rangeIt->index;
+    QVector<QSizeF>::iterator srcIt = destIt + rangeIt->count;
+
+    ++rangeIt;
+
+    while (srcIt != end) {
+        *destIt = *srcIt;
+        ++destIt;
+        ++srcIt;
+
+        if (rangeIt != rangeEnd && srcIt == begin + rangeIt->index) {
+            // Skip the items in the next removed range.
+            srcIt += rangeIt->count;
+            ++rangeIt;
+        }
+    }
+
+    m_sizeHintCache.erase(destIt, end);
+
+    // Note that the cache size might temporarily not match the model size if
+    // this function is called from KItemListView::setModel() to empty the cache.
+    if (!m_sizeHintCache.isEmpty() && m_itemListView->model()) {
+        Q_ASSERT(m_sizeHintCache.count() == m_itemListView->model()->count());
+    }
 }
 
 void KItemListSizeHintResolver::itemsMoved(int index, int count)