From d9680ead8099df9a2b06bfed61a62923778996f2 Mon Sep 17 00:00:00 2001 From: Frank Reininghaus Date: Tue, 15 Jan 2013 18:50:21 +0100 Subject: [PATCH] Re-organise the sorting code The KFileItemModel-specific parts are now separated from the generic ones, like the parallel sorting implementation. REVIEW: 108386 --- src/CMakeLists.txt | 1 - src/kitemviews/kfileitemmodel.cpp | 44 ++++- src/kitemviews/kfileitemmodel.h | 7 +- .../private/kfileitemmodelsortalgorithm.cpp | 148 ---------------- .../private/kfileitemmodelsortalgorithm.h | 164 +++++++++++++----- 5 files changed, 169 insertions(+), 195 deletions(-) delete mode 100644 src/kitemviews/private/kfileitemmodelsortalgorithm.cpp diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 4b31ab6a9..ffb232ce2 100644 --- 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/private/kfileitemmodelsortalgorithm.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 f46182b45..69db217d8 100644 --- a/src/kitemviews/kfileitemmodel.cpp +++ b/src/kitemviews/kfileitemmodel.cpp @@ -657,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); } @@ -940,7 +940,7 @@ void KFileItemModel::insertItems(const KFileItemList& items) m_groups.clear(); QList sortedItems = createItemDataList(items); - KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); + sort(sortedItems.begin(), sortedItems.end()); #ifdef KFILEITEMMODEL_DEBUG kDebug() << "[TIME] Sorting:" << timer.elapsed(); @@ -1019,7 +1019,7 @@ void KFileItemModel::removeItems(const KFileItemList& items) sortedItems.append(m_itemData.at(index)); } } - KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); + sort(sortedItems.begin(), sortedItems.end()); QList 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; } +/** + * 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::iterator begin, + QList::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; diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h index 75fbb7075..304161a02 100644 --- a/src/kitemviews/kfileitemmodel.h +++ b/src/kitemviews/kfileitemmodel.h @@ -341,6 +341,12 @@ private: */ 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::iterator begin, QList::iterator end) const; + /** * 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 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 diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp b/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp deleted file mode 100644 index ea561aeea..000000000 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp +++ /dev/null @@ -1,148 +0,0 @@ -/*************************************************************************** - * Copyright (C) 2012 by Peter Penz * - * * - * 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 -#include - -#include - -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::iterator begin, - QList::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 -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 -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 future = QtConcurrent::run(parallelSort, begin, middle, lessThan, newNumberOfThreads, parallelSortingThreshold); - parallelSort(middle, end, lessThan, newNumberOfThreads, parallelSortingThreshold); - - future.waitForFinished(); - - merge(begin, middle, end, lessThan); - } else { - sequentialSort(begin, end, lessThan); - } -} - -template -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 6e6db7d5e..278c69469 100644 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h +++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h @@ -1,67 +1,147 @@ -/*************************************************************************** - * Copyright (C) 2012 by Peter Penz * - * * - * 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 * + * Copyright (C) 2012 by Emmanuel Pescosta * + * Copyright (C) 2013 by Frank Reininghaus * + * * + * 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 -#include +#include -#include +#include /** - * @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. */ -class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm -{ -public: - static void sort(KFileItemModel* model, - QList::iterator begin, - QList::iterator end); -}; template -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 -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 future = QtConcurrent::run(parallelMergeSort, 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 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 -- 2.47.3