--- /dev/null
+// -*- C++ -*-
+
+// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/unique_copy.h
+ * @brief Parallel implementations of std::unique_copy().
+ * This file is a GNU parallel extension to the Standard C++ Library.
+ */
+
+// Written by Robert Geisberger and Robin Dapp.
+
+#ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H
+#define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1
+
+#include <parallel/parallel.h>
+#include <parallel/multiseq_selection.h>
+
+namespace __gnu_parallel
+{
+
+/** @brief Parallel std::unique_copy(), w/o explicit equality predicate.
+ * @param first Begin iterator of input sequence.
+ * @param last End iterator of input sequence.
+ * @param result Begin iterator of result sequence.
+ * @param binary_pred Equality predicate.
+ * @return End iterator of result sequence. */
+template<typename InputIterator,
+ class OutputIterator,
+ class BinaryPredicate>
+ OutputIterator
+ parallel_unique_copy(InputIterator first, InputIterator last,
+ OutputIterator result, BinaryPredicate binary_pred)
+ {
+ _GLIBCXX_CALL(last - first)
+
+ typedef std::iterator_traits<InputIterator> traits_type;
+ typedef typename traits_type::value_type value_type;
+ typedef typename traits_type::difference_type difference_type;
+
+ difference_type size = last - first;
+
+ if (size == 0)
+ return result;
+
+ // Let the first thread process two parts.
+ difference_type *counter;
+ difference_type *borders;
+
+ thread_index_t num_threads = get_max_threads();
+ // First part contains at least one element.
+# pragma omp parallel num_threads(num_threads)
+ {
+# pragma omp single
+ {
+ num_threads = omp_get_num_threads();
+ borders = new difference_type[num_threads + 2];
+ equally_split(size, num_threads + 1, borders);
+ counter = new difference_type[num_threads + 1];
+ }
+
+ thread_index_t iam = omp_get_thread_num();
+
+ difference_type begin, end;
+
+ // Check for length without duplicates
+ // Needed for position in output
+ difference_type i = 0;
+ OutputIterator out = result;
+
+ if (iam == 0)
+ {
+ begin = borders[0] + 1; // == 1
+ end = borders[iam + 1];
+
+ ++i;
+ *out++ = *first;
+
+ for (InputIterator iter = first + begin; iter < first + end; ++iter)
+ {
+ if (!binary_pred(*iter, *(iter-1)))
+ {
+ ++i;
+ *out++ = *iter;
+ }
+ }
+ }
+ else
+ {
+ begin = borders[iam]; //one part
+ end = borders[iam + 1];
+
+ for (InputIterator iter = first + begin; iter < first + end; ++iter)
+ {
+ if (!binary_pred(*iter, *(iter - 1)))
+ ++i;
+ }
+ }
+ counter[iam] = i;
+
+ // Last part still untouched.
+ difference_type begin_output;
+
+# pragma omp barrier
+
+ // Store result in output on calculated positions.
+ begin_output = 0;
+
+ if (iam == 0)
+ {
+ for (int t = 0; t < num_threads; ++t)
+ begin_output += counter[t];
+
+ i = 0;
+
+ OutputIterator iter_out = result + begin_output;
+
+ begin = borders[num_threads];
+ end = size;
+
+ for (InputIterator iter = first + begin; iter < first + end; ++iter)
+ {
+ if (iter == first || !binary_pred(*iter, *(iter - 1)))
+ {
+ ++i;
+ *iter_out++ = *iter;
+ }
+ }
+
+ counter[num_threads] = i;
+ }
+ else
+ {
+ for (int t = 0; t < iam; t++)
+ begin_output += counter[t];
+
+ OutputIterator iter_out = result + begin_output;
+ for (InputIterator iter = first + begin; iter < first + end; ++iter)
+ {
+ if (!binary_pred(*iter, *(iter-1)))
+ *iter_out++ = *iter;
+ }
+ }
+ }
+
+ difference_type end_output = 0;
+ for (int t = 0; t < num_threads + 1; t++)
+ end_output += counter[t];
+
+ delete[] borders;
+
+ return result + end_output;
+ }
+
+/** @brief Parallel std::unique_copy(), without explicit equality predicate
+ * @param first Begin iterator of input sequence.
+ * @param last End iterator of input sequence.
+ * @param result Begin iterator of result sequence.
+ * @return End iterator of result sequence. */
+template<typename InputIterator, class OutputIterator>
+ inline OutputIterator
+ parallel_unique_copy(InputIterator first, InputIterator last,
+ OutputIterator result)
+ {
+ typedef typename std::iterator_traits<InputIterator>::value_type
+ value_type;
+ return parallel_unique_copy(first, last, result,
+ std::equal_to<value_type>());
+ }
+
+}//namespace __gnu_parallel
+
+#endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */
projects / msp430-gcc.git / blobdiff