source: Daodan/MSYS2/mingw32/include/c++/11.2.0/parallel/sort.h

Last change on this file was 1166, checked in by rossy, 3 years ago

Daodan: Replace MinGW build env with an up-to-date MSYS2 env
File size: 7.5 KB
Line 
1// -*- C++ -*-
2
3// Copyright (C) 2007-2021 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
55namespace __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 */
Note: See TracBrowser for help on using the repository browser.