Re-organise the sorting code

The KFileItemModel-specific parts are now separated from the generic
ones, like the parallel sorting implementation.

REVIEW: 108386

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 4b31ab6a9cfb6d2fe56b3d3003ebefd3306e5064..ffb232ce286ad6dc646cd17f611606a17eb8ad35 100644 (file)
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -60,7 +60,6 @@ set(dolphinprivate_LIB_SRCS
     kitemviews/kstandarditemmodel.cpp
     kitemviews/private/kfileitemclipboard.cpp
     kitemviews/private/kfileitemmodeldirlister.cpp
     kitemviews/kstandarditemmodel.cpp
     kitemviews/private/kfileitemclipboard.cpp
     kitemviews/private/kfileitemmodeldirlister.cpp

-    kitemviews/private/kfileitemmodelsortalgorithm.cpp

     kitemviews/private/kfileitemmodelfilter.cpp
     kitemviews/private/kitemlistheaderwidget.cpp
     kitemviews/private/kitemlistkeyboardsearchmanager.cpp
     kitemviews/private/kfileitemmodelfilter.cpp
     kitemviews/private/kitemlistheaderwidget.cpp
     kitemviews/private/kitemlistkeyboardsearchmanager.cpp

diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index f46182b450690db1eb43b56e75d97604b3c0e0e2..69db217d899a9f8186bebaf33a34330af82d00ad 100644 (file)
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -657,7 +657,7 @@ void KFileItemModel::resortAllItems()
     m_items.clear();
 
     // Resort the items
     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);
     }
     for (int i = 0; i < itemCount; ++i) {
         m_items.insert(m_itemData.at(i)->item.url(), i);
     }


@@ -940,7 +940,7 @@ void KFileItemModel::insertItems(const KFileItemList& items)
     m_groups.clear();
 
     QList<ItemData*> sortedItems = createItemDataList(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();
 
 #ifdef KFILEITEMMODEL_DEBUG
     kDebug() << "[TIME] Sorting:" << timer.elapsed();


@@ -1019,7 +1019,7 @@ void KFileItemModel::removeItems(const KFileItemList& items)
             sortedItems.append(m_itemData.at(index));
         }
     }
             sortedItems.append(m_itemData.at(index));
         }
     }

-    KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
+    sort(sortedItems.begin(), sortedItems.end());

 
     QList<int> indexesToRemove;
     indexesToRemove.reserve(items.count());
 
     QList<int> indexesToRemove;
     indexesToRemove.reserve(items.count());


@@ -1345,6 +1345,44 @@ bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const
     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
 }
 
     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;
 int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
 {
     const KFileItem& itemA = a->item;

diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h
index 75fbb7075123f5883fcfacfb19b901988023ac66..304161a021d0f489751bae8f5fd9af53d4bf818e 100644 (file)
--- a/src/kitemviews/kfileitemmodel.h
+++ b/src/kitemviews/kfileitemmodel.h
@@ -341,6 +341,12 @@ private:
      */
     bool lessThan(const ItemData* a, const ItemData* b) const;
 
      */
     bool lessThan(const ItemData* a, const ItemData* b) const;
 

+    /**
+     * Sorts the items between \a begin and \a end using the comparison
+     * function lessThan().
+     */
+    void sort(QList<ItemData*>::iterator begin, QList<ItemData*>::iterator end) const;
+

     /**
      * Helper method for lessThan() and expandedParentsCountCompare(): Compares
      * the passed item-data using m_sortRole as criteria. Both items must
     /**
      * Helper method for lessThan() and expandedParentsCountCompare(): Compares
      * the passed item-data using m_sortRole as criteria. Both items must


@@ -477,7 +483,6 @@ private:
     QSet<KUrl> m_urlsToExpand;
 
     friend class KFileItemModelLessThan;       // Accesses lessThan() method
     QSet<KUrl> m_urlsToExpand;
 
     friend class KFileItemModelLessThan;       // Accesses lessThan() method

-    friend class KFileItemModelSortAlgorithm;  // Accesses NameRole

     friend class KFileItemModelRolesUpdater;   // Accesses emitSortProgress() method
     friend class KFileItemModelTest;           // For unit testing
     friend class KFileItemListViewTest;        // For unit testing
     friend class KFileItemModelRolesUpdater;   // Accesses emitSortProgress() method
     friend class KFileItemModelTest;           // For unit testing
     friend class KFileItemListViewTest;        // For unit testing

diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp b/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp
deleted file mode 100644 (file)
index ea561ae..0000000
--- a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp
+++ /dev/null
@@ -1,148 +0,0 @@
-/***************************************************************************
- *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>             *
- *                                                                         *
- *   This program is free software; you can redistribute it and/or modify  *
- *   it under the terms of the GNU General Public License as published by  *
- *   the Free Software Foundation; either version 2 of the License, or     *
- *   (at your option) any later version.                                   *
- *                                                                         *
- *   This program is distributed in the hope that it will be useful,       *
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
- *   GNU General Public License for more details.                          *
- *                                                                         *
- *   You should have received a copy of the GNU General Public License     *
- *   along with this program; if not, write to the                         *
- *   Free Software Foundation, Inc.,                                       *
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
- ***************************************************************************/
-
-#include "kfileitemmodelsortalgorithm.h"
-
-#include <QThread>
-#include <QtCore>
-
-#include <algorithm>
-
-class KFileItemModelLessThan
-{
-public:
-    KFileItemModelLessThan(KFileItemModel* model) :
-        m_model(model)
-    {
-    }
-
-    bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b)
-    {
-        return m_model->lessThan(a, b);
-    }
-
-private:
-    KFileItemModel* m_model;
-};
-
-void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
-                                       QList<KFileItemModel::ItemData*>::iterator begin,
-                                       QList<KFileItemModel::ItemData*>::iterator end)
-{
-    KFileItemModelLessThan lessThan(model);
-
-    if (model->sortRole() == model->roleForType(KFileItemModel::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();
-        parallelSort(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
-        sequentialSort(begin, end, lessThan);
-    }
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void sequentialSort(RandomAccessIterator begin,
-                           RandomAccessIterator end,
-                           LessThan lessThan)
-{
-    // The implementation is based on qStableSortHelper() from qalgorithms.h
-    // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
-    const int span = end - begin;
-    if (span < 2) {
-        return;
-    }
-
-    const RandomAccessIterator middle = begin + span / 2;
-    sequentialSort(begin, middle, lessThan);
-    sequentialSort(middle, end, lessThan);
-    merge(begin, middle, end, lessThan);
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void parallelSort(RandomAccessIterator begin,
-                         RandomAccessIterator end,
-                         LessThan lessThan,
-                         int numberOfThreads,
-                         int parallelSortingThreshold)
-{
-    const int span = end - begin;
-
-    if (numberOfThreads > 1 && span > parallelSortingThreshold) {
-        const int newNumberOfThreads = numberOfThreads / 2;
-        const RandomAccessIterator middle = begin + span / 2;
-
-        QFuture<void> future = QtConcurrent::run(parallelSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelSortingThreshold);
-        parallelSort(middle, end, lessThan, newNumberOfThreads, parallelSortingThreshold);
-
-        future.waitForFinished();
-
-        merge(begin, middle, end, lessThan);
-    } else {
-        sequentialSort(begin, end, lessThan);
-    }
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void merge(RandomAccessIterator begin,
-                  RandomAccessIterator pivot,
-                  RandomAccessIterator end,
-                  LessThan lessThan)
-{
-    // The implementation is based on qMerge() from qalgorithms.h
-    // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
-    const int len1 = pivot - begin;
-    const int len2 = end - pivot;
-
-    if (len1 == 0 || len2 == 0) {
-        return;
-    }
-
-    if (len1 + len2 == 2) {
-        if (lessThan(*(begin + 1), *(begin))) {
-            qSwap(*begin, *(begin + 1));
-        }
-        return;
-    }
-
-    RandomAccessIterator firstCut;
-    RandomAccessIterator secondCut;
-    int len2Half;
-    if (len1 > len2) {
-        const int len1Half = len1 / 2;
-        firstCut = begin + len1Half;
-        secondCut = std::lower_bound(pivot, end, *firstCut, lessThan);
-        len2Half = secondCut - pivot;
-    } else {
-        len2Half = len2 / 2;
-        secondCut = pivot + len2Half;
-        firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan);
-    }
-
-    std::rotate(firstCut, pivot, secondCut);
-
-    RandomAccessIterator newPivot = firstCut + len2Half;
-    merge(begin, firstCut, newPivot, lessThan);
-    merge(newPivot, secondCut, end, lessThan);
-}

diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.h b/src/kitemviews/private/kfileitemmodelsortalgorithm.h
index 6e6db7d5e1a65d4dffc236847b778d88ef5c5575..278c69469f84c397c652481dd64e3d1da89ede19 100644 (file)
--- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h
+++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h
@@ -1,67 +1,147 @@
-/***************************************************************************
- *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>             *
- *                                                                         *
- *   This program is free software; you can redistribute it and/or modify  *
- *   it under the terms of the GNU General Public License as published by  *
- *   the Free Software Foundation; either version 2 of the License, or     *
- *   (at your option) any later version.                                   *
- *                                                                         *
- *   This program is distributed in the hope that it will be useful,       *
- *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
- *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
- *   GNU General Public License for more details.                          *
- *                                                                         *
- *   You should have received a copy of the GNU General Public License     *
- *   along with this program; if not, write to the                         *
- *   Free Software Foundation, Inc.,                                       *
- *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
- ***************************************************************************/
+/*****************************************************************************
+ *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>               *
+ *   Copyright (C) 2012 by Emmanuel Pescosta <emmanuelpescosta099@gmail.com> *
+ *   Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com>      *
+ *                                                                           *
+ *   This program is free software; you can redistribute it and/or modify    *
+ *   it under the terms of the GNU General Public License as published by    *
+ *   the Free Software Foundation; either version 2 of the License, or       *
+ *   (at your option) any later version.                                     *
+ *                                                                           *
+ *   This program is distributed in the hope that it will be useful,         *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
+ *   GNU General Public License for more details.                            *
+ *                                                                           *
+ *   You should have received a copy of the GNU General Public License       *
+ *   along with this program; if not, write to the                           *
+ *   Free Software Foundation, Inc.,                                         *
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA              *
+ *****************************************************************************/

 
 #ifndef KFILEITEMMODELSORTALGORITHM_H
 #define KFILEITEMMODELSORTALGORITHM_H
 
 
 #ifndef KFILEITEMMODELSORTALGORITHM_H
 #define KFILEITEMMODELSORTALGORITHM_H
 

-#include <libdolphin_export.h>
+#include <QtCore>

 
 

-#include <kitemviews/kfileitemmodel.h>
+#include <algorithm>

 
 /**
 
 /**

- * @brief Sort algorithm for sorting items of KFileItemModel.
- *
- * Sorts the items by using KFileItemModel::lessThan() as comparison criteria.
- * The merge sort algorithm is used to assure a worst-case
- * of O(n * log(n)) and to keep the number of comparisons low.
+ * Sorts the items using the merge sort algorithm is used to assure a
+ * worst-case of O(n * log(n)) and to keep the number of comparisons low.

  *
  * The implementation is based on qStableSortHelper() from qalgorithms.h
  * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  * The sorting implementations of qAlgorithms could not be used as they
  * don't support having a member-function as comparison criteria.
  */
  *
  * The implementation is based on qStableSortHelper() from qalgorithms.h
  * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  * The sorting implementations of qAlgorithms could not be used as they
  * don't support having a member-function as comparison criteria.
  */

-class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm
-{
-public:
-    static void sort(KFileItemModel* model,
-                     QList<KFileItemModel::ItemData*>::iterator begin,
-                     QList<KFileItemModel::ItemData*>::iterator end);
-};

 
 template <typename RandomAccessIterator, typename LessThan>
 
 template <typename RandomAccessIterator, typename LessThan>

-static void sequentialSort(RandomAccessIterator begin,
-                           RandomAccessIterator end,
-                           LessThan lessThan);
+static void mergeSort(RandomAccessIterator begin,
+                      RandomAccessIterator end,
+                      LessThan lessThan)
+{
+    // The implementation is based on qStableSortHelper() from qalgorithms.h
+    // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+    const int span = end - begin;
+    if (span < 2) {
+        return;
+    }
+
+    const RandomAccessIterator middle = begin + span / 2;
+    mergeSort(begin, middle, lessThan);
+    mergeSort(middle, end, lessThan);
+    merge(begin, middle, end, lessThan);
+}
+
+/**
+ * Uses up to \a numberOfThreads threads to sort the items between
+ * \a begin and \a end. Only item ranges longer than
+ * \a parallelMergeSortingThreshold are split to be sorted by two different
+ * threads.
+ *
+ * The comparison function \a lessThan must be reentrant.
+ */

 
 template <typename RandomAccessIterator, typename LessThan>
 
 template <typename RandomAccessIterator, typename LessThan>

-static void parallelSort(RandomAccessIterator begin,
-                         RandomAccessIterator end,
-                         LessThan lessThan,
-                         int numberOfThreads,
-                         int parallelSortingThreshold = 100);
+static void parallelMergeSort(RandomAccessIterator begin,
+                              RandomAccessIterator end,
+                              LessThan lessThan,
+                              int numberOfThreads,
+                              int parallelMergeSortingThreshold = 100)
+{
+    const int span = end - begin;
+
+    if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
+        const int newNumberOfThreads = numberOfThreads / 2;
+        const RandomAccessIterator middle = begin + span / 2;
+
+        QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
+        parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
+
+        future.waitForFinished();
+
+        merge(begin, middle, end, lessThan);
+    } else {
+        mergeSort(begin, end, lessThan);
+    }
+}
+
+/**
+ * Merges the sorted item ranges between \a begin and \a pivot and
+ * between \a pivot and \a end into a single sorted range between
+ * \a begin and \a end.
+ *
+ * The implementation is based on qMerge() from qalgorithms.h
+ * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+ * The sorting implementations of qAlgorithms could not be used as they
+ * don't support having a member-function as comparison criteria.
+ */

 
 template <typename RandomAccessIterator, typename LessThan>
 static void merge(RandomAccessIterator begin,
                   RandomAccessIterator pivot,
                   RandomAccessIterator end,
 
 template <typename RandomAccessIterator, typename LessThan>
 static void merge(RandomAccessIterator begin,
                   RandomAccessIterator pivot,
                   RandomAccessIterator end,

-                  LessThan lessThan);
+                  LessThan lessThan)
+{
+    // The implementation is based on qMerge() from qalgorithms.h
+    // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).

 
 

-#endif
+    const int len1 = pivot - begin;
+    const int len2 = end - pivot;
+
+    if (len1 == 0 || len2 == 0) {
+        return;
+    }
+
+    if (len1 + len2 == 2) {
+        if (lessThan(*(begin + 1), *(begin))) {
+            qSwap(*begin, *(begin + 1));
+        }
+        return;
+    }
+
+    RandomAccessIterator firstCut;
+    RandomAccessIterator secondCut;
+    int len2Half;
+    if (len1 > len2) {
+        const int len1Half = len1 / 2;
+        firstCut = begin + len1Half;
+        secondCut = std::lower_bound(pivot, end, *firstCut, lessThan);
+        len2Half = secondCut - pivot;
+    } else {
+        len2Half = len2 / 2;
+        secondCut = pivot + len2Half;
+        firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan);
+    }

 
 

+    std::rotate(firstCut, pivot, secondCut);
+
+    RandomAccessIterator newPivot = firstCut + len2Half;
+    merge(begin, firstCut, newPivot, lessThan);
+    merge(newPivot, secondCut, end, lessThan);
+}
+
+#endif