X-Git-Url: https://cloud.milkyroute.net/gitweb/dolphin.git/blobdiff_plain/6a3f8086a372ca1c21ab474c7934e8f8e4b238f5..954e8c47906c12edaaf6e6aebdd41516eceb0d44:/src/kitemviews/private/kfileitemmodelsortalgorithm.h diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.h b/src/kitemviews/private/kfileitemmodelsortalgorithm.h index 07e5d4a81..4ee6095ca 100644 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h +++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h @@ -1,79 +1,132 @@ -/*************************************************************************** - * 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 * - ***************************************************************************/ +/* + * SPDX-FileCopyrightText: 2012 Peter Penz + * SPDX-FileCopyrightText: 2012 Emmanuel Pescosta + * SPDX-FileCopyrightText: 2013 Frank Reininghaus + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ #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. + * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies). */ -class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm + +template +static void mergeSort(RandomAccessIterator begin, + RandomAccessIterator end, + const LessThan& lessThan) { -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); - - static QList::iterator - lowerBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value); - - static QList::iterator - upperBound(KFileItemModel* model, - QList::iterator begin, - QList::iterator end, - const KFileItemModel::ItemData* value); - - static void reverse(QList::iterator begin, - QList::iterator end); -}; + // The implementation is based on qStableSortHelper() from qalgorithms.h + // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies). -#endif + 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 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 + * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies). + */ + +template +static void merge(RandomAccessIterator begin, + RandomAccessIterator pivot, + RandomAccessIterator end, + const LessThan& lessThan) +{ + // The implementation is based on qMerge() from qalgorithms.h + // SPDX-FileCopyrightText: 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); +} + +#endif