libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007-2015 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/algobase.h 00026 * @brief Parallel STL function calls corresponding to the 00027 * stl_algobase.h header. The functions defined here mainly do case 00028 * switches and call the actual parallelized versions in other files. 00029 * Inlining policy: Functions that basically only contain one 00030 * function call, are declared inline. 00031 * This file is a GNU parallel extension to the Standard C++ Library. 00032 */ 00033 00034 // Written by Johannes Singler and Felix Putze. 00035 00036 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H 00037 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1 00038 00039 #include <bits/stl_algobase.h> 00040 #include <parallel/base.h> 00041 #include <parallel/algorithmfwd.h> 00042 #include <parallel/find.h> 00043 #include <parallel/find_selectors.h> 00044 00045 namespace std _GLIBCXX_VISIBILITY(default) 00046 { 00047 namespace __parallel 00048 { 00049 // NB: equal and lexicographical_compare require mismatch. 00050 00051 // Sequential fallback 00052 template<typename _IIter1, typename _IIter2> 00053 inline pair<_IIter1, _IIter2> 00054 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00055 __gnu_parallel::sequential_tag) 00056 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); } 00057 00058 // Sequential fallback 00059 template<typename _IIter1, typename _IIter2, typename _Predicate> 00060 inline pair<_IIter1, _IIter2> 00061 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00062 _Predicate __pred, __gnu_parallel::sequential_tag) 00063 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 00064 00065 // Sequential fallback for input iterator case 00066 template<typename _IIter1, typename _IIter2, 00067 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00068 inline pair<_IIter1, _IIter2> 00069 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00070 _Predicate __pred, _IteratorTag1, _IteratorTag2) 00071 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 00072 00073 // Parallel mismatch for random access iterators 00074 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00075 pair<_RAIter1, _RAIter2> 00076 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 00077 _RAIter2 __begin2, _Predicate __pred, 00078 random_access_iterator_tag, random_access_iterator_tag) 00079 { 00080 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00081 { 00082 _RAIter1 __res = 00083 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 00084 __gnu_parallel:: 00085 __mismatch_selector()).first; 00086 return make_pair(__res , __begin2 + (__res - __begin1)); 00087 } 00088 else 00089 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); 00090 } 00091 00092 // Public interface 00093 template<typename _IIter1, typename _IIter2> 00094 inline pair<_IIter1, _IIter2> 00095 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 00096 { 00097 typedef __gnu_parallel::_EqualTo< 00098 typename std::iterator_traits<_IIter1>::value_type, 00099 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 00100 00101 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 00102 std::__iterator_category(__begin1), 00103 std::__iterator_category(__begin2)); 00104 } 00105 00106 // Public interface 00107 template<typename _IIter1, typename _IIter2, typename _Predicate> 00108 inline pair<_IIter1, _IIter2> 00109 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00110 _Predicate __pred) 00111 { 00112 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 00113 std::__iterator_category(__begin1), 00114 std::__iterator_category(__begin2)); 00115 } 00116 00117 #if __cplusplus > 201103L 00118 // Sequential fallback. 00119 template<typename _InputIterator1, typename _InputIterator2> 00120 inline pair<_InputIterator1, _InputIterator2> 00121 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 00122 _InputIterator2 __first2, _InputIterator2 __last2, 00123 __gnu_parallel::sequential_tag) 00124 { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); } 00125 00126 // Sequential fallback. 00127 template<typename _InputIterator1, typename _InputIterator2, 00128 typename _BinaryPredicate> 00129 inline pair<_InputIterator1, _InputIterator2> 00130 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 00131 _InputIterator2 __first2, _InputIterator2 __last2, 00132 _BinaryPredicate __binary_pred, 00133 __gnu_parallel::sequential_tag) 00134 { 00135 return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2, 00136 __binary_pred); 00137 } 00138 00139 // Sequential fallback for input iterator case 00140 template<typename _IIter1, typename _IIter2, 00141 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00142 inline pair<_IIter1, _IIter2> 00143 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, 00144 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 00145 _IteratorTag1, _IteratorTag2) 00146 { 00147 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 00148 __begin2, __end2, __pred); 00149 } 00150 00151 // Parallel mismatch for random access iterators 00152 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00153 pair<_RAIter1, _RAIter2> 00154 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 00155 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 00156 random_access_iterator_tag, random_access_iterator_tag) 00157 { 00158 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00159 { 00160 if ((__end2 - __begin2) < (__end1 - __begin1)) 00161 __end1 = __begin1 + (__end2 - __begin2); 00162 00163 _RAIter1 __res = 00164 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 00165 __gnu_parallel:: 00166 __mismatch_selector()).first; 00167 return make_pair(__res , __begin2 + (__res - __begin1)); 00168 } 00169 else 00170 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 00171 __begin2, __end2, __pred); 00172 } 00173 00174 template<typename _IIter1, typename _IIter2> 00175 inline pair<_IIter1, _IIter2> 00176 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 00177 { 00178 typedef __gnu_parallel::_EqualTo< 00179 typename std::iterator_traits<_IIter1>::value_type, 00180 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 00181 00182 return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 00183 std::__iterator_category(__begin1), 00184 std::__iterator_category(__begin2)); 00185 } 00186 00187 template<typename _InputIterator1, typename _InputIterator2, 00188 typename _BinaryPredicate> 00189 inline pair<_InputIterator1, _InputIterator2> 00190 mismatch(_InputIterator1 __begin1, _InputIterator1 __end1, 00191 _InputIterator2 __begin2, _InputIterator2 __end2, 00192 _BinaryPredicate __binary_pred) 00193 { 00194 return __mismatch_switch(__begin1, __end1, __begin2, __end2, 00195 __binary_pred, 00196 std::__iterator_category(__begin1), 00197 std::__iterator_category(__begin2)); 00198 } 00199 #endif 00200 00201 // Sequential fallback 00202 template<typename _IIter1, typename _IIter2> 00203 inline bool 00204 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00205 __gnu_parallel::sequential_tag) 00206 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); } 00207 00208 // Sequential fallback 00209 template<typename _IIter1, typename _IIter2, typename _Predicate> 00210 inline bool 00211 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00212 _Predicate __pred, __gnu_parallel::sequential_tag) 00213 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); } 00214 00215 // Public interface 00216 template<typename _IIter1, typename _IIter2> 00217 inline bool 00218 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 00219 { 00220 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 00221 == __end1; 00222 } 00223 00224 // Public interface 00225 template<typename _IIter1, typename _IIter2, typename _Predicate> 00226 inline bool 00227 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00228 _Predicate __pred) 00229 { 00230 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 00231 == __end1; 00232 } 00233 00234 #if __cplusplus > 201103L 00235 // Sequential fallback 00236 template<typename _IIter1, typename _IIter2> 00237 inline bool 00238 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 00239 __gnu_parallel::sequential_tag) 00240 { 00241 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2); 00242 } 00243 00244 // Sequential fallback 00245 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 00246 inline bool 00247 equal(_IIter1 __begin1, _IIter1 __end1, 00248 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred, 00249 __gnu_parallel::sequential_tag) 00250 { 00251 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2, 00252 __binary_pred); 00253 } 00254 00255 // Sequential fallback for input iterator case 00256 template<typename _IIter1, typename _IIter2, 00257 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00258 inline bool 00259 __equal_switch(_IIter1 __begin1, _IIter1 __end1, 00260 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 00261 _IteratorTag1, _IteratorTag2) 00262 { 00263 return _GLIBCXX_STD_A::equal(__begin1, __end1, 00264 __begin2, __end2, __pred); 00265 } 00266 00267 // Parallel equal for random access iterators 00268 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00269 inline bool 00270 __equal_switch(_RAIter1 __begin1, _RAIter1 __end1, 00271 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 00272 random_access_iterator_tag, random_access_iterator_tag) 00273 { 00274 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00275 { 00276 if (std::distance(__begin1, __end1) 00277 != std::distance(__begin2, __end2)) 00278 return false; 00279 00280 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2, 00281 __pred).first == __end1; 00282 } 00283 else 00284 return _GLIBCXX_STD_A::equal(__begin1, __end1, 00285 __begin2, __end2, __pred); 00286 } 00287 00288 template<typename _IIter1, typename _IIter2> 00289 inline bool 00290 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 00291 { 00292 typedef __gnu_parallel::_EqualTo< 00293 typename std::iterator_traits<_IIter1>::value_type, 00294 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 00295 00296 return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 00297 std::__iterator_category(__begin1), 00298 std::__iterator_category(__begin2)); 00299 } 00300 00301 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 00302 inline bool 00303 equal(_IIter1 __begin1, _IIter1 __end1, 00304 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred) 00305 { 00306 return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred, 00307 std::__iterator_category(__begin1), 00308 std::__iterator_category(__begin2)); 00309 } 00310 #endif 00311 00312 // Sequential fallback 00313 template<typename _IIter1, typename _IIter2> 00314 inline bool 00315 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00316 _IIter2 __begin2, _IIter2 __end2, 00317 __gnu_parallel::sequential_tag) 00318 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 00319 __begin2, __end2); } 00320 00321 // Sequential fallback 00322 template<typename _IIter1, typename _IIter2, typename _Predicate> 00323 inline bool 00324 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00325 _IIter2 __begin2, _IIter2 __end2, 00326 _Predicate __pred, __gnu_parallel::sequential_tag) 00327 { return _GLIBCXX_STD_A::lexicographical_compare( 00328 __begin1, __end1, __begin2, __end2, __pred); } 00329 00330 // Sequential fallback for input iterator case 00331 template<typename _IIter1, typename _IIter2, 00332 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00333 inline bool 00334 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 00335 _IIter2 __begin2, _IIter2 __end2, 00336 _Predicate __pred, 00337 _IteratorTag1, _IteratorTag2) 00338 { return _GLIBCXX_STD_A::lexicographical_compare( 00339 __begin1, __end1, __begin2, __end2, __pred); } 00340 00341 // Parallel lexicographical_compare for random access iterators 00342 // Limitation: Both valuetypes must be the same 00343 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00344 bool 00345 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 00346 _RAIter2 __begin2, _RAIter2 __end2, 00347 _Predicate __pred, 00348 random_access_iterator_tag, 00349 random_access_iterator_tag) 00350 { 00351 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00352 { 00353 typedef iterator_traits<_RAIter1> _TraitsType1; 00354 typedef typename _TraitsType1::value_type _ValueType1; 00355 00356 typedef iterator_traits<_RAIter2> _TraitsType2; 00357 typedef typename _TraitsType2::value_type _ValueType2; 00358 00359 typedef __gnu_parallel:: 00360 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 00361 _EqualFromLessCompare; 00362 00363 // Longer sequence in first place. 00364 if ((__end1 - __begin1) < (__end2 - __begin2)) 00365 { 00366 typedef pair<_RAIter1, _RAIter2> _SpotType; 00367 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 00368 _EqualFromLessCompare(__pred), 00369 random_access_iterator_tag(), 00370 random_access_iterator_tag()); 00371 00372 return (__mm.first == __end1) 00373 || bool(__pred(*__mm.first, *__mm.second)); 00374 } 00375 else 00376 { 00377 typedef pair<_RAIter2, _RAIter1> _SpotType; 00378 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 00379 _EqualFromLessCompare(__pred), 00380 random_access_iterator_tag(), 00381 random_access_iterator_tag()); 00382 00383 return (__mm.first != __end2) 00384 && bool(__pred(*__mm.second, *__mm.first)); 00385 } 00386 } 00387 else 00388 return _GLIBCXX_STD_A::lexicographical_compare( 00389 __begin1, __end1, __begin2, __end2, __pred); 00390 } 00391 00392 // Public interface 00393 template<typename _IIter1, typename _IIter2> 00394 inline bool 00395 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00396 _IIter2 __begin2, _IIter2 __end2) 00397 { 00398 typedef iterator_traits<_IIter1> _TraitsType1; 00399 typedef typename _TraitsType1::value_type _ValueType1; 00400 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00401 00402 typedef iterator_traits<_IIter2> _TraitsType2; 00403 typedef typename _TraitsType2::value_type _ValueType2; 00404 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00405 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 00406 00407 return __lexicographical_compare_switch( 00408 __begin1, __end1, __begin2, __end2, _LessType(), 00409 _IteratorCategory1(), _IteratorCategory2()); 00410 } 00411 00412 // Public interface 00413 template<typename _IIter1, typename _IIter2, typename _Predicate> 00414 inline bool 00415 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00416 _IIter2 __begin2, _IIter2 __end2, 00417 _Predicate __pred) 00418 { 00419 typedef iterator_traits<_IIter1> _TraitsType1; 00420 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00421 00422 typedef iterator_traits<_IIter2> _TraitsType2; 00423 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00424 00425 return __lexicographical_compare_switch( 00426 __begin1, __end1, __begin2, __end2, __pred, 00427 _IteratorCategory1(), _IteratorCategory2()); 00428 } 00429 } // end namespace 00430 } // end namespace 00431 00432 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */