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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2021 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     _GLIBCXX20_CONSTEXPR
 218     inline bool
 219     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
 220     {
 221 #if __cplusplus > 201703L
 222       if (std::is_constant_evaluated())
 223         return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
 224 #endif
 225
 226       return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
 227               == __end1;
 228     }
 229
 230   // Public interface
 231   template<typename _IIter1, typename _IIter2, typename _Predicate>
 232     _GLIBCXX20_CONSTEXPR
 233     inline bool
 234     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 235           _Predicate __pred)
 236     {
 237 #if __cplusplus > 201703L
 238       if (std::is_constant_evaluated())
 239         return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
 240 #endif
 241
 242       return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
 243               == __end1;
 244     }
 245
 246 #if __cplusplus > 201103L
 247   // Sequential fallback
 248   template<typename _IIter1, typename _IIter2>
 249     inline bool
 250     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
 251           __gnu_parallel::sequential_tag)
 252     {
 253       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
 254     }
 255
 256   // Sequential fallback
 257   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
 258     inline bool
 259     equal(_IIter1 __begin1, _IIter1 __end1,
 260           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
 261           __gnu_parallel::sequential_tag)
 262     {
 263       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
 264                                    __binary_pred);
 265     }
 266
 267   // Sequential fallback for input iterator case
 268   template<typename _IIter1, typename _IIter2,
 269            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
 270     inline bool
 271     __equal_switch(_IIter1 __begin1, _IIter1 __end1,
 272                    _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
 273                    _IteratorTag1, _IteratorTag2)
 274     {
 275       return _GLIBCXX_STD_A::equal(__begin1, __end1,
 276                                    __begin2, __end2, __pred);
 277     }
 278
 279   // Parallel equal for random access iterators
 280   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
 281     inline bool
 282     __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
 283                    _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
 284                    random_access_iterator_tag, random_access_iterator_tag)
 285     {
 286       if (_GLIBCXX_PARALLEL_CONDITION(true))
 287         {
 288           if (std::distance(__begin1, __end1)
 289               != std::distance(__begin2, __end2))
 290             return false;
 291
 292           return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
 293                                           __pred).first == __end1;
 294         }
 295       else
 296         return _GLIBCXX_STD_A::equal(__begin1, __end1,
 297                                      __begin2, __end2, __pred);
 298     }
 299
 300   template<typename _IIter1, typename _IIter2>
 301     _GLIBCXX20_CONSTEXPR
 302     inline bool
 303     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
 304     {
 305 #if __cplusplus > 201703L
 306       if (std::is_constant_evaluated())
 307         return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
 308 #endif
 309
 310       typedef __gnu_parallel::_EqualTo<
 311         typename std::iterator_traits<_IIter1>::value_type,
 312         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
 313
 314       return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
 315                             std::__iterator_category(__begin1),
 316                             std::__iterator_category(__begin2));
 317     }
 318
 319   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
 320     _GLIBCXX20_CONSTEXPR
 321     inline bool
 322     equal(_IIter1 __begin1, _IIter1 __end1,
 323           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
 324     {
 325 #if __cplusplus > 201703L
 326       if (std::is_constant_evaluated())
 327         return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
 328                                      __binary_pred);
 329 #endif
 330
 331       return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
 332                             std::__iterator_category(__begin1),
 333                             std::__iterator_category(__begin2));
 334     }
 335 #endif // C++14
 336
 337   // Sequential fallback
 338   template<typename _IIter1, typename _IIter2>
 339     inline bool
 340     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 341                             _IIter2 __begin2, _IIter2 __end2,
 342                             __gnu_parallel::sequential_tag)
 343     { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
 344                                                      __begin2, __end2); }
 345
 346   // Sequential fallback
 347   template<typename _IIter1, typename _IIter2, typename _Predicate>
 348     inline bool
 349     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 350                             _IIter2 __begin2, _IIter2 __end2,
 351                             _Predicate __pred, __gnu_parallel::sequential_tag)
 352     { return _GLIBCXX_STD_A::lexicographical_compare(
 353                __begin1, __end1, __begin2, __end2, __pred); }
 354
 355   // Sequential fallback for input iterator case
 356   template<typename _IIter1, typename _IIter2,
 357            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
 358     inline bool
 359     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
 360                                      _IIter2 __begin2, _IIter2 __end2,
 361                                      _Predicate __pred,
 362                                      _IteratorTag1, _IteratorTag2)
 363     { return _GLIBCXX_STD_A::lexicographical_compare(
 364                __begin1, __end1, __begin2, __end2, __pred); }
 365
 366   // Parallel lexicographical_compare for random access iterators
 367   // Limitation: Both valuetypes must be the same
 368   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
 369     bool
 370     __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
 371                                      _RAIter2 __begin2, _RAIter2 __end2,
 372                                      _Predicate __pred,
 373                                      random_access_iterator_tag,
 374                                      random_access_iterator_tag)
 375     {
 376       if (_GLIBCXX_PARALLEL_CONDITION(true))
 377         {
 378           typedef iterator_traits<_RAIter1> _TraitsType1;
 379           typedef typename _TraitsType1::value_type _ValueType1;
 380
 381           typedef iterator_traits<_RAIter2> _TraitsType2;
 382           typedef typename _TraitsType2::value_type _ValueType2;
 383
 384           typedef __gnu_parallel::
 385                   _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
 386                   _EqualFromLessCompare;
 387
 388           // Longer sequence in first place.
 389           if ((__end1 - __begin1) < (__end2 - __begin2))
 390             {
 391               typedef pair<_RAIter1, _RAIter2> _SpotType;
 392               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
 393                                              _EqualFromLessCompare(__pred),
 394                                              random_access_iterator_tag(),
 395                                              random_access_iterator_tag());
 396
 397               return (__mm.first == __end1)
 398                         || bool(__pred(*__mm.first, *__mm.second));
 399             }
 400           else
 401             {
 402               typedef pair<_RAIter2, _RAIter1> _SpotType;
 403               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
 404                                              _EqualFromLessCompare(__pred),
 405                                              random_access_iterator_tag(),
 406                                              random_access_iterator_tag());
 407
 408               return (__mm.first != __end2)
 409                         && bool(__pred(*__mm.second, *__mm.first));
 410             }
 411         }
 412       else
 413         return _GLIBCXX_STD_A::lexicographical_compare(
 414                  __begin1, __end1, __begin2, __end2, __pred);
 415     }
 416
 417   // Public interface
 418   template<typename _IIter1, typename _IIter2>
 419     _GLIBCXX20_CONSTEXPR
 420     inline bool
 421     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 422                             _IIter2 __begin2, _IIter2 __end2)
 423     {
 424 #if __cplusplus > 201703L
 425       if (std::is_constant_evaluated())
 426         return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
 427                                                        __begin2, __end2);
 428 #endif
 429
 430       typedef iterator_traits<_IIter1> _TraitsType1;
 431       typedef typename _TraitsType1::value_type _ValueType1;
 432       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 433
 434       typedef iterator_traits<_IIter2> _TraitsType2;
 435       typedef typename _TraitsType2::value_type _ValueType2;
 436       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 437       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
 438
 439       return __lexicographical_compare_switch(
 440                __begin1, __end1, __begin2, __end2, _LessType(),
 441                _IteratorCategory1(), _IteratorCategory2());
 442     }
 443
 444   // Public interface
 445   template<typename _IIter1, typename _IIter2, typename _Predicate>
 446     _GLIBCXX20_CONSTEXPR
 447     inline bool
 448     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 449                             _IIter2 __begin2, _IIter2 __end2,
 450                             _Predicate __pred)
 451     {
 452 #if __cplusplus > 201703L
 453       if (std::is_constant_evaluated())
 454         return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
 455                                                        __begin2, __end2,
 456                                                        __pred);
 457 #endif
 458
 459       typedef iterator_traits<_IIter1> _TraitsType1;
 460       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 461
 462       typedef iterator_traits<_IIter2> _TraitsType2;
 463       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 464
 465       return __lexicographical_compare_switch(
 466                __begin1, __end1, __begin2, __end2, __pred,
 467                _IteratorCategory1(), _IteratorCategory2());
 468     }
 469
 470 #if __cpp_lib_three_way_comparison
 471   using _GLIBCXX_STD_A::lexicographical_compare_three_way;
 472 #endif
 473 } // end namespace
 474 } // end namespace
 475
 476 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */