3 // Copyright (C) 2007, 2008 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 2, 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 // 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.
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
31 /** @file parallel/merge.h
32 * @brief Parallel implementation of std::merge().
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_MERGE_H
39 #define _GLIBCXX_PARALLEL_MERGE_H 1
41 #include <parallel/basic_iterator.h>
42 #include <bits/stl_algo.h>
44 namespace __gnu_parallel
46 /** @brief Merge routine being able to merge only the @c max_length
49 * The @c begin iterators are advanced accordingly, they might not
50 * reach @c end, in contrast to the usual variant.
51 * @param begin1 Begin iterator of first sequence.
52 * @param end1 End iterator of first sequence.
53 * @param begin2 Begin iterator of second sequence.
54 * @param end2 End iterator of second sequence.
55 * @param target Target begin iterator.
56 * @param max_length Maximum number of elements to merge.
57 * @param comp Comparator.
58 * @return Output end iterator. */
59 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
60 typename OutputIterator
, typename _DifferenceTp
,
63 merge_advance_usual(RandomAccessIterator1
& begin1
,
64 RandomAccessIterator1 end1
,
65 RandomAccessIterator2
& begin2
,
66 RandomAccessIterator2 end2
, OutputIterator target
,
67 _DifferenceTp max_length
, Comparator comp
)
69 typedef _DifferenceTp difference_type
;
70 while (begin1
!= end1
&& begin2
!= end2
&& max_length
> 0)
72 // array1[i1] < array0[i0]
73 if (comp(*begin2
, *begin1
))
74 *target
++ = *begin2
++;
76 *target
++ = *begin1
++;
82 target
= std::copy(begin1
, begin1
+ max_length
, target
);
87 target
= std::copy(begin2
, begin2
+ max_length
, target
);
93 /** @brief Merge routine being able to merge only the @c max_length
96 * The @c begin iterators are advanced accordingly, they might not
97 * reach @c end, in contrast to the usual variant.
98 * Specially designed code should allow the compiler to generate
99 * conditional moves instead of branches.
100 * @param begin1 Begin iterator of first sequence.
101 * @param end1 End iterator of first sequence.
102 * @param begin2 Begin iterator of second sequence.
103 * @param end2 End iterator of second sequence.
104 * @param target Target begin iterator.
105 * @param max_length Maximum number of elements to merge.
106 * @param comp Comparator.
107 * @return Output end iterator. */
108 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
109 typename OutputIterator
, typename _DifferenceTp
,
112 merge_advance_movc(RandomAccessIterator1
& begin1
,
113 RandomAccessIterator1 end1
,
114 RandomAccessIterator2
& begin2
,
115 RandomAccessIterator2 end2
,
116 OutputIterator target
,
117 _DifferenceTp max_length
, Comparator comp
)
119 typedef _DifferenceTp difference_type
;
120 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
122 typedef typename
std::iterator_traits
<RandomAccessIterator2
>::value_type
125 #if _GLIBCXX_ASSERTIONS
126 _GLIBCXX_PARALLEL_ASSERT(max_length
>= 0);
129 while (begin1
!= end1
&& begin2
!= end2
&& max_length
> 0)
131 RandomAccessIterator1 next1
= begin1
+ 1;
132 RandomAccessIterator2 next2
= begin2
+ 1;
133 value_type1 element1
= *begin1
;
134 value_type2 element2
= *begin2
;
136 if (comp(element2
, element1
))
151 target
= std::copy(begin1
, begin1
+ max_length
, target
);
152 begin1
+= max_length
;
156 target
= std::copy(begin2
, begin2
+ max_length
, target
);
157 begin2
+= max_length
;
162 /** @brief Merge routine being able to merge only the @c max_length
165 * The @c begin iterators are advanced accordingly, they might not
166 * reach @c end, in contrast to the usual variant.
167 * Static switch on whether to use the conditional-move variant.
168 * @param begin1 Begin iterator of first sequence.
169 * @param end1 End iterator of first sequence.
170 * @param begin2 Begin iterator of second sequence.
171 * @param end2 End iterator of second sequence.
172 * @param target Target begin iterator.
173 * @param max_length Maximum number of elements to merge.
174 * @param comp Comparator.
175 * @return Output end iterator. */
176 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
177 typename OutputIterator
, typename _DifferenceTp
,
179 inline OutputIterator
180 merge_advance(RandomAccessIterator1
& begin1
, RandomAccessIterator1 end1
,
181 RandomAccessIterator2
& begin2
, RandomAccessIterator2 end2
,
182 OutputIterator target
, _DifferenceTp max_length
,
185 _GLIBCXX_CALL(max_length
)
187 return merge_advance_movc(begin1
, end1
, begin2
, end2
, target
,
191 /** @brief Merge routine fallback to sequential in case the
192 iterators of the two input sequences are of different type.
193 * @param begin1 Begin iterator of first sequence.
194 * @param end1 End iterator of first sequence.
195 * @param begin2 Begin iterator of second sequence.
196 * @param end2 End iterator of second sequence.
197 * @param target Target begin iterator.
198 * @param max_length Maximum number of elements to merge.
199 * @param comp Comparator.
200 * @return Output end iterator. */
201 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
202 typename RandomAccessIterator3
, typename Comparator
>
203 inline RandomAccessIterator3
204 parallel_merge_advance(RandomAccessIterator1
& begin1
,
205 RandomAccessIterator1 end1
,
206 RandomAccessIterator2
& begin2
,
207 // different iterators, parallel implementation
209 RandomAccessIterator2 end2
,
210 RandomAccessIterator3 target
, typename
211 std::iterator_traits
<RandomAccessIterator1
>::
212 difference_type max_length
, Comparator comp
)
213 { return merge_advance(begin1
, end1
, begin2
, end2
, target
,
216 /** @brief Parallel merge routine being able to merge only the @c
217 * max_length smallest elements.
219 * The @c begin iterators are advanced accordingly, they might not
220 * reach @c end, in contrast to the usual variant.
221 * The functionality is projected onto parallel_multiway_merge.
222 * @param begin1 Begin iterator of first sequence.
223 * @param end1 End iterator of first sequence.
224 * @param begin2 Begin iterator of second sequence.
225 * @param end2 End iterator of second sequence.
226 * @param target Target begin iterator.
227 * @param max_length Maximum number of elements to merge.
228 * @param comp Comparator.
229 * @return Output end iterator.
231 template<typename RandomAccessIterator1
, typename RandomAccessIterator3
,
233 inline RandomAccessIterator3
234 parallel_merge_advance(RandomAccessIterator1
& begin1
,
235 RandomAccessIterator1 end1
,
236 RandomAccessIterator1
& begin2
,
237 RandomAccessIterator1 end2
,
238 RandomAccessIterator3 target
, typename
239 std::iterator_traits
<RandomAccessIterator1
>::
240 difference_type max_length
, Comparator comp
)
243 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
244 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::
245 difference_type difference_type1
/* == difference_type2 */;
246 typedef typename
std::iterator_traits
<RandomAccessIterator3
>::
247 difference_type difference_type3
;
248 typedef typename
std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
251 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
252 seqs
[2] = { std::make_pair(begin1
, end1
),
253 std::make_pair(begin2
, end2
) };
254 RandomAccessIterator3
255 target_end
= parallel_multiway_merge
256 < /* stable = */ true, /* sentinels = */ false>(
257 seqs
, seqs
+ 2, target
, comp
,
258 multiway_merge_exact_splitting
259 < /* stable = */ true, iterator_pair
*,
260 Comparator
, difference_type1
>,
265 } //namespace __gnu_parallel