32 #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
33 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
49 template<
typename RandomAccessIterator,
typename Comparator>
50 typename std::iterator_traits<RandomAccessIterator>::difference_type
52 RandomAccessIterator end,
54 <RandomAccessIterator>::difference_type pivot_rank,
56 <RandomAccessIterator>::difference_type
60 typedef typename traits_type::value_type value_type;
61 typedef typename traits_type::difference_type difference_type;
63 difference_type n = end - begin;
64 num_samples =
std::min(num_samples, n);
68 static_cast<value_type*
>(::operator
new(num_samples
69 *
sizeof(value_type)));
71 for (difference_type s = 0; s < num_samples; ++s)
73 const unsigned long long index =
static_cast<unsigned long long>(s)
75 ::new(&(samples[s])) value_type(begin[index]);
78 __gnu_sequential::sort(samples, samples + num_samples, comp);
80 value_type& pivot = samples[pivot_rank * num_samples / n];
84 difference_type split =
87 ::operator
delete(samples);
99 template<
typename RandomAccessIterator,
typename Comparator>
102 RandomAccessIterator end,
107 typedef typename traits_type::value_type value_type;
108 typedef typename traits_type::difference_type difference_type;
110 if (num_threads <= 1)
112 __gnu_sequential::sort(begin, end, comp);
116 difference_type n = end - begin, pivot_rank;
123 if ((num_threads % 2) == 1)
124 num_threads_left = num_threads / 2 + 1;
126 num_threads_left = num_threads / 2;
128 pivot_rank = n * num_threads_left / num_threads;
130 difference_type split =
135 #pragma omp parallel sections num_threads(2)
139 comp, num_threads_left);
142 comp, num_threads - num_threads_left);
155 template<
typename RandomAccessIterator,
typename Comparator>
158 RandomAccessIterator end,
165 typedef typename traits_type::value_type value_type;
166 typedef typename traits_type::difference_type difference_type;
168 difference_type n = end - begin;
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
std::iterator_traits< RandomAccessIterator >::difference_type parallel_partition(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads)
Parallel implementation of std::partition.
Similar to std::binder2nd, but giving the argument types explicitly.
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort(). This file is a GNU parallel extension to the Standard C++ Library.
std::iterator_traits< RandomAccessIterator >::difference_type parallel_sort_qs_divide(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type pivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_type num_samples, thread_index_t num_threads)
Unbalanced quicksort divide step.
GNU parallel code for public use.
static const _Settings & get()
Get the global settings.
void parallel_sort_qs(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
Unbalanced quicksort main call.
void parallel_sort_qs_conquer(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
Unbalanced quicksort conquer step.
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...