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 void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
  26                                        QList<KFileItemModel::ItemData*>::iterator begin,
  27                                        QList<KFileItemModel::ItemData*>::iterator end)
  28 {
  29     if (model->sortRole() == model->roleForType(KFileItemModel::NameRole)) {
  30         // Sorting by name can be expensive, in particular if natural sorting is
  31         // enabled. Use all CPU cores to speed up the sorting process.
  32         static const int numberOfThreads = QThread::idealThreadCount();
  33         parallelSort(model, begin, end, numberOfThreads);
  34     } else {
  35         // Sorting by other roles is quite fast. Use only one thread to prevent
  36         // problems caused by non-reentrant comparison functions, see
  37         // https://bugs.kde.org/show_bug.cgi?id=312679
  38         sequentialSort(model, begin, end);
  39     }
  40 }
  41
  42 void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model,
  43                                                  QList< KFileItemModel::ItemData* >::iterator begin,
  44                                                  QList< KFileItemModel::ItemData* >::iterator end)
  45 {
  46     // The implementation is based on qStableSortHelper() from qalgorithms.h
  47     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  48
  49     const int span = end - begin;
  50     if (span < 2) {
  51         return;
  52     }
  53
  54     const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  55     sequentialSort(model, begin, middle);
  56     sequentialSort(model, middle, end);
  57     merge(model, begin, middle, end);
  58 }
  59
  60 void KFileItemModelSortAlgorithm::parallelSort(KFileItemModel* model,
  61                                                QList< KFileItemModel::ItemData* >::iterator begin,
  62                                                QList< KFileItemModel::ItemData* >::iterator end,
  63                                                const int numberOfThreads)
  64 {
  65     const int span = end - begin;
  66
  67     if (numberOfThreads > 1 && span > 100) {
  68         const int newNumberOfThreads = numberOfThreads / 2;
  69         const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  70
  71         QFuture<void> future = QtConcurrent::run(parallelSort, model, begin, middle, newNumberOfThreads);
  72         parallelSort(model, middle, end, newNumberOfThreads);
  73
  74         future.waitForFinished();
  75
  76         merge(model, begin, middle, end);
  77     } else {
  78         sequentialSort(model, begin, end);
  79     }
  80 }
  81
  82 void KFileItemModelSortAlgorithm::merge(KFileItemModel* model,
  83                                         QList<KFileItemModel::ItemData*>::iterator begin,
  84                                         QList<KFileItemModel::ItemData*>::iterator pivot,
  85                                         QList<KFileItemModel::ItemData*>::iterator end)
  86 {
  87     // The implementation is based on qMerge() from qalgorithms.h
  88     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  89
  90     const int len1 = pivot - begin;
  91     const int len2 = end - pivot;
  92
  93     if (len1 == 0 || len2 == 0) {
  94         return;
  95     }
  96
  97     if (len1 + len2 == 2) {
  98         if (model->lessThan(*(begin + 1), *(begin))) {
  99             qSwap(*begin, *(begin + 1));
 100         }
 101         return;
 102     }
 103
 104     QList<KFileItemModel::ItemData*>::iterator firstCut;
 105     QList<KFileItemModel::ItemData*>::iterator secondCut;
 106     int len2Half;
 107     if (len1 > len2) {
 108         const int len1Half = len1 / 2;
 109         firstCut = begin + len1Half;
 110         secondCut = lowerBound(model, pivot, end, *firstCut);
 111         len2Half = secondCut - pivot;
 112     } else {
 113         len2Half = len2 / 2;
 114         secondCut = pivot + len2Half;
 115         firstCut = upperBound(model, begin, pivot, *secondCut);
 116     }
 117
 118     reverse(firstCut, pivot);
 119     reverse(pivot, secondCut);
 120     reverse(firstCut, 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 }
 179
 180 void KFileItemModelSortAlgorithm::reverse(QList<KFileItemModel::ItemData*>::iterator begin,
 181                                           QList<KFileItemModel::ItemData*>::iterator end)
 182 {
 183     // The implementation is based on qReverse() from qalgorithms.h
 184     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 185
 186     --end;
 187     while (begin < end) {
 188         qSwap(*begin++, *end--);
 189     }
 190 }