libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/merge.h 00026 * @brief Parallel implementation of std::merge(). 00027 * This file is a GNU parallel extension to the Standard C++ Library. 00028 */ 00029 00030 // Written by Johannes Singler. 00031 00032 #ifndef _GLIBCXX_PARALLEL_MERGE_H 00033 #define _GLIBCXX_PARALLEL_MERGE_H 1 00034 00035 #include <parallel/basic_iterator.h> 00036 #include <bits/stl_algo.h> 00037 00038 namespace __gnu_parallel 00039 { 00040 /** @brief Merge routine being able to merge only the @c max_length 00041 * smallest elements. 00042 * 00043 * The @c begin iterators are advanced accordingly, they might not 00044 * reach @c end, in contrast to the usual variant. 00045 * @param begin1 Begin iterator of first sequence. 00046 * @param end1 End iterator of first sequence. 00047 * @param begin2 Begin iterator of second sequence. 00048 * @param end2 End iterator of second sequence. 00049 * @param target Target begin iterator. 00050 * @param max_length Maximum number of elements to merge. 00051 * @param comp Comparator. 00052 * @return Output end iterator. */ 00053 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00054 typename OutputIterator, typename _DifferenceTp, 00055 typename Comparator> 00056 OutputIterator 00057 merge_advance_usual(RandomAccessIterator1& begin1, 00058 RandomAccessIterator1 end1, 00059 RandomAccessIterator2& begin2, 00060 RandomAccessIterator2 end2, OutputIterator target, 00061 _DifferenceTp max_length, Comparator comp) 00062 { 00063 typedef _DifferenceTp difference_type; 00064 while (begin1 != end1 && begin2 != end2 && max_length > 0) 00065 { 00066 // array1[i1] < array0[i0] 00067 if (comp(*begin2, *begin1)) 00068 *target++ = *begin2++; 00069 else 00070 *target++ = *begin1++; 00071 --max_length; 00072 } 00073 00074 if (begin1 != end1) 00075 { 00076 target = std::copy(begin1, begin1 + max_length, target); 00077 begin1 += max_length; 00078 } 00079 else 00080 { 00081 target = std::copy(begin2, begin2 + max_length, target); 00082 begin2 += max_length; 00083 } 00084 return target; 00085 } 00086 00087 /** @brief Merge routine being able to merge only the @c max_length 00088 * smallest elements. 00089 * 00090 * The @c begin iterators are advanced accordingly, they might not 00091 * reach @c end, in contrast to the usual variant. 00092 * Specially designed code should allow the compiler to generate 00093 * conditional moves instead of branches. 00094 * @param begin1 Begin iterator of first sequence. 00095 * @param end1 End iterator of first sequence. 00096 * @param begin2 Begin iterator of second sequence. 00097 * @param end2 End iterator of second sequence. 00098 * @param target Target begin iterator. 00099 * @param max_length Maximum number of elements to merge. 00100 * @param comp Comparator. 00101 * @return Output end iterator. */ 00102 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00103 typename OutputIterator, typename _DifferenceTp, 00104 typename Comparator> 00105 OutputIterator 00106 merge_advance_movc(RandomAccessIterator1& begin1, 00107 RandomAccessIterator1 end1, 00108 RandomAccessIterator2& begin2, 00109 RandomAccessIterator2 end2, 00110 OutputIterator target, 00111 _DifferenceTp max_length, Comparator comp) 00112 { 00113 typedef _DifferenceTp difference_type; 00114 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00115 value_type1; 00116 typedef typename std::iterator_traits<RandomAccessIterator2>::value_type 00117 value_type2; 00118 00119 #if _GLIBCXX_ASSERTIONS 00120 _GLIBCXX_PARALLEL_ASSERT(max_length >= 0); 00121 #endif 00122 00123 while (begin1 != end1 && begin2 != end2 && max_length > 0) 00124 { 00125 RandomAccessIterator1 next1 = begin1 + 1; 00126 RandomAccessIterator2 next2 = begin2 + 1; 00127 value_type1 element1 = *begin1; 00128 value_type2 element2 = *begin2; 00129 00130 if (comp(element2, element1)) 00131 { 00132 element1 = element2; 00133 begin2 = next2; 00134 } 00135 else 00136 begin1 = next1; 00137 00138 *target = element1; 00139 00140 ++target; 00141 --max_length; 00142 } 00143 if (begin1 != end1) 00144 { 00145 target = std::copy(begin1, begin1 + max_length, target); 00146 begin1 += max_length; 00147 } 00148 else 00149 { 00150 target = std::copy(begin2, begin2 + max_length, target); 00151 begin2 += max_length; 00152 } 00153 return target; 00154 } 00155 00156 /** @brief Merge routine being able to merge only the @c max_length 00157 * smallest elements. 00158 * 00159 * The @c begin iterators are advanced accordingly, they might not 00160 * reach @c end, in contrast to the usual variant. 00161 * Static switch on whether to use the conditional-move variant. 00162 * @param begin1 Begin iterator of first sequence. 00163 * @param end1 End iterator of first sequence. 00164 * @param begin2 Begin iterator of second sequence. 00165 * @param end2 End iterator of second sequence. 00166 * @param target Target begin iterator. 00167 * @param max_length Maximum number of elements to merge. 00168 * @param comp Comparator. 00169 * @return Output end iterator. */ 00170 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00171 typename OutputIterator, typename _DifferenceTp, 00172 typename Comparator> 00173 inline OutputIterator 00174 merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, 00175 RandomAccessIterator2& begin2, RandomAccessIterator2 end2, 00176 OutputIterator target, _DifferenceTp max_length, 00177 Comparator comp) 00178 { 00179 _GLIBCXX_CALL(max_length) 00180 00181 return merge_advance_movc(begin1, end1, begin2, end2, target, 00182 max_length, comp); 00183 } 00184 00185 /** @brief Merge routine fallback to sequential in case the 00186 iterators of the two input sequences are of different type. 00187 * @param begin1 Begin iterator of first sequence. 00188 * @param end1 End iterator of first sequence. 00189 * @param begin2 Begin iterator of second sequence. 00190 * @param end2 End iterator of second sequence. 00191 * @param target Target begin iterator. 00192 * @param max_length Maximum number of elements to merge. 00193 * @param comp Comparator. 00194 * @return Output end iterator. */ 00195 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00196 typename RandomAccessIterator3, typename Comparator> 00197 inline RandomAccessIterator3 00198 parallel_merge_advance(RandomAccessIterator1& begin1, 00199 RandomAccessIterator1 end1, 00200 RandomAccessIterator2& begin2, 00201 // different iterators, parallel implementation 00202 // not available 00203 RandomAccessIterator2 end2, 00204 RandomAccessIterator3 target, typename 00205 std::iterator_traits<RandomAccessIterator1>:: 00206 difference_type max_length, Comparator comp) 00207 { return merge_advance(begin1, end1, begin2, end2, target, 00208 max_length, comp); } 00209 00210 /** @brief Parallel merge routine being able to merge only the @c 00211 * max_length smallest elements. 00212 * 00213 * The @c begin iterators are advanced accordingly, they might not 00214 * reach @c end, in contrast to the usual variant. 00215 * The functionality is projected onto parallel_multiway_merge. 00216 * @param begin1 Begin iterator of first sequence. 00217 * @param end1 End iterator of first sequence. 00218 * @param begin2 Begin iterator of second sequence. 00219 * @param end2 End iterator of second sequence. 00220 * @param target Target begin iterator. 00221 * @param max_length Maximum number of elements to merge. 00222 * @param comp Comparator. 00223 * @return Output end iterator. 00224 */ 00225 template<typename RandomAccessIterator1, typename RandomAccessIterator3, 00226 typename Comparator> 00227 inline RandomAccessIterator3 00228 parallel_merge_advance(RandomAccessIterator1& begin1, 00229 RandomAccessIterator1 end1, 00230 RandomAccessIterator1& begin2, 00231 RandomAccessIterator1 end2, 00232 RandomAccessIterator3 target, typename 00233 std::iterator_traits<RandomAccessIterator1>:: 00234 difference_type max_length, Comparator comp) 00235 { 00236 typedef typename 00237 std::iterator_traits<RandomAccessIterator1>::value_type value_type; 00238 typedef typename std::iterator_traits<RandomAccessIterator1>:: 00239 difference_type difference_type1 /* == difference_type2 */; 00240 typedef typename std::iterator_traits<RandomAccessIterator3>:: 00241 difference_type difference_type3; 00242 typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1> 00243 iterator_pair; 00244 00245 iterator_pair 00246 seqs[2] = { std::make_pair(begin1, end1), 00247 std::make_pair(begin2, end2) }; 00248 RandomAccessIterator3 00249 target_end = parallel_multiway_merge 00250 < /* stable = */ true, /* sentinels = */ false>( 00251 seqs, seqs + 2, target, 00252 multiway_merge_exact_splitting 00253 < /* stable = */ true, iterator_pair*, 00254 Comparator, difference_type1>, 00255 max_length, comp, omp_get_max_threads()); 00256 00257 return target_end; 00258 } 00259 } //namespace __gnu_parallel 00260 00261 #endif /* _GLIBCXX_PARALLEL_MERGE_H */