33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
43 #define _GLIBCXX_VOLATILE volatile
45 namespace __gnu_parallel
53 template<
typename RandomAccessIterator,
typename Predicate>
54 typename std::iterator_traits<RandomAccessIterator>::difference_type
59 typedef typename traits_type::value_type value_type;
60 typedef typename traits_type::difference_type difference_type;
62 difference_type n = end - begin;
73 bool* reserved_left = NULL, * reserved_right = NULL;
77 omp_lock_t result_lock;
78 omp_init_lock(&result_lock);
81 if(
right - left + 1 >= 2 * num_threads * chunk_size)
82 # pragma omp parallel num_threads(num_threads)
86 num_threads = omp_get_num_threads();
87 reserved_left =
new bool[num_threads];
88 reserved_right =
new bool[num_threads];
93 / (
double)num_threads);
98 while (
right - left + 1 >= 2 * num_threads * chunk_size)
102 difference_type num_chunks = (
right - left + 1) / chunk_size;
104 for (
int r = 0; r < num_threads; ++r)
106 reserved_left[r] =
false;
107 reserved_right[r] =
false;
114 difference_type thread_left, thread_left_border,
115 thread_right, thread_right_border;
116 thread_left = left + 1;
119 thread_left_border = thread_left - 1;
120 thread_right = n - 1;
121 thread_right_border = thread_right + 1;
123 bool iam_finished =
false;
124 while (!iam_finished)
126 if (thread_left > thread_left_border)
128 omp_set_lock(&result_lock);
129 if (left + (chunk_size - 1) >
right)
134 thread_left_border = left + (chunk_size - 1);
137 omp_unset_lock(&result_lock);
140 if (thread_right < thread_right_border)
142 omp_set_lock(&result_lock);
143 if (left >
right - (chunk_size - 1))
147 thread_right =
right;
148 thread_right_border =
right - (chunk_size - 1);
151 omp_unset_lock(&result_lock);
158 while (thread_left < thread_right)
160 while (pred(begin[thread_left])
161 && thread_left <= thread_left_border)
163 while (!pred(begin[thread_right])
164 && thread_right >= thread_right_border)
167 if (thread_left > thread_left_border
168 || thread_right < thread_right_border)
172 std::swap(begin[thread_left], begin[thread_right]);
179 if (thread_left <= thread_left_border)
182 if (thread_right >= thread_right_border)
190 leftnew = left - leftover_left * chunk_size;
191 rightnew =
right + leftover_right * chunk_size;
197 if (thread_left <= thread_left_border
198 && thread_left_border >= leftnew)
201 reserved_left[(left - (thread_left_border + 1)) / chunk_size]
206 if (thread_right >= thread_right_border
207 && thread_right_border <= rightnew)
210 reserved_right[((thread_right_border - 1) -
right)
211 / chunk_size] =
true;
216 if (thread_left <= thread_left_border
217 && thread_left_border < leftnew)
220 difference_type swapstart = -1;
221 omp_set_lock(&result_lock);
222 for (
int r = 0; r < leftover_left; ++r)
223 if (!reserved_left[r])
225 reserved_left[r] =
true;
226 swapstart = left - (r + 1) * chunk_size;
229 omp_unset_lock(&result_lock);
231 #if _GLIBCXX_ASSERTIONS
232 _GLIBCXX_PARALLEL_ASSERT(swapstart != -1);
235 std::swap_ranges(begin + thread_left_border
237 begin + thread_left_border + 1,
241 if (thread_right >= thread_right_border
242 && thread_right_border > rightnew)
245 difference_type swapstart = -1;
246 omp_set_lock(&result_lock);
247 for (
int r = 0; r < leftover_right; ++r)
248 if (!reserved_right[r])
250 reserved_right[r] =
true;
251 swapstart =
right + r * chunk_size + 1;
254 omp_unset_lock(&result_lock);
256 #if _GLIBCXX_ASSERTIONS
257 _GLIBCXX_PARALLEL_ASSERT(swapstart != -1);
260 std::swap_ranges(begin + thread_right_border,
261 begin + thread_right_border + chunk_size,
264 #if _GLIBCXX_ASSERTIONS
269 for (
int r = 0; r < leftover_left; ++r)
270 _GLIBCXX_PARALLEL_ASSERT(reserved_left[r]);
271 for (
int r = 0; r < leftover_right; ++r)
272 _GLIBCXX_PARALLEL_ASSERT(reserved_right[r]);
283 # pragma omp flush(left, right)
286 difference_type final_left =
left, final_right =
right;
288 while (final_left < final_right)
291 while (pred(begin[final_left]) && final_left < final_right)
295 while (!pred(begin[final_right]) && final_left < final_right)
298 if (final_left == final_right)
300 std::swap(begin[final_left], begin[final_right]);
307 delete[] reserved_left;
308 delete[] reserved_right;
310 omp_destroy_lock(&result_lock);
314 if (final_left < n && !pred(begin[final_left]))
318 return final_left + 1;
328 template<
typename RandomAccessIterator,
typename Comparator>
331 RandomAccessIterator end, Comparator comp)
334 typedef typename traits_type::value_type value_type;
335 typedef typename traits_type::difference_type difference_type;
339 RandomAccessIterator split;
343 difference_type minimum_length = std::max<difference_type>(2,
347 while (static_cast<sequence_index_t>(end - begin) >= minimum_length)
349 difference_type n = end - begin;
351 RandomAccessIterator pivot_pos = begin + rng(n);
354 if (pivot_pos != (end - 1))
355 std::swap(*pivot_pos, *(end - 1));
365 pred(comp, *pivot_pos);
368 RandomAccessIterator split_pos1, split_pos2;
375 if (split_pos1 != pivot_pos)
376 std::swap(*split_pos1, *pivot_pos);
377 pivot_pos = split_pos1;
380 if ((split_pos1 + 1 - begin) < (n >> 7)
381 || (end - split_pos1) < (n >> 7))
388 value_type,
bool>(comp, *pivot_pos));
391 split_pos2 = __gnu_sequential::partition(split_pos1 + 1,
396 split_pos2 = split_pos1 + 1;
399 if (split_pos2 <= nth)
401 else if (nth < split_pos1)
408 __gnu_sequential::nth_element(begin, nth, end, comp);
416 template<
typename RandomAccessIterator,
typename Comparator>
419 RandomAccessIterator middle,
420 RandomAccessIterator end, Comparator comp)
423 std::sort(begin, middle, comp);
428 #undef _GLIBCXX_VOLATILE