libstdc++-v3/include/parallel/algobase.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2023 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 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 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     inline _FIterator1
 519     search(_FIterator1 __begin1, _FIterator1 __end1,
 520            _FIterator2 __begin2, _FIterator2 __end2,
 521            _BinaryPredicate  __pred)
 522     {
 523       return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
 524                              std::__iterator_category(__begin1),
 525                              std::__iterator_category(__begin2));
 526     }
 527 } // end namespace __parallel
 528 } // end namespace std
 529
 530 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */