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