BRE12
parallel_sort.h
1 /*
2  Copyright 2005-2016 Intel Corporation. All Rights Reserved.
3 
4  This file is part of Threading Building Blocks. Threading Building Blocks is free software;
5  you can redistribute it and/or modify it under the terms of the GNU General Public License
6  version 2 as published by the Free Software Foundation. Threading Building Blocks is
7  distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
8  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
9  See the GNU General Public License for more details. You should have received a copy of
10  the GNU General Public License along with Threading Building Blocks; if not, write to the
11  Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
12 
13  As a special exception, you may use this file as part of a free software library without
14  restriction. Specifically, if other files instantiate templates or use macros or inline
15  functions from this file, or you compile this file and link it with other files to produce
16  an executable, this file does not by itself cause the resulting executable to be covered
17  by the GNU General Public License. This exception does not however invalidate any other
18  reasons why the executable file might be covered by the GNU General Public License.
19 */
20 
21 #ifndef __TBB_parallel_sort_H
22 #define __TBB_parallel_sort_H
23 
24 #include "parallel_for.h"
25 #include "blocked_range.h"
26 #include "internal/_range_iterator.h"
27 #include <algorithm>
28 #include <iterator>
29 #include <functional>
30 
31 namespace tbb {
32 
33 namespace interface9 {
35 namespace internal {
36 
37 using tbb::internal::no_assign;
38 
40 
43 template<typename RandomAccessIterator, typename Compare>
44 class quick_sort_range: private no_assign {
45 
46  inline size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const {
47  return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp( array[l], array[r]) ? r : l ) )
48  : ( comp(array[r], array[m]) ? m : ( comp( array[r], array[l] ) ? r : l ) );
49  }
50 
51  inline size_t pseudo_median_of_nine( const RandomAccessIterator &array, const quick_sort_range &range ) const {
52  size_t offset = range.size/8u;
53  return median_of_three(array,
54  median_of_three(array, 0, offset, offset*2),
55  median_of_three(array, offset*3, offset*4, offset*5),
56  median_of_three(array, offset*6, offset*7, range.size - 1) );
57 
58  }
59 
60  size_t split_range( quick_sort_range& range ) {
61  using std::iter_swap;
62  RandomAccessIterator array = range.begin;
63  RandomAccessIterator key0 = range.begin;
64  size_t m = pseudo_median_of_nine(array, range);
65  if (m) iter_swap ( array, array+m );
66 
67  size_t i=0;
68  size_t j=range.size;
69  // Partition interval [i+1,j-1] with key *key0.
70  for(;;) {
71  __TBB_ASSERT( i<j, NULL );
72  // Loop must terminate since array[l]==*key0.
73  do {
74  --j;
75  __TBB_ASSERT( i<=j, "bad ordering relation?" );
76  } while( comp( *key0, array[j] ));
77  do {
78  __TBB_ASSERT( i<=j, NULL );
79  if( i==j ) goto partition;
80  ++i;
81  } while( comp( array[i],*key0 ));
82  if( i==j ) goto partition;
83  iter_swap( array+i, array+j );
84  }
85 partition:
86  // Put the partition key were it belongs
87  iter_swap( array+j, key0 );
88  // array[l..j) is less or equal to key.
89  // array(j..r) is greater or equal to key.
90  // array[j] is equal to key
91  i=j+1;
92  size_t new_range_size = range.size-i;
93  range.size = j;
94  return new_range_size;
95  }
96 
97 public:
98 
99  static const size_t grainsize = 500;
100  const Compare &comp;
101  size_t size;
102  RandomAccessIterator begin;
103 
104  quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) :
105  comp(comp_), size(size_), begin(begin_) {}
106 
107  bool empty() const {return size==0;}
108  bool is_divisible() const {return size>=grainsize;}
109 
110  quick_sort_range( quick_sort_range& range, split )
111  : comp(range.comp)
112  , size(split_range(range))
113  // +1 accounts for the pivot element, which is at its correct place
114  // already and, therefore, is not included into subranges.
115  , begin(range.begin+range.size+1) {}
116 };
117 
118 #if __TBB_TASK_GROUP_CONTEXT
119 
121 template<typename RandomAccessIterator, typename Compare>
122 class quick_sort_pretest_body : no_assign {
123  const Compare &comp;
124 
125 public:
126  quick_sort_pretest_body(const Compare &_comp) : comp(_comp) {}
127 
128  void operator()( const blocked_range<RandomAccessIterator>& range ) const {
129  task &my_task = task::self();
130  RandomAccessIterator my_end = range.end();
131 
132  int i = 0;
133  for (RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i) {
134  if ( i%64 == 0 && my_task.is_cancelled() ) break;
135 
136  // The k-1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1
137  if ( comp( *(k), *(k-1) ) ) {
138  my_task.cancel_group_execution();
139  break;
140  }
141  }
142  }
143 
144 };
145 #endif /* __TBB_TASK_GROUP_CONTEXT */
146 
148 
149 template<typename RandomAccessIterator, typename Compare>
150 struct quick_sort_body {
151  void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const {
152  //SerialQuickSort( range.begin, range.size, range.comp );
153  std::sort( range.begin, range.begin + range.size, range.comp );
154  }
155 };
156 
158 
159 template<typename RandomAccessIterator, typename Compare>
160 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
161 #if __TBB_TASK_GROUP_CONTEXT
162  task_group_context my_context;
163  const int serial_cutoff = 9;
164 
165  __TBB_ASSERT( begin + serial_cutoff < end, "min_parallel_size is smaller than serial cutoff?" );
166  RandomAccessIterator k = begin;
167  for ( ; k != begin + serial_cutoff; ++k ) {
168  if ( comp( *(k+1), *k ) ) {
169  goto do_parallel_quick_sort;
170  }
171  }
172 
173  parallel_for( blocked_range<RandomAccessIterator>(k+1, end),
174  quick_sort_pretest_body<RandomAccessIterator,Compare>(comp),
175  auto_partitioner(),
176  my_context);
177 
178  if (my_context.is_group_execution_cancelled())
179 do_parallel_quick_sort:
180 #endif /* __TBB_TASK_GROUP_CONTEXT */
181  parallel_for( quick_sort_range<RandomAccessIterator,Compare>(begin, end-begin, comp ),
182  quick_sort_body<RandomAccessIterator,Compare>(),
183  auto_partitioner() );
184 }
185 
186 } // namespace internal
188 } // namespace interfaceX
189 
202 
204 
207 template<typename RandomAccessIterator, typename Compare>
208 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp) {
209  const int min_parallel_size = 500;
210  if( end > begin ) {
211  if (end - begin < min_parallel_size) {
212  std::sort(begin, end, comp);
213  } else {
214  interface9::internal::parallel_quick_sort(begin, end, comp);
215  }
216  }
217 }
218 
220 
221 template<typename RandomAccessIterator>
222 inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
223  parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
224 }
225 
227 
228 template<typename Range, typename Compare>
229 void parallel_sort(Range& rng, const Compare& comp) {
230  parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
231 }
232 
234 
235 template<typename Range, typename Compare>
236 void parallel_sort(const Range& rng, const Compare& comp) {
237  parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
238 }
239 
241 
242 template<typename Range>
243 void parallel_sort(Range& rng) {
244  parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
245 }
246 
248 
249 template<typename Range>
250 void parallel_sort(const Range& rng) {
251  parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
252 }
253 
255 
256 template<typename T>
257 inline void parallel_sort( T * begin, T * end ) {
258  parallel_sort( begin, end, std::less< T >() );
259 }
261 
262 
263 } // namespace tbb
264 
265 #endif
266 
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
Definition: parallel_sort.h:208
void parallel_for(const Range &range, const Body &body)
Parallel iteration over range with default partitioner.
Definition: parallel_for.h:185
*/
Definition: material.h:665
Definition: _flow_graph_async_msg_impl.h:32
The namespace tbb contains all components of the library.
Definition: parallel_for.h:44