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   /** @brief Parallel std::unique_copy(), w/__o explicit equality predicate.
  41     *  @param __first Begin iterator of input sequence.
  42     *  @param __last End iterator of input sequence.
  43     *  @param __result Begin iterator of result __sequence.
  44     *  @param __binary_pred Equality predicate.
  45     *  @return End iterator of result __sequence. */
  46   template<typename _IIter,
  47            class _OutputIterator,
  48            class _BinaryPredicate>
  49     _OutputIterator
  50     __parallel_unique_copy(_IIter __first, _IIter __last,
  51                            _OutputIterator __result,
  52                            _BinaryPredicate __binary_pred)
  53     {
  54       _GLIBCXX_CALL(__last - __first)
  55
  56       typedef std::iterator_traits<_IIter> _TraitsType;
  57       typedef typename _TraitsType::value_type _ValueType;
  58       typedef typename _TraitsType::difference_type _DifferenceType;
  59
  60       _DifferenceType __size = __last - __first;
  61
  62       if (__size == 0)
  63         return __result;
  64
  65       // Let the first thread process two parts.
  66       _DifferenceType *__counter;
  67       _DifferenceType *__borders;
  68
  69       _ThreadIndex __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 _DifferenceType[__num_threads + 2];
  77           equally_split(__size, __num_threads + 1, __borders);
  78           __counter = new _DifferenceType[__num_threads + 1];
  79         }
  80
  81         _ThreadIndex __iam = omp_get_thread_num();
  82
  83         _DifferenceType __begin, __end;
  84
  85         // Check for length without duplicates
  86         // Needed for position in output
  87         _DifferenceType __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 (_IIter __iter = __first + __begin; __iter < __first + __end;
  99                  ++__iter)
 100               {
 101                 if (!__binary_pred(*__iter, *(__iter - 1)))
 102                   {
 103                     ++__i;
 104                     *__out++ = *__iter;
 105                   }
 106               }
 107           }
 108         else
 109           {
 110             __begin = __borders[__iam]; //one part
 111             __end = __borders[__iam + 1];
 112
 113             for (_IIter __iter = __first + __begin; __iter < __first + __end;
 114                  ++__iter)
 115               {
 116                 if (!__binary_pred(*__iter, *(__iter - 1)))
 117                   ++__i;
 118               }
 119           }
 120         __counter[__iam] = __i;
 121
 122         // Last part still untouched.
 123         _DifferenceType __begin_output;
 124
 125 #       pragma omp barrier
 126
 127         // Store result in output on calculated positions.
 128         __begin_output = 0;
 129
 130         if (__iam == 0)
 131           {
 132             for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
 133               __begin_output += __counter[__t];
 134
 135             __i = 0;
 136
 137             _OutputIterator __iter_out = __result + __begin_output;
 138
 139             __begin = __borders[__num_threads];
 140             __end = __size;
 141
 142             for (_IIter __iter = __first + __begin; __iter < __first + __end;
 143                  ++__iter)
 144               {
 145                 if (__iter == __first
 146                     || !__binary_pred(*__iter, *(__iter - 1)))
 147                   {
 148                     ++__i;
 149                     *__iter_out++ = *__iter;
 150                   }
 151               }
 152
 153             __counter[__num_threads] = __i;
 154           }
 155         else
 156           {
 157             for (_ThreadIndex __t = 0; __t < __iam; __t++)
 158               __begin_output += __counter[__t];
 159
 160             _OutputIterator __iter_out = __result + __begin_output;
 161             for (_IIter __iter = __first + __begin; __iter < __first + __end;
 162                  ++__iter)
 163               {
 164                 if (!__binary_pred(*__iter, *(__iter - 1)))
 165                   *__iter_out++ = *__iter;
 166               }
 167           }
 168       }
 169
 170       _DifferenceType __end_output = 0;
 171       for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
 172         __end_output += __counter[__t];
 173
 174       delete[] __borders;
 175
 176       return __result + __end_output;
 177     }
 178
 179   /** @brief Parallel std::unique_copy(), without explicit equality predicate
 180     *  @param __first Begin iterator of input sequence.
 181     *  @param __last End iterator of input sequence.
 182     *  @param __result Begin iterator of result __sequence.
 183     *  @return End iterator of result __sequence. */
 184   template<typename _IIter, class _OutputIterator>
 185     inline _OutputIterator
 186     __parallel_unique_copy(_IIter __first, _IIter __last,
 187                            _OutputIterator __result)
 188     {
 189       typedef typename std::iterator_traits<_IIter>::value_type
 190         _ValueType;
 191       return __parallel_unique_copy(__first, __last, __result,
 192                                     std::equal_to<_ValueType>());
 193     }
 194
 195 }//namespace __gnu_parallel
 196
 197 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */