contrib/gcc-4.4/libstdc++-v3/include/parallel/list_partition.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/list_partition.h
  26  *  @brief Functionality to split sequence referenced by only input
  27  *  iterators.
  28  *  This file is a GNU parallel extension to the Standard C++ Library.
  29  */
  30
  31 // Written by Leonor Frias Moya and Johannes Singler.
  32
  33 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H
  34 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1
  35
  36 #include <parallel/parallel.h>
  37 #include <vector>
  38
  39 namespace __gnu_parallel
  40 {
  41   /** @brief Shrinks and doubles the ranges.
  42    *  @param os_starts Start positions worked on (oversampled).
  43    *  @param count_to_two Counts up to 2.
  44    *  @param range_length Current length of a chunk.
  45    *  @param make_twice Whether the @c os_starts is allowed to be
  46    *  grown or not
  47    */
  48   template<typename InputIterator>
  49     void
  50     shrink_and_double(std::vector<InputIterator>& os_starts,
  51                       size_t& count_to_two, size_t& range_length,
  52                       const bool make_twice)
  53     {
  54       ++count_to_two;
  55       if (not make_twice or count_to_two < 2)
  56         shrink(os_starts, count_to_two, range_length);
  57       else
  58         {
  59           os_starts.resize((os_starts.size() - 1) * 2 + 1);
  60           count_to_two = 0;
  61         }
  62     }
  63
  64   /** @brief Combines two ranges into one and thus halves the number of ranges.
  65    *  @param os_starts Start positions worked on (oversampled).
  66    *  @param count_to_two Counts up to 2.
  67    *  @param range_length Current length of a chunk. */
  68   template<typename InputIterator>
  69     void
  70     shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
  71            size_t& range_length)
  72     {
  73       for (typename std::vector<InputIterator>::size_type i = 0;
  74            i <= (os_starts.size() / 2); ++i)
  75         os_starts[i] = os_starts[i * 2];
  76       range_length *= 2;
  77     }
  78
  79   /** @brief Splits a sequence given by input iterators into parts of
  80    * almost equal size
  81    *
  82    *  The function needs only one pass over the sequence.
  83    *  @param begin Begin iterator of input sequence.
  84    *  @param end End iterator of input sequence.
  85    *  @param starts Start iterators for the resulting parts, dimension
  86    *  @c num_parts+1. For convenience, @c starts @c [num_parts]
  87    *  contains the end iterator of the sequence.
  88    *  @param lengths Length of the resulting parts.
  89    *  @param num_parts Number of parts to split the sequence into.
  90    *  @param f Functor to be applied to each element by traversing it
  91    *  @param oversampling Oversampling factor. If 0, then the
  92    *  partitions will differ in at most @f$ \sqrt{\mathrm{end} -
  93    *  \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
  94    *  longest and the shortest part is bounded by @f$
  95    *  1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
  96    *  @return Length of the whole sequence.
  97    */
  98   template<typename InputIterator, typename FunctorType>
  99     size_t
 100     list_partition(const InputIterator begin, const InputIterator end,
 101                    InputIterator* starts, size_t* lengths, const int num_parts,
 102                    FunctorType& f, int oversampling = 0)
 103     {
 104       bool make_twice = false;
 105
 106       // The resizing algorithm is chosen according to the oversampling factor.
 107       if (oversampling == 0)
 108         {
 109           make_twice = true;
 110           oversampling = 1;
 111         }
 112
 113       std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
 114
 115       os_starts[0]= begin;
 116       InputIterator prev = begin, it = begin;
 117       size_t dist_limit = 0, dist = 0;
 118       size_t cur = 1, next = 1;
 119       size_t range_length = 1;
 120       size_t count_to_two = 0;
 121       while (it != end)
 122         {
 123           cur = next;
 124           for (; cur < os_starts.size() and it != end; ++cur)
 125             {
 126               for (dist_limit += range_length;
 127                    dist < dist_limit and it != end; ++dist)
 128                 {
 129                   f(it);
 130                   ++it;
 131                 }
 132               os_starts[cur] = it;
 133             }
 134
 135           // Must compare for end and not cur < os_starts.size() , because
 136           // cur could be == os_starts.size() as well
 137           if (it == end)
 138             break;
 139
 140           shrink_and_double(os_starts, count_to_two, range_length, make_twice);
 141           next = os_starts.size() / 2 + 1;
 142         }
 143
 144       // Calculation of the parts (one must be extracted from current
 145       // because the partition beginning at end, consists only of
 146       // itself).
 147       size_t size_part = (cur - 1) / num_parts;
 148       int size_greater = static_cast<int>((cur - 1) % num_parts);
 149       starts[0] = os_starts[0];
 150
 151       size_t index = 0;
 152
 153       // Smallest partitions.
 154       for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
 155         {
 156           lengths[i - 1] =  size_part * range_length;
 157           index += size_part;
 158           starts[i] = os_starts[index];
 159         }
 160
 161       // Biggest partitions.
 162       for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
 163         {
 164           lengths[i - 1] =  (size_part+1) * range_length;
 165           index += (size_part+1);
 166           starts[i] = os_starts[index];
 167         }
 168
 169       // Correction of the end size (the end iteration has not finished).
 170       lengths[num_parts - 1] -= (dist_limit - dist);
 171
 172       return dist;
 173     }
 174 }
 175
 176 #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */