]>
Commit | Line | Data |
---|---|---|
6482a45c | 1 | // -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2007-2016 Free Software Foundation, Inc. |
6482a45c | 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 | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
6482a45c | 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 | ||
6bc9506f | 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/>. | |
6482a45c | 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 | { | |
73337dee | 40 | /** @brief Merge routine being able to merge only the @c __max_length |
6482a45c | 41 | * smallest elements. |
42 | * | |
73337dee | 43 | * The @c __begin iterators are advanced accordingly, they might not |
44 | * reach @c __end, in contrast to the usual variant. | |
34475802 | 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. | |
6482a45c | 52 | * @return Output end iterator. */ |
34475802 | 53 | template<typename _RAIter1, typename _RAIter2, |
84ec5566 | 54 | typename _OutputIterator, typename _DifferenceTp, |
55 | typename _Compare> | |
34475802 | 56 | _OutputIterator |
757532bc | 57 | __merge_advance_usual(_RAIter1& __begin1, _RAIter1 __end1, |
58 | _RAIter2& __begin2, _RAIter2 __end2, | |
59 | _OutputIterator __target, | |
60 | _DifferenceTp __max_length, _Compare __comp) | |
0be20f8a | 61 | { |
34475802 | 62 | typedef _DifferenceTp _DifferenceType; |
63 | while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0) | |
84ec5566 | 64 | { |
65 | // array1[__i1] < array0[i0] | |
66 | if (__comp(*__begin2, *__begin1)) | |
67 | *__target++ = *__begin2++; | |
68 | else | |
69 | *__target++ = *__begin1++; | |
70 | --__max_length; | |
71 | } | |
0be20f8a | 72 | |
34475802 | 73 | if (__begin1 != __end1) |
84ec5566 | 74 | { |
75 | __target = std::copy(__begin1, __begin1 + __max_length, __target); | |
76 | __begin1 += __max_length; | |
77 | } | |
0be20f8a | 78 | else |
84ec5566 | 79 | { |
80 | __target = std::copy(__begin2, __begin2 + __max_length, __target); | |
81 | __begin2 += __max_length; | |
82 | } | |
34475802 | 83 | return __target; |
0be20f8a | 84 | } |
6482a45c | 85 | |
73337dee | 86 | /** @brief Merge routine being able to merge only the @c __max_length |
6482a45c | 87 | * smallest elements. |
88 | * | |
73337dee | 89 | * The @c __begin iterators are advanced accordingly, they might not |
90 | * reach @c __end, in contrast to the usual variant. | |
6482a45c | 91 | * Specially designed code should allow the compiler to generate |
92 | * conditional moves instead of branches. | |
34475802 | 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. | |
6482a45c | 100 | * @return Output end iterator. */ |
34475802 | 101 | template<typename _RAIter1, typename _RAIter2, |
84ec5566 | 102 | typename _OutputIterator, typename _DifferenceTp, |
103 | typename _Compare> | |
34475802 | 104 | _OutputIterator |
757532bc | 105 | __merge_advance_movc(_RAIter1& __begin1, _RAIter1 __end1, |
106 | _RAIter2& __begin2, _RAIter2 __end2, | |
107 | _OutputIterator __target, | |
108 | _DifferenceTp __max_length, _Compare __comp) | |
0be20f8a | 109 | { |
34475802 | 110 | typedef _DifferenceTp _DifferenceType; |
111 | typedef typename std::iterator_traits<_RAIter1>::value_type | |
30238171 | 112 | _ValueType1; |
34475802 | 113 | typedef typename std::iterator_traits<_RAIter2>::value_type |
30238171 | 114 | _ValueType2; |
6482a45c | 115 | |
116 | #if _GLIBCXX_ASSERTIONS | |
34475802 | 117 | _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0); |
6482a45c | 118 | #endif |
119 | ||
34475802 | 120 | while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0) |
84ec5566 | 121 | { |
122 | _RAIter1 __next1 = __begin1 + 1; | |
123 | _RAIter2 __next2 = __begin2 + 1; | |
30238171 | 124 | _ValueType1 __element1 = *__begin1; |
125 | _ValueType2 __element2 = *__begin2; | |
0be20f8a | 126 | |
84ec5566 | 127 | if (__comp(__element2, __element1)) |
128 | { | |
129 | __element1 = __element2; | |
130 | __begin2 = __next2; | |
131 | } | |
132 | else | |
133 | __begin1 = __next1; | |
0be20f8a | 134 | |
84ec5566 | 135 | *__target = __element1; |
0be20f8a | 136 | |
84ec5566 | 137 | ++__target; |
138 | --__max_length; | |
139 | } | |
34475802 | 140 | if (__begin1 != __end1) |
84ec5566 | 141 | { |
142 | __target = std::copy(__begin1, __begin1 + __max_length, __target); | |
143 | __begin1 += __max_length; | |
144 | } | |
0be20f8a | 145 | else |
84ec5566 | 146 | { |
147 | __target = std::copy(__begin2, __begin2 + __max_length, __target); | |
148 | __begin2 += __max_length; | |
149 | } | |
34475802 | 150 | return __target; |
0be20f8a | 151 | } |
6482a45c | 152 | |
73337dee | 153 | /** @brief Merge routine being able to merge only the @c __max_length |
6482a45c | 154 | * smallest elements. |
155 | * | |
73337dee | 156 | * The @c __begin iterators are advanced accordingly, they might not |
157 | * reach @c __end, in contrast to the usual variant. | |
6482a45c | 158 | * Static switch on whether to use the conditional-move variant. |
34475802 | 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. | |
6482a45c | 166 | * @return Output end iterator. */ |
34475802 | 167 | template<typename _RAIter1, typename _RAIter2, |
84ec5566 | 168 | typename _OutputIterator, typename _DifferenceTp, |
169 | typename _Compare> | |
34475802 | 170 | inline _OutputIterator |
171 | __merge_advance(_RAIter1& __begin1, _RAIter1 __end1, | |
757532bc | 172 | _RAIter2& __begin2, _RAIter2 __end2, |
173 | _OutputIterator __target, _DifferenceTp __max_length, | |
174 | _Compare __comp) | |
0be20f8a | 175 | { |
34475802 | 176 | _GLIBCXX_CALL(__max_length) |
6482a45c | 177 | |
757532bc | 178 | return __merge_advance_movc(__begin1, __end1, __begin2, __end2, |
179 | __target, __max_length, __comp); | |
0be20f8a | 180 | } |
6482a45c | 181 | |
182 | /** @brief Merge routine fallback to sequential in case the | |
183 | iterators of the two input sequences are of different type. | |
34475802 | 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. | |
6482a45c | 191 | * @return Output end iterator. */ |
34475802 | 192 | template<typename _RAIter1, typename _RAIter2, |
84ec5566 | 193 | typename _RAIter3, typename _Compare> |
34475802 | 194 | inline _RAIter3 |
757532bc | 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) | |
34475802 | 202 | { return __merge_advance(__begin1, __end1, __begin2, __end2, __target, |
757532bc | 203 | __max_length, __comp); } |
6482a45c | 204 | |
73337dee | 205 | /** @brief Parallel merge routine being able to merge only the @c |
34475802 | 206 | * __max_length smallest elements. |
6482a45c | 207 | * |
73337dee | 208 | * The @c __begin iterators are advanced accordingly, they might not |
209 | * reach @c __end, in contrast to the usual variant. | |
6482a45c | 210 | * The functionality is projected onto parallel_multiway_merge. |
34475802 | 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. | |
6482a45c | 218 | * @return Output end iterator. |
219 | */ | |
34475802 | 220 | template<typename _RAIter1, typename _RAIter3, |
84ec5566 | 221 | typename _Compare> |
34475802 | 222 | inline _RAIter3 |
757532bc | 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) | |
0be20f8a | 228 | { |
3aa2bf8f | 229 | typedef typename |
34475802 | 230 | std::iterator_traits<_RAIter1>::value_type _ValueType; |
231 | typedef typename std::iterator_traits<_RAIter1>:: | |
84ec5566 | 232 | difference_type _DifferenceType1 /* == difference_type2 */; |
34475802 | 233 | typedef typename std::iterator_traits<_RAIter3>:: |
84ec5566 | 234 | difference_type _DifferenceType3; |
34475802 | 235 | typedef typename std::pair<_RAIter1, _RAIter1> |
236 | _IteratorPair; | |
0be20f8a | 237 | |
757532bc | 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()); | |
0be20f8a | 246 | |
34475802 | 247 | return __target_end; |
0be20f8a | 248 | } |
84ec5566 | 249 | } //namespace __gnu_parallel |
6482a45c | 250 | |
a8aa9db5 | 251 | #endif /* _GLIBCXX_PARALLEL_MERGE_H */ |