00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/equally_split.h 00026 * This file is a GNU parallel extension to the Standard C++ Library. 00027 */ 00028 00029 // Written by Johannes Singler. 00030 00031 #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 00032 #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1 00033 00034 namespace __gnu_parallel 00035 { 00036 /** @brief Function to split a sequence into parts of almost equal size. 00037 * 00038 * The resulting sequence s of length num_threads+1 contains the splitting 00039 * positions when splitting the range [0,n) into parts of almost 00040 * equal size (plus minus 1). The first entry is 0, the last one 00041 * n. There may result empty parts. 00042 * @param n Number of elements 00043 * @param num_threads Number of parts 00044 * @param s Splitters 00045 * @returns End of splitter sequence, i. e. @c s+num_threads+1 */ 00046 template<typename difference_type, typename OutputIterator> 00047 OutputIterator 00048 equally_split(difference_type n, thread_index_t num_threads, OutputIterator s) 00049 { 00050 difference_type chunk_length = n / num_threads; 00051 difference_type num_longer_chunks = n % num_threads; 00052 difference_type pos = 0; 00053 for (thread_index_t i = 0; i < num_threads; ++i) 00054 { 00055 *s++ = pos; 00056 pos += (i < num_longer_chunks) ? (chunk_length + 1) : chunk_length; 00057 } 00058 *s++ = n; 00059 return s; 00060 } 00061 00062 00063 /** @brief Function to split a sequence into parts of almost equal size. 00064 * 00065 * Returns the position of the splitting point between 00066 * thread number thread_no (included) and 00067 * thread number thread_no+1 (excluded). 00068 * @param n Number of elements 00069 * @param num_threads Number of parts 00070 * @returns _SplittingAlgorithm point */ 00071 template<typename difference_type> 00072 difference_type 00073 equally_split_point(difference_type n, 00074 thread_index_t num_threads, 00075 thread_index_t thread_no) 00076 { 00077 difference_type chunk_length = n / num_threads; 00078 difference_type num_longer_chunks = n % num_threads; 00079 if (thread_no < num_longer_chunks) 00080 return thread_no * (chunk_length + 1); 00081 else 00082 return num_longer_chunks * (chunk_length + 1) 00083 + (thread_no - num_longer_chunks) * chunk_length; 00084 } 00085 } 00086 00087 #endif /* _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H */