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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2017 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 _IIter>
  49     void
  50     __shrink_and_double(std::vector<_IIter>& __os_starts,
  51                         size_t& __count_to_two, size_t& __range_length,
  52                         const bool __make_twice)
  53     {
  54       ++__count_to_two;
  55       if (!__make_twice || __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 _IIter>
  69     void
  70     __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two,
  71              size_t& __range_length)
  72     {
  73       for (typename std::vector<_IIter>::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
  93    *  \f$\sqrt{\mathrm{end} - \mathrm{begin}}\f$
  94    *  elements. Otherwise, the ratio between the
  95    *  longest and the shortest part is bounded by
  96    *  \f$1/(\mathrm{oversampling} \cdot \mathrm{num\_parts})\f$
  97    *  @return Length of the whole sequence.
  98    */
  99   template<typename _IIter, typename _FunctorType>
 100     size_t
 101     list_partition(const _IIter __begin, const _IIter __end,
 102                    _IIter* __starts, size_t* __lengths, const int __num_parts,
 103                    _FunctorType& __f, int __oversampling = 0)
 104     {
 105       bool __make_twice = false;
 106
 107       // The resizing algorithm is chosen according to the oversampling factor.
 108       if (__oversampling == 0)
 109         {
 110           __make_twice = true;
 111           __oversampling = 1;
 112         }
 113
 114       std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1);
 115
 116       __os_starts[0] = __begin;
 117       _IIter __prev  = __begin, __it = __begin;
 118       size_t __dist_limit = 0, __dist = 0;
 119       size_t __cur = 1, __next = 1;
 120       size_t __range_length = 1;
 121       size_t __count_to_two = 0;
 122       while (__it != __end)
 123         {
 124           __cur = __next;
 125           for (; __cur < __os_starts.size() and __it != __end; ++__cur)
 126             {
 127               for (__dist_limit += __range_length;
 128                    __dist < __dist_limit and __it != __end; ++__dist)
 129                 {
 130                   __f(__it);
 131                   ++__it;
 132                 }
 133               __os_starts[__cur] = __it;
 134             }
 135
 136           // Must compare for end and not __cur < __os_starts.size() , because
 137           // __cur could be == __os_starts.size() as well
 138           if (__it == __end)
 139             break;
 140
 141           __shrink_and_double(__os_starts, __count_to_two, __range_length,
 142                               __make_twice);
 143           __next = __os_starts.size() / 2 + 1;
 144         }
 145
 146       // Calculation of the parts (one must be extracted from __current
 147       // because the partition beginning at end, consists only of
 148       // itself).
 149       size_t __size_part = (__cur - 1) / __num_parts;
 150       int __size_greater = static_cast<int>((__cur - 1) % __num_parts);
 151       __starts[0] = __os_starts[0];
 152
 153       size_t __index = 0;
 154
 155       // Smallest partitions.
 156       for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i)
 157         {
 158           __lengths[__i - 1] =  __size_part * __range_length;
 159           __index += __size_part;
 160           __starts[__i] = __os_starts[__index];
 161         }
 162
 163       // Biggest partitions.
 164       for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts;
 165            ++__i)
 166         {
 167           __lengths[__i - 1] =  (__size_part+1) * __range_length;
 168           __index += (__size_part+1);
 169           __starts[__i] = __os_starts[__index];
 170         }
 171
 172       // Correction of the end size (the end iteration has not finished).
 173       __lengths[__num_parts - 1] -= (__dist_limit - __dist);
 174
 175       return __dist;
 176     }
 177 }
 178
 179 #endif /* _GLIBCXX_PARALLEL_LIST_PARTITION_H */