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

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