21 #ifndef __TBB_parallel_sort_H 22 #define __TBB_parallel_sort_H 30 #if __TBB_TASK_GROUP_CONTEXT 36 namespace interface9 {
46 template<
typename RandomAccessIterator,
typename Compare>
49 inline size_t median_of_three(
const RandomAccessIterator &array,
size_t l,
size_t m,
size_t r)
const {
50 return comp(array[l], array[m]) ? (
comp(array[m], array[r]) ? m : (
comp( array[l], array[r]) ? r : l ) )
51 : (
comp(array[r], array[m]) ? m : (
comp( array[r], array[l] ) ? r : l ) );
55 size_t offset = range.
size/8u;
65 RandomAccessIterator array = range.
begin;
66 RandomAccessIterator key0 = range.
begin;
68 if (m) iter_swap ( array, array+m );
79 }
while(
comp( *key0, array[j] ));
82 if( i==j )
goto partition;
84 }
while(
comp( array[i],*key0 ));
85 if( i==j )
goto partition;
86 iter_swap( array+i, array+j );
90 iter_swap( array+j, key0 );
95 size_t new_range_size = range.
size-i;
97 return new_range_size;
121 #if __TBB_TASK_GROUP_CONTEXT 124 template<
typename RandomAccessIterator,
typename Compare>
133 RandomAccessIterator my_end = range.
end();
136 for (RandomAccessIterator k = range.
begin(); k != my_end; ++k, ++i) {
140 if (
comp( *(k), *(k-1) ) ) {
152 template<
typename RandomAccessIterator,
typename Compare>
162 template<
typename RandomAccessIterator,
typename Compare>
164 #if __TBB_TASK_GROUP_CONTEXT 166 const int serial_cutoff = 9;
168 __TBB_ASSERT(
begin + serial_cutoff <
end,
"min_parallel_size is smaller than serial cutoff?" );
169 RandomAccessIterator k =
begin;
170 for ( ; k !=
begin + serial_cutoff; ++k ) {
171 if ( comp( *(k+1), *k ) ) {
172 goto do_parallel_quick_sort;
182 do_parallel_quick_sort:
210 template<
typename RandomAccessIterator,
typename Compare>
212 const int min_parallel_size = 500;
214 if (
end -
begin < min_parallel_size) {
224 template<
typename RandomAccessIterator>
226 parallel_sort(
begin,
end, std::less<
typename std::iterator_traits<RandomAccessIterator>::value_type >() );
231 template<
typename Range,
typename Compare>
238 template<
typename Range>
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
const_iterator begin() const
Beginning of range.
size_t split_range(quick_sort_range &range)
Range used in quicksort to split elements into subranges based on a value.
A range over which to iterate.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
auto first(Container &c) -> decltype(begin(c))
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
Used to form groups of tasks.
Base class for user-defined tasks.
static task &__TBB_EXPORTED_FUNC self()
The innermost task being executed or destroyed by the current thread at the moment.
Base class for types that should not be assigned.
void operator()(const blocked_range< RandomAccessIterator > &range) const
auto last(Container &c) -> decltype(begin(c))
const_iterator end() const
One past last value in range.
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
void parallel_quick_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Wrapper method to initiate the sort by calling parallel_for.
Dummy type that distinguishes splitting constructor from copy constructor.
Body class used to sort elements in a range that is smaller than the grainsize.
void parallel_for(const Range &range, const Body &body)
Parallel iteration over range with default partitioner.
bool __TBB_EXPORTED_METHOD is_group_execution_cancelled() const
Returns true if the context received cancellation request.
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
quick_sort_pretest_body(const Compare &_comp)
bool cancel_group_execution()
Initiates cancellation of all tasks in this cancellation group and its subordinate groups.
bool is_cancelled() const
Returns true if the context has received cancellation request.
RandomAccessIterator begin
static const size_t grainsize
bool is_divisible() const
quick_sort_range(quick_sort_range &range, split)
Body class used to test if elements in a range are presorted.