1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2016 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 __merge_advance_usual(_RAIter1 & __begin1,_RAIter1 __end1,_RAIter2 & __begin2,_RAIter2 __end2,_OutputIterator __target,_DifferenceTp __max_length,_Compare __comp)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 __merge_advance_movc(_RAIter1 & __begin1,_RAIter1 __end1,_RAIter2 & __begin2,_RAIter2 __end2,_OutputIterator __target,_DifferenceTp __max_length,_Compare __comp)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 __merge_advance(_RAIter1 & __begin1,_RAIter1 __end1,_RAIter2 & __begin2,_RAIter2 __end2,_OutputIterator __target,_DifferenceTp __max_length,_Compare __comp)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 __parallel_merge_advance(_RAIter1 & __begin1,_RAIter1 __end1,_RAIter2 & __begin2,_RAIter2 __end2,_RAIter3 __target,typename std::iterator_traits<_RAIter1>::difference_type __max_length,_Compare __comp)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 __parallel_merge_advance(_RAIter1 & __begin1,_RAIter1 __end1,_RAIter1 & __begin2,_RAIter1 __end2,_RAIter3 __target,typename std::iterator_traits<_RAIter1>::difference_type __max_length,_Compare __comp)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 */ 252