1 /*
2 Copyright (c) 2005-2020 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #ifndef __TBB_parallel_sort_H
18 #define __TBB_parallel_sort_H
19
20 #define __TBB_parallel_sort_H_include_area
21 #include "internal/_warning_suppress_enable_notice.h"
22
23 #include "parallel_for.h"
24 #include "blocked_range.h"
25 #include "internal/_range_iterator.h"
26 #include <algorithm>
27 #include <iterator>
28 #include <functional>
29 #if __TBB_TASK_GROUP_CONTEXT
30 #include "tbb_profiling.h"
31 #endif
32
33 namespace tbb {
34
35 namespace interface9 {
36 //! @cond INTERNAL
37 namespace internal {
38
39 using tbb::internal::no_assign;
40
41 //! Range used in quicksort to split elements into subranges based on a value.
42 /** The split operation selects a splitter and places all elements less than or equal
43 to the value in the first range and the remaining elements in the second range.
44 @ingroup algorithms */
45 template<typename RandomAccessIterator, typename Compare>
46 class quick_sort_range: private no_assign {
47
median_of_three(const RandomAccessIterator & array,size_t l,size_t m,size_t r)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 ) );
51 }
52
pseudo_median_of_nine(const RandomAccessIterator & array,const quick_sort_range & range)53 inline size_t pseudo_median_of_nine( const RandomAccessIterator &array, const quick_sort_range &range ) const {
54 size_t offset = range.size/8u;
55 return median_of_three(array,
56 median_of_three(array, 0, offset, offset*2),
57 median_of_three(array, offset*3, offset*4, offset*5),
58 median_of_three(array, offset*6, offset*7, range.size - 1) );
59
60 }
61
split_range(quick_sort_range & range)62 size_t split_range( quick_sort_range& range ) {
63 using std::iter_swap;
64 RandomAccessIterator array = range.begin;
65 RandomAccessIterator key0 = range.begin;
66 size_t m = pseudo_median_of_nine(array, range);
67 if (m) iter_swap ( array, array+m );
68
69 size_t i=0;
70 size_t j=range.size;
71 // Partition interval [i+1,j-1] with key *key0.
72 for(;;) {
73 __TBB_ASSERT( i<j, NULL );
74 // Loop must terminate since array[l]==*key0.
75 do {
76 --j;
77 __TBB_ASSERT( i<=j, "bad ordering relation?" );
78 } while( comp( *key0, array[j] ));
79 do {
80 __TBB_ASSERT( i<=j, NULL );
81 if( i==j ) goto partition;
82 ++i;
83 } while( comp( array[i],*key0 ));
84 if( i==j ) goto partition;
85 iter_swap( array+i, array+j );
86 }
87 partition:
88 // Put the partition key were it belongs
89 iter_swap( array+j, key0 );
90 // array[l..j) is less or equal to key.
91 // array(j..r) is greater or equal to key.
92 // array[j] is equal to key
93 i=j+1;
94 size_t new_range_size = range.size-i;
95 range.size = j;
96 return new_range_size;
97 }
98
99 public:
100
101 static const size_t grainsize = 500;
102 const Compare ∁
103 size_t size;
104 RandomAccessIterator begin;
105
quick_sort_range(RandomAccessIterator begin_,size_t size_,const Compare & comp_)106 quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) :
107 comp(comp_), size(size_), begin(begin_) {}
108
empty()109 bool empty() const {return size==0;}
is_divisible()110 bool is_divisible() const {return size>=grainsize;}
111
quick_sort_range(quick_sort_range & range,split)112 quick_sort_range( quick_sort_range& range, split )
113 : comp(range.comp)
114 , size(split_range(range))
115 // +1 accounts for the pivot element, which is at its correct place
116 // already and, therefore, is not included into subranges.
117 , begin(range.begin+range.size+1) {}
118 };
119
120 #if __TBB_TASK_GROUP_CONTEXT
121 //! Body class used to test if elements in a range are presorted
122 /** @ingroup algorithms */
123 template<typename RandomAccessIterator, typename Compare>
124 class quick_sort_pretest_body : no_assign {
125 const Compare ∁
126
127 public:
quick_sort_pretest_body(const Compare & _comp)128 quick_sort_pretest_body(const Compare &_comp) : comp(_comp) {}
129
operator()130 void operator()( const blocked_range<RandomAccessIterator>& range ) const {
131 task &my_task = task::self();
132 RandomAccessIterator my_end = range.end();
133
134 int i = 0;
135 for (RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i) {
136 if ( i%64 == 0 && my_task.is_cancelled() ) break;
137
138 // The k-1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1
139 if ( comp( *(k), *(k-1) ) ) {
140 my_task.cancel_group_execution();
141 break;
142 }
143 }
144 }
145
146 };
147 #endif /* __TBB_TASK_GROUP_CONTEXT */
148
149 //! Body class used to sort elements in a range that is smaller than the grainsize.
150 /** @ingroup algorithms */
151 template<typename RandomAccessIterator, typename Compare>
152 struct quick_sort_body {
operatorquick_sort_body153 void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const {
154 //SerialQuickSort( range.begin, range.size, range.comp );
155 std::sort( range.begin, range.begin + range.size, range.comp );
156 }
157 };
158
159 //! Wrapper method to initiate the sort by calling parallel_for.
160 /** @ingroup algorithms */
161 template<typename RandomAccessIterator, typename Compare>
parallel_quick_sort(RandomAccessIterator begin,RandomAccessIterator end,const Compare & comp)162 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
163 #if __TBB_TASK_GROUP_CONTEXT
164 task_group_context my_context(PARALLEL_SORT);
165 const int serial_cutoff = 9;
166
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;
172 }
173 }
174
175 parallel_for( blocked_range<RandomAccessIterator>(k+1, end),
176 quick_sort_pretest_body<RandomAccessIterator,Compare>(comp),
177 auto_partitioner(),
178 my_context);
179
180 if (my_context.is_group_execution_cancelled())
181 do_parallel_quick_sort:
182 #endif /* __TBB_TASK_GROUP_CONTEXT */
183 parallel_for( quick_sort_range<RandomAccessIterator,Compare>(begin, end-begin, comp ),
184 quick_sort_body<RandomAccessIterator,Compare>(),
185 auto_partitioner() );
186 }
187
188 } // namespace internal
189 //! @endcond
190 } // namespace interfaceX
191
192 /** \page parallel_sort_iter_req Requirements on iterators for parallel_sort
193 Requirements on the iterator type \c It and its value type \c T for \c parallel_sort:
194
195 - \code void iter_swap( It a, It b ) \endcode Swaps the values of the elements the given
196 iterators \c a and \c b are pointing to. \c It should be a random access iterator.
197
198 - \code bool Compare::operator()( const T& x, const T& y ) \endcode True if x comes before y;
199 **/
200
201 /** \name parallel_sort
202 See also requirements on \ref parallel_sort_iter_req "iterators for parallel_sort". **/
203 //@{
204
205 //! Sorts the data in [begin,end) using the given comparator
206 /** The compare function object is used for all comparisons between elements during sorting.
207 The compare object must define a bool operator() function.
208 @ingroup algorithms **/
209 template<typename RandomAccessIterator, typename Compare>
parallel_sort(RandomAccessIterator begin,RandomAccessIterator end,const Compare & comp)210 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp) {
211 const int min_parallel_size = 500;
212 if( end > begin ) {
213 if (end - begin < min_parallel_size) {
214 std::sort(begin, end, comp);
215 } else {
216 interface9::internal::parallel_quick_sort(begin, end, comp);
217 }
218 }
219 }
220
221 //! Sorts the data in [begin,end) with a default comparator \c std::less<RandomAccessIterator>
222 /** @ingroup algorithms **/
223 template<typename RandomAccessIterator>
parallel_sort(RandomAccessIterator begin,RandomAccessIterator end)224 inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
225 parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
226 }
227
228 //! Sorts the data in rng using the given comparator
229 /** @ingroup algorithms **/
230 template<typename Range, typename Compare>
parallel_sort(Range & rng,const Compare & comp)231 void parallel_sort(Range& rng, const Compare& comp) {
232 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
233 }
234
235 //! Sorts the data in rng with a default comparator \c std::less<RandomAccessIterator>
236 /** @ingroup algorithms **/
237 template<typename Range>
parallel_sort(Range & rng)238 void parallel_sort(Range& rng) {
239 parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
240 }
241
242 //! Sorts the data in the range \c [begin,end) with a default comparator \c std::less<T>
243 /** @ingroup algorithms **/
244 template<typename T>
parallel_sort(T * begin,T * end)245 inline void parallel_sort( T * begin, T * end ) {
246 parallel_sort( begin, end, std::less< T >() );
247 }
248 //@}
249
250
251 } // namespace tbb
252
253 #include "internal/_warning_suppress_disable_notice.h"
254 #undef __TBB_parallel_sort_H_include_area
255
256 #endif
257
258