unique_copy.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef _GLIBCXX_PARALLEL_UNIQUE_H
00039 #define _GLIBCXX_PARALLEL_UNIQUE_H 1
00040
00041 #include <parallel/parallel.h>
00042 #include <parallel/multiseq_selection.h>
00043
00044 namespace __gnu_parallel
00045 {
00046
00047
00048
00049
00050
00051
00052
00053 template<typename InputIterator,
00054 class OutputIterator,
00055 class BinaryPredicate>
00056 OutputIterator
00057 parallel_unique_copy(InputIterator first, InputIterator last,
00058 OutputIterator result, BinaryPredicate binary_pred)
00059 {
00060 _GLIBCXX_CALL(last - first)
00061
00062 typedef std::iterator_traits<InputIterator> traits_type;
00063 typedef typename traits_type::value_type value_type;
00064 typedef typename traits_type::difference_type difference_type;
00065
00066 difference_type size = last - first;
00067
00068 if (size == 0)
00069 return result;
00070
00071
00072 difference_type *counter;
00073 difference_type *borders;
00074
00075 thread_index_t num_threads = get_max_threads();
00076
00077 # pragma omp parallel num_threads(num_threads)
00078 {
00079 # pragma omp single
00080 {
00081 num_threads = omp_get_num_threads();
00082 borders = new difference_type[num_threads + 2];
00083 equally_split(size, num_threads + 1, borders);
00084 counter = new difference_type[num_threads + 1];
00085 }
00086
00087 thread_index_t iam = omp_get_thread_num();
00088
00089 difference_type begin, end;
00090
00091
00092
00093 difference_type i = 0;
00094 OutputIterator out = result;
00095
00096 if (iam == 0)
00097 {
00098 begin = borders[0] + 1;
00099 end = borders[iam + 1];
00100
00101 ++i;
00102 *out++ = *first;
00103
00104 for (InputIterator iter = first + begin; iter < first + end; ++iter)
00105 {
00106 if (!binary_pred(*iter, *(iter-1)))
00107 {
00108 ++i;
00109 *out++ = *iter;
00110 }
00111 }
00112 }
00113 else
00114 {
00115 begin = borders[iam];
00116 end = borders[iam + 1];
00117
00118 for (InputIterator iter = first + begin; iter < first + end; ++iter)
00119 {
00120 if (!binary_pred(*iter, *(iter - 1)))
00121 ++i;
00122 }
00123 }
00124 counter[iam] = i;
00125
00126
00127 difference_type begin_output;
00128
00129 # pragma omp barrier
00130
00131
00132 begin_output = 0;
00133
00134 if (iam == 0)
00135 {
00136 for (int t = 0; t < num_threads; ++t)
00137 begin_output += counter[t];
00138
00139 i = 0;
00140
00141 OutputIterator iter_out = result + begin_output;
00142
00143 begin = borders[num_threads];
00144 end = size;
00145
00146 for (InputIterator iter = first + begin; iter < first + end; ++iter)
00147 {
00148 if (iter == first || !binary_pred(*iter, *(iter - 1)))
00149 {
00150 ++i;
00151 *iter_out++ = *iter;
00152 }
00153 }
00154
00155 counter[num_threads] = i;
00156 }
00157 else
00158 {
00159 for (int t = 0; t < iam; t++)
00160 begin_output += counter[t];
00161
00162 OutputIterator iter_out = result + begin_output;
00163 for (InputIterator iter = first + begin; iter < first + end; ++iter)
00164 {
00165 if (!binary_pred(*iter, *(iter-1)))
00166 *iter_out++ = *iter;
00167 }
00168 }
00169 }
00170
00171 difference_type end_output = 0;
00172 for (int t = 0; t < num_threads + 1; t++)
00173 end_output += counter[t];
00174
00175 delete[] borders;
00176
00177 return result + end_output;
00178 }
00179
00180
00181
00182
00183
00184
00185 template<typename InputIterator, class OutputIterator>
00186 inline OutputIterator
00187 parallel_unique_copy(InputIterator first, InputIterator last,
00188 OutputIterator result)
00189 {
00190 typedef typename std::iterator_traits<InputIterator>::value_type
00191 value_type;
00192 return parallel_unique_copy(first, last, result,
00193 std::equal_to<value_type>());
00194 }
00195
00196 }
00197
00198 #endif