1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2018 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_PARALLEL_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 _RAIter, 59 typename _Compare, typename _Parallelism> 60 void 61 __parallel_sort(_RAIter __begin, _RAIter __end, 62 _Compare __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 * @tparam __stable Sort stable. 71 * @callgraph 72 */ 73 template<bool __stable, typename _RAIter, typename _Compare> 74 inline void 75 __parallel_sort(_RAIter __begin, _RAIter __end, 76 _Compare __comp, multiway_mergesort_tag __parallelism) 77 { 78 _GLIBCXX_CALL(__end - __begin) 79 80 if(_Settings::get().sort_splitting == EXACT) 81 parallel_sort_mwms<__stable, true> 82 (__begin, __end, __comp, __parallelism.__get_num_threads()); 83 else 84 parallel_sort_mwms<__stable, false> 85 (__begin, __end, __comp, __parallelism.__get_num_threads()); 86 } 87 88 /** 89 * @brief Choose multiway mergesort with exact splitting, 90 * for parallel sorting. 91 * @param __begin Begin iterator of input sequence. 92 * @param __end End iterator of input sequence. 93 * @param __comp Comparator. 94 * @tparam __stable Sort stable. 95 * @callgraph 96 */ 97 template<bool __stable, typename _RAIter, typename _Compare> 98 inline void 99 __parallel_sort(_RAIter __begin, _RAIter __end, 100 _Compare __comp, 101 multiway_mergesort_exact_tag __parallelism) 102 { 103 _GLIBCXX_CALL(__end - __begin) 104 105 parallel_sort_mwms<__stable, true> 106 (__begin, __end, __comp, __parallelism.__get_num_threads()); 107 } 108 109 /** 110 * @brief Choose multiway mergesort with splitting by sampling, 111 * for parallel sorting. 112 * @param __begin Begin iterator of input sequence. 113 * @param __end End iterator of input sequence. 114 * @param __comp Comparator. 115 * @tparam __stable Sort stable. 116 * @callgraph 117 */ 118 template<bool __stable, typename _RAIter, typename _Compare> 119 inline void 120 __parallel_sort(_RAIter __begin, _RAIter __end, 121 _Compare __comp, 122 multiway_mergesort_sampling_tag __parallelism) 123 { 124 _GLIBCXX_CALL(__end - __begin) 125 126 parallel_sort_mwms<__stable, false> 127 (__begin, __end, __comp, __parallelism.__get_num_threads()); 128 } 129 130 /** 131 * @brief Choose quicksort for parallel sorting. 132 * @param __begin Begin iterator of input sequence. 133 * @param __end End iterator of input sequence. 134 * @param __comp Comparator. 135 * @tparam __stable Sort stable. 136 * @callgraph 137 */ 138 template<bool __stable, typename _RAIter, typename _Compare> 139 inline void 140 __parallel_sort(_RAIter __begin, _RAIter __end, 141 _Compare __comp, quicksort_tag __parallelism) 142 { 143 _GLIBCXX_CALL(__end - __begin) 144 145 _GLIBCXX_PARALLEL_ASSERT(__stable == false); 146 147 __parallel_sort_qs(__begin, __end, __comp, 148 __parallelism.__get_num_threads()); 149 } 150 151 /** 152 * @brief Choose balanced quicksort for parallel sorting. 153 * @param __begin Begin iterator of input sequence. 154 * @param __end End iterator of input sequence. 155 * @param __comp Comparator. 156 * @tparam __stable Sort stable. 157 * @callgraph 158 */ 159 template<bool __stable, typename _RAIter, typename _Compare> 160 inline void 161 __parallel_sort(_RAIter __begin, _RAIter __end, 162 _Compare __comp, balanced_quicksort_tag __parallelism) 163 { 164 _GLIBCXX_CALL(__end - __begin) 165 166 _GLIBCXX_PARALLEL_ASSERT(__stable == false); 167 168 __parallel_sort_qsb(__begin, __end, __comp, 169 __parallelism.__get_num_threads()); 170 } 171 172 /** 173 * @brief Choose multiway mergesort with exact splitting, 174 * for parallel sorting. 175 * @param __begin Begin iterator of input sequence. 176 * @param __end End iterator of input sequence. 177 * @param __comp Comparator. 178 * @tparam __stable Sort stable. 179 * @callgraph 180 */ 181 template<bool __stable, typename _RAIter, typename _Compare> 182 inline void 183 __parallel_sort(_RAIter __begin, _RAIter __end, 184 _Compare __comp, default_parallel_tag __parallelism) 185 { 186 _GLIBCXX_CALL(__end - __begin) 187 188 __parallel_sort<__stable> 189 (__begin, __end, __comp, 190 multiway_mergesort_exact_tag(__parallelism.__get_num_threads())); 191 } 192 193 /** 194 * @brief Choose a parallel sorting algorithm. 195 * @param __begin Begin iterator of input sequence. 196 * @param __end End iterator of input sequence. 197 * @param __comp Comparator. 198 * @tparam __stable Sort stable. 199 * @callgraph 200 */ 201 template<bool __stable, typename _RAIter, typename _Compare> 202 inline void 203 __parallel_sort(_RAIter __begin, _RAIter __end, 204 _Compare __comp, parallel_tag __parallelism) 205 { 206 _GLIBCXX_CALL(__end - __begin) 207 typedef std::iterator_traits<_RAIter> _TraitsType; 208 typedef typename _TraitsType::value_type _ValueType; 209 typedef typename _TraitsType::difference_type _DifferenceType; 210 211 if (false) ; 212 #if _GLIBCXX_MERGESORT 213 else if (__stable || _Settings::get().sort_algorithm == MWMS) 214 { 215 if(_Settings::get().sort_splitting == EXACT) 216 parallel_sort_mwms<__stable, true> 217 (__begin, __end, __comp, __parallelism.__get_num_threads()); 218 else 219 parallel_sort_mwms<false, false> 220 (__begin, __end, __comp, __parallelism.__get_num_threads()); 221 } 222 #endif 223 #if _GLIBCXX_QUICKSORT 224 else if (_Settings::get().sort_algorithm == QS) 225 __parallel_sort_qs(__begin, __end, __comp, 226 __parallelism.__get_num_threads()); 227 #endif 228 #if _GLIBCXX_BAL_QUICKSORT 229 else if (_Settings::get().sort_algorithm == QS_BALANCED) 230 __parallel_sort_qsb(__begin, __end, __comp, 231 __parallelism.__get_num_threads()); 232 #endif 233 else 234 __gnu_sequential::sort(__begin, __end, __comp); 235 } 236 } // end namespace __gnu_parallel 237 238 #endif /* _GLIBCXX_PARALLEL_SORT_H */ 239