libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/unique_copy.h 00026 * @brief Parallel implementations of std::unique_copy(). 00027 * This file is a GNU parallel extension to the Standard C++ Library. 00028 */ 00029 00030 // Written by Robert Geisberger and Robin Dapp. 00031 00032 #ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H 00033 #define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1 00034 00035 #include <parallel/parallel.h> 00036 #include <parallel/multiseq_selection.h> 00037 00038 namespace __gnu_parallel 00039 { 00040 00041 /** @brief Parallel std::unique_copy(), w/o explicit equality predicate. 00042 * @param first Begin iterator of input sequence. 00043 * @param last End iterator of input sequence. 00044 * @param result Begin iterator of result sequence. 00045 * @param binary_pred Equality predicate. 00046 * @return End iterator of result sequence. */ 00047 template<typename InputIterator, 00048 class OutputIterator, 00049 class BinaryPredicate> 00050 OutputIterator 00051 parallel_unique_copy(InputIterator first, InputIterator last, 00052 OutputIterator result, BinaryPredicate binary_pred) 00053 { 00054 _GLIBCXX_CALL(last - first) 00055 00056 typedef std::iterator_traits<InputIterator> traits_type; 00057 typedef typename traits_type::value_type value_type; 00058 typedef typename traits_type::difference_type difference_type; 00059 00060 difference_type size = last - first; 00061 00062 if (size == 0) 00063 return result; 00064 00065 // Let the first thread process two parts. 00066 difference_type *counter; 00067 difference_type *borders; 00068 00069 thread_index_t num_threads = get_max_threads(); 00070 // First part contains at least one element. 00071 # pragma omp parallel num_threads(num_threads) 00072 { 00073 # pragma omp single 00074 { 00075 num_threads = omp_get_num_threads(); 00076 borders = new difference_type[num_threads + 2]; 00077 equally_split(size, num_threads + 1, borders); 00078 counter = new difference_type[num_threads + 1]; 00079 } 00080 00081 thread_index_t iam = omp_get_thread_num(); 00082 00083 difference_type begin, end; 00084 00085 // Check for length without duplicates 00086 // Needed for position in output 00087 difference_type i = 0; 00088 OutputIterator out = result; 00089 00090 if (iam == 0) 00091 { 00092 begin = borders[0] + 1; // == 1 00093 end = borders[iam + 1]; 00094 00095 ++i; 00096 *out++ = *first; 00097 00098 for (InputIterator iter = first + begin; iter < first + end; ++iter) 00099 { 00100 if (!binary_pred(*iter, *(iter-1))) 00101 { 00102 ++i; 00103 *out++ = *iter; 00104 } 00105 } 00106 } 00107 else 00108 { 00109 begin = borders[iam]; //one part 00110 end = borders[iam + 1]; 00111 00112 for (InputIterator iter = first + begin; iter < first + end; ++iter) 00113 { 00114 if (!binary_pred(*iter, *(iter - 1))) 00115 ++i; 00116 } 00117 } 00118 counter[iam] = i; 00119 00120 // Last part still untouched. 00121 difference_type begin_output; 00122 00123 # pragma omp barrier 00124 00125 // Store result in output on calculated positions. 00126 begin_output = 0; 00127 00128 if (iam == 0) 00129 { 00130 for (int t = 0; t < num_threads; ++t) 00131 begin_output += counter[t]; 00132 00133 i = 0; 00134 00135 OutputIterator iter_out = result + begin_output; 00136 00137 begin = borders[num_threads]; 00138 end = size; 00139 00140 for (InputIterator iter = first + begin; iter < first + end; ++iter) 00141 { 00142 if (iter == first || !binary_pred(*iter, *(iter - 1))) 00143 { 00144 ++i; 00145 *iter_out++ = *iter; 00146 } 00147 } 00148 00149 counter[num_threads] = i; 00150 } 00151 else 00152 { 00153 for (int t = 0; t < iam; t++) 00154 begin_output += counter[t]; 00155 00156 OutputIterator iter_out = result + begin_output; 00157 for (InputIterator iter = first + begin; iter < first + end; ++iter) 00158 { 00159 if (!binary_pred(*iter, *(iter-1))) 00160 *iter_out++ = *iter; 00161 } 00162 } 00163 } 00164 00165 difference_type end_output = 0; 00166 for (int t = 0; t < num_threads + 1; t++) 00167 end_output += counter[t]; 00168 00169 delete[] borders; 00170 00171 return result + end_output; 00172 } 00173 00174 /** @brief Parallel std::unique_copy(), without explicit equality predicate 00175 * @param first Begin iterator of input sequence. 00176 * @param last End iterator of input sequence. 00177 * @param result Begin iterator of result sequence. 00178 * @return End iterator of result sequence. */ 00179 template<typename InputIterator, class OutputIterator> 00180 inline OutputIterator 00181 parallel_unique_copy(InputIterator first, InputIterator last, 00182 OutputIterator result) 00183 { 00184 typedef typename std::iterator_traits<InputIterator>::value_type 00185 value_type; 00186 return parallel_unique_copy(first, last, result, 00187 std::equal_to<value_type>()); 00188 } 00189 00190 }//namespace __gnu_parallel 00191 00192 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */