libstdc++-v3/include/parallel/unique_copy.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file parallel/unique_copy.h
  26  *  @brief Parallel implementations of std::unique_copy().
  27  *  This file is a GNU parallel extension to the Standard C++ Library.
  28  */
  29
  30 // Written by Robert Geisberger and Robin Dapp.
  31
  32 #ifndef _GLIBCXX_PARALLEL_UNIQUE_COPY_H
  33 #define _GLIBCXX_PARALLEL_UNIQUE_COPY_H 1
  34
  35 #include <parallel/parallel.h>
  36 #include <parallel/multiseq_selection.h>
  37
  38 namespace __gnu_parallel
  39 {
  40
  41 /** @brief Parallel std::unique_copy(), w/o explicit equality predicate.
  42   *  @param first Begin iterator of input sequence.
  43   *  @param last End iterator of input sequence.
  44   *  @param result Begin iterator of result sequence.
  45   *  @param binary_pred Equality predicate.
  46   *  @return End iterator of result sequence. */
  47 template<typename InputIterator,
  48          class OutputIterator,
  49          class BinaryPredicate>
  50   OutputIterator
  51   parallel_unique_copy(InputIterator first, InputIterator last,
  52                        OutputIterator result, BinaryPredicate binary_pred)
  53   {
  54     _GLIBCXX_CALL(last - first)
  55
  56     typedef std::iterator_traits<InputIterator> traits_type;
  57     typedef typename traits_type::value_type value_type;
  58     typedef typename traits_type::difference_type difference_type;
  59
  60     difference_type size = last - first;
  61
  62     if (size == 0)
  63       return result;
  64
  65     // Let the first thread process two parts.
  66     difference_type *counter;
  67     difference_type *borders;
  68
  69     thread_index_t num_threads = get_max_threads();
  70     // First part contains at least one element.
  71 #   pragma omp parallel num_threads(num_threads)
  72       {
  73 #       pragma omp single
  74           {
  75             num_threads = omp_get_num_threads();
  76             borders = new difference_type[num_threads + 2];
  77             equally_split(size, num_threads + 1, borders);
  78             counter = new difference_type[num_threads + 1];
  79           }
  80
  81         thread_index_t iam = omp_get_thread_num();
  82
  83         difference_type begin, end;
  84
  85         // Check for length without duplicates
  86         // Needed for position in output
  87         difference_type i = 0;
  88         OutputIterator out = result;
  89
  90         if (iam == 0)
  91         {
  92           begin = borders[0] + 1;       // == 1
  93           end = borders[iam + 1];
  94
  95           ++i;
  96           *out++ = *first;
  97
  98           for (InputIterator iter = first + begin; iter < first + end; ++iter)
  99             {
 100               if (!binary_pred(*iter, *(iter-1)))
 101                 {
 102                   ++i;
 103                   *out++ = *iter;
 104                 }
 105             }
 106         }
 107       else
 108         {
 109           begin = borders[iam]; //one part
 110           end = borders[iam + 1];
 111
 112           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 113             {
 114               if (!binary_pred(*iter, *(iter - 1)))
 115                 ++i;
 116             }
 117         }
 118       counter[iam] = i;
 119
 120       // Last part still untouched.
 121       difference_type begin_output;
 122
 123 #     pragma omp barrier
 124
 125       // Store result in output on calculated positions.
 126       begin_output = 0;
 127
 128       if (iam == 0)
 129         {
 130           for (int t = 0; t < num_threads; ++t)
 131             begin_output += counter[t];
 132
 133           i = 0;
 134
 135           OutputIterator iter_out = result + begin_output;
 136
 137           begin = borders[num_threads];
 138           end = size;
 139
 140           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 141             {
 142               if (iter == first || !binary_pred(*iter, *(iter - 1)))
 143                 {
 144                   ++i;
 145                   *iter_out++ = *iter;
 146                 }
 147             }
 148
 149           counter[num_threads] = i;
 150         }
 151       else
 152         {
 153           for (int t = 0; t < iam; t++)
 154             begin_output += counter[t];
 155
 156           OutputIterator iter_out = result + begin_output;
 157           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 158             {
 159               if (!binary_pred(*iter, *(iter-1)))
 160                 *iter_out++ = *iter;
 161             }
 162         }
 163     }
 164
 165     difference_type end_output = 0;
 166     for (int t = 0; t < num_threads + 1; t++)
 167       end_output += counter[t];
 168
 169     delete[] borders;
 170
 171     return result + end_output;
 172   }
 173
 174 /** @brief Parallel std::unique_copy(), without explicit equality predicate
 175   *  @param first Begin iterator of input sequence.
 176   *  @param last End iterator of input sequence.
 177   *  @param result Begin iterator of result sequence.
 178   *  @return End iterator of result sequence. */
 179 template<typename InputIterator, class OutputIterator>
 180   inline OutputIterator
 181   parallel_unique_copy(InputIterator first, InputIterator last,
 182                        OutputIterator result)
 183   {
 184     typedef typename std::iterator_traits<InputIterator>::value_type
 185       value_type;
 186     return parallel_unique_copy(first, last, result,
 187                                 std::equal_to<value_type>());
 188   }
 189
 190 }//namespace __gnu_parallel
 191
 192 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */