l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/unique_copy.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/unique_copy.h
  32  *  @brief Parallel implementations of std::unique_copy().
  33  *  This file is a GNU parallel extension to the Standard C++ Library.
  34  */
  35
  36 // Written by Robert Geisberger and Robin Dapp.
  37
  38 #ifndef _GLIBCXX_PARALLEL_UNIQUE_H
  39 #define _GLIBCXX_PARALLEL_UNIQUE_H 1
  40
  41 #include <parallel/parallel.h>
  42 #include <parallel/multiseq_selection.h>
  43
  44 namespace __gnu_parallel
  45 {
  46
  47 /** @brief Parallel std::unique_copy(), w/o explicit equality predicate.
  48   *  @param first Begin iterator of input sequence.
  49   *  @param last End iterator of input sequence.
  50   *  @param result Begin iterator of result sequence.
  51   *  @param binary_pred Equality predicate.
  52   *  @return End iterator of result sequence. */
  53 template<typename InputIterator,
  54          class OutputIterator,
  55          class BinaryPredicate>
  56   OutputIterator
  57   parallel_unique_copy(InputIterator first, InputIterator last,
  58                        OutputIterator result, BinaryPredicate binary_pred)
  59   {
  60     _GLIBCXX_CALL(last - first)
  61
  62     typedef std::iterator_traits<InputIterator> traits_type;
  63     typedef typename traits_type::value_type value_type;
  64     typedef typename traits_type::difference_type difference_type;
  65
  66     difference_type size = last - first;
  67
  68     if (size == 0)
  69       return result;
  70
  71     // Let the first thread process two parts.
  72     difference_type *counter;
  73     difference_type *borders;
  74
  75     thread_index_t num_threads = get_max_threads();
  76     // First part contains at least one element.
  77 #   pragma omp parallel num_threads(num_threads)
  78       {
  79 #       pragma omp single
  80           {
  81             num_threads = omp_get_num_threads();
  82             borders = new difference_type[num_threads + 2];
  83             equally_split(size, num_threads + 1, borders);
  84             counter = new difference_type[num_threads + 1];
  85           }
  86
  87         thread_index_t iam = omp_get_thread_num();
  88
  89         difference_type begin, end;
  90
  91         // Check for length without duplicates
  92         // Needed for position in output
  93         difference_type i = 0;
  94         OutputIterator out = result;
  95
  96         if (iam == 0)
  97         {
  98           begin = borders[0] + 1;       // == 1
  99           end = borders[iam + 1];
 100
 101           ++i;
 102           *out++ = *first;
 103
 104           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 105             {
 106               if (!binary_pred(*iter, *(iter-1)))
 107                 {
 108                   ++i;
 109                   *out++ = *iter;
 110                 }
 111             }
 112         }
 113       else
 114         {
 115           begin = borders[iam]; //one part
 116           end = borders[iam + 1];
 117
 118           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 119             {
 120               if (!binary_pred(*iter, *(iter - 1)))
 121                 ++i;
 122             }
 123         }
 124       counter[iam] = i;
 125
 126       // Last part still untouched.
 127       difference_type begin_output;
 128
 129 #     pragma omp barrier
 130
 131       // Store result in output on calculated positions.
 132       begin_output = 0;
 133
 134       if (iam == 0)
 135         {
 136           for (int t = 0; t < num_threads; ++t)
 137             begin_output += counter[t];
 138
 139           i = 0;
 140
 141           OutputIterator iter_out = result + begin_output;
 142
 143           begin = borders[num_threads];
 144           end = size;
 145
 146           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 147             {
 148               if (iter == first || !binary_pred(*iter, *(iter - 1)))
 149                 {
 150                   ++i;
 151                   *iter_out++ = *iter;
 152                 }
 153             }
 154
 155           counter[num_threads] = i;
 156         }
 157       else
 158         {
 159           for (int t = 0; t < iam; t++)
 160             begin_output += counter[t];
 161
 162           OutputIterator iter_out = result + begin_output;
 163           for (InputIterator iter = first + begin; iter < first + end; ++iter)
 164             {
 165               if (!binary_pred(*iter, *(iter-1)))
 166                 *iter_out++ = *iter;
 167             }
 168         }
 169     }
 170
 171     difference_type end_output = 0;
 172     for (int t = 0; t < num_threads + 1; t++)
 173       end_output += counter[t];
 174
 175     delete[] borders;
 176
 177     return result + end_output;
 178   }
 179
 180 /** @brief Parallel std::unique_copy(), without explicit equality predicate
 181   *  @param first Begin iterator of input sequence.
 182   *  @param last End iterator of input sequence.
 183   *  @param result Begin iterator of result sequence.
 184   *  @return End iterator of result sequence. */
 185 template<typename InputIterator, class OutputIterator>
 186   inline OutputIterator
 187   parallel_unique_copy(InputIterator first, InputIterator last,
 188                        OutputIterator result)
 189   {
 190     typedef typename std::iterator_traits<InputIterator>::value_type
 191       value_type;
 192     return parallel_unique_copy(first, last, result,
 193                                 std::equal_to<value_type>());
 194   }
 195
 196 }//namespace __gnu_parallel
 197
 198 #endif