libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/sort.h 00026 * @brief Parallel sorting algorithm switch. 00027 * This file is a GNU parallel extension to the Standard C++ Library. 00028 */ 00029 00030 // Written by Johannes Singler. 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 //prototype 00058 template<bool __stable, typename _RAIter, 00059 typename _Compare, typename _Parallelism> 00060 void 00061 __parallel_sort(_RAIter __begin, _RAIter __end, 00062 _Compare __comp, _Parallelism __parallelism); 00063 00064 /** 00065 * @brief Choose multiway mergesort, splitting variant at run-time, 00066 * for parallel sorting. 00067 * @param __begin Begin iterator of input sequence. 00068 * @param __end End iterator of input sequence. 00069 * @param __comp Comparator. 00070 * @callgraph 00071 */ 00072 template<bool __stable, typename _RAIter, typename _Compare> 00073 inline void 00074 __parallel_sort(_RAIter __begin, _RAIter __end, 00075 _Compare __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 * @brief Choose multiway mergesort with exact splitting, 00089 * for parallel sorting. 00090 * @param __begin Begin iterator of input sequence. 00091 * @param __end End iterator of input sequence. 00092 * @param __comp Comparator. 00093 * @callgraph 00094 */ 00095 template<bool __stable, typename _RAIter, typename _Compare> 00096 inline void 00097 __parallel_sort(_RAIter __begin, _RAIter __end, 00098 _Compare __comp, 00099 multiway_mergesort_exact_tag __parallelism) 00100 { 00101 _GLIBCXX_CALL(__end - __begin) 00102 00103 parallel_sort_mwms<__stable, true> 00104 (__begin, __end, __comp, __parallelism.__get_num_threads()); 00105 } 00106 00107 /** 00108 * @brief Choose multiway mergesort with splitting by sampling, 00109 * for parallel sorting. 00110 * @param __begin Begin iterator of input sequence. 00111 * @param __end End iterator of input sequence. 00112 * @param __comp Comparator. 00113 * @callgraph 00114 */ 00115 template<bool __stable, typename _RAIter, typename _Compare> 00116 inline void 00117 __parallel_sort(_RAIter __begin, _RAIter __end, 00118 _Compare __comp, 00119 multiway_mergesort_sampling_tag __parallelism) 00120 { 00121 _GLIBCXX_CALL(__end - __begin) 00122 00123 parallel_sort_mwms<__stable, false> 00124 (__begin, __end, __comp, __parallelism.__get_num_threads()); 00125 } 00126 00127 /** 00128 * @brief Choose quicksort for parallel sorting. 00129 * @param __begin Begin iterator of input sequence. 00130 * @param __end End iterator of input sequence. 00131 * @param __comp Comparator. 00132 * @callgraph 00133 */ 00134 template<bool __stable, typename _RAIter, typename _Compare> 00135 inline void 00136 __parallel_sort(_RAIter __begin, _RAIter __end, 00137 _Compare __comp, quicksort_tag __parallelism) 00138 { 00139 _GLIBCXX_CALL(__end - __begin) 00140 00141 _GLIBCXX_PARALLEL_ASSERT(__stable == false); 00142 00143 __parallel_sort_qs(__begin, __end, __comp, 00144 __parallelism.__get_num_threads()); 00145 } 00146 00147 /** 00148 * @brief Choose balanced quicksort for parallel sorting. 00149 * @param __begin Begin iterator of input sequence. 00150 * @param __end End iterator of input sequence. 00151 * @param __comp Comparator. 00152 * @param __stable Sort __stable. 00153 * @callgraph 00154 */ 00155 template<bool __stable, typename _RAIter, typename _Compare> 00156 inline void 00157 __parallel_sort(_RAIter __begin, _RAIter __end, 00158 _Compare __comp, balanced_quicksort_tag __parallelism) 00159 { 00160 _GLIBCXX_CALL(__end - __begin) 00161 00162 _GLIBCXX_PARALLEL_ASSERT(__stable == false); 00163 00164 __parallel_sort_qsb(__begin, __end, __comp, 00165 __parallelism.__get_num_threads()); 00166 } 00167 00168 /** 00169 * @brief Choose multiway mergesort with exact splitting, 00170 * for parallel sorting. 00171 * @param __begin Begin iterator of input sequence. 00172 * @param __end End iterator of input sequence. 00173 * @param __comp Comparator. 00174 * @callgraph 00175 */ 00176 template<bool __stable, typename _RAIter, typename _Compare> 00177 inline void 00178 __parallel_sort(_RAIter __begin, _RAIter __end, 00179 _Compare __comp, default_parallel_tag __parallelism) 00180 { 00181 _GLIBCXX_CALL(__end - __begin) 00182 00183 __parallel_sort<__stable> 00184 (__begin, __end, __comp, 00185 multiway_mergesort_exact_tag(__parallelism.__get_num_threads())); 00186 } 00187 00188 /** 00189 * @brief Choose a parallel sorting algorithm. 00190 * @param __begin Begin iterator of input sequence. 00191 * @param __end End iterator of input sequence. 00192 * @param __comp Comparator. 00193 * @param __stable Sort __stable. 00194 * @callgraph 00195 */ 00196 template<bool __stable, typename _RAIter, typename _Compare> 00197 inline void 00198 __parallel_sort(_RAIter __begin, _RAIter __end, 00199 _Compare __comp, parallel_tag __parallelism) 00200 { 00201 _GLIBCXX_CALL(__end - __begin) 00202 typedef std::iterator_traits<_RAIter> _TraitsType; 00203 typedef typename _TraitsType::value_type _ValueType; 00204 typedef typename _TraitsType::difference_type _DifferenceType; 00205 00206 if (false) ; 00207 #if _GLIBCXX_MERGESORT 00208 else if (__stable || _Settings::get().sort_algorithm == MWMS) 00209 { 00210 if(_Settings::get().sort_splitting == EXACT) 00211 parallel_sort_mwms<__stable, true> 00212 (__begin, __end, __comp, __parallelism.__get_num_threads()); 00213 else 00214 parallel_sort_mwms<false, false> 00215 (__begin, __end, __comp, __parallelism.__get_num_threads()); 00216 } 00217 #endif 00218 #if _GLIBCXX_QUICKSORT 00219 else if (_Settings::get().sort_algorithm == QS) 00220 __parallel_sort_qs(__begin, __end, __comp, 00221 __parallelism.__get_num_threads()); 00222 #endif 00223 #if _GLIBCXX_BAL_QUICKSORT 00224 else if (_Settings::get().sort_algorithm == QS_BALANCED) 00225 __parallel_sort_qsb(__begin, __end, __comp, 00226 __parallelism.__get_num_threads()); 00227 #endif 00228 else 00229 __gnu_sequential::sort(__begin, __end, __comp); 00230 } 00231 } // end namespace __gnu_parallel 00232 00233 #endif /* _GLIBCXX_PARALLEL_SORT_H */