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 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 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 205 std::iterator_traits<RandomAccessIterator1>:: 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 233 std::iterator_traits<RandomAccessIterator1>:: 234 difference_type max_length, Comparator comp) 235 { 236 typedef typename 237 std::iterator_traits<RandomAccessIterator1>::value_type value_type; 238 typedef typename std::iterator_traits<RandomAccessIterator1>:: 239 difference_type difference_type1 /* == difference_type2 */; 240 typedef typename std::iterator_traits<RandomAccessIterator3>:: 241 difference_type difference_type3; 242 typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1> 243 iterator_pair; 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, 252 multiway_merge_exact_splitting 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 */ 262
