libstdc++
sort.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2024 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
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
45#endif
46
47#if _GLIBCXX_QUICKSORT
48#include <parallel/quicksort.h>
49#endif
50
51#if _GLIBCXX_BAL_QUICKSORT
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,
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,
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 */
Implementation of a dynamically load-balanced parallel quicksort.
Defines on whether to include algorithm variants.
Includes the original header files concerned with iterators except for stream iterators....
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
Parallel multiway merge sort. This file is a GNU parallel extension to the Standard C++ Library.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Implementation of a unbalanced parallel quicksort (in-place). This file is a GNU parallel extension t...
GNU parallel code for public use.
void __parallel_sort_qsb(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Top-level quicksort routine.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition types.h:45
void __parallel_sort_qs(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Unbalanced quicksort main call.
Definition quicksort.h:154
static const _Settings & get()
Get the global settings.
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition tags.h:47
_ThreadIndex __get_num_threads()
Find out desired number of threads.
Definition tags.h:63
Recommends parallel execution using the default parallel algorithm.
Definition tags.h:80
Forces parallel sorting using multiway mergesort at compile time.
Definition tags.h:129
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition tags.h:138
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition tags.h:147
Forces parallel sorting using unbalanced quicksort at compile time.
Definition tags.h:156
Forces parallel sorting using balanced quicksort at compile time.
Definition tags.h:165