1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2023 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 3, 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 // 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.
19
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/>.
24
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.
28 */
29
30 // Written by Johannes Singler.
31
32 #ifndef _GLIBCXX_PARALLEL_MERGE_H
33 #define _GLIBCXX_PARALLEL_MERGE_H 1
34
35 #include <parallel/basic_iterator.h>
36 #include <bits/stl_algo.h>
37
38 namespace __gnu_parallel
39 {
40 /** @brief Merge routine being able to merge only the @c __max_length
41 * smallest elements.
42 *
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,
55 typename _Compare>
56 _OutputIterator
57 __merge_advance_usual(_RAIter1& __begin1, _RAIter1 __end1,
58 _RAIter2& __begin2, _RAIter2 __end2,
59 _OutputIterator __target,
60 _DifferenceTp __max_length, _Compare __comp)
61 {
62 typedef _DifferenceTp _DifferenceType;
63 while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
64 {
65 // array1[__i1] < array0[i0]
66 if (__comp(*__begin2, *__begin1))
67 *__target++ = *__begin2++;
68 else
69 *__target++ = *__begin1++;
70 --__max_length;
71 }
72
73 if (__begin1 != __end1)
74 {
75 __target = std::copy(__begin1, __begin1 + __max_length, __target);
76 __begin1 += __max_length;
77 }
78 else
79 {
80 __target = std::copy(__begin2, __begin2 + __max_length, __target);
81 __begin2 += __max_length;
82 }
83 return __target;
84 }
85
86 /** @brief Merge routine being able to merge only the @c __max_length
87 * smallest elements.
88 *
89 * The @c __begin iterators are advanced accordingly, they might not
90 * reach @c __end, in contrast to the usual variant.
91 * Specially designed code should allow the compiler to generate
92 * conditional moves instead of branches.
93 * @param __begin1 Begin iterator of first sequence.
94 * @param __end1 End iterator of first sequence.
95 * @param __begin2 Begin iterator of second sequence.
96 * @param __end2 End iterator of second sequence.
97 * @param __target Target begin iterator.
98 * @param __max_length Maximum number of elements to merge.
99 * @param __comp Comparator.
100 * @return Output end iterator. */
101 template<typename _RAIter1, typename _RAIter2,
102 typename _OutputIterator, typename _DifferenceTp,
103 typename _Compare>
104 _OutputIterator
105 __merge_advance_movc(_RAIter1& __begin1, _RAIter1 __end1,
106 _RAIter2& __begin2, _RAIter2 __end2,
107 _OutputIterator __target,
108 _DifferenceTp __max_length, _Compare __comp)
109 {
110 typedef _DifferenceTp _DifferenceType;
111 typedef typename std::iterator_traits<_RAIter1>::value_type
112 _ValueType1;
113 typedef typename std::iterator_traits<_RAIter2>::value_type
114 _ValueType2;
115
116 #if _GLIBCXX_PARALLEL_ASSERTIONS
117 _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0);
118 #endif
119
120 while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
121 {
122 _RAIter1 __next1 = __begin1 + 1;
123 _RAIter2 __next2 = __begin2 + 1;
124 _ValueType1 __element1 = *__begin1;
125 _ValueType2 __element2 = *__begin2;
126
127 if (__comp(__element2, __element1))
128 {
129 __element1 = __element2;
130 __begin2 = __next2;
131 }
132 else
133 __begin1 = __next1;
134
135 *__target = __element1;
136
137 ++__target;
138 --__max_length;
139 }
140 if (__begin1 != __end1)
141 {
142 __target = std::copy(__begin1, __begin1 + __max_length, __target);
143 __begin1 += __max_length;
144 }
145 else
146 {
147 __target = std::copy(__begin2, __begin2 + __max_length, __target);
148 __begin2 += __max_length;
149 }
150 return __target;
151 }
152
153 /** @brief Merge routine being able to merge only the @c __max_length
154 * smallest elements.
155 *
156 * The @c __begin iterators are advanced accordingly, they might not
157 * reach @c __end, in contrast to the usual variant.
158 * Static switch on whether to use the conditional-move variant.
159 * @param __begin1 Begin iterator of first sequence.
160 * @param __end1 End iterator of first sequence.
161 * @param __begin2 Begin iterator of second sequence.
162 * @param __end2 End iterator of second sequence.
163 * @param __target Target begin iterator.
164 * @param __max_length Maximum number of elements to merge.
165 * @param __comp Comparator.
166 * @return Output end iterator. */
167 template<typename _RAIter1, typename _RAIter2,
168 typename _OutputIterator, typename _DifferenceTp,
169 typename _Compare>
170 inline _OutputIterator
171 __merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
172 _RAIter2& __begin2, _RAIter2 __end2,
173 _OutputIterator __target, _DifferenceTp __max_length,
174 _Compare __comp)
175 {
176 _GLIBCXX_CALL(__max_length)
177
178 return __merge_advance_movc(__begin1, __end1, __begin2, __end2,
179 __target, __max_length, __comp);
180 }
181
182 /** @brief Merge routine fallback to sequential in case the
183 iterators of the two input sequences are of different type.
184 * @param __begin1 Begin iterator of first sequence.
185 * @param __end1 End iterator of first sequence.
186 * @param __begin2 Begin iterator of second sequence.
187 * @param __end2 End iterator of second sequence.
188 * @param __target Target begin iterator.
189 * @param __max_length Maximum number of elements to merge.
190 * @param __comp Comparator.
191 * @return Output end iterator. */
192 template<typename _RAIter1, typename _RAIter2,
193 typename _RAIter3, typename _Compare>
194 inline _RAIter3
195 __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
196 _RAIter2& __begin2,
197 // different iterators, parallel implementation
198 // not available
199 _RAIter2 __end2, _RAIter3 __target, typename
200 std::iterator_traits<_RAIter1>::
201 difference_type __max_length, _Compare __comp)
202 { return __merge_advance(__begin1, __end1, __begin2, __end2, __target,
203 __max_length, __comp); }
204
205 /** @brief Parallel merge routine being able to merge only the @c
206 * __max_length smallest elements.
207 *
208 * The @c __begin iterators are advanced accordingly, they might not
209 * reach @c __end, in contrast to the usual variant.
210 * The functionality is projected onto parallel_multiway_merge.
211 * @param __begin1 Begin iterator of first sequence.
212 * @param __end1 End iterator of first sequence.
213 * @param __begin2 Begin iterator of second sequence.
214 * @param __end2 End iterator of second sequence.
215 * @param __target Target begin iterator.
216 * @param __max_length Maximum number of elements to merge.
217 * @param __comp Comparator.
218 * @return Output end iterator.
219 */
220 template<typename _RAIter1, typename _RAIter3,
221 typename _Compare>
222 inline _RAIter3
223 __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
224 _RAIter1& __begin2, _RAIter1 __end2,
225 _RAIter3 __target, typename
226 std::iterator_traits<_RAIter1>::
227 difference_type __max_length, _Compare __comp)
228 {
229 typedef typename
230 std::iterator_traits<_RAIter1>::value_type _ValueType;
231 typedef typename std::iterator_traits<_RAIter1>::
232 difference_type _DifferenceType1 /* == difference_type2 */;
233 typedef typename std::iterator_traits<_RAIter3>::
234 difference_type _DifferenceType3;
235 typedef typename std::pair<_RAIter1, _RAIter1>
236 _IteratorPair;
237
238 _IteratorPair __seqs[2] = { std::make_pair(__begin1, __end1),
239 std::make_pair(__begin2, __end2) };
240 _RAIter3 __target_end = parallel_multiway_merge
241 < /* __stable = */ true, /* __sentinels = */ false>
242 (__seqs, __seqs + 2, __target, multiway_merge_exact_splitting
243 < /* __stable = */ true, _IteratorPair*,
244 _Compare, _DifferenceType1>, __max_length, __comp,
245 omp_get_max_threads());
246
247 return __target_end;
248 }
249 } //namespace __gnu_parallel
250
251 #endif /* _GLIBCXX_PARALLEL_MERGE_H */