1 files changed, 137 insertions, 54 deletions

diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index 6c015db37..ab39e55e5 100644
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -58,7 +58,6 @@ KFileItemModel::KFileItemModel(QObject* parent) :
     m_urlsToExpand()
 {
     m_dirLister = new KFileItemModelDirLister(this);
-    m_dirLister->setAutoUpdate(true);
     m_dirLister->setDelayedMimeTypes(true);
 
     const QWidget* parentWidget = qobject_cast<QWidget*>(parent);
@@ -658,7 +657,7 @@ void KFileItemModel::resortAllItems()
     m_items.clear();
 
     // Resort the items
-    KFileItemModelSortAlgorithm::sort(this, m_itemData.begin(), m_itemData.end());
+    sort(m_itemData.begin(), m_itemData.end());
     for (int i = 0; i < itemCount; ++i) {
         m_items.insert(m_itemData.at(i)->item.url(), i);
     }
@@ -941,7 +940,7 @@ void KFileItemModel::insertItems(const KFileItemList& items)
     m_groups.clear();
 
     QList<ItemData*> sortedItems = createItemDataList(items);
-    KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
+    sort(sortedItems.begin(), sortedItems.end());
 
 #ifdef KFILEITEMMODEL_DEBUG
     kDebug() << "[TIME] Sorting:" << timer.elapsed();
@@ -1000,6 +999,36 @@ void KFileItemModel::insertItems(const KFileItemList& items)
 #endif
 }
 
+static KItemRangeList sortedIndexesToKItemRangeList(const QList<int> sortedNumbers)
+{
+    if (sortedNumbers.empty()) {
+        return KItemRangeList();
+    }
+
+    KItemRangeList result;
+
+    QList<int>::const_iterator it = sortedNumbers.begin();
+    int index = *it;
+    int count = 1;
+
+    ++it;
+
+    QList<int>::const_iterator end = sortedNumbers.end();
+    while (it != end) {
+        if (*it == index + count) {
+            ++count;
+        } else {
+            result << KItemRange(index, count);
+            index = *it;
+            count = 1;
+        }
+        ++it;
+    }
+
+    result << KItemRange(index, count);
+    return result;
+}
+
 void KFileItemModel::removeItems(const KFileItemList& items)
 {
     if (items.isEmpty()) {
@@ -1012,68 +1041,55 @@ void KFileItemModel::removeItems(const KFileItemList& items)
 
     m_groups.clear();
 
-    QList<ItemData*> sortedItems;
-    sortedItems.reserve(items.count());
-    foreach (const KFileItem& item, items) {
-        const int index = m_items.value(item.url(), -1);
-        if (index >= 0) {
-            sortedItems.append(m_itemData.at(index));
-        }
-    }
-    KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
-
+    // Step 1: Determine the indexes of the removed items, remove them from
+    //         the hash m_items, and free the ItemData.
     QList<int> indexesToRemove;
     indexesToRemove.reserve(items.count());
+    foreach (const KFileItem& item, items) {
+        const KUrl url = item.url();
+        const int index = m_items.value(url, -1);
+        if (index >= 0) {
+            indexesToRemove.append(index);
 
-    // Calculate the item ranges that will get deleted
-    KItemRangeList itemRanges;
-    int removedAtIndex = -1;
-    int removedCount = 0;
-    int targetIndex = 0;
-    foreach (const ItemData* itemData, sortedItems) {
-        const KFileItem& itemToRemove = itemData->item;
+            // Prevent repeated expensive rehashing by using QHash::erase(),
+            // rather than QHash::remove().
+            QHash<KUrl, int>::iterator it = m_items.find(url);
+            m_items.erase(it);
 
-        const int previousTargetIndex = targetIndex;
-        while (targetIndex < m_itemData.count()) {
-            if (m_itemData.at(targetIndex)->item.url() == itemToRemove.url()) {
-                break;
-            }
-            ++targetIndex;
-        }
-        if (targetIndex >= m_itemData.count()) {
+            ItemData* data = m_itemData.at(index);
+            delete data;
+            m_itemData[index] = 0;
+        } else {
             kWarning() << "Item that should be deleted has not been found!";
-            return;
-        }
-
-        if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
-            itemRanges << KItemRange(removedAtIndex, removedCount);
-            removedAtIndex = targetIndex;
-            removedCount = 0;
-        }
-
-        indexesToRemove.append(targetIndex);
-        if (removedAtIndex < 0) {
-            removedAtIndex = targetIndex;
         }
-        ++removedCount;
-        ++targetIndex;
     }
 
-    // Delete the items
-    for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
-        const int indexToRemove = indexesToRemove.at(i);
-        ItemData* data = m_itemData.at(indexToRemove);
+    std::sort(indexesToRemove.begin(), indexesToRemove.end());
 
-        m_items.remove(data->item.url());
+    // Step 2: Remove the ItemData pointers from the list m_itemData.
+    const KItemRangeList itemRanges = sortedIndexesToKItemRangeList(indexesToRemove);
+    int target = itemRanges.at(0).index;
+    int source = itemRanges.at(0).index + itemRanges.at(0).count;
+    int nextRange = 1;
 
-        delete data;
-        m_itemData.removeAt(indexToRemove);
+    const int oldItemDataCount = m_itemData.count();
+    while (source < oldItemDataCount) {
+        if (nextRange < itemRanges.count() - 1 && source == itemRanges.at(nextRange).index) {
+            // Skip the items in the next removed range.
+            source += itemRanges.at(nextRange).count;
+            ++nextRange;
+        }
+        m_itemData[target] = m_itemData[source];
+        ++target;
+        ++source;
     }
 
-    // The indexes of all m_items must be adjusted, not only the index
-    // of the removed items
-    const int itemDataCount = m_itemData.count();
-    for (int i = 0; i < itemDataCount; ++i) {
+    m_itemData.erase(m_itemData.end() - indexesToRemove.count(), m_itemData.end());
+
+    // Step 3: Adjust indexes in the hash m_items. Note that all indexes
+    //         might have been changed by the removal of the items.
+    const int newItemDataCount = m_itemData.count();
+    for (int i = 0; i < newItemDataCount; ++i) {
         m_items.insert(m_itemData.at(i)->item.url(), i);
     }
 
@@ -1081,7 +1097,6 @@ void KFileItemModel::removeItems(const KFileItemList& items)
         m_expandedParentsCountRoot = UninitializedExpandedParentsCountRoot;
     }
 
-    itemRanges << KItemRange(removedAtIndex, removedCount);
     emit itemsRemoved(itemRanges);
 }
 
@@ -1346,6 +1361,44 @@ bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const
     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
 }
 
+/**
+ * Helper class for KFileItemModel::sort().
+ */
+class KFileItemModelLessThan
+{
+public:
+    KFileItemModelLessThan(const KFileItemModel* model) :
+        m_model(model)
+    {
+    }
+
+    bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const
+    {
+        return m_model->lessThan(a, b);
+    }
+
+private:
+    const KFileItemModel* m_model;
+};
+
+void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin,
+                          QList<KFileItemModel::ItemData*>::iterator end) const
+{
+    KFileItemModelLessThan lessThan(this);
+
+    if (m_sortRole == NameRole) {
+        // Sorting by name can be expensive, in particular if natural sorting is
+        // enabled. Use all CPU cores to speed up the sorting process.
+        static const int numberOfThreads = QThread::idealThreadCount();
+        parallelMergeSort(begin, end, lessThan, numberOfThreads);
+    } else {
+        // Sorting by other roles is quite fast. Use only one thread to prevent
+        // problems caused by non-reentrant comparison functions, see
+        // https://bugs.kde.org/show_bug.cgi?id=312679
+        mergeSort(begin, end, lessThan);
+    }
+}
+
 int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
 {
     const KFileItem& itemA = a->item;
@@ -1963,4 +2016,34 @@ void KFileItemModel::determineMimeTypes(const KFileItemList& items, int timeout)
     }
 }
 
+bool KFileItemModel::isConsistent() const
+{
+    // Check that m_items and m_itemData are consistent, and that the items are sorted.
+    if (m_items.count() != m_itemData.count()) {
+        return false;
+    }
+
+    for (int i = 0; i < count(); ++i) {
+        const KFileItem item = fileItem(i);
+        if (item.isNull()) {
+            qWarning() << "Item" << i << "is null";
+            return false;
+        }
+
+        const int itemIndex = index(item);
+        if (itemIndex != i) {
+            qWarning() << "Item" << i << "has a wrong index:" << itemIndex;
+            return false;
+        }
+
+        if (i > 0 && !lessThan(m_itemData.at(i - 1), m_itemData.at(i))) {
+            qWarning() << "The order of items" << i - 1 << "and" << i << "is wrong:"
+                << fileItem(i - 1) << fileItem(i);
+            return false;
+        }
+    }
+
+    return true;
+}
+
 #include "kfileitemmodel.moc"