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 RandomAccessIterator, 00059 typename Comparator, typename Parallelism> 00060 void 00061 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 00062 Comparator 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 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 * @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 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 * @brief Choose multiway mergesort with splitting by sampling, 00108 * for parallel sorting. 00109 * @param begin Begin iterator of input sequence. 00110 * @param end End iterator of input sequence. 00111 * @param comp Comparator. 00112 * @callgraph 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 * @brief Choose quicksort for parallel sorting. 00127 * @param begin Begin iterator of input sequence. 00128 * @param end End iterator of input sequence. 00129 * @param comp Comparator. 00130 * @callgraph 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 * @brief Choose balanced quicksort for parallel sorting. 00146 * @param begin Begin iterator of input sequence. 00147 * @param end End iterator of input sequence. 00148 * @param comp Comparator. 00149 * @param stable Sort stable. 00150 * @callgraph 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 * @brief Choose multiway mergesort with exact splitting, 00167 * for parallel sorting. 00168 * @param begin Begin iterator of input sequence. 00169 * @param end End iterator of input sequence. 00170 * @param comp Comparator. 00171 * @callgraph 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 * @brief Choose a parallel sorting algorithm. 00188 * @param begin Begin iterator of input sequence. 00189 * @param end End iterator of input sequence. 00190 * @param comp Comparator. 00191 * @param stable Sort stable. 00192 * @callgraph 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 } // end namespace __gnu_parallel 00228 00229 #endif /* _GLIBCXX_PARALLEL_SORT_H */