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 RandomAccessIterator,
59  typename Comparator, typename Parallelism>
60  void
61  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
62  Comparator 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 RandomAccessIterator, typename Comparator>
73  inline void
74  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
75  Comparator 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 RandomAccessIterator, typename Comparator>
96  inline void
97  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
98  Comparator comp, multiway_mergesort_exact_tag parallelism)
99  {
100  _GLIBCXX_CALL(end - begin)
101 
102  parallel_sort_mwms<stable, true>
103  (begin, end, comp, parallelism.get_num_threads());
104  }
105 
106  /**
107  * @brief Choose multiway mergesort with splitting by sampling,
108  * for parallel sorting.
109  * @param begin Begin iterator of input sequence.
110  * @param end End iterator of input sequence.
111  * @param comp Comparator.
112  * @callgraph
113  */
114  template<bool stable, typename RandomAccessIterator, typename Comparator>
115  inline void
116  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
117  Comparator comp, multiway_mergesort_sampling_tag parallelism)
118  {
119  _GLIBCXX_CALL(end - begin)
120 
121  parallel_sort_mwms<stable, false>
122  (begin, end, comp, parallelism.get_num_threads());
123  }
124 
125  /**
126  * @brief Choose quicksort for parallel sorting.
127  * @param begin Begin iterator of input sequence.
128  * @param end End iterator of input sequence.
129  * @param comp Comparator.
130  * @callgraph
131  */
132  template<bool stable, typename RandomAccessIterator, typename Comparator>
133  inline void
134  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
135  Comparator comp, quicksort_tag parallelism)
136  {
137  _GLIBCXX_CALL(end - begin)
138 
139  _GLIBCXX_PARALLEL_ASSERT(stable == false);
140 
141  parallel_sort_qs(begin, end, comp, parallelism.get_num_threads());
142  }
143 
144  /**
145  * @brief Choose balanced quicksort for parallel sorting.
146  * @param begin Begin iterator of input sequence.
147  * @param end End iterator of input sequence.
148  * @param comp Comparator.
149  * @param stable Sort stable.
150  * @callgraph
151  */
152  template<bool stable, typename RandomAccessIterator, typename Comparator>
153  inline void
154  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
155  Comparator comp, balanced_quicksort_tag parallelism)
156  {
157  _GLIBCXX_CALL(end - begin)
158 
159  _GLIBCXX_PARALLEL_ASSERT(stable == false);
160 
161  parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
162  }
163 
164 
165  /**
166  * @brief Choose multiway mergesort with exact splitting,
167  * for parallel sorting.
168  * @param begin Begin iterator of input sequence.
169  * @param end End iterator of input sequence.
170  * @param comp Comparator.
171  * @callgraph
172  */
173  template<bool stable, typename RandomAccessIterator, typename Comparator>
174  inline void
175  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
176  Comparator comp, default_parallel_tag parallelism)
177  {
178  _GLIBCXX_CALL(end - begin)
179 
180  parallel_sort<stable>
181  (begin, end, comp,
183  }
184 
185 
186  /**
187  * @brief Choose a parallel sorting algorithm.
188  * @param begin Begin iterator of input sequence.
189  * @param end End iterator of input sequence.
190  * @param comp Comparator.
191  * @param stable Sort stable.
192  * @callgraph
193  */
194  template<bool stable, typename RandomAccessIterator, typename Comparator>
195  inline void
196  parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
197  Comparator comp, parallel_tag parallelism)
198  {
199  _GLIBCXX_CALL(end - begin)
200  typedef std::iterator_traits<RandomAccessIterator> traits_type;
201  typedef typename traits_type::value_type value_type;
202  typedef typename traits_type::difference_type difference_type;
203 
204  if (false) ;
205 #if _GLIBCXX_MERGESORT
206  else if (stable || _Settings::get().sort_algorithm == MWMS)
207  {
208  if(_Settings::get().sort_splitting == EXACT)
209  parallel_sort_mwms<stable, true>
210  (begin, end, comp, parallelism.get_num_threads());
211  else
212  parallel_sort_mwms<false, false>
213  (begin, end, comp, parallelism.get_num_threads());
214  }
215 #endif
216 #if _GLIBCXX_QUICKSORT
217  else if (_Settings::get().sort_algorithm == QS)
218  parallel_sort_qs(begin, end, comp, parallelism.get_num_threads());
219 #endif
220 #if _GLIBCXX_BAL_QUICKSORT
221  else if (_Settings::get().sort_algorithm == QS_BALANCED)
222  parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
223 #endif
224  else
225  __gnu_sequential::sort(begin, end, comp);
226  }
227 } // end namespace __gnu_parallel
228 
229 #endif /* _GLIBCXX_PARALLEL_SORT_H */
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:134
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:143
void parallel_sort_qsb(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
Top-level quicksort routine.
Defines on whether to include algorithm variants.
thread_index_t get_num_threads()
Find out desired number of threads.
Definition: tags.h:67
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:170
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:161
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time...
Definition: tags.h:152
GNU parallel code for public use.
static const _Settings & get()
Get the global settings.
Implementation of a unbalanced parallel quicksort (in-place). This file is a GNU parallel extension t...
Parallel multiway merge sort. This file is a GNU parallel extension to the Standard C++ Library...
void parallel_sort_qs(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
Unbalanced quicksort main call.
Definition: quicksort.h:157
Implementation of a dynamically load-balanced parallel quicksort.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Recommends parallel execution at compile time, optionally using a user-specified number of threads...
Definition: tags.h:46
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:85