src/kitemviews/private/kfileitemmodelsortalgorithm.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>             *
   3  *                                                                         *
   4  *   This program is free software; you can redistribute it and/or modify  *
   5  *   it under the terms of the GNU General Public License as published by  *
   6  *   the Free Software Foundation; either version 2 of the License, or     *
   7  *   (at your option) any later version.                                   *
   8  *                                                                         *
   9  *   This program is distributed in the hope that it will be useful,       *
  10  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  12  *   GNU General Public License for more details.                          *
  13  *                                                                         *
  14  *   You should have received a copy of the GNU General Public License     *
  15  *   along with this program; if not, write to the                         *
  16  *   Free Software Foundation, Inc.,                                       *
  17  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
  18  ***************************************************************************/
  19
  20 #include "kfileitemmodelsortalgorithm.h"
  21
  22 #include <QThread>
  23 #include <QtCore>
  24
  25 #include <algorithm>
  26
  27 class KFileItemModelLessThan
  28 {
  29 public:
  30     KFileItemModelLessThan(KFileItemModel* model) :
  31         m_model(model)
  32     {
  33     }
  34
  35     bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b)
  36     {
  37         return m_model->lessThan(a, b);
  38     }
  39
  40 private:
  41     KFileItemModel* m_model;
  42 };
  43
  44 void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
  45                                        QList<KFileItemModel::ItemData*>::iterator begin,
  46                                        QList<KFileItemModel::ItemData*>::iterator end)
  47 {
  48     KFileItemModelLessThan lessThan(model);
  49
  50     if (model->sortRole() == model->roleForType(KFileItemModel::NameRole)) {
  51         // Sorting by name can be expensive, in particular if natural sorting is
  52         // enabled. Use all CPU cores to speed up the sorting process.
  53         static const int numberOfThreads = QThread::idealThreadCount();
  54         parallelSort(begin, end, lessThan, numberOfThreads);
  55     } else {
  56         // Sorting by other roles is quite fast. Use only one thread to prevent
  57         // problems caused by non-reentrant comparison functions, see
  58         // https://bugs.kde.org/show_bug.cgi?id=312679
  59         sequentialSort(begin, end, lessThan);
  60     }
  61 }
  62
  63 template <typename RandomAccessIterator, typename LessThan>
  64 static void sequentialSort(RandomAccessIterator begin,
  65                            RandomAccessIterator end,
  66                            LessThan lessThan)
  67 {
  68     // The implementation is based on qStableSortHelper() from qalgorithms.h
  69     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  70
  71     const int span = end - begin;
  72     if (span < 2) {
  73         return;
  74     }
  75
  76     const RandomAccessIterator middle = begin + span / 2;
  77     sequentialSort(begin, middle, lessThan);
  78     sequentialSort(middle, end, lessThan);
  79     merge(begin, middle, end, lessThan);
  80 }
  81
  82 template <typename RandomAccessIterator, typename LessThan>
  83 static void parallelSort(RandomAccessIterator begin,
  84                          RandomAccessIterator end,
  85                          LessThan lessThan,
  86                          int numberOfThreads,
  87                          int parallelSortingThreshold)
  88 {
  89     const int span = end - begin;
  90
  91     if (numberOfThreads > 1 && span > parallelSortingThreshold) {
  92         const int newNumberOfThreads = numberOfThreads / 2;
  93         const RandomAccessIterator middle = begin + span / 2;
  94
  95         QFuture<void> future = QtConcurrent::run(parallelSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelSortingThreshold);
  96         parallelSort(middle, end, lessThan, newNumberOfThreads, parallelSortingThreshold);
  97
  98         future.waitForFinished();
  99
 100         merge(begin, middle, end, lessThan);
 101     } else {
 102         sequentialSort(begin, end, lessThan);
 103     }
 104 }
 105
 106 template <typename RandomAccessIterator, typename LessThan>
 107 static void merge(RandomAccessIterator begin,
 108                   RandomAccessIterator pivot,
 109                   RandomAccessIterator end,
 110                   LessThan lessThan)
 111 {
 112     // The implementation is based on qMerge() from qalgorithms.h
 113     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 114
 115     const int len1 = pivot - begin;
 116     const int len2 = end - pivot;
 117
 118     if (len1 == 0 || len2 == 0) {
 119         return;
 120     }
 121
 122     if (len1 + len2 == 2) {
 123         if (lessThan(*(begin + 1), *(begin))) {
 124             qSwap(*begin, *(begin + 1));
 125         }
 126         return;
 127     }
 128
 129     RandomAccessIterator firstCut;
 130     RandomAccessIterator secondCut;
 131     int len2Half;
 132     if (len1 > len2) {
 133         const int len1Half = len1 / 2;
 134         firstCut = begin + len1Half;
 135         secondCut = std::lower_bound(pivot, end, *firstCut, lessThan);
 136         len2Half = secondCut - pivot;
 137     } else {
 138         len2Half = len2 / 2;
 139         secondCut = pivot + len2Half;
 140         firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan);
 141     }
 142
 143     std::rotate(firstCut, pivot, secondCut);
 144
 145     RandomAccessIterator newPivot = firstCut + len2Half;
 146     merge(begin, firstCut, newPivot, lessThan);
 147     merge(newPivot, secondCut, end, lessThan);
 148 }