diff options
author | paolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4> | 2009-11-06 11:39:35 +0000 |
---|---|---|
committer | paolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4> | 2009-11-06 11:39:35 +0000 |
commit | 757532bc0009f194eb011d0d83d1667bd147dd9e (patch) | |
tree | 1adc66e5655ae213d189aebc713a5de316b8dbee /libstdc++-v3/include/parallel/quicksort.h | |
parent | fc5c0d58120116e4853824dd1dec0d007ede1738 (diff) | |
download | gcc-757532bc0009f194eb011d0d83d1667bd147dd9e.tar.gz |
2009-11-06 Paolo Carlini <paolo.carlini@oracle.com>
* include/parallel/multiway_merge.h: Simple formatting and
uglification fixes.
* include/parallel/find_selectors.h: Likewise.
* include/parallel/losertree.h: Likewise.
* include/parallel/list_partition.h: Likewise.
* include/parallel/for_each.h: Likewise.
* include/parallel/multiseq_selection.h: Likewise.
* include/parallel/workstealing.h: Likewise.
* include/parallel/par_loop.h: Likewise.
* include/parallel/numeric: Likewise.
* include/parallel/quicksort.h: Likewise.
* include/parallel/equally_split.h: Likewise.
* include/parallel/omp_loop_static.h: Likewise.
* include/parallel/random_shuffle.h: Likewise.
* include/parallel/balanced_quicksort.h: Likewise.
* include/parallel/tags.h: Likewise.
* include/parallel/set_operations.h: Likewise.
* include/parallel/merge.h: Likewise.
* include/parallel/unique_copy.h: Likewise.
* include/parallel/multiway_mergesort.h: Likewise.
* include/parallel/search.h: Likewise.
* include/parallel/partition.h: Likewise.
* include/parallel/partial_sum.h: Likewise.
* include/parallel/find.h: Likewise.
* include/parallel/queue.h: Likewise.
* include/parallel/omp_loop.h: Likewise.
* include/parallel/checkers.h: Likewise.
* include/parallel/sort.h: Likewise.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@153966 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3/include/parallel/quicksort.h')
-rw-r--r-- | libstdc++-v3/include/parallel/quicksort.h | 56 |
1 files changed, 25 insertions, 31 deletions
diff --git a/libstdc++-v3/include/parallel/quicksort.h b/libstdc++-v3/include/parallel/quicksort.h index 1ed46b4a77f..508c3c1763c 100644 --- a/libstdc++-v3/include/parallel/quicksort.h +++ b/libstdc++-v3/include/parallel/quicksort.h @@ -48,13 +48,12 @@ namespace __gnu_parallel */ template<typename _RAIter, typename _Compare> typename std::iterator_traits<_RAIter>::difference_type - __parallel_sort_qs_divide(_RAIter __begin, - _RAIter __end, - _Compare __comp, typename std::iterator_traits - <_RAIter>::difference_type __pivot_rank, - typename std::iterator_traits - <_RAIter>::difference_type - __num_samples, _ThreadIndex __num_threads) + __parallel_sort_qs_divide(_RAIter __begin, _RAIter __end, + _Compare __comp, typename std::iterator_traits + <_RAIter>::difference_type __pivot_rank, + typename std::iterator_traits + <_RAIter>::difference_type + __num_samples, _ThreadIndex __num_threads) { typedef std::iterator_traits<_RAIter> _TraitsType; typedef typename _TraitsType::value_type _ValueType; @@ -64,25 +63,24 @@ namespace __gnu_parallel __num_samples = std::min(__num_samples, __n); // Allocate uninitialized, to avoid default constructor. - _ValueType* __samples = - static_cast<_ValueType*>(::operator new(__num_samples - * sizeof(_ValueType))); + _ValueType* __samples = static_cast<_ValueType*> + (::operator new(__num_samples * sizeof(_ValueType))); for (_DifferenceType __s = 0; __s < __num_samples; ++__s) { - const unsigned long long __index - = static_cast<unsigned long long>(__s) * __n / __num_samples; + const unsigned long long __index = static_cast<unsigned long long> + (__s) * __n / __num_samples; ::new(&(__samples[__s])) _ValueType(__begin[__index]); } __gnu_sequential::sort(__samples, __samples + __num_samples, __comp); - _ValueType& pivot = __samples[__pivot_rank * __num_samples / __n]; + _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n]; __gnu_parallel::binder2nd<_Compare, _ValueType, _ValueType, bool> - __pred(__comp, pivot); - _DifferenceType __split = - __parallel_partition(__begin, __end, __pred, __num_threads); + __pred(__comp, __pivot); + _DifferenceType __split = __parallel_partition(__begin, __end, + __pred, __num_threads); ::operator delete(__samples); @@ -98,10 +96,9 @@ namespace __gnu_parallel */ template<typename _RAIter, typename _Compare> void - __parallel_sort_qs_conquer(_RAIter __begin, - _RAIter __end, - _Compare __comp, - _ThreadIndex __num_threads) + __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end, + _Compare __comp, + _ThreadIndex __num_threads) { typedef std::iterator_traits<_RAIter> _TraitsType; typedef typename _TraitsType::value_type _ValueType; @@ -127,24 +124,22 @@ namespace __gnu_parallel __pivot_rank = __n * __num_threads_left / __num_threads; - _DifferenceType __split = - __parallel_sort_qs_divide(__begin, __end, __comp, __pivot_rank, - _Settings::get().sort_qs_num_samples_preset, - __num_threads); + _DifferenceType __split = __parallel_sort_qs_divide + (__begin, __end, __comp, __pivot_rank, + _Settings::get().sort_qs_num_samples_preset, __num_threads); #pragma omp parallel sections num_threads(2) { #pragma omp section __parallel_sort_qs_conquer(__begin, __begin + __split, - __comp, __num_threads_left); + __comp, __num_threads_left); #pragma omp section __parallel_sort_qs_conquer(__begin + __split, __end, - __comp, __num_threads - __num_threads_left); + __comp, __num_threads - __num_threads_left); } } - /** @brief Unbalanced quicksort main call. * @param __begin Begin iterator of input sequence. * @param __end End iterator input sequence, ignored. @@ -154,10 +149,9 @@ namespace __gnu_parallel */ template<typename _RAIter, typename _Compare> void - __parallel_sort_qs(_RAIter __begin, - _RAIter __end, - _Compare __comp, - _ThreadIndex __num_threads) + __parallel_sort_qs(_RAIter __begin, _RAIter __end, + _Compare __comp, + _ThreadIndex __num_threads) { _GLIBCXX_CALL(__n) |