libstdc++
sort.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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  * @callgraph
71  */
72  template<bool __stable, typename _RAIter, typename _Compare>
73  inline void
74  __parallel_sort(_RAIter __begin, _RAIter __end,
75  _Compare __comp, multiway_mergesort_tag __parallelism)
76  {
77  _GLIBCXX_CALL(__end - __begin)
78 
79  if(_Settings::get().sort_splitting == EXACT)
80  parallel_sort_mwms<__stable, true>
81  (__begin, __end, __comp, __parallelism.__get_num_threads());
82  else
83  parallel_sort_mwms<__stable, false>
84  (__begin, __end, __comp, __parallelism.__get_num_threads());
85  }
86 
87  /**
88  * @brief Choose multiway mergesort with exact splitting,
89  * for parallel sorting.
90  * @param __begin Begin iterator of input sequence.
91  * @param __end End iterator of input sequence.
92  * @param __comp Comparator.
93  * @callgraph
94  */
95  template<bool __stable, typename _RAIter, typename _Compare>
96  inline void
97  __parallel_sort(_RAIter __begin, _RAIter __end,
98  _Compare __comp,
99  multiway_mergesort_exact_tag __parallelism)
100  {
101  _GLIBCXX_CALL(__end - __begin)
102 
103  parallel_sort_mwms<__stable, true>
104  (__begin, __end, __comp, __parallelism.__get_num_threads());
105  }
106 
107  /**
108  * @brief Choose multiway mergesort with splitting by sampling,
109  * for parallel sorting.
110  * @param __begin Begin iterator of input sequence.
111  * @param __end End iterator of input sequence.
112  * @param __comp Comparator.
113  * @callgraph
114  */
115  template<bool __stable, typename _RAIter, typename _Compare>
116  inline void
117  __parallel_sort(_RAIter __begin, _RAIter __end,
118  _Compare __comp,
119  multiway_mergesort_sampling_tag __parallelism)
120  {
121  _GLIBCXX_CALL(__end - __begin)
122 
123  parallel_sort_mwms<__stable, false>
124  (__begin, __end, __comp, __parallelism.__get_num_threads());
125  }
126 
127  /**
128  * @brief Choose quicksort for parallel sorting.
129  * @param __begin Begin iterator of input sequence.
130  * @param __end End iterator of input sequence.
131  * @param __comp Comparator.
132  * @callgraph
133  */
134  template<bool __stable, typename _RAIter, typename _Compare>
135  inline void
136  __parallel_sort(_RAIter __begin, _RAIter __end,
137  _Compare __comp, quicksort_tag __parallelism)
138  {
139  _GLIBCXX_CALL(__end - __begin)
140 
141  _GLIBCXX_PARALLEL_ASSERT(__stable == false);
142 
143  __parallel_sort_qs(__begin, __end, __comp,
144  __parallelism.__get_num_threads());
145  }
146 
147  /**
148  * @brief Choose balanced quicksort for parallel sorting.
149  * @param __begin Begin iterator of input sequence.
150  * @param __end End iterator of input sequence.
151  * @param __comp Comparator.
152  * @param __stable Sort __stable.
153  * @callgraph
154  */
155  template<bool __stable, typename _RAIter, typename _Compare>
156  inline void
157  __parallel_sort(_RAIter __begin, _RAIter __end,
158  _Compare __comp, balanced_quicksort_tag __parallelism)
159  {
160  _GLIBCXX_CALL(__end - __begin)
161 
162  _GLIBCXX_PARALLEL_ASSERT(__stable == false);
163 
164  __parallel_sort_qsb(__begin, __end, __comp,
165  __parallelism.__get_num_threads());
166  }
167 
168  /**
169  * @brief Choose multiway mergesort with exact splitting,
170  * for parallel sorting.
171  * @param __begin Begin iterator of input sequence.
172  * @param __end End iterator of input sequence.
173  * @param __comp Comparator.
174  * @callgraph
175  */
176  template<bool __stable, typename _RAIter, typename _Compare>
177  inline void
178  __parallel_sort(_RAIter __begin, _RAIter __end,
179  _Compare __comp, default_parallel_tag __parallelism)
180  {
181  _GLIBCXX_CALL(__end - __begin)
182 
183  __parallel_sort<__stable>
184  (__begin, __end, __comp,
186  }
187 
188  /**
189  * @brief Choose a parallel sorting algorithm.
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.
194  * @callgraph
195  */
196  template<bool __stable, typename _RAIter, typename _Compare>
197  inline void
198  __parallel_sort(_RAIter __begin, _RAIter __end,
199  _Compare __comp, parallel_tag __parallelism)
200  {
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;
205 
206  if (false) ;
207 #if _GLIBCXX_MERGESORT
208  else if (__stable || _Settings::get().sort_algorithm == MWMS)
209  {
210  if(_Settings::get().sort_splitting == EXACT)
211  parallel_sort_mwms<__stable, true>
212  (__begin, __end, __comp, __parallelism.__get_num_threads());
213  else
214  parallel_sort_mwms<false, false>
215  (__begin, __end, __comp, __parallelism.__get_num_threads());
216  }
217 #endif
218 #if _GLIBCXX_QUICKSORT
219  else if (_Settings::get().sort_algorithm == QS)
220  __parallel_sort_qs(__begin, __end, __comp,
221  __parallelism.__get_num_threads());
222 #endif
223 #if _GLIBCXX_BAL_QUICKSORT
224  else if (_Settings::get().sort_algorithm == QS_BALANCED)
225  __parallel_sort_qsb(__begin, __end, __comp,
226  __parallelism.__get_num_threads());
227 #endif
228  else
229  __gnu_sequential::sort(__begin, __end, __comp);
230  }
231 } // end namespace __gnu_parallel
232 
233 #endif /* _GLIBCXX_PARALLEL_SORT_H */
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:44
static const _Settings & get()
Get the global settings.
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
void __parallel_sort_qs(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Unbalanced quicksort main call.
Definition: quicksort.h:154
Recommends parallel execution at compile time, optionally using a user-specified number of threads...
Definition: tags.h:46
Implementation of a dynamically load-balanced parallel quicksort.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Parallel multiway merge sort. This file is a GNU parallel extension to the Standard C++ Library...
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Defines on whether to include algorithm variants.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:164
void __parallel_sort_qsb(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Top-level quicksort routine.
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:79
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time...
Definition: tags.h:146
_ThreadIndex __get_num_threads()
Find out desired number of threads.
Definition: tags.h:63
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:155
Implementation of a unbalanced parallel quicksort (in-place). This file is a GNU parallel extension t...
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:128
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:137