]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
c2ba9709 JS |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
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 | ||
748086b7 JJ |
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. | |
c2ba9709 | 19 | |
748086b7 JJ |
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/>. | |
c2ba9709 JS |
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_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 | { | |
15ac3c72 | 57 | //prototype |
1acba85b JS |
58 | template<bool __stable, typename _RAIter, |
59 | typename _Compare, typename _Parallelism> | |
d7066497 | 60 | void |
1acba85b JS |
61 | parallel_sort(_RAIter __begin, _RAIter __end, |
62 | _Compare __comp, _Parallelism __parallelism); | |
15ac3c72 | 63 | |
c2ba9709 | 64 | /** |
d7066497 JS |
65 | * @brief Choose multiway mergesort, splitting variant at run-time, |
66 | * for parallel sorting. | |
1acba85b JS |
67 | * @param __begin Begin iterator of input sequence. |
68 | * @param __end End iterator of input sequence. | |
69 | * @param __comp Comparator. | |
d7066497 JS |
70 | * @callgraph |
71 | */ | |
1acba85b | 72 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 73 | inline void |
1acba85b JS |
74 | parallel_sort(_RAIter __begin, _RAIter __end, |
75 | _Compare __comp, multiway_mergesort_tag __parallelism) | |
d7066497 | 76 | { |
1acba85b | 77 | _GLIBCXX_CALL(__end - __begin) |
d7066497 JS |
78 | |
79 | if(_Settings::get().sort_splitting == EXACT) | |
1acba85b JS |
80 | parallel_sort_mwms<__stable, true> |
81 | (__begin, __end, __comp, __parallelism.__get_num_threads()); | |
d7066497 | 82 | else |
1acba85b JS |
83 | parallel_sort_mwms<__stable, false> |
84 | (__begin, __end, __comp, __parallelism.__get_num_threads()); | |
d7066497 JS |
85 | } |
86 | ||
87 | /** | |
721641c4 | 88 | * @brief Choose multiway mergesort with exact splitting, |
d7066497 | 89 | * for parallel sorting. |
1acba85b JS |
90 | * @param __begin Begin iterator of input sequence. |
91 | * @param __end End iterator of input sequence. | |
92 | * @param __comp Comparator. | |
d7066497 JS |
93 | * @callgraph |
94 | */ | |
1acba85b | 95 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 96 | inline void |
1acba85b JS |
97 | parallel_sort(_RAIter __begin, _RAIter __end, |
98 | _Compare __comp, multiway_mergesort_exact_tag __parallelism) | |
d7066497 | 99 | { |
1acba85b | 100 | _GLIBCXX_CALL(__end - __begin) |
d7066497 | 101 | |
1acba85b JS |
102 | parallel_sort_mwms<__stable, true> |
103 | (__begin, __end, __comp, __parallelism.__get_num_threads()); | |
d7066497 JS |
104 | } |
105 | ||
106 | /** | |
107 | * @brief Choose multiway mergesort with splitting by sampling, | |
108 | * for parallel sorting. | |
1acba85b JS |
109 | * @param __begin Begin iterator of input sequence. |
110 | * @param __end End iterator of input sequence. | |
111 | * @param __comp Comparator. | |
d7066497 JS |
112 | * @callgraph |
113 | */ | |
1acba85b | 114 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 115 | inline void |
1acba85b JS |
116 | parallel_sort(_RAIter __begin, _RAIter __end, |
117 | _Compare __comp, multiway_mergesort_sampling_tag __parallelism) | |
d7066497 | 118 | { |
1acba85b | 119 | _GLIBCXX_CALL(__end - __begin) |
d7066497 | 120 | |
1acba85b JS |
121 | parallel_sort_mwms<__stable, false> |
122 | (__begin, __end, __comp, __parallelism.__get_num_threads()); | |
d7066497 JS |
123 | } |
124 | ||
125 | /** | |
126 | * @brief Choose quicksort for parallel sorting. | |
1acba85b JS |
127 | * @param __begin Begin iterator of input sequence. |
128 | * @param __end End iterator of input sequence. | |
129 | * @param __comp Comparator. | |
d7066497 JS |
130 | * @callgraph |
131 | */ | |
1acba85b | 132 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 133 | inline void |
1acba85b JS |
134 | parallel_sort(_RAIter __begin, _RAIter __end, |
135 | _Compare __comp, quicksort_tag __parallelism) | |
d7066497 | 136 | { |
1acba85b | 137 | _GLIBCXX_CALL(__end - __begin) |
d7066497 | 138 | |
1acba85b | 139 | _GLIBCXX_PARALLEL_ASSERT(__stable == false); |
d7066497 | 140 | |
15ac3c72 JS |
141 | __parallel_sort_qs(__begin, __end, __comp, |
142 | __parallelism.__get_num_threads()); | |
d7066497 JS |
143 | } |
144 | ||
145 | /** | |
146 | * @brief Choose balanced quicksort for parallel sorting. | |
1acba85b JS |
147 | * @param __begin Begin iterator of input sequence. |
148 | * @param __end End iterator of input sequence. | |
149 | * @param __comp Comparator. | |
150 | * @param __stable Sort __stable. | |
d7066497 JS |
151 | * @callgraph |
152 | */ | |
1acba85b | 153 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 154 | inline void |
1acba85b JS |
155 | parallel_sort(_RAIter __begin, _RAIter __end, |
156 | _Compare __comp, balanced_quicksort_tag __parallelism) | |
d7066497 | 157 | { |
1acba85b | 158 | _GLIBCXX_CALL(__end - __begin) |
d7066497 | 159 | |
1acba85b | 160 | _GLIBCXX_PARALLEL_ASSERT(__stable == false); |
d7066497 | 161 | |
15ac3c72 JS |
162 | __parallel_sort_qsb(__begin, __end, __comp, |
163 | __parallelism.__get_num_threads()); | |
d7066497 JS |
164 | } |
165 | ||
166 | ||
167 | /** | |
721641c4 | 168 | * @brief Choose multiway mergesort with exact splitting, |
d7066497 | 169 | * for parallel sorting. |
1acba85b JS |
170 | * @param __begin Begin iterator of input sequence. |
171 | * @param __end End iterator of input sequence. | |
172 | * @param __comp Comparator. | |
d7066497 JS |
173 | * @callgraph |
174 | */ | |
1acba85b | 175 | template<bool __stable, typename _RAIter, typename _Compare> |
d7066497 | 176 | inline void |
1acba85b JS |
177 | parallel_sort(_RAIter __begin, _RAIter __end, |
178 | _Compare __comp, default_parallel_tag __parallelism) | |
d7066497 | 179 | { |
1acba85b | 180 | _GLIBCXX_CALL(__end - __begin) |
d7066497 | 181 | |
1acba85b JS |
182 | parallel_sort<__stable> |
183 | (__begin, __end, __comp, | |
184 | multiway_mergesort_exact_tag(__parallelism.__get_num_threads())); | |
d7066497 JS |
185 | } |
186 | ||
187 | ||
188 | /** | |
c2ba9709 | 189 | * @brief Choose a parallel sorting algorithm. |
1acba85b JS |
190 | * @param __begin Begin iterator of input sequence. |
191 | * @param __end End iterator of input sequence. | |
192 | * @param __comp Comparator. | |
193 | * @param __stable Sort __stable. | |
c2ba9709 JS |
194 | * @callgraph |
195 | */ | |
1acba85b | 196 | template<bool __stable, typename _RAIter, typename _Compare> |
5817ff8e | 197 | inline void |
1acba85b JS |
198 | parallel_sort(_RAIter __begin, _RAIter __end, |
199 | _Compare __comp, parallel_tag __parallelism) | |
5817ff8e | 200 | { |
1acba85b JS |
201 | _GLIBCXX_CALL(__end - __begin) |
202 | typedef std::iterator_traits<_RAIter> _TraitsType; | |
203 | typedef typename _TraitsType::value_type _ValueType; | |
204 | typedef typename _TraitsType::difference_type _DifferenceType; | |
5817ff8e | 205 | |
d7066497 | 206 | if (false) ; |
c2ba9709 | 207 | #if _GLIBCXX_MERGESORT |
1acba85b | 208 | else if (__stable || _Settings::get().sort_algorithm == MWMS) |
d7066497 JS |
209 | { |
210 | if(_Settings::get().sort_splitting == EXACT) | |
1acba85b JS |
211 | parallel_sort_mwms<__stable, true> |
212 | (__begin, __end, __comp, __parallelism.__get_num_threads()); | |
d7066497 JS |
213 | else |
214 | parallel_sort_mwms<false, false> | |
1acba85b | 215 | (__begin, __end, __comp, __parallelism.__get_num_threads()); |
d7066497 | 216 | } |
c2ba9709 JS |
217 | #endif |
218 | #if _GLIBCXX_QUICKSORT | |
d7066497 | 219 | else if (_Settings::get().sort_algorithm == QS) |
15ac3c72 JS |
220 | __parallel_sort_qs(__begin, __end, __comp, |
221 | __parallelism.__get_num_threads()); | |
c2ba9709 JS |
222 | #endif |
223 | #if _GLIBCXX_BAL_QUICKSORT | |
d7066497 | 224 | else if (_Settings::get().sort_algorithm == QS_BALANCED) |
15ac3c72 JS |
225 | __parallel_sort_qsb(__begin, __end, __comp, |
226 | __parallelism.__get_num_threads()); | |
c2ba9709 | 227 | #endif |
d7066497 | 228 | else |
1acba85b | 229 | __gnu_sequential::sort(__begin, __end, __comp); |
5817ff8e | 230 | } |
c2ba9709 JS |
231 | } // end namespace __gnu_parallel |
232 | ||
cbcd1e45 | 233 | #endif /* _GLIBCXX_PARALLEL_SORT_H */ |