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