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