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 #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
00042
00043
00044
00045
00046
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
00066 difference_type *counter;
00067 difference_type *borders;
00068
00069 thread_index_t num_threads = get_max_threads();
00070
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
00086
00087 difference_type i = 0;
00088 OutputIterator out = result;
00089
00090 if (iam == 0)
00091 {
00092 begin = borders[0] + 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];
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
00121 difference_type begin_output;
00122
00123 # pragma omp barrier
00124
00125
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
00175
00176
00177
00178
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 }
00191
00192 #endif