Intel(R) Threading Building Blocks Doxygen Documentation
version 4.2.3
|
Go to the documentation of this file.
17 #ifndef __TBB_parallel_sort_H
18 #define __TBB_parallel_sort_H
20 #define __TBB_parallel_sort_H_include_area
29 #if __TBB_TASK_GROUP_CONTEXT
35 namespace interface9 {
45 template<
typename RandomAccessIterator,
typename Compare>
48 inline size_t median_of_three(
const RandomAccessIterator &array,
size_t l,
size_t m,
size_t r)
const {
49 return comp(array[l], array[m]) ? (
comp(array[m], array[r]) ? m : (
comp( array[l], array[r]) ? r : l ) )
50 : (
comp(array[r], array[m]) ? m : (
comp( array[r], array[l] ) ? r : l ) );
54 size_t offset = range.
size/8u;
64 RandomAccessIterator array = range.
begin;
65 RandomAccessIterator key0 = range.
begin;
67 if (m) iter_swap ( array, array+m );
78 }
while(
comp( *key0, array[j] ));
81 if( i==j )
goto partition;
83 }
while(
comp( array[i],*key0 ));
84 if( i==j )
goto partition;
85 iter_swap( array+i, array+j );
89 iter_swap( array+j, key0 );
94 size_t new_range_size = range.
size-i;
96 return new_range_size;
120 #if __TBB_TASK_GROUP_CONTEXT
123 template<
typename RandomAccessIterator,
typename Compare>
132 RandomAccessIterator my_end = range.
end();
135 for (RandomAccessIterator k = range.
begin(); k != my_end; ++k, ++i) {
139 if (
comp( *(k), *(k-1) ) ) {
151 template<
typename RandomAccessIterator,
typename Compare>
161 template<
typename RandomAccessIterator,
typename Compare>
163 #if __TBB_TASK_GROUP_CONTEXT
165 const int serial_cutoff = 9;
167 __TBB_ASSERT(
begin + serial_cutoff <
end,
"min_parallel_size is smaller than serial cutoff?" );
168 RandomAccessIterator k =
begin;
169 for ( ; k !=
begin + serial_cutoff; ++k ) {
170 if ( comp( *(k+1), *k ) ) {
171 goto do_parallel_quick_sort;
181 do_parallel_quick_sort:
209 template<
typename RandomAccessIterator,
typename Compare>
211 const int min_parallel_size = 500;
213 if (
end -
begin < min_parallel_size) {
223 template<
typename RandomAccessIterator>
225 parallel_sort(
begin,
end, std::less<
typename std::iterator_traits<RandomAccessIterator>::value_type >() );
230 template<
typename Range,
typename Compare>
237 template<
typename Range>
254 #undef __TBB_parallel_sort_H_include_area
Body class used to test if elements in a range are presorted.
void operator()(const blocked_range< RandomAccessIterator > &range) const
const_iterator begin() const
Beginning of 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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
const_iterator end() const
One past last value in range.
Range used in quicksort to split elements into subranges based on a value.
quick_sort_range(quick_sort_range &range, split)
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
bool cancel_group_execution()
Initiates cancellation of all tasks in this cancellation group and its subordinate groups.
Used to form groups of tasks.
Dummy type that distinguishes splitting constructor from copy constructor.
quick_sort_pretest_body(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
void parallel_for(const Range &range, const Body &body)
Parallel iteration over range with default partitioner.
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
Base class for types that should not be assigned.
Base class for user-defined tasks.
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
size_t split_range(quick_sort_range &range)
RandomAccessIterator begin
A range over which to iterate.
bool is_cancelled() const
Returns true if the context has received cancellation request.
bool is_divisible() const
auto first(Container &c) -> decltype(begin(c))
Body class used to sort elements in a range that is smaller than the grainsize.
bool __TBB_EXPORTED_METHOD is_group_execution_cancelled() const
Returns true if the context received cancellation request.
static const size_t grainsize
auto last(Container &c) -> decltype(begin(c))
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
static task &__TBB_EXPORTED_FUNC self()
The innermost task being executed or destroyed by the current thread at the moment.
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
void parallel_quick_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Wrapper method to initiate the sort by calling parallel_for.
Copyright © 2005-2020 Intel Corporation. All Rights Reserved.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are
registered trademarks or trademarks of Intel Corporation or its
subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.