From: Frank Reininghaus Date: Tue, 15 Jan 2013 17:47:00 +0000 (+0100) Subject: Change the sort and merge functions to a more generic form. X-Git-Url: https://cloud.milkyroute.net/gitweb/dolphin.git/commitdiff_plain/87ac18f0310c12f031dc7c639737473643a6ddc9 Change the sort and merge functions to a more generic form. This might make it easier to reuse the parallel sorting code. Moreover, some the upperBound/lowerBound functions have been removed because equivalents are provided by the STL. --- diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h index ef9dc98b9..75fbb7075 100644 --- a/src/kitemviews/kfileitemmodel.h +++ b/src/kitemviews/kfileitemmodel.h @@ -476,7 +476,8 @@ private: // and done step after step in slotCompleted(). QSet m_urlsToExpand; - friend class KFileItemModelSortAlgorithm; // Accesses lessThan() method + 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 index a09d0cd80..ea561aeea 100644 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp +++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp @@ -24,26 +24,46 @@ #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(model, begin, end, numberOfThreads); + 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(model, begin, end); + sequentialSort(begin, end, lessThan); } } -void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model, - QList< KFileItemModel::ItemData* >::iterator begin, - QList< KFileItemModel::ItemData* >::iterator end) +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). @@ -53,38 +73,41 @@ void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model, return; } - const QList::iterator middle = begin + span / 2; - sequentialSort(model, begin, middle); - sequentialSort(model, middle, end); - merge(model, begin, middle, end); + const RandomAccessIterator middle = begin + span / 2; + sequentialSort(begin, middle, lessThan); + sequentialSort(middle, end, lessThan); + merge(begin, middle, end, lessThan); } -void KFileItemModelSortAlgorithm::parallelSort(KFileItemModel* model, - QList< KFileItemModel::ItemData* >::iterator begin, - QList< KFileItemModel::ItemData* >::iterator end, - const int numberOfThreads) +template +static void parallelSort(RandomAccessIterator begin, + RandomAccessIterator end, + LessThan lessThan, + int numberOfThreads, + int parallelSortingThreshold) { const int span = end - begin; - if (numberOfThreads > 1 && span > 100) { + if (numberOfThreads > 1 && span > parallelSortingThreshold) { const int newNumberOfThreads = numberOfThreads / 2; - const QList::iterator middle = begin + span / 2; + const RandomAccessIterator middle = begin + span / 2; - QFuture future = QtConcurrent::run(parallelSort, model, begin, middle, newNumberOfThreads); - parallelSort(model, middle, end, newNumberOfThreads); + QFuture future = QtConcurrent::run(parallelSort, begin, middle, lessThan, newNumberOfThreads, parallelSortingThreshold); + parallelSort(middle, end, lessThan, newNumberOfThreads, parallelSortingThreshold); future.waitForFinished(); - merge(model, begin, middle, end); + merge(begin, middle, end, lessThan); } else { - sequentialSort(model, begin, end); + sequentialSort(begin, end, lessThan); } } -void KFileItemModelSortAlgorithm::merge(KFileItemModel* model, - QList::iterator begin, - QList::iterator pivot, - QList::iterator end) +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). @@ -97,82 +120,29 @@ void KFileItemModelSortAlgorithm::merge(KFileItemModel* model, } if (len1 + len2 == 2) { - if (model->lessThan(*(begin + 1), *(begin))) { + if (lessThan(*(begin + 1), *(begin))) { qSwap(*begin, *(begin + 1)); } return; } - QList::iterator firstCut; - QList::iterator secondCut; + RandomAccessIterator firstCut; + RandomAccessIterator secondCut; int len2Half; if (len1 > len2) { const int len1Half = len1 / 2; firstCut = begin + len1Half; - secondCut = lowerBound(model, pivot, end, *firstCut); + secondCut = std::lower_bound(pivot, end, *firstCut, lessThan); len2Half = secondCut - pivot; } else { len2Half = len2 / 2; secondCut = pivot + len2Half; - firstCut = upperBound(model, begin, pivot, *secondCut); + firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan); } std::rotate(firstCut, pivot, secondCut); - const QList::iterator newPivot = firstCut + len2Half; - merge(model, begin, firstCut, newPivot); - merge(model, newPivot, secondCut, end); -} - - -QList::iterator -KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value) -{ - // The implementation is based on qLowerBound() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - QList::iterator middle; - int n = int(end - begin); - int half; - - while (n > 0) { - half = n >> 1; - middle = begin + half; - if (model->lessThan(*middle, value)) { - begin = middle + 1; - n -= half + 1; - } else { - n = half; - } - } - return begin; -} - -QList::iterator -KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value) -{ - // The implementation is based on qUpperBound() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - QList::iterator middle; - int n = end - begin; - int half; - - while (n > 0) { - half = n >> 1; - middle = begin + half; - if (model->lessThan(value, *middle)) { - n = half; - } else { - begin = middle + 1; - n -= half + 1; - } - } - return begin; + 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 b86d490aa..6e6db7d5e 100644 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h +++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h @@ -42,34 +42,25 @@ public: static void sort(KFileItemModel* model, QList::iterator begin, QList::iterator end); +}; -private: - static void sequentialSort(KFileItemModel* model, - QList::iterator begin, - QList::iterator end); - - static void parallelSort(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const int numberOfThreads); - - static void merge(KFileItemModel* model, - QList::iterator begin, - QList::iterator pivot, - QList::iterator end); +template +static void sequentialSort(RandomAccessIterator begin, + RandomAccessIterator end, + LessThan lessThan); - static QList::iterator - lowerBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value); +template +static void parallelSort(RandomAccessIterator begin, + RandomAccessIterator end, + LessThan lessThan, + int numberOfThreads, + int parallelSortingThreshold = 100); - static QList::iterator - upperBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value); -}; +template +static void merge(RandomAccessIterator begin, + RandomAccessIterator pivot, + RandomAccessIterator end, + LessThan lessThan); #endif