Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
00033 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
00034
00035 #include <parallel/parallel.h>
00036 #include <parallel/partition.h>
00037
00038 namespace __gnu_parallel
00039 {
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 template<typename _RAIter, typename _Compare>
00050 typename std::iterator_traits<_RAIter>::difference_type
00051 __parallel_sort_qs_divide(_RAIter __begin, _RAIter __end,
00052 _Compare __comp, typename std::iterator_traits
00053 <_RAIter>::difference_type __pivot_rank,
00054 typename std::iterator_traits
00055 <_RAIter>::difference_type
00056 __num_samples, _ThreadIndex __num_threads)
00057 {
00058 typedef std::iterator_traits<_RAIter> _TraitsType;
00059 typedef typename _TraitsType::value_type _ValueType;
00060 typedef typename _TraitsType::difference_type _DifferenceType;
00061
00062 _DifferenceType __n = __end - __begin;
00063 __num_samples = std::min(__num_samples, __n);
00064
00065
00066 _ValueType* __samples = static_cast<_ValueType*>
00067 (::operator new(__num_samples * sizeof(_ValueType)));
00068
00069 for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
00070 {
00071 const unsigned long long __index = static_cast<unsigned long long>
00072 (__s) * __n / __num_samples;
00073 ::new(&(__samples[__s])) _ValueType(__begin[__index]);
00074 }
00075
00076 __gnu_sequential::sort(__samples, __samples + __num_samples, __comp);
00077
00078 _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n];
00079
00080 __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
00081 __pred(__comp, __pivot);
00082 _DifferenceType __split = __parallel_partition(__begin, __end,
00083 __pred, __num_threads);
00084
00085 ::operator delete(__samples);
00086
00087 return __split;
00088 }
00089
00090
00091
00092
00093
00094
00095
00096
00097 template<typename _RAIter, typename _Compare>
00098 void
00099 __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end,
00100 _Compare __comp,
00101 _ThreadIndex __num_threads)
00102 {
00103 typedef std::iterator_traits<_RAIter> _TraitsType;
00104 typedef typename _TraitsType::value_type _ValueType;
00105 typedef typename _TraitsType::difference_type _DifferenceType;
00106
00107 if (__num_threads <= 1)
00108 {
00109 __gnu_sequential::sort(__begin, __end, __comp);
00110 return;
00111 }
00112
00113 _DifferenceType __n = __end - __begin, __pivot_rank;
00114
00115 if (__n <= 1)
00116 return;
00117
00118 _ThreadIndex __num_threads_left;
00119
00120 if ((__num_threads % 2) == 1)
00121 __num_threads_left = __num_threads / 2 + 1;
00122 else
00123 __num_threads_left = __num_threads / 2;
00124
00125 __pivot_rank = __n * __num_threads_left / __num_threads;
00126
00127 _DifferenceType __split = __parallel_sort_qs_divide
00128 (__begin, __end, __comp, __pivot_rank,
00129 _Settings::get().sort_qs_num_samples_preset, __num_threads);
00130
00131 #pragma omp parallel sections num_threads(2)
00132 {
00133 #pragma omp section
00134 __parallel_sort_qs_conquer(__begin, __begin + __split,
00135 __comp, __num_threads_left);
00136 #pragma omp section
00137 __parallel_sort_qs_conquer(__begin + __split, __end,
00138 __comp, __num_threads - __num_threads_left);
00139 }
00140 }
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150 template<typename _RAIter, typename _Compare>
00151 void
00152 __parallel_sort_qs(_RAIter __begin, _RAIter __end,
00153 _Compare __comp,
00154 _ThreadIndex __num_threads)
00155 {
00156 _GLIBCXX_CALL(__n)
00157
00158 typedef std::iterator_traits<_RAIter> _TraitsType;
00159 typedef typename _TraitsType::value_type _ValueType;
00160 typedef typename _TraitsType::difference_type _DifferenceType;
00161
00162 _DifferenceType __n = __end - __begin;
00163
00164
00165 if (__num_threads > __n)
00166 __num_threads = static_cast<_ThreadIndex>(__n);
00167
00168 __parallel_sort_qs_conquer(
00169 __begin, __begin + __n, __comp, __num_threads);
00170 }
00171
00172 }
00173
00174 #endif