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_SORT_H
00033 #define _GLIBCXX_PARALLEL_SORT_H 1
00034
00035 #include <parallel/basic_iterator.h>
00036 #include <parallel/features.h>
00037 #include <parallel/parallel.h>
00038
00039 #if _GLIBCXX_ASSERTIONS
00040 #include <parallel/checkers.h>
00041 #endif
00042
00043 #if _GLIBCXX_MERGESORT
00044 #include <parallel/multiway_mergesort.h>
00045 #endif
00046
00047 #if _GLIBCXX_QUICKSORT
00048 #include <parallel/quicksort.h>
00049 #endif
00050
00051 #if _GLIBCXX_BAL_QUICKSORT
00052 #include <parallel/balanced_quicksort.h>
00053 #endif
00054
00055 namespace __gnu_parallel
00056 {
00057
00058 template<bool stable, typename RandomAccessIterator,
00059 typename Comparator, typename Parallelism>
00060 void
00061 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00062 Comparator comp, Parallelism parallelism);
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072 template<bool stable, typename RandomAccessIterator, typename Comparator>
00073 inline void
00074 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00075 Comparator comp, multiway_mergesort_tag parallelism)
00076 {
00077 _GLIBCXX_CALL(end - begin)
00078
00079 if(_Settings::get().sort_splitting == EXACT)
00080 parallel_sort_mwms<stable, true>
00081 (begin, end, comp, parallelism.get_num_threads());
00082 else
00083 parallel_sort_mwms<stable, false>
00084 (begin, end, comp, parallelism.get_num_threads());
00085 }
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095 template<bool stable, typename RandomAccessIterator, typename Comparator>
00096 inline void
00097 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00098 Comparator comp, multiway_mergesort_exact_tag parallelism)
00099 {
00100 _GLIBCXX_CALL(end - begin)
00101
00102 parallel_sort_mwms<stable, true>
00103 (begin, end, comp, parallelism.get_num_threads());
00104 }
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114 template<bool stable, typename RandomAccessIterator, typename Comparator>
00115 inline void
00116 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00117 Comparator comp, multiway_mergesort_sampling_tag parallelism)
00118 {
00119 _GLIBCXX_CALL(end - begin)
00120
00121 parallel_sort_mwms<stable, false>
00122 (begin, end, comp, parallelism.get_num_threads());
00123 }
00124
00125
00126
00127
00128
00129
00130
00131
00132 template<bool stable, typename RandomAccessIterator, typename Comparator>
00133 inline void
00134 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00135 Comparator comp, quicksort_tag parallelism)
00136 {
00137 _GLIBCXX_CALL(end - begin)
00138
00139 _GLIBCXX_PARALLEL_ASSERT(stable == false);
00140
00141 parallel_sort_qs(begin, end, comp, parallelism.get_num_threads());
00142 }
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152 template<bool stable, typename RandomAccessIterator, typename Comparator>
00153 inline void
00154 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00155 Comparator comp, balanced_quicksort_tag parallelism)
00156 {
00157 _GLIBCXX_CALL(end - begin)
00158
00159 _GLIBCXX_PARALLEL_ASSERT(stable == false);
00160
00161 parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
00162 }
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173 template<bool stable, typename RandomAccessIterator, typename Comparator>
00174 inline void
00175 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00176 Comparator comp, default_parallel_tag parallelism)
00177 {
00178 _GLIBCXX_CALL(end - begin)
00179
00180 parallel_sort<stable>
00181 (begin, end, comp,
00182 multiway_mergesort_exact_tag(parallelism.get_num_threads()));
00183 }
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194 template<bool stable, typename RandomAccessIterator, typename Comparator>
00195 inline void
00196 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
00197 Comparator comp, parallel_tag parallelism)
00198 {
00199 _GLIBCXX_CALL(end - begin)
00200 typedef std::iterator_traits<RandomAccessIterator> traits_type;
00201 typedef typename traits_type::value_type value_type;
00202 typedef typename traits_type::difference_type difference_type;
00203
00204 if (false) ;
00205 #if _GLIBCXX_MERGESORT
00206 else if (stable || _Settings::get().sort_algorithm == MWMS)
00207 {
00208 if(_Settings::get().sort_splitting == EXACT)
00209 parallel_sort_mwms<stable, true>
00210 (begin, end, comp, parallelism.get_num_threads());
00211 else
00212 parallel_sort_mwms<false, false>
00213 (begin, end, comp, parallelism.get_num_threads());
00214 }
00215 #endif
00216 #if _GLIBCXX_QUICKSORT
00217 else if (_Settings::get().sort_algorithm == QS)
00218 parallel_sort_qs(begin, end, comp, parallelism.get_num_threads());
00219 #endif
00220 #if _GLIBCXX_BAL_QUICKSORT
00221 else if (_Settings::get().sort_algorithm == QS_BALANCED)
00222 parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
00223 #endif
00224 else
00225 __gnu_sequential::sort(begin, end, comp);
00226 }
00227 }
00228
00229 #endif