libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 /** @brief Parallel std::unique_copy(), w/__o explicit equality predicate. 00041 * @param __first Begin iterator of input sequence. 00042 * @param __last End iterator of input sequence. 00043 * @param __result Begin iterator of result __sequence. 00044 * @param __binary_pred Equality predicate. 00045 * @return End iterator of result __sequence. */ 00046 template<typename _IIter, 00047 class _OutputIterator, 00048 class _BinaryPredicate> 00049 _OutputIterator 00050 __parallel_unique_copy(_IIter __first, _IIter __last, 00051 _OutputIterator __result, 00052 _BinaryPredicate __binary_pred) 00053 { 00054 _GLIBCXX_CALL(__last - __first) 00055 00056 typedef std::iterator_traits<_IIter> _TraitsType; 00057 typedef typename _TraitsType::value_type _ValueType; 00058 typedef typename _TraitsType::difference_type _DifferenceType; 00059 00060 _DifferenceType __size = __last - __first; 00061 00062 if (__size == 0) 00063 return __result; 00064 00065 // Let the first thread process two parts. 00066 _DifferenceType *__counter; 00067 _DifferenceType *__borders; 00068 00069 _ThreadIndex __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 _DifferenceType[__num_threads + 2]; 00077 __equally_split(__size, __num_threads + 1, __borders); 00078 __counter = new _DifferenceType[__num_threads + 1]; 00079 } 00080 00081 _ThreadIndex __iam = omp_get_thread_num(); 00082 00083 _DifferenceType __begin, __end; 00084 00085 // Check for length without duplicates 00086 // Needed for position in output 00087 _DifferenceType __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 (_IIter __iter = __first + __begin; __iter < __first + __end; 00099 ++__iter) 00100 { 00101 if (!__binary_pred(*__iter, *(__iter - 1))) 00102 { 00103 ++__i; 00104 *__out++ = *__iter; 00105 } 00106 } 00107 } 00108 else 00109 { 00110 __begin = __borders[__iam]; //one part 00111 __end = __borders[__iam + 1]; 00112 00113 for (_IIter __iter = __first + __begin; __iter < __first + __end; 00114 ++__iter) 00115 { 00116 if (!__binary_pred(*__iter, *(__iter - 1))) 00117 ++__i; 00118 } 00119 } 00120 __counter[__iam] = __i; 00121 00122 // Last part still untouched. 00123 _DifferenceType __begin_output; 00124 00125 # pragma omp barrier 00126 00127 // Store result in output on calculated positions. 00128 __begin_output = 0; 00129 00130 if (__iam == 0) 00131 { 00132 for (_ThreadIndex __t = 0; __t < __num_threads; ++__t) 00133 __begin_output += __counter[__t]; 00134 00135 __i = 0; 00136 00137 _OutputIterator __iter_out = __result + __begin_output; 00138 00139 __begin = __borders[__num_threads]; 00140 __end = __size; 00141 00142 for (_IIter __iter = __first + __begin; __iter < __first + __end; 00143 ++__iter) 00144 { 00145 if (__iter == __first 00146 || !__binary_pred(*__iter, *(__iter - 1))) 00147 { 00148 ++__i; 00149 *__iter_out++ = *__iter; 00150 } 00151 } 00152 00153 __counter[__num_threads] = __i; 00154 } 00155 else 00156 { 00157 for (_ThreadIndex __t = 0; __t < __iam; __t++) 00158 __begin_output += __counter[__t]; 00159 00160 _OutputIterator __iter_out = __result + __begin_output; 00161 for (_IIter __iter = __first + __begin; __iter < __first + __end; 00162 ++__iter) 00163 { 00164 if (!__binary_pred(*__iter, *(__iter - 1))) 00165 *__iter_out++ = *__iter; 00166 } 00167 } 00168 } 00169 00170 _DifferenceType __end_output = 0; 00171 for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++) 00172 __end_output += __counter[__t]; 00173 00174 delete[] __borders; 00175 00176 return __result + __end_output; 00177 } 00178 00179 /** @brief Parallel std::unique_copy(), without explicit equality predicate 00180 * @param __first Begin iterator of input sequence. 00181 * @param __last End iterator of input sequence. 00182 * @param __result Begin iterator of result __sequence. 00183 * @return End iterator of result __sequence. */ 00184 template<typename _IIter, class _OutputIterator> 00185 inline _OutputIterator 00186 __parallel_unique_copy(_IIter __first, _IIter __last, 00187 _OutputIterator __result) 00188 { 00189 typedef typename std::iterator_traits<_IIter>::value_type 00190 _ValueType; 00191 return __parallel_unique_copy(__first, __last, __result, 00192 std::equal_to<_ValueType>()); 00193 } 00194 00195 }//namespace __gnu_parallel 00196 00197 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */