1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file parallel/sort.h 26 * @brief Parallel sorting algorithm switch. 27 * This file is a GNU parallel extension to the Standard C++ Library. 28 */ 29 30 // Written by Johannes Singler. 31 32 #ifndef _GLIBCXX_PARALLEL_SORT_H 33 #define _GLIBCXX_PARALLEL_SORT_H 1 34 35 #include <parallel/basic_iterator.h> 36 #include <parallel/features.h> 37 #include <parallel/parallel.h> 38 39 #if _GLIBCXX_ASSERTIONS 40 #include <parallel/checkers.h> 41 #endif 42 43 #if _GLIBCXX_MERGESORT 44 #include <parallel/multiway_mergesort.h> 45 #endif 46 47 #if _GLIBCXX_QUICKSORT 48 #include <parallel/quicksort.h> 49 #endif 50 51 #if _GLIBCXX_BAL_QUICKSORT 52 #include <parallel/balanced_quicksort.h> 53 #endif 54 55 namespace __gnu_parallel 56 { 57 //prototype 58 template<bool stable, typename RandomAccessIterator, 59 typename Comparator, typename Parallelism> 60 void 61 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 62 Comparator comp, Parallelism parallelism); 63 64 /** 65 * @brief Choose multiway mergesort, splitting variant at run-time, 66 * for parallel sorting. 67 * @param begin Begin iterator of input sequence. 68 * @param end End iterator of input sequence. 69 * @param comp Comparator. 70 * @callgraph 71 */ 72 template<bool stable, typename RandomAccessIterator, typename Comparator> 73 inline void 74 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 75 Comparator comp, multiway_mergesort_tag parallelism) 76 { 77 _GLIBCXX_CALL(end - begin) 78 79 if(_Settings::get().sort_splitting == EXACT) 80 parallel_sort_mwms<stable, true> 81 (begin, end, comp, parallelism.get_num_threads()); 82 else 83 parallel_sort_mwms<stable, false> 84 (begin, end, comp, parallelism.get_num_threads()); 85 } 86 87 /** 88 * @brief Choose multiway mergesort with exact splitting, 89 * for parallel sorting. 90 * @param begin Begin iterator of input sequence. 91 * @param end End iterator of input sequence. 92 * @param comp Comparator. 93 * @callgraph 94 */ 95 template<bool stable, typename RandomAccessIterator, typename Comparator> 96 inline void 97 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 98 Comparator comp, multiway_mergesort_exact_tag parallelism) 99 { 100 _GLIBCXX_CALL(end - begin) 101 102 parallel_sort_mwms<stable, true> 103 (begin, end, comp, parallelism.get_num_threads()); 104 } 105 106 /** 107 * @brief Choose multiway mergesort with splitting by sampling, 108 * for parallel sorting. 109 * @param begin Begin iterator of input sequence. 110 * @param end End iterator of input sequence. 111 * @param comp Comparator. 112 * @callgraph 113 */ 114 template<bool stable, typename RandomAccessIterator, typename Comparator> 115 inline void 116 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 117 Comparator comp, multiway_mergesort_sampling_tag parallelism) 118 { 119 _GLIBCXX_CALL(end - begin) 120 121 parallel_sort_mwms<stable, false> 122 (begin, end, comp, parallelism.get_num_threads()); 123 } 124 125 /** 126 * @brief Choose quicksort for parallel sorting. 127 * @param begin Begin iterator of input sequence. 128 * @param end End iterator of input sequence. 129 * @param comp Comparator. 130 * @callgraph 131 */ 132 template<bool stable, typename RandomAccessIterator, typename Comparator> 133 inline void 134 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 135 Comparator comp, quicksort_tag parallelism) 136 { 137 _GLIBCXX_CALL(end - begin) 138 139 _GLIBCXX_PARALLEL_ASSERT(stable == false); 140 141 parallel_sort_qs(begin, end, comp, parallelism.get_num_threads()); 142 } 143 144 /** 145 * @brief Choose balanced quicksort for parallel sorting. 146 * @param begin Begin iterator of input sequence. 147 * @param end End iterator of input sequence. 148 * @param comp Comparator. 149 * @param stable Sort stable. 150 * @callgraph 151 */ 152 template<bool stable, typename RandomAccessIterator, typename Comparator> 153 inline void 154 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 155 Comparator comp, balanced_quicksort_tag parallelism) 156 { 157 _GLIBCXX_CALL(end - begin) 158 159 _GLIBCXX_PARALLEL_ASSERT(stable == false); 160 161 parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads()); 162 } 163 164 165 /** 166 * @brief Choose multiway mergesort with exact splitting, 167 * for parallel sorting. 168 * @param begin Begin iterator of input sequence. 169 * @param end End iterator of input sequence. 170 * @param comp Comparator. 171 * @callgraph 172 */ 173 template<bool stable, typename RandomAccessIterator, typename Comparator> 174 inline void 175 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 176 Comparator comp, default_parallel_tag parallelism) 177 { 178 _GLIBCXX_CALL(end - begin) 179 180 parallel_sort<stable> 181 (begin, end, comp, 182 multiway_mergesort_exact_tag(parallelism.get_num_threads())); 183 } 184 185 186 /** 187 * @brief Choose a parallel sorting algorithm. 188 * @param begin Begin iterator of input sequence. 189 * @param end End iterator of input sequence. 190 * @param comp Comparator. 191 * @param stable Sort stable. 192 * @callgraph 193 */ 194 template<bool stable, typename RandomAccessIterator, typename Comparator> 195 inline void 196 parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, 197 Comparator comp, parallel_tag parallelism) 198 { 199 _GLIBCXX_CALL(end - begin) 200 typedef std::iterator_traits<RandomAccessIterator> traits_type; 201 typedef typename traits_type::value_type value_type; 202 typedef typename traits_type::difference_type difference_type; 203 204 if (false) ; 205 #if _GLIBCXX_MERGESORT 206 else if (stable || _Settings::get().sort_algorithm == MWMS) 207 { 208 if(_Settings::get().sort_splitting == EXACT) 209 parallel_sort_mwms<stable, true> 210 (begin, end, comp, parallelism.get_num_threads()); 211 else 212 parallel_sort_mwms<false, false> 213 (begin, end, comp, parallelism.get_num_threads()); 214 } 215 #endif 216 #if _GLIBCXX_QUICKSORT 217 else if (_Settings::get().sort_algorithm == QS) 218 parallel_sort_qs(begin, end, comp, parallelism.get_num_threads()); 219 #endif 220 #if _GLIBCXX_BAL_QUICKSORT 221 else if (_Settings::get().sort_algorithm == QS_BALANCED) 222 parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads()); 223 #endif 224 else 225 __gnu_sequential::sort(begin, end, comp); 226 } 227 } // end namespace __gnu_parallel 228 229 #endif /* _GLIBCXX_PARALLEL_SORT_H */ 230
