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/quicksort.h 26 * @brief Implementation of a unbalanced parallel quicksort (in-place). 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_QUICKSORT_H 33 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1 34 35 #include <parallel/parallel.h> 36 #include <parallel/partition.h> 37 38 namespace __gnu_parallel 39 { 40 /** @brief Unbalanced quicksort divide step. 41 * @param begin Begin iterator of subsequence. 42 * @param end End iterator of subsequence. 43 * @param comp Comparator. 44 * @param pivot_rank Desired rank of the pivot. 45 * @param num_samples Choose pivot from that many samples. 46 * @param num_threads Number of threads that are allowed to work on 47 * this part. 48 */ 49 template<typename RandomAccessIterator, typename Comparator> 50 typename std::iterator_traits<RandomAccessIterator>::difference_type 51 parallel_sort_qs_divide(RandomAccessIterator begin, 52 RandomAccessIterator end, 53 Comparator comp, typename std::iterator_traits 54 <RandomAccessIterator>::difference_type pivot_rank, 55 typename std::iterator_traits 56 <RandomAccessIterator>::difference_type 57 num_samples, thread_index_t num_threads) 58 { 59 typedef std::iterator_traits<RandomAccessIterator> traits_type; 60 typedef typename traits_type::value_type value_type; 61 typedef typename traits_type::difference_type difference_type; 62 63 difference_type n = end - begin; 64 num_samples = std::min(num_samples, n); 65 66 // Allocate uninitialized, to avoid default constructor. 67 value_type* samples = 68 static_cast<value_type*>(::operator new(num_samples 69 * sizeof(value_type))); 70 71 for (difference_type s = 0; s < num_samples; ++s) 72 { 73 const unsigned long long index = static_cast<unsigned long long>(s) 74 * n / num_samples; 75 ::new(&(samples[s])) value_type(begin[index]); 76 } 77 78 __gnu_sequential::sort(samples, samples + num_samples, comp); 79 80 value_type& pivot = samples[pivot_rank * num_samples / n]; 81 82 __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool> 83 pred(comp, pivot); 84 difference_type split = 85 parallel_partition(begin, end, pred, num_threads); 86 87 ::operator delete(samples); 88 89 return split; 90 } 91 92 /** @brief Unbalanced quicksort conquer step. 93 * @param begin Begin iterator of subsequence. 94 * @param end End iterator of subsequence. 95 * @param comp Comparator. 96 * @param num_threads Number of threads that are allowed to work on 97 * this part. 98 */ 99 template<typename RandomAccessIterator, typename Comparator> 100 void 101 parallel_sort_qs_conquer(RandomAccessIterator begin, 102 RandomAccessIterator end, 103 Comparator comp, 104 thread_index_t num_threads) 105 { 106 typedef std::iterator_traits<RandomAccessIterator> traits_type; 107 typedef typename traits_type::value_type value_type; 108 typedef typename traits_type::difference_type difference_type; 109 110 if (num_threads <= 1) 111 { 112 __gnu_sequential::sort(begin, end, comp); 113 return; 114 } 115 116 difference_type n = end - begin, pivot_rank; 117 118 if (n <= 1) 119 return; 120 121 thread_index_t num_threads_left; 122 123 if ((num_threads % 2) == 1) 124 num_threads_left = num_threads / 2 + 1; 125 else 126 num_threads_left = num_threads / 2; 127 128 pivot_rank = n * num_threads_left / num_threads; 129 130 difference_type split = 131 parallel_sort_qs_divide(begin, end, comp, pivot_rank, 132 _Settings::get().sort_qs_num_samples_preset, 133 num_threads); 134 135 #pragma omp parallel sections num_threads(2) 136 { 137 #pragma omp section 138 parallel_sort_qs_conquer(begin, begin + split, 139 comp, num_threads_left); 140 #pragma omp section 141 parallel_sort_qs_conquer(begin + split, end, 142 comp, num_threads - num_threads_left); 143 } 144 } 145 146 147 148 /** @brief Unbalanced quicksort main call. 149 * @param begin Begin iterator of input sequence. 150 * @param end End iterator input sequence, ignored. 151 * @param comp Comparator. 152 * @param num_threads Number of threads that are allowed to work on 153 * this part. 154 */ 155 template<typename RandomAccessIterator, typename Comparator> 156 void 157 parallel_sort_qs(RandomAccessIterator begin, 158 RandomAccessIterator end, 159 Comparator comp, 160 thread_index_t num_threads) 161 { 162 _GLIBCXX_CALL(n) 163 164 typedef std::iterator_traits<RandomAccessIterator> traits_type; 165 typedef typename traits_type::value_type value_type; 166 typedef typename traits_type::difference_type difference_type; 167 168 difference_type n = end - begin; 169 170 // At least one element per processor. 171 if (num_threads > n) 172 num_threads = static_cast<thread_index_t>(n); 173 174 parallel_sort_qs_conquer(begin, begin + n, comp, num_threads); 175 } 176 177 } //namespace __gnu_parallel 178 179 #endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */ 180
