1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 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/equally_split.h 26 * This file is a GNU parallel extension to the Standard C++ Library. 27 */ 28 29 // Written by Johannes Singler. 30 31 #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 32 #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1 33 34 namespace __gnu_parallel 35 { 36 /** @brief Function to split a sequence into parts of almost equal size. 37 * 38 * The resulting sequence s of length num_threads+1 contains the splitting 39 * positions when splitting the range [0,n) into parts of almost 40 * equal size (plus minus 1). The first entry is 0, the last one 41 * n. There may result empty parts. 42 * @param n Number of elements 43 * @param num_threads Number of parts 44 * @param s Splitters 45 * @returns End of splitter sequence, i. e. @c s+num_threads+1 */ 46 template<typename difference_type, typename OutputIterator> 47 OutputIterator 48 equally_split(difference_type n, thread_index_t num_threads, OutputIterator s) 49 { 50 difference_type chunk_length = n / num_threads; 51 difference_type num_longer_chunks = n % num_threads; 52 difference_type pos = 0; 53 for (thread_index_t i = 0; i < num_threads; ++i) 54 { 55 *s++ = pos; 56 pos += (i < num_longer_chunks) ? (chunk_length + 1) : chunk_length; 57 } 58 *s++ = n; 59 return s; 60 } 61 62 63 /** @brief Function to split a sequence into parts of almost equal size. 64 * 65 * Returns the position of the splitting point between 66 * thread number thread_no (included) and 67 * thread number thread_no+1 (excluded). 68 * @param n Number of elements 69 * @param num_threads Number of parts 70 * @returns _SplittingAlgorithm point */ 71 template<typename difference_type> 72 difference_type 73 equally_split_point(difference_type n, 74 thread_index_t num_threads, 75 thread_index_t thread_no) 76 { 77 difference_type chunk_length = n / num_threads; 78 difference_type num_longer_chunks = n % num_threads; 79 if (thread_no < num_longer_chunks) 80 return thread_no * (chunk_length + 1); 81 else 82 return num_longer_chunks * (chunk_length + 1) 83 + (thread_no - num_longer_chunks) * chunk_length; 84 } 85 } 86 87 #endif /* _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H */ 88
