Differential D23507 Diff 64767 src/kitemviews/private/kfileitemmodelsortalgorithm.h

Changeset View

Standalone View

src/kitemviews/private/kfileitemmodelsortalgorithm.h

Show All 21 Lines
22	#ifndef KFILEITEMMODELSORTALGORITHM_H	22		#ifndef KFILEITEMMODELSORTALGORITHM_H
23	#define KFILEITEMMODELSORTALGORITHM_H	23		#define KFILEITEMMODELSORTALGORITHM_H
24		24
25	#include <QtConcurrentRun>	25		#include <QtConcurrentRun>
26		26
27	#include <algorithm>	27		#include <algorithm>
28		28
29	/**	29		/**
30	* Sorts the items using the merge sort algorithm is used to assure a
31	* worst-case of O(n * log(n)) and to keep the number of comparisons low.
32	*
33	* The implementation is based on qStableSortHelper() from qalgorithms.h
34	* Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
35	*/
36
37	template <typename RandomAccessIterator, typename LessThan>
38	static void mergeSort(RandomAccessIterator begin,
39	RandomAccessIterator end,
40	const LessThan& lessThan)
41	{
42	// The implementation is based on qStableSortHelper() from qalgorithms.h
43	// Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
44
45	const int span = end - begin;
46	if (span < 2) {
47	return;
48	}
49
50	const RandomAccessIterator middle = begin + span / 2;
51	mergeSort(begin, middle, lessThan);
52	mergeSort(middle, end, lessThan);
53	merge(begin, middle, end, lessThan);
54	}
55
56	/**
57	* Uses up to \a numberOfThreads threads to sort the items between
58	* \a begin and \a end. Only item ranges longer than
59	* \a parallelMergeSortingThreshold are split to be sorted by two different
60	* threads.
61	*
62	* The comparison function \a lessThan must be reentrant.
63	*/
64
65	template <typename RandomAccessIterator, typename LessThan>
66	static void parallelMergeSort(RandomAccessIterator begin,
67	RandomAccessIterator end,
68	LessThan lessThan,
69	int numberOfThreads,
70	int parallelMergeSortingThreshold = 100)
71	{
72	const int span = end - begin;
73
74	if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
75	const int newNumberOfThreads = numberOfThreads / 2;
76	const RandomAccessIterator middle = begin + span / 2;
77
78	QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
79	parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
80
81	future.waitForFinished();
82
83	merge(begin, middle, end, lessThan);
84	} else {
85	mergeSort(begin, end, lessThan);
86	}
87	}
88
89	/**
90	* Merges the sorted item ranges between \a begin and \a pivot and	30		* Merges the sorted item ranges between \a begin and \a pivot and
91	* between \a pivot and \a end into a single sorted range between	31		* between \a pivot and \a end into a single sorted range between
92	* \a begin and \a end.	32		* \a begin and \a end.
93	*	33		*
94	* The implementation is based on qMerge() from qalgorithms.h	34		* The implementation is based on qMerge() from qalgorithms.h
95	* Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).	35		* Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
96	*/	36		*/
97		37
Show All 38 Lines		43	{
136		76
137	std::rotate(firstCut, pivot, secondCut);	77		std::rotate(firstCut, pivot, secondCut);
138		78
139	RandomAccessIterator newPivot = firstCut + len2Half;	79		RandomAccessIterator newPivot = firstCut + len2Half;
140	merge(begin, firstCut, newPivot, lessThan);	80		merge(begin, firstCut, newPivot, lessThan);
141	merge(newPivot, secondCut, end, lessThan);	81		merge(newPivot, secondCut, end, lessThan);
142	}	82		}
143		83
		84		/**
			mevenUnsubmitted Not Done Could you keep this function line at line 30 instead of moving, so that the diff actually shows what changed. meven: Could you keep this function line at line 30 instead of moving, so that the diff actually shows…
		85		* Uses up to \a numberOfThreads threads to sort the items between
		86		* \a begin and \a end. Only item ranges longer than
		87		* \a parallelMergeSortingThreshold are split to be sorted by two different
		88		* threads.
		89		*
		90		* The comparison function \a lessThan must be reentrant.
		91		*/
		92
		93		template <typename RandomAccessIterator, typename LessThan>
		94		static void parallelMergeSort(RandomAccessIterator begin,
		95		RandomAccessIterator end,
		96		LessThan lessThan,
		97		int numberOfThreads,
		98		int parallelMergeSortingThreshold = 100)
		99		{
		100		const int span = end - begin;
		101
		102		if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
		103		const int newNumberOfThreads = numberOfThreads / 2;
		104		const RandomAccessIterator middle = begin + span / 2;
		105
		106		QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
		107		parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
		108
		109		future.waitForFinished();
		110
		111		merge(begin, middle, end, lessThan);
		112		} else {
		113		std::stable_sort(begin, end, lessThan);
		114		}
		115		}
		116
144	#endif	117		#endif
145		118