00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License 00017 // along with this library; see the file COPYING. If not, write to 00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 00019 // MA 02111-1307, USA. 00020 00021 // As a special exception, you may use this file as part of a free 00022 // software library without restriction. Specifically, if other files 00023 // instantiate templates or use macros or inline functions from this 00024 // file, or you compile this file and link it with other files to 00025 // produce an executable, this file does not by itself cause the 00026 // resulting executable to be covered by the GNU General Public 00027 // License. This exception does not however invalidate any other 00028 // reasons why the executable file might be covered by the GNU General 00029 // Public License. 00030 00031 /** @file parallel/equally_split.h 00032 * This file is a GNU parallel extension to the Standard C++ Library. 00033 */ 00034 00035 // Written by Johannes Singler. 00036 00037 #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 00038 #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1 00039 00040 namespace __gnu_parallel 00041 { 00042 /** @brief Function to split a sequence into parts of almost equal size. 00043 * 00044 * The resulting sequence s of length num_threads+1 contains the splitting 00045 * positions when splitting the range [0,n) into parts of almost 00046 * equal size (plus minus 1). The first entry is 0, the last one 00047 * n. There may result empty parts. 00048 * @param n Number of elements 00049 * @param num_threads Number of parts 00050 * @param s Splitters 00051 * @returns End of splitter sequence, i. e. @c s+num_threads+1 */ 00052 template<typename difference_type, typename OutputIterator> 00053 OutputIterator 00054 equally_split(difference_type n, thread_index_t num_threads, OutputIterator s) 00055 { 00056 difference_type chunk_length = n / num_threads; 00057 difference_type num_longer_chunks = n % num_threads; 00058 difference_type pos = 0; 00059 for (thread_index_t i = 0; i < num_threads; ++i) 00060 { 00061 *s++ = pos; 00062 pos += (i < num_longer_chunks) ? (chunk_length + 1) : chunk_length; 00063 } 00064 *s++ = n; 00065 return s; 00066 } 00067 00068 00069 /** @brief Function to split a sequence into parts of almost equal size. 00070 * 00071 * Returns the position of the splitting point between 00072 * thread number thread_no (included) and 00073 * thread number thread_no+1 (excluded). 00074 * @param n Number of elements 00075 * @param num_threads Number of parts 00076 * @returns _SplittingAlgorithm point */ 00077 template<typename difference_type> 00078 difference_type 00079 equally_split_point(difference_type n, 00080 thread_index_t num_threads, 00081 thread_index_t thread_no) 00082 { 00083 difference_type chunk_length = n / num_threads; 00084 difference_type num_longer_chunks = n % num_threads; 00085 if (thread_no < num_longer_chunks) 00086 return thread_no * (chunk_length + 1); 00087 else 00088 return num_longer_chunks * (chunk_length + 1) 00089 + (thread_no - num_longer_chunks) * chunk_length; 00090 } 00091 } 00092 00093 #endif