1*38fd1498Szrj // -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2007-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the terms 7*38fd1498Szrj // of the GNU General Public License as published by the Free Software 8*38fd1498Szrj // Foundation; either version 3, or (at your option) any later 9*38fd1498Szrj // version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, but 12*38fd1498Szrj // WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*38fd1498Szrj // General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj /** @file parallel/equally_split.h 26*38fd1498Szrj * This file is a GNU parallel extension to the Standard C++ Library. 27*38fd1498Szrj */ 28*38fd1498Szrj 29*38fd1498Szrj // Written by Johannes Singler. 30*38fd1498Szrj 31*38fd1498Szrj #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 32*38fd1498Szrj #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1 33*38fd1498Szrj 34*38fd1498Szrj namespace __gnu_parallel 35*38fd1498Szrj { 36*38fd1498Szrj /** @brief function to split a sequence into parts of almost equal size. 37*38fd1498Szrj * 38*38fd1498Szrj * The resulting sequence __s of length __num_threads+1 contains the 39*38fd1498Szrj * splitting positions when splitting the range [0,__n) into parts of 40*38fd1498Szrj * almost equal size (plus minus 1). The first entry is 0, the last 41*38fd1498Szrj * one n. There may result empty parts. 42*38fd1498Szrj * @param __n Number of elements 43*38fd1498Szrj * @param __num_threads Number of parts 44*38fd1498Szrj * @param __s Splitters 45*38fd1498Szrj * @returns End of __splitter sequence, i.e. @c __s+__num_threads+1 */ 46*38fd1498Szrj template<typename _DifferenceType, typename _OutputIterator> 47*38fd1498Szrj _OutputIterator __equally_split(_DifferenceType __n,_ThreadIndex __num_threads,_OutputIterator __s)48*38fd1498Szrj __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, 49*38fd1498Szrj _OutputIterator __s) 50*38fd1498Szrj { 51*38fd1498Szrj _DifferenceType __chunk_length = __n / __num_threads; 52*38fd1498Szrj _DifferenceType __num_longer_chunks = __n % __num_threads; 53*38fd1498Szrj _DifferenceType __pos = 0; 54*38fd1498Szrj for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) 55*38fd1498Szrj { 56*38fd1498Szrj *__s++ = __pos; 57*38fd1498Szrj __pos += ((__i < __num_longer_chunks) 58*38fd1498Szrj ? (__chunk_length + 1) : __chunk_length); 59*38fd1498Szrj } 60*38fd1498Szrj *__s++ = __n; 61*38fd1498Szrj return __s; 62*38fd1498Szrj } 63*38fd1498Szrj 64*38fd1498Szrj /** @brief function to split a sequence into parts of almost equal size. 65*38fd1498Szrj * 66*38fd1498Szrj * Returns the position of the splitting point between 67*38fd1498Szrj * thread number __thread_no (included) and 68*38fd1498Szrj * thread number __thread_no+1 (excluded). 69*38fd1498Szrj * @param __n Number of elements 70*38fd1498Szrj * @param __num_threads Number of parts 71*38fd1498Szrj * @param __thread_no Number of threads 72*38fd1498Szrj * @returns splitting point */ 73*38fd1498Szrj template<typename _DifferenceType> 74*38fd1498Szrj _DifferenceType __equally_split_point(_DifferenceType __n,_ThreadIndex __num_threads,_ThreadIndex __thread_no)75*38fd1498Szrj __equally_split_point(_DifferenceType __n, 76*38fd1498Szrj _ThreadIndex __num_threads, 77*38fd1498Szrj _ThreadIndex __thread_no) 78*38fd1498Szrj { 79*38fd1498Szrj _DifferenceType __chunk_length = __n / __num_threads; 80*38fd1498Szrj _DifferenceType __num_longer_chunks = __n % __num_threads; 81*38fd1498Szrj if (__thread_no < __num_longer_chunks) 82*38fd1498Szrj return __thread_no * (__chunk_length + 1); 83*38fd1498Szrj else 84*38fd1498Szrj return __num_longer_chunks * (__chunk_length + 1) 85*38fd1498Szrj + (__thread_no - __num_longer_chunks) * __chunk_length; 86*38fd1498Szrj } 87*38fd1498Szrj } 88*38fd1498Szrj 89*38fd1498Szrj #endif /* _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H */ 90