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 _RAIter1, typename _RAIter2,
54 typename _OutputIterator, typename _DifferenceTp,
57 __merge_advance_usual(_RAIter1& __begin1,
60 _RAIter2 __end2, _OutputIterator __target,
61 _DifferenceTp __max_length, _Compare __comp)
63 typedef _DifferenceTp _DifferenceType;
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++;
74 if (__begin1 != __end1)
76 __target = std::copy(__begin1, __begin1 + __max_length, __target);
77 __begin1 += __max_length;
81 __target = std::copy(__begin2, __begin2 + __max_length, __target);
82 __begin2 += __max_length;
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 _RAIter1, typename _RAIter2,
103 typename _OutputIterator, typename _DifferenceTp,
106 __merge_advance_movc(_RAIter1& __begin1,
110 _OutputIterator __target,
111 _DifferenceTp __max_length, _Compare __comp)
113 typedef _DifferenceTp _DifferenceType;
114 typedef typename std::iterator_traits<_RAIter1>::value_type
116 typedef typename std::iterator_traits<_RAIter2>::value_type
119 #if _GLIBCXX_ASSERTIONS
120 _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0);
123 while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
125 _RAIter1 __next1 = __begin1 + 1;
126 _RAIter2 __next2 = __begin2 + 1;
127 _ValueType1 __element1 = *__begin1;
128 _ValueType2 __element2 = *__begin2;
130 if (__comp(__element2, __element1))
132 __element1 = __element2;
138 *__target = __element1;
143 if (__begin1 != __end1)
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 _RAIter1, typename _RAIter2,
171 typename _OutputIterator, typename _DifferenceTp,
173 inline _OutputIterator
174 __merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
175 _RAIter2& __begin2, _RAIter2 __end2,
176 _OutputIterator __target, _DifferenceTp __max_length,
179 _GLIBCXX_CALL(__max_length)
181 return __merge_advance_movc(__begin1, __end1, __begin2, __end2, __target,
182 __max_length, __comp);
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 _RAIter1, typename _RAIter2,
196 typename _RAIter3, typename _Compare>
198 __parallel_merge_advance(_RAIter1& __begin1,
201 // different iterators, parallel implementation
204 _RAIter3 __target, typename
205 std::iterator_traits<_RAIter1>::
206 difference_type __max_length, _Compare __comp)
207 { return __merge_advance(__begin1, __end1, __begin2, __end2, __target,
208 __max_length, __comp); }
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 _RAIter1, typename _RAIter3,
228 __parallel_merge_advance(_RAIter1& __begin1,
232 _RAIter3 __target, typename
233 std::iterator_traits<_RAIter1>::
234 difference_type __max_length, _Compare __comp)
237 std::iterator_traits<_RAIter1>::value_type _ValueType;
238 typedef typename std::iterator_traits<_RAIter1>::
239 difference_type _DifferenceType1 /* == difference_type2 */;
240 typedef typename std::iterator_traits<_RAIter3>::
241 difference_type _DifferenceType3;
242 typedef typename std::pair<_RAIter1, _RAIter1>
246 seqs[2] = { std::make_pair(__begin1, __end1),
247 std::make_pair(__begin2, __end2) };
249 __target_end = parallel_multiway_merge
250 < /* __stable = */ true, /* __sentinels = */ false>(
251 seqs, seqs + 2, __target,
252 multiway_merge_exact_splitting
253 < /* __stable = */ true, _IteratorPair*,
254 _Compare, _DifferenceType1>,
255 __max_length, __comp, omp_get_max_threads());
259 } //namespace __gnu_parallel
261 #endif /* _GLIBCXX_PARALLEL_MERGE_H */