libstdc++
unique_copy.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/unique_copy.h
00026  *  @brief Parallel implementations of std::unique_copy().
00027  *  This file is a GNU parallel extension to the Standard C++ Library.
00028  */
00029 
00030 // Written by Robert Geisberger and Robin Dapp.
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   /** @brief Parallel std::unique_copy(), w/__o explicit equality predicate.
00041     *  @param __first Begin iterator of input sequence.
00042     *  @param __last End iterator of input sequence.
00043     *  @param __result Begin iterator of result __sequence.
00044     *  @param __binary_pred Equality predicate.
00045     *  @return End iterator of result __sequence. */
00046   template<typename _IIter,
00047            class _OutputIterator,
00048            class _BinaryPredicate>
00049     _OutputIterator
00050     __parallel_unique_copy(_IIter __first, _IIter __last,
00051                _OutputIterator __result,
00052                _BinaryPredicate __binary_pred)
00053     {
00054       _GLIBCXX_CALL(__last - __first)
00055 
00056       typedef std::iterator_traits<_IIter> _TraitsType;
00057       typedef typename _TraitsType::value_type _ValueType;
00058       typedef typename _TraitsType::difference_type _DifferenceType;
00059 
00060       _DifferenceType __size = __last - __first;
00061 
00062       if (__size == 0)
00063     return __result;
00064 
00065       // Let the first thread process two parts.
00066       _DifferenceType *__counter;
00067       _DifferenceType *__borders;
00068 
00069       _ThreadIndex __num_threads = __get_max_threads();
00070       // First part contains at least one element.
00071 #     pragma omp parallel num_threads(__num_threads)
00072       {
00073 #       pragma omp single
00074     {
00075       __num_threads = omp_get_num_threads();
00076       __borders = new _DifferenceType[__num_threads + 2];
00077       equally_split(__size, __num_threads + 1, __borders);
00078       __counter = new _DifferenceType[__num_threads + 1];
00079     }
00080 
00081     _ThreadIndex __iam = omp_get_thread_num();
00082 
00083     _DifferenceType __begin, __end;
00084 
00085     // Check for length without duplicates
00086     // Needed for position in output
00087     _DifferenceType __i = 0;
00088     _OutputIterator __out = __result;
00089 
00090     if (__iam == 0)
00091           {
00092             __begin = __borders[0] + 1;   // == 1
00093             __end = __borders[__iam + 1];
00094 
00095             ++__i;
00096             *__out++ = *__first;
00097 
00098             for (_IIter __iter = __first + __begin; __iter < __first + __end;
00099          ++__iter)
00100               {
00101             if (!__binary_pred(*__iter, *(__iter - 1)))
00102                   {
00103                     ++__i;
00104                     *__out++ = *__iter;
00105                   }
00106               }
00107           }
00108     else
00109           {
00110             __begin = __borders[__iam]; //one part
00111             __end = __borders[__iam + 1];
00112 
00113             for (_IIter __iter = __first + __begin; __iter < __first + __end;
00114          ++__iter)
00115               {
00116             if (!__binary_pred(*__iter, *(__iter - 1)))
00117                   ++__i;
00118               }
00119           }
00120     __counter[__iam] = __i;
00121 
00122     // Last part still untouched.
00123     _DifferenceType __begin_output;
00124 
00125 #       pragma omp barrier
00126 
00127     // Store result in output on calculated positions.
00128     __begin_output = 0;
00129 
00130     if (__iam == 0)
00131           {
00132             for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
00133               __begin_output += __counter[__t];
00134 
00135             __i = 0;
00136 
00137             _OutputIterator __iter_out = __result + __begin_output;
00138 
00139             __begin = __borders[__num_threads];
00140             __end = __size;
00141 
00142             for (_IIter __iter = __first + __begin; __iter < __first + __end;
00143          ++__iter)
00144               {
00145             if (__iter == __first
00146             || !__binary_pred(*__iter, *(__iter - 1)))
00147                   {
00148                     ++__i;
00149                     *__iter_out++ = *__iter;
00150                   }
00151               }
00152 
00153             __counter[__num_threads] = __i;
00154           }
00155     else
00156           {
00157             for (_ThreadIndex __t = 0; __t < __iam; __t++)
00158               __begin_output += __counter[__t];
00159 
00160             _OutputIterator __iter_out = __result + __begin_output;
00161             for (_IIter __iter = __first + __begin; __iter < __first + __end;
00162          ++__iter)
00163               {
00164             if (!__binary_pred(*__iter, *(__iter - 1)))
00165                   *__iter_out++ = *__iter;
00166               }
00167           }
00168       }
00169 
00170       _DifferenceType __end_output = 0;
00171       for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
00172     __end_output += __counter[__t];
00173 
00174       delete[] __borders;
00175 
00176       return __result + __end_output;
00177     }
00178 
00179   /** @brief Parallel std::unique_copy(), without explicit equality predicate
00180     *  @param __first Begin iterator of input sequence.
00181     *  @param __last End iterator of input sequence.
00182     *  @param __result Begin iterator of result __sequence.
00183     *  @return End iterator of result __sequence. */
00184   template<typename _IIter, class _OutputIterator>
00185     inline _OutputIterator
00186     __parallel_unique_copy(_IIter __first, _IIter __last,
00187                _OutputIterator __result)
00188     {
00189       typedef typename std::iterator_traits<_IIter>::value_type
00190     _ValueType;
00191       return __parallel_unique_copy(__first, __last, __result,
00192                     std::equal_to<_ValueType>());
00193     }
00194 
00195 }//namespace __gnu_parallel
00196 
00197 #endif /* _GLIBCXX_PARALLEL_UNIQUE_COPY_H */