Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/11/parallel/list_partition.h


$ cat -n /usr/include/c++/11/parallel/list_partition.h

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2021 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 */