21 #ifndef __TBB_parallel_sort_H 22 #define __TBB_parallel_sort_H 24 #include "parallel_for.h" 25 #include "blocked_range.h" 26 #include "internal/_range_iterator.h" 33 namespace interface9 {
37 using tbb::internal::no_assign;
43 template<
typename RandomAccessIterator,
typename Compare>
44 class quick_sort_range:
private no_assign {
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 ) );
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) );
60 size_t split_range( quick_sort_range& range ) {
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 );
71 __TBB_ASSERT( i<j, NULL );
75 __TBB_ASSERT( i<=j,
"bad ordering relation?" );
76 }
while( comp( *key0, array[j] ));
78 __TBB_ASSERT( i<=j, NULL );
79 if( i==j )
goto partition;
81 }
while( comp( array[i],*key0 ));
82 if( i==j )
goto partition;
83 iter_swap( array+i, array+j );
87 iter_swap( array+j, key0 );
92 size_t new_range_size = range.size-i;
94 return new_range_size;
99 static const size_t grainsize = 500;
102 RandomAccessIterator begin;
104 quick_sort_range( RandomAccessIterator begin_,
size_t size_,
const Compare &comp_ ) :
105 comp(comp_), size(size_), begin(begin_) {}
107 bool empty()
const {
return size==0;}
108 bool is_divisible()
const {
return size>=grainsize;}
110 quick_sort_range( quick_sort_range& range, split )
112 , size(split_range(range))
115 , begin(range.begin+range.size+1) {}
118 #if __TBB_TASK_GROUP_CONTEXT 121 template<
typename RandomAccessIterator,
typename Compare>
122 class quick_sort_pretest_body : no_assign {
126 quick_sort_pretest_body(
const Compare &_comp) : comp(_comp) {}
128 void operator()(
const blocked_range<RandomAccessIterator>& range )
const {
129 task &my_task = task::self();
130 RandomAccessIterator my_end = range.end();
133 for (RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i) {
134 if ( i%64 == 0 && my_task.is_cancelled() )
break;
137 if ( comp( *(k), *(k-1) ) ) {
138 my_task.cancel_group_execution();
149 template<
typename RandomAccessIterator,
typename Compare>
150 struct quick_sort_body {
151 void operator()(
const quick_sort_range<RandomAccessIterator,Compare>& range )
const {
153 std::sort( range.begin, range.begin + range.size, range.comp );
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;
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;
173 parallel_for( blocked_range<RandomAccessIterator>(k+1, end),
174 quick_sort_pretest_body<RandomAccessIterator,Compare>(comp),
178 if (my_context.is_group_execution_cancelled())
179 do_parallel_quick_sort:
181 parallel_for( quick_sort_range<RandomAccessIterator,Compare>(begin, end-begin, comp ),
182 quick_sort_body<RandomAccessIterator,Compare>(),
183 auto_partitioner() );
207 template<
typename RandomAccessIterator,
typename Compare>
208 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end,
const Compare& comp) {
209 const int min_parallel_size = 500;
211 if (end - begin < min_parallel_size) {
212 std::sort(begin, end, comp);
214 interface9::internal::parallel_quick_sort(begin, end, comp);
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 >() );
228 template<
typename Range,
typename Compare>
230 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
235 template<
typename Range,
typename Compare>
237 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
242 template<
typename Range>
244 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
249 template<
typename Range>
251 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
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