libstdc++
merge.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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 RandomAccessIterator1, typename RandomAccessIterator2,
54  typename OutputIterator, typename _DifferenceTp,
55  typename Comparator>
56  OutputIterator
57  merge_advance_usual(RandomAccessIterator1& begin1,
58  RandomAccessIterator1 end1,
59  RandomAccessIterator2& begin2,
60  RandomAccessIterator2 end2, OutputIterator target,
61  _DifferenceTp max_length, Comparator comp)
62  {
63  typedef _DifferenceTp difference_type;
64  while (begin1 != end1 && begin2 != end2 && max_length > 0)
65  {
66  // array1[i1] < array0[i0]
67  if (comp(*begin2, *begin1))
68  *target++ = *begin2++;
69  else
70  *target++ = *begin1++;
71  --max_length;
72  }
73 
74  if (begin1 != end1)
75  {
76  target = std::copy(begin1, begin1 + max_length, target);
77  begin1 += max_length;
78  }
79  else
80  {
81  target = std::copy(begin2, begin2 + max_length, target);
82  begin2 += max_length;
83  }
84  return target;
85  }
86 
87  /** @brief Merge routine being able to merge only the @c max_length
88  * smallest elements.
89  *
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 RandomAccessIterator1, typename RandomAccessIterator2,
103  typename OutputIterator, typename _DifferenceTp,
104  typename Comparator>
105  OutputIterator
106  merge_advance_movc(RandomAccessIterator1& begin1,
107  RandomAccessIterator1 end1,
108  RandomAccessIterator2& begin2,
109  RandomAccessIterator2 end2,
110  OutputIterator target,
111  _DifferenceTp max_length, Comparator comp)
112  {
113  typedef _DifferenceTp difference_type;
114  typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
115  value_type1;
116  typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
117  value_type2;
118 
119 #if _GLIBCXX_ASSERTIONS
120  _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
121 #endif
122 
123  while (begin1 != end1 && begin2 != end2 && max_length > 0)
124  {
125  RandomAccessIterator1 next1 = begin1 + 1;
126  RandomAccessIterator2 next2 = begin2 + 1;
127  value_type1 element1 = *begin1;
128  value_type2 element2 = *begin2;
129 
130  if (comp(element2, element1))
131  {
132  element1 = element2;
133  begin2 = next2;
134  }
135  else
136  begin1 = next1;
137 
138  *target = element1;
139 
140  ++target;
141  --max_length;
142  }
143  if (begin1 != end1)
144  {
145  target = std::copy(begin1, begin1 + max_length, target);
146  begin1 += max_length;
147  }
148  else
149  {
150  target = std::copy(begin2, begin2 + max_length, target);
151  begin2 += max_length;
152  }
153  return target;
154  }
155 
156  /** @brief Merge routine being able to merge only the @c max_length
157  * smallest elements.
158  *
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 RandomAccessIterator1, typename RandomAccessIterator2,
171  typename OutputIterator, typename _DifferenceTp,
172  typename Comparator>
173  inline OutputIterator
174  merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
175  RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
176  OutputIterator target, _DifferenceTp max_length,
177  Comparator comp)
178  {
179  _GLIBCXX_CALL(max_length)
180 
181  return merge_advance_movc(begin1, end1, begin2, end2, target,
182  max_length, comp);
183  }
184 
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 RandomAccessIterator1, typename RandomAccessIterator2,
196  typename RandomAccessIterator3, typename Comparator>
197  inline RandomAccessIterator3
198  parallel_merge_advance(RandomAccessIterator1& begin1,
199  RandomAccessIterator1 end1,
200  RandomAccessIterator2& begin2,
201  // different iterators, parallel implementation
202  // not available
203  RandomAccessIterator2 end2,
204  RandomAccessIterator3 target, typename
206  difference_type max_length, Comparator comp)
207  { return merge_advance(begin1, end1, begin2, end2, target,
208  max_length, comp); }
209 
210  /** @brief Parallel merge routine being able to merge only the @c
211  * max_length smallest elements.
212  *
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.
224  */
225  template<typename RandomAccessIterator1, typename RandomAccessIterator3,
226  typename Comparator>
227  inline RandomAccessIterator3
228  parallel_merge_advance(RandomAccessIterator1& begin1,
229  RandomAccessIterator1 end1,
230  RandomAccessIterator1& begin2,
231  RandomAccessIterator1 end2,
232  RandomAccessIterator3 target, typename
234  difference_type max_length, Comparator comp)
235  {
236  typedef typename
237  std::iterator_traits<RandomAccessIterator1>::value_type value_type;
239  difference_type difference_type1 /* == difference_type2 */;
241  difference_type difference_type3;
244 
245  iterator_pair
246  seqs[2] = { std::make_pair(begin1, end1),
247  std::make_pair(begin2, end2) };
248  RandomAccessIterator3
249  target_end = parallel_multiway_merge
250  < /* stable = */ true, /* sentinels = */ false>(
251  seqs, seqs + 2, target,
253  < /* stable = */ true, iterator_pair*,
254  Comparator, difference_type1>,
255  max_length, comp, omp_get_max_threads());
256 
257  return target_end;
258  }
259 } //namespace __gnu_parallel
260 
261 #endif /* _GLIBCXX_PARALLEL_MERGE_H */
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:44
OutputIterator merge_advance_movc(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Definition: merge.h:106
GNU parallel code for public use.
RandomAccessIterator3 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Splitter splitter, _DifferenceTp length, Comparator comp, thread_index_t num_threads)
Parallel multi-way merge routine.
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Definition: merge.h:174
RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition: merge.h:198
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
OutputIterator merge_advance_usual(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Definition: merge.h:57
void multiway_merge_exact_splitting(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
Exact splitting for parallel multiway-merge routine.