17 #ifndef __TBB_parallel_sort_H 18 #define __TBB_parallel_sort_H 26 #if __TBB_TASK_GROUP_CONTEXT 32 namespace interface9 {
42 template<
typename RandomAccessIterator,
typename Compare>
45 inline size_t median_of_three(
const RandomAccessIterator &array,
size_t l,
size_t m,
size_t r)
const {
46 return comp(array[l], array[m]) ? (
comp(array[m], array[r]) ? m : (
comp( array[l], array[r]) ? r : l ) )
47 : (
comp(array[r], array[m]) ? m : (
comp( array[r], array[l] ) ? r : l ) );
51 size_t offset = range.
size/8u;
61 RandomAccessIterator array = range.
begin;
62 RandomAccessIterator key0 = range.
begin;
64 if (m) iter_swap ( array, array+m );
75 }
while(
comp( *key0, array[j] ));
78 if( i==j )
goto partition;
80 }
while(
comp( array[i],*key0 ));
81 if( i==j )
goto partition;
82 iter_swap( array+i, array+j );
86 iter_swap( array+j, key0 );
91 size_t new_range_size = range.
size-i;
93 return new_range_size;
117 #if __TBB_TASK_GROUP_CONTEXT 120 template<
typename RandomAccessIterator,
typename Compare>
129 RandomAccessIterator my_end = range.
end();
132 for (RandomAccessIterator k = range.
begin(); k != my_end; ++k, ++i) {
136 if (
comp( *(k), *(k-1) ) ) {
148 template<
typename RandomAccessIterator,
typename Compare>
158 template<
typename RandomAccessIterator,
typename Compare>
160 #if __TBB_TASK_GROUP_CONTEXT 162 const int serial_cutoff = 9;
164 __TBB_ASSERT(
begin + serial_cutoff <
end,
"min_parallel_size is smaller than serial cutoff?" );
165 RandomAccessIterator k =
begin;
166 for ( ; k !=
begin + serial_cutoff; ++k ) {
167 if ( comp( *(k+1), *k ) ) {
168 goto do_parallel_quick_sort;
178 do_parallel_quick_sort:
206 template<
typename RandomAccessIterator,
typename Compare>
208 const int min_parallel_size = 500;
210 if (
end -
begin < min_parallel_size) {
220 template<
typename RandomAccessIterator>
222 parallel_sort(
begin,
end, std::less<
typename std::iterator_traits<RandomAccessIterator>::value_type >() );
227 template<
typename Range,
typename Compare>
234 template<
typename Range>
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
quick_sort_pretest_body(const Compare &_comp)
static task &__TBB_EXPORTED_FUNC self()
The innermost task being executed or destroyed by the current thread at the moment.
Dummy type that distinguishes splitting constructor from copy constructor.
void parallel_quick_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Wrapper method to initiate the sort by calling parallel_for.
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
void parallel_for(const Range &range, const Body &body)
Parallel iteration over range with default partitioner.
RandomAccessIterator begin
bool cancel_group_execution()
Initiates cancellation of all tasks in this cancellation group and its subordinate groups.
Used to form groups of tasks.
Body class used to sort elements in a range that is smaller than the grainsize.
quick_sort_range(quick_sort_range &range, split)
void operator()(const blocked_range< RandomAccessIterator > &range) const
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
Base class for user-defined tasks.
const_iterator begin() const
Beginning of range.
Base class for types that should not be assigned.
bool __TBB_EXPORTED_METHOD is_group_execution_cancelled() const
Returns true if the context received cancellation request.
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
Body class used to test if elements in a range are presorted.
auto first(Container &c) -> decltype(begin(c))
Range used in quicksort to split elements into subranges based on a value.
static const size_t grainsize
auto last(Container &c) -> decltype(begin(c))
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
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
const_iterator end() const
One past last value in range.
bool is_cancelled() const
Returns true if the context has received cancellation request.
A range over which to iterate.
bool is_divisible() const
size_t split_range(quick_sort_range &range)