1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2023 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file parallel/sort.h
26 * @brief Parallel sorting algorithm switch.
27 * This file is a GNU parallel extension to the Standard C++ Library.
28 */
29
30 // Written by Johannes Singler.
31
32 #ifndef _GLIBCXX_PARALLEL_SORT_H
33 #define _GLIBCXX_PARALLEL_SORT_H 1
34
35 #include <parallel/basic_iterator.h>
36 #include <parallel/features.h>
37 #include <parallel/parallel.h>
38
39 #if _GLIBCXX_PARALLEL_ASSERTIONS
40 #include <parallel/checkers.h>
41 #endif
42
43 #if _GLIBCXX_MERGESORT
44 #include <parallel/multiway_mergesort.h>
45 #endif
46
47 #if _GLIBCXX_QUICKSORT
48 #include <parallel/quicksort.h>
49 #endif
50
51 #if _GLIBCXX_BAL_QUICKSORT
52 #include <parallel/balanced_quicksort.h>
53 #endif
54
55 namespace __gnu_parallel
56 {
57 //prototype
58 template<bool __stable, typename _RAIter,
59 typename _Compare, typename _Parallelism>
60 void
61 __parallel_sort(_RAIter __begin, _RAIter __end,
62 _Compare __comp, _Parallelism __parallelism);
63
64 /**
65 * @brief Choose multiway mergesort, splitting variant at run-time,
66 * for parallel sorting.
67 * @param __begin Begin iterator of input sequence.
68 * @param __end End iterator of input sequence.
69 * @param __comp Comparator.
70 * @tparam __stable Sort stable.
71 * @callgraph
72 */
73 template<bool __stable, typename _RAIter, typename _Compare>
74 inline void
75 __parallel_sort(_RAIter __begin, _RAIter __end,
76 _Compare __comp, multiway_mergesort_tag __parallelism)
77 {
78 _GLIBCXX_CALL(__end - __begin)
79
80 if(_Settings::get().sort_splitting == EXACT)
81 parallel_sort_mwms<__stable, true>
82 (__begin, __end, __comp, __parallelism.__get_num_threads());
83 else
84 parallel_sort_mwms<__stable, false>
85 (__begin, __end, __comp, __parallelism.__get_num_threads());
86 }
87
88 /**
89 * @brief Choose multiway mergesort with exact splitting,
90 * for parallel sorting.
91 * @param __begin Begin iterator of input sequence.
92 * @param __end End iterator of input sequence.
93 * @param __comp Comparator.
94 * @tparam __stable Sort stable.
95 * @callgraph
96 */
97 template<bool __stable, typename _RAIter, typename _Compare>
98 inline void
99 __parallel_sort(_RAIter __begin, _RAIter __end,
100 _Compare __comp,
101 multiway_mergesort_exact_tag __parallelism)
102 {
103 _GLIBCXX_CALL(__end - __begin)
104
105 parallel_sort_mwms<__stable, true>
106 (__begin, __end, __comp, __parallelism.__get_num_threads());
107 }
108
109 /**
110 * @brief Choose multiway mergesort with splitting by sampling,
111 * for parallel sorting.
112 * @param __begin Begin iterator of input sequence.
113 * @param __end End iterator of input sequence.
114 * @param __comp Comparator.
115 * @tparam __stable Sort stable.
116 * @callgraph
117 */
118 template<bool __stable, typename _RAIter, typename _Compare>
119 inline void
120 __parallel_sort(_RAIter __begin, _RAIter __end,
121 _Compare __comp,
122 multiway_mergesort_sampling_tag __parallelism)
123 {
124 _GLIBCXX_CALL(__end - __begin)
125
126 parallel_sort_mwms<__stable, false>
127 (__begin, __end, __comp, __parallelism.__get_num_threads());
128 }
129
130 /**
131 * @brief Choose quicksort for parallel sorting.
132 * @param __begin Begin iterator of input sequence.
133 * @param __end End iterator of input sequence.
134 * @param __comp Comparator.
135 * @tparam __stable Sort stable.
136 * @callgraph
137 */
138 template<bool __stable, typename _RAIter, typename _Compare>
139 inline void
140 __parallel_sort(_RAIter __begin, _RAIter __end,
141 _Compare __comp, quicksort_tag __parallelism)
142 {
143 _GLIBCXX_CALL(__end - __begin)
144
145 _GLIBCXX_PARALLEL_ASSERT(__stable == false);
146
147 __parallel_sort_qs(__begin, __end, __comp,
148 __parallelism.__get_num_threads());
149 }
150
151 /**
152 * @brief Choose balanced quicksort for parallel sorting.
153 * @param __begin Begin iterator of input sequence.
154 * @param __end End iterator of input sequence.
155 * @param __comp Comparator.
156 * @tparam __stable Sort stable.
157 * @callgraph
158 */
159 template<bool __stable, typename _RAIter, typename _Compare>
160 inline void
161 __parallel_sort(_RAIter __begin, _RAIter __end,
162 _Compare __comp, balanced_quicksort_tag __parallelism)
163 {
164 _GLIBCXX_CALL(__end - __begin)
165
166 _GLIBCXX_PARALLEL_ASSERT(__stable == false);
167
168 __parallel_sort_qsb(__begin, __end, __comp,
169 __parallelism.__get_num_threads());
170 }
171
172 /**
173 * @brief Choose multiway mergesort with exact splitting,
174 * for parallel sorting.
175 * @param __begin Begin iterator of input sequence.
176 * @param __end End iterator of input sequence.
177 * @param __comp Comparator.
178 * @tparam __stable Sort stable.
179 * @callgraph
180 */
181 template<bool __stable, typename _RAIter, typename _Compare>
182 inline void
183 __parallel_sort(_RAIter __begin, _RAIter __end,
184 _Compare __comp, default_parallel_tag __parallelism)
185 {
186 _GLIBCXX_CALL(__end - __begin)
187
188 __parallel_sort<__stable>
189 (__begin, __end, __comp,
190 multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
191 }
192
193 /**
194 * @brief Choose a parallel sorting algorithm.
195 * @param __begin Begin iterator of input sequence.
196 * @param __end End iterator of input sequence.
197 * @param __comp Comparator.
198 * @tparam __stable Sort stable.
199 * @callgraph
200 */
201 template<bool __stable, typename _RAIter, typename _Compare>
202 inline void
203 __parallel_sort(_RAIter __begin, _RAIter __end,
204 _Compare __comp, parallel_tag __parallelism)
205 {
206 _GLIBCXX_CALL(__end - __begin)
207 typedef std::iterator_traits<_RAIter> _TraitsType;
208 typedef typename _TraitsType::value_type _ValueType;
209 typedef typename _TraitsType::difference_type _DifferenceType;
210
211 if (false) ;
212 #if _GLIBCXX_MERGESORT
213 else if (__stable || _Settings::get().sort_algorithm == MWMS)
214 {
215 if(_Settings::get().sort_splitting == EXACT)
216 parallel_sort_mwms<__stable, true>
217 (__begin, __end, __comp, __parallelism.__get_num_threads());
218 else
219 parallel_sort_mwms<false, false>
220 (__begin, __end, __comp, __parallelism.__get_num_threads());
221 }
222 #endif
223 #if _GLIBCXX_QUICKSORT
224 else if (_Settings::get().sort_algorithm == QS)
225 __parallel_sort_qs(__begin, __end, __comp,
226 __parallelism.__get_num_threads());
227 #endif
228 #if _GLIBCXX_BAL_QUICKSORT
229 else if (_Settings::get().sort_algorithm == QS_BALANCED)
230 __parallel_sort_qsb(__begin, __end, __comp,
231 __parallelism.__get_num_threads());
232 #endif
233 else
234 __gnu_sequential::sort(__begin, __end, __comp);
235 }
236 } // end namespace __gnu_parallel
237
238 #endif /* _GLIBCXX_PARALLEL_SORT_H */