3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 /** @file parallel/merge.h
26 * @brief Parallel implementation of std::merge().
27 * This file is a GNU parallel extension to the Standard C++ Library.
30 // Written by Johannes Singler.
32 #ifndef _GLIBCXX_PARALLEL_MERGE_H
33 #define _GLIBCXX_PARALLEL_MERGE_H 1
35 #include <parallel/basic_iterator.h>
36 #include <bits/stl_algo.h>
38 namespace __gnu_parallel
40 /** @brief Merge routine being able to merge only the @c max_length
43 * The @c begin iterators are advanced accordingly, they might not
44 * reach @c end, in contrast to the usual variant.
45 * @param begin1 Begin iterator of first sequence.
46 * @param end1 End iterator of first sequence.
47 * @param begin2 Begin iterator of second sequence.
48 * @param end2 End iterator of second sequence.
49 * @param target Target begin iterator.
50 * @param max_length Maximum number of elements to merge.
51 * @param comp Comparator.
52 * @return Output end iterator. */
53 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
54 typename OutputIterator
, typename _DifferenceTp
,
57 merge_advance_usual(RandomAccessIterator1
& begin1
,
58 RandomAccessIterator1 end1
,
59 RandomAccessIterator2
& begin2
,
60 RandomAccessIterator2 end2
, OutputIterator target
,
61 _DifferenceTp max_length
, Comparator comp
)
63 typedef _DifferenceTp difference_type
;
64 while (begin1
!= end1
&& begin2
!= end2
&& max_length
> 0)
66 // array1[i1] < array0[i0]
67 if (comp(*begin2
, *begin1
))
68 *target
++ = *begin2
++;
70 *target
++ = *begin1
++;
76 target
= std::copy(begin1
, begin1
+ max_length
, target
);
81 target
= std::copy(begin2
, begin2
+ max_length
, target
);
87 /** @brief Merge routine being able to merge only the @c max_length
90 * The @c begin iterators are advanced accordingly, they might not
91 * reach @c end, in contrast to the usual variant.
92 * Specially designed code should allow the compiler to generate
93 * conditional moves instead of branches.
94 * @param begin1 Begin iterator of first sequence.
95 * @param end1 End iterator of first sequence.
96 * @param begin2 Begin iterator of second sequence.
97 * @param end2 End iterator of second sequence.
98 * @param target Target begin iterator.
99 * @param max_length Maximum number of elements to merge.
100 * @param comp Comparator.
101 * @return Output end iterator. */
102 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
103 typename OutputIterator
, typename _DifferenceTp
,
106 merge_advance_movc(RandomAccessIterator1
& begin1
,
107 RandomAccessIterator1 end1
,
108 RandomAccessIterator2
& begin2
,
109 RandomAccessIterator2 end2
,
110 OutputIterator target
,
111 _DifferenceTp max_length
, Comparator comp
)
113 typedef _DifferenceTp difference_type
;
114 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
116 typedef typename
std::iterator_traits
<RandomAccessIterator2
>::value_type
119 #if _GLIBCXX_ASSERTIONS
120 _GLIBCXX_PARALLEL_ASSERT(max_length
>= 0);
123 while (begin1
!= end1
&& begin2
!= end2
&& max_length
> 0)
125 RandomAccessIterator1 next1
= begin1
+ 1;
126 RandomAccessIterator2 next2
= begin2
+ 1;
127 value_type1 element1
= *begin1
;
128 value_type2 element2
= *begin2
;
130 if (comp(element2
, element1
))
145 target
= std::copy(begin1
, begin1
+ max_length
, target
);
146 begin1
+= max_length
;
150 target
= std::copy(begin2
, begin2
+ max_length
, target
);
151 begin2
+= max_length
;
156 /** @brief Merge routine being able to merge only the @c max_length
159 * The @c begin iterators are advanced accordingly, they might not
160 * reach @c end, in contrast to the usual variant.
161 * Static switch on whether to use the conditional-move variant.
162 * @param begin1 Begin iterator of first sequence.
163 * @param end1 End iterator of first sequence.
164 * @param begin2 Begin iterator of second sequence.
165 * @param end2 End iterator of second sequence.
166 * @param target Target begin iterator.
167 * @param max_length Maximum number of elements to merge.
168 * @param comp Comparator.
169 * @return Output end iterator. */
170 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
171 typename OutputIterator
, typename _DifferenceTp
,
173 inline OutputIterator
174 merge_advance(RandomAccessIterator1
& begin1
, RandomAccessIterator1 end1
,
175 RandomAccessIterator2
& begin2
, RandomAccessIterator2 end2
,
176 OutputIterator target
, _DifferenceTp max_length
,
179 _GLIBCXX_CALL(max_length
)
181 return merge_advance_movc(begin1
, end1
, begin2
, end2
, target
,
185 /** @brief Merge routine fallback to sequential in case the
186 iterators of the two input sequences are of different type.
187 * @param begin1 Begin iterator of first sequence.
188 * @param end1 End iterator of first sequence.
189 * @param begin2 Begin iterator of second sequence.
190 * @param end2 End iterator of second sequence.
191 * @param target Target begin iterator.
192 * @param max_length Maximum number of elements to merge.
193 * @param comp Comparator.
194 * @return Output end iterator. */
195 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
196 typename RandomAccessIterator3
, typename Comparator
>
197 inline RandomAccessIterator3
198 parallel_merge_advance(RandomAccessIterator1
& begin1
,
199 RandomAccessIterator1 end1
,
200 RandomAccessIterator2
& begin2
,
201 // different iterators, parallel implementation
203 RandomAccessIterator2 end2
,
204 RandomAccessIterator3 target
, typename
205 std::iterator_traits
<RandomAccessIterator1
>::
206 difference_type max_length
, Comparator comp
)
207 { return merge_advance(begin1
, end1
, begin2
, end2
, target
,
210 /** @brief Parallel merge routine being able to merge only the @c
211 * max_length smallest elements.
213 * The @c begin iterators are advanced accordingly, they might not
214 * reach @c end, in contrast to the usual variant.
215 * The functionality is projected onto parallel_multiway_merge.
216 * @param begin1 Begin iterator of first sequence.
217 * @param end1 End iterator of first sequence.
218 * @param begin2 Begin iterator of second sequence.
219 * @param end2 End iterator of second sequence.
220 * @param target Target begin iterator.
221 * @param max_length Maximum number of elements to merge.
222 * @param comp Comparator.
223 * @return Output end iterator.
225 template<typename RandomAccessIterator1
, typename RandomAccessIterator3
,
227 inline RandomAccessIterator3
228 parallel_merge_advance(RandomAccessIterator1
& begin1
,
229 RandomAccessIterator1 end1
,
230 RandomAccessIterator1
& begin2
,
231 RandomAccessIterator1 end2
,
232 RandomAccessIterator3 target
, typename
233 std::iterator_traits
<RandomAccessIterator1
>::
234 difference_type max_length
, Comparator comp
)
237 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
238 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::
239 difference_type difference_type1
/* == difference_type2 */;
240 typedef typename
std::iterator_traits
<RandomAccessIterator3
>::
241 difference_type difference_type3
;
242 typedef typename
std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
246 seqs
[2] = { std::make_pair(begin1
, end1
),
247 std::make_pair(begin2
, end2
) };
248 RandomAccessIterator3
249 target_end
= parallel_multiway_merge
250 < /* stable = */ true, /* sentinels = */ false>(
251 seqs
, seqs
+ 2, target
,
252 multiway_merge_exact_splitting
253 < /* stable = */ true, iterator_pair
*,
254 Comparator
, difference_type1
>,
255 max_length
, comp
, omp_get_max_threads());
259 } //namespace __gnu_parallel
261 #endif /* _GLIBCXX_PARALLEL_MERGE_H */