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/unique_copy.h 26 * @brief Parallel implementations of std::unique_copy(). 27 * This file is a GNU parallel extension to the Standard C++ Library. 28 */ 29 30 // Written by Robert Geisberger and Robin Dapp. 31 32 #ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H 33 #define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1 34 35 #include <parallel/parallel.h> 36 #include <parallel/multiseq_selection.h> 37 38 namespace __gnu_parallel 39 { 40 41 /** @brief Parallel std::unique_copy(), w/o explicit equality predicate. 42 * @param first Begin iterator of input sequence. 43 * @param last End iterator of input sequence. 44 * @param result Begin iterator of result sequence. 45 * @param binary_pred Equality predicate. 46 * @return End iterator of result sequence. */ 47 template<typename InputIterator, 48 class OutputIterator, 49 class BinaryPredicate> 50 OutputIterator 51 parallel_unique_copy(InputIterator first, InputIterator last, 52 OutputIterator result, BinaryPredicate binary_pred) 53 { 54 _GLIBCXX_CALL(last - first) 55 56 typedef std::iterator_traits<InputIterator> traits_type; 57 typedef typename traits_type::value_type value_type; 58 typedef typename traits_type::difference_type difference_type; 59 60 difference_type size = last - first; 61 62 if (size == 0) 63 return result; 64 65 // Let the first thread process two parts. 66 difference_type *counter; 67 difference_type *borders; 68 69 thread_index_t num_threads = get_max_threads(); 70 // First part contains at least one element. 71 # pragma omp parallel num_threads(num_threads) 72 { 73 # pragma omp single 74 { 75 num_threads = omp_get_num_threads(); 76 borders = new difference_type[num_threads + 2]; 77 equally_split(size, num_threads + 1, borders); 78 counter = new difference_type[num_threads + 1]; 79 } 80 81 thread_index_t iam = omp_get_thread_num(); 82 83 difference_type begin, end; 84 85 // Check for length without duplicates 86 // Needed for position in output 87 difference_type i = 0; 88 OutputIterator out = result; 89 90 if (iam == 0) 91 { 92 begin = borders[0] + 1; // == 1 93 end = borders[iam + 1]; 94 95 ++i; 96 *out++ = *first; 97 98 for (InputIterator iter = first + begin; iter < first + end; ++iter) 99 { 100 if (!binary_pred(*iter, *(iter-1))) 101 { 102 ++i; 103 *out++ = *iter; 104 } 105 } 106 } 107 else 108 { 109 begin = borders[iam]; //one part 110 end = borders[iam + 1]; 111 112 for (InputIterator iter = first + begin; iter < first + end; ++iter) 113 { 114 if (!binary_pred(*iter, *(iter - 1))) 115 ++i; 116 } 117 } 118 counter[iam] = i; 119 120 // Last part still untouched. 121 difference_type begin_output; 122 123 # pragma omp barrier 124 125 // Store result in output on calculated positions. 126 begin_output = 0; 127 128 if (iam == 0) 129 { 130 for (int t = 0; t < num_threads; ++t) 131 begin_output += counter[t]; 132 133 i = 0; 134 135 OutputIterator iter_out = result + begin_output; 136 137 begin = borders[num_threads]; 138 end = size; 139 140 for (InputIterator iter = first + begin; iter < first + end; ++iter) 141 { 142 if (iter == first || !binary_pred(*iter, *(iter - 1))) 143 { 144 ++i; 145 *iter_out++ = *iter; 146 } 147 } 148 149 counter[num_threads] = i; 150 } 151 else 152 { 153 for (int t = 0; t < iam; t++) 154 begin_output += counter[t]; 155 156 OutputIterator iter_out = result + begin_output; 157 for (InputIterator iter = first + begin; iter < first + end; ++iter) 158 { 159 if (!binary_pred(*iter, *(iter-1))) 160 *iter_out++ = *iter; 161 } 162 } 163 } 164 165 difference_type end_output = 0; 166 for (int t = 0; t < num_threads + 1; t++) 167 end_output += counter[t]; 168 169 delete[] borders; 170 171 return result + end_output; 172 } 173 174 /** @brief Parallel std::unique_copy(), without explicit equality predicate 175 * @param first Begin iterator of input sequence. 176 * @param last End iterator of input sequence. 177 * @param result Begin iterator of result sequence. 178 * @return End iterator of result sequence. */ 179 template<typename InputIterator, class OutputIterator> 180 inline OutputIterator 181 parallel_unique_copy(InputIterator first, InputIterator last, 182 OutputIterator result) 183 { 184 typedef typename std::iterator_traits<InputIterator>::value_type 185 value_type; 186 return parallel_unique_copy(first, last, result, 187 std::equal_to<value_type>()); 188 } 189 190 }//namespace __gnu_parallel 191 192 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */ 193
