Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/parallel/algobase.h
1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2025 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 #include <parallel/search.h> 45 46 namespace std _GLIBCXX_VISIBILITY(default) 47 { 48 namespace __parallel 49 { 50 // NB: equal and lexicographical_compare require mismatch. 51 52 // Sequential fallback 53 template<typename _IIter1, typename _IIter2> 54 inline pair<_IIter1, _IIter2> 55 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 56 __gnu_parallel::sequential_tag) 57 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); } 58 59 // Sequential fallback 60 template<typename _IIter1, typename _IIter2, typename _Predicate> 61 inline pair<_IIter1, _IIter2> 62 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 63 _Predicate __pred, __gnu_parallel::sequential_tag) 64 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 65 66 // Sequential fallback for input iterator case 67 template<typename _IIter1, typename _IIter2, 68 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 69 inline pair<_IIter1, _IIter2> 70 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 71 _Predicate __pred, _IteratorTag1, _IteratorTag2) 72 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 73 74 // Parallel mismatch for random access iterators 75 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 76 pair<_RAIter1, _RAIter2> 77 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 78 _RAIter2 __begin2, _Predicate __pred, 79 random_access_iterator_tag, random_access_iterator_tag) 80 { 81 if (_GLIBCXX_PARALLEL_CONDITION(true)) 82 { 83 _RAIter1 __res = 84 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 85 __gnu_parallel:: 86 __mismatch_selector()).first; 87 return std::make_pair(__res , __begin2 + (__res - __begin1)); 88 } 89 else 90 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); 91 } 92 93 // Public interface 94 template<typename _IIter1, typename _IIter2> 95 inline pair<_IIter1, _IIter2> 96 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 97 { 98 typedef __gnu_parallel::_EqualTo< 99 typename std::iterator_traits<_IIter1>::value_type, 100 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 101 102 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 103 std::__iterator_category(__begin1), 104 std::__iterator_category(__begin2)); 105 } 106 107 // Public interface 108 template<typename _IIter1, typename _IIter2, typename _Predicate> 109 inline pair<_IIter1, _IIter2> 110 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 111 _Predicate __pred) 112 { 113 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 114 std::__iterator_category(__begin1), 115 std::__iterator_category(__begin2)); 116 } 117 118 #if __cplusplus > 201103L 119 // Sequential fallback. 120 template<typename _InputIterator1, typename _InputIterator2> 121 inline pair<_InputIterator1, _InputIterator2> 122 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 123 _InputIterator2 __first2, _InputIterator2 __last2, 124 __gnu_parallel::sequential_tag) 125 { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); } 126 127 // Sequential fallback. 128 template<typename _InputIterator1, typename _InputIterator2, 129 typename _BinaryPredicate> 130 inline pair<_InputIterator1, _InputIterator2> 131 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 132 _InputIterator2 __first2, _InputIterator2 __last2, 133 _BinaryPredicate __binary_pred, 134 __gnu_parallel::sequential_tag) 135 { 136 return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2, 137 __binary_pred); 138 } 139 140 // Sequential fallback for input iterator case 141 template<typename _IIter1, typename _IIter2, 142 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 143 inline pair<_IIter1, _IIter2> 144 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, 145 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 146 _IteratorTag1, _IteratorTag2) 147 { 148 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 149 __begin2, __end2, __pred); 150 } 151 152 // Parallel mismatch for random access iterators 153 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 154 pair<_RAIter1, _RAIter2> 155 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 156 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 157 random_access_iterator_tag, random_access_iterator_tag) 158 { 159 if (_GLIBCXX_PARALLEL_CONDITION(true)) 160 { 161 if ((__end2 - __begin2) < (__end1 - __begin1)) 162 __end1 = __begin1 + (__end2 - __begin2); 163 164 _RAIter1 __res = 165 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 166 __gnu_parallel:: 167 __mismatch_selector()).first; 168 return std::make_pair(__res , __begin2 + (__res - __begin1)); 169 } 170 else 171 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, 172 __begin2, __end2, __pred); 173 } 174 175 template<typename _IIter1, typename _IIter2> 176 inline pair<_IIter1, _IIter2> 177 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 178 { 179 typedef __gnu_parallel::_EqualTo< 180 typename std::iterator_traits<_IIter1>::value_type, 181 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 182 183 return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 184 std::__iterator_category(__begin1), 185 std::__iterator_category(__begin2)); 186 } 187 188 template<typename _InputIterator1, typename _InputIterator2, 189 typename _BinaryPredicate> 190 inline pair<_InputIterator1, _InputIterator2> 191 mismatch(_InputIterator1 __begin1, _InputIterator1 __end1, 192 _InputIterator2 __begin2, _InputIterator2 __end2, 193 _BinaryPredicate __binary_pred) 194 { 195 return __mismatch_switch(__begin1, __end1, __begin2, __end2, 196 __binary_pred, 197 std::__iterator_category(__begin1), 198 std::__iterator_category(__begin2)); 199 } 200 #endif 201 202 // Sequential fallback 203 template<typename _IIter1, typename _IIter2> 204 inline bool 205 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 206 __gnu_parallel::sequential_tag) 207 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); } 208 209 // Sequential fallback 210 template<typename _IIter1, typename _IIter2, typename _Predicate> 211 inline bool 212 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 213 _Predicate __pred, __gnu_parallel::sequential_tag) 214 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); } 215 216 // Public interface 217 template<typename _IIter1, typename _IIter2> 218 _GLIBCXX20_CONSTEXPR 219 inline bool 220 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 221 { 222 #if __cplusplus > 201703L 223 if (std::is_constant_evaluated()) 224 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); 225 #endif 226 227 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 228 == __end1; 229 } 230 231 // Public interface 232 template<typename _IIter1, typename _IIter2, typename _Predicate> 233 _GLIBCXX20_CONSTEXPR 234 inline bool 235 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 236 _Predicate __pred) 237 { 238 #if __cplusplus > 201703L 239 if (std::is_constant_evaluated()) 240 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); 241 #endif 242 243 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 244 == __end1; 245 } 246 247 #if __cplusplus > 201103L 248 // Sequential fallback 249 template<typename _IIter1, typename _IIter2> 250 inline bool 251 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 252 __gnu_parallel::sequential_tag) 253 { 254 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2); 255 } 256 257 // Sequential fallback 258 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 259 inline bool 260 equal(_IIter1 __begin1, _IIter1 __end1, 261 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred, 262 __gnu_parallel::sequential_tag) 263 { 264 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2, 265 __binary_pred); 266 } 267 268 // Sequential fallback for input iterator case 269 template<typename _IIter1, typename _IIter2, 270 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 271 inline bool 272 __equal_switch(_IIter1 __begin1, _IIter1 __end1, 273 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred, 274 _IteratorTag1, _IteratorTag2) 275 { 276 return _GLIBCXX_STD_A::equal(__begin1, __end1, 277 __begin2, __end2, __pred); 278 } 279 280 // Parallel equal for random access iterators 281 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 282 inline bool 283 __equal_switch(_RAIter1 __begin1, _RAIter1 __end1, 284 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 285 random_access_iterator_tag, random_access_iterator_tag) 286 { 287 if (_GLIBCXX_PARALLEL_CONDITION(true)) 288 { 289 if (std::distance(__begin1, __end1) 290 != std::distance(__begin2, __end2)) 291 return false; 292 293 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2, 294 __pred).first == __end1; 295 } 296 else 297 return _GLIBCXX_STD_A::equal(__begin1, __end1, 298 __begin2, __end2, __pred); 299 } 300 301 template<typename _IIter1, typename _IIter2> 302 _GLIBCXX20_CONSTEXPR 303 inline bool 304 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2) 305 { 306 #if __cplusplus > 201703L 307 if (std::is_constant_evaluated()) 308 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2); 309 #endif 310 311 typedef __gnu_parallel::_EqualTo< 312 typename std::iterator_traits<_IIter1>::value_type, 313 typename std::iterator_traits<_IIter2>::value_type> _EqualTo; 314 315 return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(), 316 std::__iterator_category(__begin1), 317 std::__iterator_category(__begin2)); 318 } 319 320 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 321 _GLIBCXX20_CONSTEXPR 322 inline bool 323 equal(_IIter1 __begin1, _IIter1 __end1, 324 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred) 325 { 326 #if __cplusplus > 201703L 327 if (std::is_constant_evaluated()) 328 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2, 329 __binary_pred); 330 #endif 331 332 return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred, 333 std::__iterator_category(__begin1), 334 std::__iterator_category(__begin2)); 335 } 336 #endif // C++14 337 338 // Sequential fallback 339 template<typename _IIter1, typename _IIter2> 340 inline bool 341 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 342 _IIter2 __begin2, _IIter2 __end2, 343 __gnu_parallel::sequential_tag) 344 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 345 __begin2, __end2); } 346 347 // Sequential fallback 348 template<typename _IIter1, typename _IIter2, typename _Predicate> 349 inline bool 350 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 351 _IIter2 __begin2, _IIter2 __end2, 352 _Predicate __pred, __gnu_parallel::sequential_tag) 353 { return _GLIBCXX_STD_A::lexicographical_compare( 354 __begin1, __end1, __begin2, __end2, __pred); } 355 356 // Sequential fallback for input iterator case 357 template<typename _IIter1, typename _IIter2, 358 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 359 inline bool 360 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 361 _IIter2 __begin2, _IIter2 __end2, 362 _Predicate __pred, 363 _IteratorTag1, _IteratorTag2) 364 { return _GLIBCXX_STD_A::lexicographical_compare( 365 __begin1, __end1, __begin2, __end2, __pred); } 366 367 // Parallel lexicographical_compare for random access iterators 368 // Limitation: Both valuetypes must be the same 369 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 370 bool 371 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 372 _RAIter2 __begin2, _RAIter2 __end2, 373 _Predicate __pred, 374 random_access_iterator_tag, 375 random_access_iterator_tag) 376 { 377 if (_GLIBCXX_PARALLEL_CONDITION(true)) 378 { 379 typedef iterator_traits<_RAIter1> _TraitsType1; 380 typedef typename _TraitsType1::value_type _ValueType1; 381 382 typedef iterator_traits<_RAIter2> _TraitsType2; 383 typedef typename _TraitsType2::value_type _ValueType2; 384 385 typedef __gnu_parallel:: 386 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 387 _EqualFromLessCompare; 388 389 // Longer sequence in first place. 390 if ((__end1 - __begin1) < (__end2 - __begin2)) 391 { 392 typedef pair<_RAIter1, _RAIter2> _SpotType; 393 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 394 _EqualFromLessCompare(__pred), 395 random_access_iterator_tag(), 396 random_access_iterator_tag()); 397 398 return (__mm.first == __end1) 399 || bool(__pred(*__mm.first, *__mm.second)); 400 } 401 else 402 { 403 typedef pair<_RAIter2, _RAIter1> _SpotType; 404 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 405 _EqualFromLessCompare(__pred), 406 random_access_iterator_tag(), 407 random_access_iterator_tag()); 408 409 return (__mm.first != __end2) 410 && bool(__pred(*__mm.second, *__mm.first)); 411 } 412 } 413 else 414 return _GLIBCXX_STD_A::lexicographical_compare( 415 __begin1, __end1, __begin2, __end2, __pred); 416 } 417 418 // Public interface 419 template<typename _IIter1, typename _IIter2> 420 _GLIBCXX20_CONSTEXPR 421 inline bool 422 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 423 _IIter2 __begin2, _IIter2 __end2) 424 { 425 #if __cplusplus > 201703L 426 if (std::is_constant_evaluated()) 427 return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 428 __begin2, __end2); 429 #endif 430 431 typedef iterator_traits<_IIter1> _TraitsType1; 432 typedef typename _TraitsType1::value_type _ValueType1; 433 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 434 435 typedef iterator_traits<_IIter2> _TraitsType2; 436 typedef typename _TraitsType2::value_type _ValueType2; 437 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 438 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 439 440 return __lexicographical_compare_switch( 441 __begin1, __end1, __begin2, __end2, _LessType(), 442 _IteratorCategory1(), _IteratorCategory2()); 443 } 444 445 // Public interface 446 template<typename _IIter1, typename _IIter2, typename _Predicate> 447 _GLIBCXX20_CONSTEXPR 448 inline bool 449 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 450 _IIter2 __begin2, _IIter2 __end2, 451 _Predicate __pred) 452 { 453 #if __cplusplus > 201703L 454 if (std::is_constant_evaluated()) 455 return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 456 __begin2, __end2, 457 __pred); 458 #endif 459 460 typedef iterator_traits<_IIter1> _TraitsType1; 461 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 462 463 typedef iterator_traits<_IIter2> _TraitsType2; 464 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 465 466 return __lexicographical_compare_switch( 467 __begin1, __end1, __begin2, __end2, __pred, 468 _IteratorCategory1(), _IteratorCategory2()); 469 } 470 471 #if __cpp_lib_three_way_comparison 472 using _GLIBCXX_STD_A::lexicographical_compare_three_way; 473 #endif 474 475 // Public interface. 476 template<typename _FIterator1, typename _FIterator2, 477 typename _BinaryPredicate> 478 inline _FIterator1 479 search(_FIterator1 __begin1, _FIterator1 __end1, 480 _FIterator2 __begin2, _FIterator2 __end2, 481 _BinaryPredicate __pred, __gnu_parallel::sequential_tag) 482 { return _GLIBCXX_STD_A::search( 483 __begin1, __end1, __begin2, __end2, __pred); } 484 485 // Parallel algorithm for random access iterator. 486 template<typename _RAIter1, typename _RAIter2, 487 typename _BinaryPredicate> 488 _RAIter1 489 __search_switch(_RAIter1 __begin1, _RAIter1 __end1, 490 _RAIter2 __begin2, _RAIter2 __end2, 491 _BinaryPredicate __pred, 492 random_access_iterator_tag, random_access_iterator_tag) 493 { 494 if (_GLIBCXX_PARALLEL_CONDITION( 495 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 496 >= __gnu_parallel::_Settings::get().search_minimal_n)) 497 return __gnu_parallel::__search_template(__begin1, __end1, 498 __begin2, __end2, __pred); 499 else 500 return search(__begin1, __end1, __begin2, __end2, __pred, 501 __gnu_parallel::sequential_tag()); 502 } 503 504 // Sequential fallback for input iterator case 505 template<typename _FIterator1, typename _FIterator2, 506 typename _BinaryPredicate, typename _IteratorTag1, 507 typename _IteratorTag2> 508 inline _FIterator1 509 __search_switch(_FIterator1 __begin1, _FIterator1 __end1, 510 _FIterator2 __begin2, _FIterator2 __end2, 511 _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) 512 { return search(__begin1, __end1, __begin2, __end2, __pred, 513 __gnu_parallel::sequential_tag()); } 514 515 // Public interface 516 template<typename _FIterator1, typename _FIterator2, 517 typename _BinaryPredicate> 518 _GLIBCXX20_CONSTEXPR 519 inline _FIterator1 520 search(_FIterator1 __begin1, _FIterator1 __end1, 521 _FIterator2 __begin2, _FIterator2 __end2, 522 _BinaryPredicate __pred) 523 { 524 #if __cplusplus > 201703L 525 if (std::is_constant_evaluated()) 526 return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2, 527 std::move(__pred)); 528 #endif 529 return __search_switch(__begin1, __end1, __begin2, __end2, __pred, 530 std::__iterator_category(__begin1), 531 std::__iterator_category(__begin2)); 532 } 533 } // end namespace __parallel 534 } // end namespace std 535 536 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
