1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2018 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/algobase.h 26 * @brief Parallel STL function calls corresponding to the 27 * stl_algobase.h header. The functions defined here mainly do case 28 * switches and call the actual parallelized versions in other files. 29 * Inlining policy: Functions that basically only contain one 30 * function call, are declared inline. 31 * This file is a GNU parallel extension to the Standard C++ Library. 32 */ 33 34 // Written by Johannes Singler and Felix Putze. 35 36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H 37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1 38 39 #include <bits/stl_algobase.h> 40 #include <parallel/base.h> 41 #include <parallel/algorithmfwd.h> 42 #include <parallel/find.h> 43 #include <parallel/find_selectors.h> 44 45 namespace std _GLIBCXX_VISIBILITY(default) 46 { 47 namespace __parallel 48 { 49 // NB: equal and lexicographical_compare require mismatch. 50 51 // Sequential fallback 52 template<typename _IIter1, typename _IIter2> 53 inline pair<_IIter1, _IIter2> 54 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 55 __gnu_parallel::sequential_tag) 56 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); } 57 58 // Sequential fallback 59 template<typename _IIter1, typename _IIter2, typename _Predicate> 60 inline pair<_IIter1, _IIter2> 61 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 62 _Predicate __pred, __gnu_parallel::sequential_tag) 63 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 64 65 // Sequential fallback for input iterator case 66 template<typename _IIter1, typename _IIter2, 67 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 68 inline pair<_IIter1, _IIter2> 69 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 70 _Predicate __pred, _IteratorTag1, _IteratorTag2) 71 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 72 73 // Parallel mismatch for random access iterators 74 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 75 pair<_RAIter1, _RAIter2> 76 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 77 _RAIter2 __begin2, _Predicate __pred, 78 random_access_iterator_tag, random_access_iterator_tag) 79 { 80 if (_GLIBCXX_PARALLEL_CONDITION(true)) 81 { 82 _RAIter1 __res = 83 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 84 __gnu_parallel:: 85 __mismatch_selector()).first; 86 return make_pair(__res , __begin2 + (__res - __begin1)); 87 } 88 else 89 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); 90 } 91 92 // Public interface 93 template<typename _IIter1, typename _IIter2> 94 inline pair<_IIter1, _IIter2> 95 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 96 { 97 typedef __gnu_parallel::_EqualTo< 98 typename std::iterator_traits<_IIter1>::value_type, 99 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 100 101 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 102 std::__iterator_category(__begin1), 103 std::__iterator_category(__begin2)); 104 } 105 106 // Public interface 107 template<typename _IIter1, typename _IIter2, typename _Predicate> 108 inline pair<_IIter1, _IIter2> 109 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 110 _Predicate __pred) 111 { 112 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 113 std::__iterator_category(__begin1), 114 std::__iterator_category(__begin2)); 115 } 116 117 #if __cplusplus > 201103L 118 // Sequential fallback. 119 template<typename _InputIterator1, typename _InputIterator2> 120 inline pair<_InputIterator1, _InputIterator2> 121 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 122 _InputIterator2 __first2, _InputIterator2 __last2, 123 __gnu_parallel::sequential_tag) 124 { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); } 125 126 // Sequential fallback. 127 template<typename _InputIterator1, typename _InputIterator2, 128 typename _BinaryPredicate> 129 inline pair<_InputIterator1, _InputIterator2> 130 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 131 _InputIterator2 __first2, _InputIterator2 __last2, 132 _BinaryPredicate __binary_pred, 133 __gnu_parallel::sequential_tag) 134 { 135 return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2, 136 __binary_pred); 137 } 138 139 // Sequential fallback for input iterator case 140 template<typename _IIter1, typename _IIter2, 141 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 142 inline pair<_IIter1, _IIter2> 143 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, 144 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 145 _IteratorTag1, _IteratorTag2) 146 { 147 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 148 __begin2, __end2, __pred); 149 } 150 151 // Parallel mismatch for random access iterators 152 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 153 pair<_RAIter1, _RAIter2> 154 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 155 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 156 random_access_iterator_tag, random_access_iterator_tag) 157 { 158 if (_GLIBCXX_PARALLEL_CONDITION(true)) 159 { 160 if ((__end2 - __begin2) < (__end1 - __begin1)) 161 __end1 = __begin1 + (__end2 - __begin2); 162 163 _RAIter1 __res = 164 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 165 __gnu_parallel:: 166 __mismatch_selector()).first; 167 return make_pair(__res , __begin2 + (__res - __begin1)); 168 } 169 else 170 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 171 __begin2, __end2, __pred); 172 } 173 174 template<typename _IIter1, typename _IIter2> 175 inline pair<_IIter1, _IIter2> 176 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 177 { 178 typedef __gnu_parallel::_EqualTo< 179 typename std::iterator_traits<_IIter1>::value_type, 180 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 181 182 return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 183 std::__iterator_category(__begin1), 184 std::__iterator_category(__begin2)); 185 } 186 187 template<typename _InputIterator1, typename _InputIterator2, 188 typename _BinaryPredicate> 189 inline pair<_InputIterator1, _InputIterator2> 190 mismatch(_InputIterator1 __begin1, _InputIterator1 __end1, 191 _InputIterator2 __begin2, _InputIterator2 __end2, 192 _BinaryPredicate __binary_pred) 193 { 194 return __mismatch_switch(__begin1, __end1, __begin2, __end2, 195 __binary_pred, 196 std::__iterator_category(__begin1), 197 std::__iterator_category(__begin2)); 198 } 199 #endif 200 201 // Sequential fallback 202 template<typename _IIter1, typename _IIter2> 203 inline bool 204 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 205 __gnu_parallel::sequential_tag) 206 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); } 207 208 // Sequential fallback 209 template<typename _IIter1, typename _IIter2, typename _Predicate> 210 inline bool 211 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 212 _Predicate __pred, __gnu_parallel::sequential_tag) 213 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); } 214 215 // Public interface 216 template<typename _IIter1, typename _IIter2> 217 inline bool 218 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 219 { 220 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 221 == __end1; 222 } 223 224 // Public interface 225 template<typename _IIter1, typename _IIter2, typename _Predicate> 226 inline bool 227 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 228 _Predicate __pred) 229 { 230 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 231 == __end1; 232 } 233 234 #if __cplusplus > 201103L 235 // Sequential fallback 236 template<typename _IIter1, typename _IIter2> 237 inline bool 238 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 239 __gnu_parallel::sequential_tag) 240 { 241 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2); 242 } 243 244 // Sequential fallback 245 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 246 inline bool 247 equal(_IIter1 __begin1, _IIter1 __end1, 248 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred, 249 __gnu_parallel::sequential_tag) 250 { 251 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2, 252 __binary_pred); 253 } 254 255 // Sequential fallback for input iterator case 256 template<typename _IIter1, typename _IIter2, 257 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 258 inline bool 259 __equal_switch(_IIter1 __begin1, _IIter1 __end1, 260 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 261 _IteratorTag1, _IteratorTag2) 262 { 263 return _GLIBCXX_STD_A::equal(__begin1, __end1, 264 __begin2, __end2, __pred); 265 } 266 267 // Parallel equal for random access iterators 268 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 269 inline bool 270 __equal_switch(_RAIter1 __begin1, _RAIter1 __end1, 271 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 272 random_access_iterator_tag, random_access_iterator_tag) 273 { 274 if (_GLIBCXX_PARALLEL_CONDITION(true)) 275 { 276 if (std::distance(__begin1, __end1) 277 != std::distance(__begin2, __end2)) 278 return false; 279 280 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2, 281 __pred).first == __end1; 282 } 283 else 284 return _GLIBCXX_STD_A::equal(__begin1, __end1, 285 __begin2, __end2, __pred); 286 } 287 288 template<typename _IIter1, typename _IIter2> 289 inline bool 290 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 291 { 292 typedef __gnu_parallel::_EqualTo< 293 typename std::iterator_traits<_IIter1>::value_type, 294 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 295 296 return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 297 std::__iterator_category(__begin1), 298 std::__iterator_category(__begin2)); 299 } 300 301 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 302 inline bool 303 equal(_IIter1 __begin1, _IIter1 __end1, 304 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred) 305 { 306 return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred, 307 std::__iterator_category(__begin1), 308 std::__iterator_category(__begin2)); 309 } 310 #endif 311 312 // Sequential fallback 313 template<typename _IIter1, typename _IIter2> 314 inline bool 315 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 316 _IIter2 __begin2, _IIter2 __end2, 317 __gnu_parallel::sequential_tag) 318 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 319 __begin2, __end2); } 320 321 // Sequential fallback 322 template<typename _IIter1, typename _IIter2, typename _Predicate> 323 inline bool 324 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 325 _IIter2 __begin2, _IIter2 __end2, 326 _Predicate __pred, __gnu_parallel::sequential_tag) 327 { return _GLIBCXX_STD_A::lexicographical_compare( 328 __begin1, __end1, __begin2, __end2, __pred); } 329 330 // Sequential fallback for input iterator case 331 template<typename _IIter1, typename _IIter2, 332 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 333 inline bool 334 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 335 _IIter2 __begin2, _IIter2 __end2, 336 _Predicate __pred, 337 _IteratorTag1, _IteratorTag2) 338 { return _GLIBCXX_STD_A::lexicographical_compare( 339 __begin1, __end1, __begin2, __end2, __pred); } 340 341 // Parallel lexicographical_compare for random access iterators 342 // Limitation: Both valuetypes must be the same 343 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 344 bool 345 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 346 _RAIter2 __begin2, _RAIter2 __end2, 347 _Predicate __pred, 348 random_access_iterator_tag, 349 random_access_iterator_tag) 350 { 351 if (_GLIBCXX_PARALLEL_CONDITION(true)) 352 { 353 typedef iterator_traits<_RAIter1> _TraitsType1; 354 typedef typename _TraitsType1::value_type _ValueType1; 355 356 typedef iterator_traits<_RAIter2> _TraitsType2; 357 typedef typename _TraitsType2::value_type _ValueType2; 358 359 typedef __gnu_parallel:: 360 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 361 _EqualFromLessCompare; 362 363 // Longer sequence in first place. 364 if ((__end1 - __begin1) < (__end2 - __begin2)) 365 { 366 typedef pair<_RAIter1, _RAIter2> _SpotType; 367 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 368 _EqualFromLessCompare(__pred), 369 random_access_iterator_tag(), 370 random_access_iterator_tag()); 371 372 return (__mm.first == __end1) 373 || bool(__pred(*__mm.first, *__mm.second)); 374 } 375 else 376 { 377 typedef pair<_RAIter2, _RAIter1> _SpotType; 378 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 379 _EqualFromLessCompare(__pred), 380 random_access_iterator_tag(), 381 random_access_iterator_tag()); 382 383 return (__mm.first != __end2) 384 && bool(__pred(*__mm.second, *__mm.first)); 385 } 386 } 387 else 388 return _GLIBCXX_STD_A::lexicographical_compare( 389 __begin1, __end1, __begin2, __end2, __pred); 390 } 391 392 // Public interface 393 template<typename _IIter1, typename _IIter2> 394 inline bool 395 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 396 _IIter2 __begin2, _IIter2 __end2) 397 { 398 typedef iterator_traits<_IIter1> _TraitsType1; 399 typedef typename _TraitsType1::value_type _ValueType1; 400 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 401 402 typedef iterator_traits<_IIter2> _TraitsType2; 403 typedef typename _TraitsType2::value_type _ValueType2; 404 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 405 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 406 407 return __lexicographical_compare_switch( 408 __begin1, __end1, __begin2, __end2, _LessType(), 409 _IteratorCategory1(), _IteratorCategory2()); 410 } 411 412 // Public interface 413 template<typename _IIter1, typename _IIter2, typename _Predicate> 414 inline bool 415 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 416 _IIter2 __begin2, _IIter2 __end2, 417 _Predicate __pred) 418 { 419 typedef iterator_traits<_IIter1> _TraitsType1; 420 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 421 422 typedef iterator_traits<_IIter2> _TraitsType2; 423 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 424 425 return __lexicographical_compare_switch( 426 __begin1, __end1, __begin2, __end2, __pred, 427 _IteratorCategory1(), _IteratorCategory2()); 428 } 429 } // end namespace 430 } // end namespace 431 432 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ 433