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 void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
  28                                        QList<KFileItemModel::ItemData*>::iterator begin,
  29                                        QList<KFileItemModel::ItemData*>::iterator end)
  30 {
  31     if (model->sortRole() == model->roleForType(KFileItemModel::NameRole)) {
  32         // Sorting by name can be expensive, in particular if natural sorting is
  33         // enabled. Use all CPU cores to speed up the sorting process.
  34         static const int numberOfThreads = QThread::idealThreadCount();
  35         parallelSort(model, begin, end, numberOfThreads);
  36     } else {
  37         // Sorting by other roles is quite fast. Use only one thread to prevent
  38         // problems caused by non-reentrant comparison functions, see
  39         // https://bugs.kde.org/show_bug.cgi?id=312679
  40         sequentialSort(model, begin, end);
  41     }
  42 }
  43
  44 void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model,
  45                                                  QList< KFileItemModel::ItemData* >::iterator begin,
  46                                                  QList< KFileItemModel::ItemData* >::iterator end)
  47 {
  48     // The implementation is based on qStableSortHelper() from qalgorithms.h
  49     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  50
  51     const int span = end - begin;
  52     if (span < 2) {
  53         return;
  54     }
  55
  56     const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  57     sequentialSort(model, begin, middle);
  58     sequentialSort(model, middle, end);
  59     merge(model, begin, middle, end);
  60 }
  61
  62 void KFileItemModelSortAlgorithm::parallelSort(KFileItemModel* model,
  63                                                QList< KFileItemModel::ItemData* >::iterator begin,
  64                                                QList< KFileItemModel::ItemData* >::iterator end,
  65                                                const int numberOfThreads)
  66 {
  67     const int span = end - begin;
  68
  69     if (numberOfThreads > 1 && span > 100) {
  70         const int newNumberOfThreads = numberOfThreads / 2;
  71         const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  72
  73         QFuture<void> future = QtConcurrent::run(parallelSort, model, begin, middle, newNumberOfThreads);
  74         parallelSort(model, middle, end, newNumberOfThreads);
  75
  76         future.waitForFinished();
  77
  78         merge(model, begin, middle, end);
  79     } else {
  80         sequentialSort(model, begin, end);
  81     }
  82 }
  83
  84 void KFileItemModelSortAlgorithm::merge(KFileItemModel* model,
  85                                         QList<KFileItemModel::ItemData*>::iterator begin,
  86                                         QList<KFileItemModel::ItemData*>::iterator pivot,
  87                                         QList<KFileItemModel::ItemData*>::iterator end)
  88 {
  89     // The implementation is based on qMerge() from qalgorithms.h
  90     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  91
  92     const int len1 = pivot - begin;
  93     const int len2 = end - pivot;
  94
  95     if (len1 == 0 || len2 == 0) {
  96         return;
  97     }
  98
  99     if (len1 + len2 == 2) {
 100         if (model->lessThan(*(begin + 1), *(begin))) {
 101             qSwap(*begin, *(begin + 1));
 102         }
 103         return;
 104     }
 105
 106     QList<KFileItemModel::ItemData*>::iterator firstCut;
 107     QList<KFileItemModel::ItemData*>::iterator secondCut;
 108     int len2Half;
 109     if (len1 > len2) {
 110         const int len1Half = len1 / 2;
 111         firstCut = begin + len1Half;
 112         secondCut = lowerBound(model, pivot, end, *firstCut);
 113         len2Half = secondCut - pivot;
 114     } else {
 115         len2Half = len2 / 2;
 116         secondCut = pivot + len2Half;
 117         firstCut = upperBound(model, begin, pivot, *secondCut);
 118     }
 119
 120     std::rotate(firstCut, pivot, secondCut);
 121
 122     const QList<KFileItemModel::ItemData*>::iterator newPivot = firstCut + len2Half;
 123     merge(model, begin, firstCut, newPivot);
 124     merge(model, newPivot, secondCut, end);
 125 }
 126
 127
 128 QList<KFileItemModel::ItemData*>::iterator
 129 KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model,
 130                                         QList<KFileItemModel::ItemData*>::iterator begin,
 131                                         QList<KFileItemModel::ItemData*>::iterator end,
 132                                         const KFileItemModel::ItemData* value)
 133 {
 134     // The implementation is based on qLowerBound() from qalgorithms.h
 135     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 136
 137     QList<KFileItemModel::ItemData*>::iterator middle;
 138     int n = int(end - begin);
 139     int half;
 140
 141     while (n > 0) {
 142         half = n >> 1;
 143         middle = begin + half;
 144         if (model->lessThan(*middle, value)) {
 145             begin = middle + 1;
 146             n -= half + 1;
 147         } else {
 148             n = half;
 149         }
 150     }
 151     return begin;
 152 }
 153
 154 QList<KFileItemModel::ItemData*>::iterator
 155 KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model,
 156                                         QList<KFileItemModel::ItemData*>::iterator begin,
 157                                         QList<KFileItemModel::ItemData*>::iterator end,
 158                                         const KFileItemModel::ItemData* value)
 159 {
 160     // The implementation is based on qUpperBound() from qalgorithms.h
 161     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 162
 163     QList<KFileItemModel::ItemData*>::iterator middle;
 164     int n = end - begin;
 165     int half;
 166
 167     while (n > 0) {
 168         half = n >> 1;
 169         middle = begin + half;
 170         if (model->lessThan(value, *middle)) {
 171             n = half;
 172         } else {
 173             begin = middle + 1;
 174             n -= half + 1;
 175         }
 176     }
 177     return begin;
 178 }