]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2007 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 2, 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 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | /** @file parallel/equally_split.h | |
32 | * This file is a GNU parallel extension to the Standard C++ Library. | |
33 | */ | |
34 | ||
35 | // Written by Johannes Singler. | |
36 | ||
37 | #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H | |
38 | #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1 | |
39 | ||
40 | namespace __gnu_parallel | |
41 | { | |
e683ee2a JS |
42 | /** @brief Function to split a sequence into parts of almost equal size. |
43 | * | |
44 | * The resulting sequence s of length num_threads+1 contains the splitting | |
45 | * positions when splitting the range [0,n) into parts of almost | |
46 | * equal size (plus minus 1). The first entry is 0, the last one | |
47 | * n. There may result empty parts. | |
48 | * @param n Number of elements | |
49 | * @param num_threads Number of parts | |
50 | * @param s Splitters | |
51 | * @returns End of splitter sequence, i. e. @c s+num_threads+1 */ | |
52 | template<typename difference_type, typename OutputIterator> | |
c2ba9709 | 53 | OutputIterator |
ee1b5fc5 | 54 | equally_split(difference_type n, thread_index_t num_threads, OutputIterator s) |
c2ba9709 | 55 | { |
ee1b5fc5 BK |
56 | difference_type chunk_length = n / num_threads; |
57 | difference_type num_longer_chunks = n % num_threads; | |
58 | difference_type pos = 0; | |
e683ee2a | 59 | for (thread_index_t i = 0; i < num_threads; ++i) |
c2ba9709 | 60 | { |
e683ee2a JS |
61 | *s++ = pos; |
62 | pos += (i < num_longer_chunks) ? (chunk_length + 1) : chunk_length; | |
c2ba9709 JS |
63 | } |
64 | *s++ = n; | |
65 | return s; | |
66 | } | |
e683ee2a JS |
67 | |
68 | ||
69 | /** @brief Function to split a sequence into parts of almost equal size. | |
70 | * | |
71 | * Returns the position of the splitting point between | |
72 | * thread number thread_no (included) and | |
73 | * thread number thread_no+1 (excluded). | |
74 | * @param n Number of elements | |
75 | * @param num_threads Number of parts | |
ee1b5fc5 | 76 | * @returns _SplittingAlgorithm point */ |
e683ee2a JS |
77 | template<typename difference_type> |
78 | difference_type | |
79 | equally_split_point(difference_type n, | |
80 | thread_index_t num_threads, | |
81 | thread_index_t thread_no) | |
82 | { | |
ee1b5fc5 BK |
83 | difference_type chunk_length = n / num_threads; |
84 | difference_type num_longer_chunks = n % num_threads; | |
85 | if (thread_no < num_longer_chunks) | |
e683ee2a JS |
86 | return thread_no * (chunk_length + 1); |
87 | else | |
88 | return num_longer_chunks * (chunk_length + 1) | |
89 | + (thread_no - num_longer_chunks) * chunk_length; | |
90 | } | |
c2ba9709 JS |
91 | } |
92 | ||
cbcd1e45 | 93 | #endif /* _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H */ |