3 // Copyright (C) 2007-2023 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 /** @file parallel/sort.h
26 * @brief Parallel sorting algorithm switch.
27 * This file is a GNU parallel extension to the Standard C++ Library.
30 // Written by Johannes Singler.
32 #ifndef _GLIBCXX_PARALLEL_SORT_H
33 #define _GLIBCXX_PARALLEL_SORT_H 1
35 #include <parallel/basic_iterator.h>
36 #include <parallel/features.h>
37 #include <parallel/parallel.h>
39 #if _GLIBCXX_PARALLEL_ASSERTIONS
40 #include <parallel/checkers.h>
43 #if _GLIBCXX_MERGESORT
44 #include <parallel/multiway_mergesort.h>
47 #if _GLIBCXX_QUICKSORT
48 #include <parallel/quicksort.h>
51 #if _GLIBCXX_BAL_QUICKSORT
52 #include <parallel/balanced_quicksort.h>
55 namespace __gnu_parallel
58 template<bool __stable
, typename _RAIter
,
59 typename _Compare
, typename _Parallelism
>
61 __parallel_sort(_RAIter __begin
, _RAIter __end
,
62 _Compare __comp
, _Parallelism __parallelism
);
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.
73 template<bool __stable
, typename _RAIter
, typename _Compare
>
75 __parallel_sort(_RAIter __begin
, _RAIter __end
,
76 _Compare __comp
, multiway_mergesort_tag __parallelism
)
78 _GLIBCXX_CALL(__end
- __begin
)
80 if(_Settings::get().sort_splitting
== EXACT
)
81 parallel_sort_mwms
<__stable
, true>
82 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
84 parallel_sort_mwms
<__stable
, false>
85 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
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.
97 template<bool __stable
, typename _RAIter
, typename _Compare
>
99 __parallel_sort(_RAIter __begin
, _RAIter __end
,
101 multiway_mergesort_exact_tag __parallelism
)
103 _GLIBCXX_CALL(__end
- __begin
)
105 parallel_sort_mwms
<__stable
, true>
106 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
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.
118 template<bool __stable
, typename _RAIter
, typename _Compare
>
120 __parallel_sort(_RAIter __begin
, _RAIter __end
,
122 multiway_mergesort_sampling_tag __parallelism
)
124 _GLIBCXX_CALL(__end
- __begin
)
126 parallel_sort_mwms
<__stable
, false>
127 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
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.
138 template<bool __stable
, typename _RAIter
, typename _Compare
>
140 __parallel_sort(_RAIter __begin
, _RAIter __end
,
141 _Compare __comp
, quicksort_tag __parallelism
)
143 _GLIBCXX_CALL(__end
- __begin
)
145 _GLIBCXX_PARALLEL_ASSERT(__stable
== false);
147 __parallel_sort_qs(__begin
, __end
, __comp
,
148 __parallelism
.__get_num_threads());
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.
159 template<bool __stable
, typename _RAIter
, typename _Compare
>
161 __parallel_sort(_RAIter __begin
, _RAIter __end
,
162 _Compare __comp
, balanced_quicksort_tag __parallelism
)
164 _GLIBCXX_CALL(__end
- __begin
)
166 _GLIBCXX_PARALLEL_ASSERT(__stable
== false);
168 __parallel_sort_qsb(__begin
, __end
, __comp
,
169 __parallelism
.__get_num_threads());
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.
181 template<bool __stable
, typename _RAIter
, typename _Compare
>
183 __parallel_sort(_RAIter __begin
, _RAIter __end
,
184 _Compare __comp
, default_parallel_tag __parallelism
)
186 _GLIBCXX_CALL(__end
- __begin
)
188 __parallel_sort
<__stable
>
189 (__begin
, __end
, __comp
,
190 multiway_mergesort_exact_tag(__parallelism
.__get_num_threads()));
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.
201 template<bool __stable
, typename _RAIter
, typename _Compare
>
203 __parallel_sort(_RAIter __begin
, _RAIter __end
,
204 _Compare __comp
, parallel_tag __parallelism
)
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
;
212 #if _GLIBCXX_MERGESORT
213 else if (__stable
|| _Settings::get().sort_algorithm
== MWMS
)
215 if(_Settings::get().sort_splitting
== EXACT
)
216 parallel_sort_mwms
<__stable
, true>
217 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
219 parallel_sort_mwms
<false, false>
220 (__begin
, __end
, __comp
, __parallelism
.__get_num_threads());
223 #if _GLIBCXX_QUICKSORT
224 else if (_Settings::get().sort_algorithm
== QS
)
225 __parallel_sort_qs(__begin
, __end
, __comp
,
226 __parallelism
.__get_num_threads());
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());
234 __gnu_sequential::sort(__begin
, __end
, __comp
);
236 } // end namespace __gnu_parallel
238 #endif /* _GLIBCXX_PARALLEL_SORT_H */