libstdc++
merge.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2014 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 
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_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>
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 */
void multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
Exact splitting for parallel multiway-merge routine.
_OutputIterator __merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:171
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
_OutputIterator __merge_advance_movc(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:105
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
_RAIter3 __parallel_merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition: merge.h:195
_OutputIterator __merge_advance_usual(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:57
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:45
_RAIter3 parallel_multiway_merge(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads)
Parallel multi-way merge routine.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.