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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2017 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 */