libstdc++
algobase.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/algobase.h
00026  *  @brief Parallel STL function calls corresponding to the
00027  *  stl_algobase.h header.  The functions defined here mainly do case
00028  *  switches and call the actual parallelized versions in other files.
00029  *  Inlining policy: Functions that basically only contain one
00030  *  function call, are declared inline.
00031  *  This file is a GNU parallel extension to the Standard C++ Library.
00032  */
00033 
00034 // Written by Johannes Singler and Felix Putze.
00035 
00036 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
00037 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
00038 
00039 #include <bits/stl_algobase.h>
00040 #include <parallel/base.h>
00041 #include <parallel/algorithmfwd.h>
00042 #include <parallel/find.h>
00043 #include <parallel/find_selectors.h>
00044 
00045 namespace std _GLIBCXX_VISIBILITY(default)
00046 {
00047 namespace __parallel
00048 {
00049   // NB: equal and lexicographical_compare require mismatch.
00050 
00051   // Sequential fallback
00052   template<typename _IIter1, typename _IIter2>
00053     inline pair<_IIter1, _IIter2>
00054     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00055              __gnu_parallel::sequential_tag)
00056     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }
00057 
00058   // Sequential fallback
00059   template<typename _IIter1, typename _IIter2, typename _Predicate>
00060     inline pair<_IIter1, _IIter2>
00061     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00062              _Predicate __pred, __gnu_parallel::sequential_tag)
00063     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
00064 
00065   // Sequential fallback for input iterator case
00066   template<typename _IIter1, typename _IIter2,
00067            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00068     inline pair<_IIter1, _IIter2>
00069     __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00070                       _Predicate __pred, _IteratorTag1, _IteratorTag2)
00071     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
00072 
00073   // Parallel mismatch for random access iterators
00074   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00075     pair<_RAIter1, _RAIter2>
00076     __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
00077                       _RAIter2 __begin2, _Predicate __pred, 
00078                       random_access_iterator_tag, random_access_iterator_tag)
00079     {
00080       if (_GLIBCXX_PARALLEL_CONDITION(true))
00081         {
00082           _RAIter1 __res =
00083             __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
00084                                             __gnu_parallel::
00085                                             __mismatch_selector()).first;
00086           return make_pair(__res , __begin2 + (__res - __begin1));
00087         }
00088       else
00089         return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
00090     }
00091 
00092   // Public interface
00093   template<typename _IIter1, typename _IIter2>
00094     inline pair<_IIter1, _IIter2>
00095     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
00096     {
00097       typedef __gnu_parallel::_EqualTo<
00098         typename std::iterator_traits<_IIter1>::value_type,
00099         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
00100 
00101       return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
00102                                std::__iterator_category(__begin1),
00103                                std::__iterator_category(__begin2));
00104     }
00105 
00106   // Public interface
00107   template<typename _IIter1, typename _IIter2, typename _Predicate>
00108     inline pair<_IIter1, _IIter2>
00109     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00110              _Predicate __pred)
00111     {
00112       return __mismatch_switch(__begin1, __end1, __begin2, __pred,
00113                                std::__iterator_category(__begin1),
00114                                std::__iterator_category(__begin2));
00115     }
00116 
00117 #if __cplusplus > 201103L
00118   // Sequential fallback.
00119   template<typename _InputIterator1, typename _InputIterator2>
00120     inline pair<_InputIterator1, _InputIterator2>
00121     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00122              _InputIterator2 __first2, _InputIterator2 __last2,
00123              __gnu_parallel::sequential_tag)
00124     { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
00125 
00126   // Sequential fallback.
00127   template<typename _InputIterator1, typename _InputIterator2,
00128            typename _BinaryPredicate>
00129     inline pair<_InputIterator1, _InputIterator2>
00130     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00131              _InputIterator2 __first2, _InputIterator2 __last2,
00132              _BinaryPredicate __binary_pred,
00133              __gnu_parallel::sequential_tag)
00134     {
00135       return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
00136                                       __binary_pred);
00137     }
00138 
00139   // Sequential fallback for input iterator case
00140   template<typename _IIter1, typename _IIter2,
00141            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00142     inline pair<_IIter1, _IIter2>
00143     __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
00144                       _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
00145                       _IteratorTag1, _IteratorTag2)
00146     {
00147       return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
00148                                       __begin2, __end2, __pred);
00149     }
00150 
00151   // Parallel mismatch for random access iterators
00152   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00153     pair<_RAIter1, _RAIter2>
00154     __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
00155                       _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 
00156                       random_access_iterator_tag, random_access_iterator_tag)
00157     {
00158       if (_GLIBCXX_PARALLEL_CONDITION(true))
00159         {
00160           if ((__end2 - __begin2) < (__end1 - __begin1))
00161             __end1 = __begin1 + (__end2 - __begin2);
00162 
00163           _RAIter1 __res =
00164             __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
00165                                             __gnu_parallel::
00166                                             __mismatch_selector()).first;
00167           return make_pair(__res , __begin2 + (__res - __begin1));
00168         }
00169       else
00170         return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
00171                                         __begin2, __end2, __pred);
00172     }
00173 
00174   template<typename _IIter1, typename _IIter2>
00175     inline pair<_IIter1, _IIter2>
00176     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
00177     {
00178       typedef __gnu_parallel::_EqualTo<
00179         typename std::iterator_traits<_IIter1>::value_type,
00180         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
00181 
00182       return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
00183                                std::__iterator_category(__begin1),
00184                                std::__iterator_category(__begin2));
00185     }
00186 
00187   template<typename _InputIterator1, typename _InputIterator2,
00188            typename _BinaryPredicate>
00189     inline pair<_InputIterator1, _InputIterator2>
00190     mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
00191              _InputIterator2 __begin2, _InputIterator2 __end2,
00192              _BinaryPredicate __binary_pred)
00193     {
00194       return __mismatch_switch(__begin1, __end1, __begin2, __end2,
00195                                __binary_pred,
00196                                std::__iterator_category(__begin1),
00197                                std::__iterator_category(__begin2));
00198     }
00199 #endif
00200 
00201   // Sequential fallback
00202   template<typename _IIter1, typename _IIter2>
00203     inline bool
00204     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00205           __gnu_parallel::sequential_tag)
00206     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
00207 
00208   // Sequential fallback
00209   template<typename _IIter1, typename _IIter2, typename _Predicate>
00210     inline bool
00211     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00212           _Predicate __pred, __gnu_parallel::sequential_tag)
00213     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
00214 
00215   // Public interface
00216   template<typename _IIter1, typename _IIter2>
00217     inline bool
00218     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
00219     {
00220       return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
00221               == __end1;
00222     }
00223 
00224   // Public interface
00225   template<typename _IIter1, typename _IIter2, typename _Predicate>
00226     inline bool
00227     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00228           _Predicate __pred)
00229     {
00230       return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
00231               == __end1;
00232     }
00233 
00234 #if __cplusplus > 201103L
00235   // Sequential fallback
00236   template<typename _IIter1, typename _IIter2>
00237     inline bool
00238     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
00239           __gnu_parallel::sequential_tag)
00240     {
00241       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
00242     }
00243 
00244   // Sequential fallback
00245   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
00246     inline bool
00247     equal(_IIter1 __begin1, _IIter1 __end1,
00248           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
00249           __gnu_parallel::sequential_tag)
00250     {
00251       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
00252                                    __binary_pred);
00253     }
00254 
00255   // Sequential fallback for input iterator case
00256   template<typename _IIter1, typename _IIter2,
00257            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00258     inline bool
00259     __equal_switch(_IIter1 __begin1, _IIter1 __end1,
00260                    _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
00261                    _IteratorTag1, _IteratorTag2)
00262     {
00263       return _GLIBCXX_STD_A::equal(__begin1, __end1,
00264                                    __begin2, __end2, __pred);
00265     }
00266 
00267   // Parallel equal for random access iterators
00268   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00269     inline bool
00270     __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
00271                    _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 
00272                    random_access_iterator_tag, random_access_iterator_tag)
00273     {
00274       if (_GLIBCXX_PARALLEL_CONDITION(true))
00275         {
00276           if (std::distance(__begin1, __end1)
00277               != std::distance(__begin2, __end2))
00278             return false;
00279 
00280           return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
00281                                           __pred).first == __end1;
00282         }
00283       else
00284         return _GLIBCXX_STD_A::equal(__begin1, __end1,
00285                                      __begin2, __end2, __pred);
00286     }
00287 
00288   template<typename _IIter1, typename _IIter2>
00289     inline bool
00290     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
00291     {
00292       typedef __gnu_parallel::_EqualTo<
00293         typename std::iterator_traits<_IIter1>::value_type,
00294         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
00295 
00296       return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
00297                             std::__iterator_category(__begin1),
00298                             std::__iterator_category(__begin2));
00299     }
00300 
00301   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
00302     inline bool
00303     equal(_IIter1 __begin1, _IIter1 __end1,
00304           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
00305     {
00306       return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
00307                             std::__iterator_category(__begin1),
00308                             std::__iterator_category(__begin2));
00309     }
00310 #endif
00311 
00312   // Sequential fallback
00313   template<typename _IIter1, typename _IIter2>
00314     inline bool
00315     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
00316                             _IIter2 __begin2, _IIter2 __end2, 
00317                             __gnu_parallel::sequential_tag)
00318     { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
00319                                                      __begin2, __end2); }
00320 
00321   // Sequential fallback
00322   template<typename _IIter1, typename _IIter2, typename _Predicate>
00323     inline bool
00324     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
00325                             _IIter2 __begin2, _IIter2 __end2, 
00326                             _Predicate __pred, __gnu_parallel::sequential_tag)
00327     { return _GLIBCXX_STD_A::lexicographical_compare(
00328                __begin1, __end1, __begin2, __end2, __pred); }
00329 
00330   // Sequential fallback for input iterator case
00331   template<typename _IIter1, typename _IIter2,
00332            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00333     inline bool
00334     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
00335                                      _IIter2 __begin2, _IIter2 __end2, 
00336                                      _Predicate __pred,
00337                                      _IteratorTag1, _IteratorTag2)
00338     { return _GLIBCXX_STD_A::lexicographical_compare(
00339                __begin1, __end1, __begin2, __end2, __pred); }
00340 
00341   // Parallel lexicographical_compare for random access iterators
00342   // Limitation: Both valuetypes must be the same
00343   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00344     bool
00345     __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
00346                                      _RAIter2 __begin2, _RAIter2 __end2,
00347                                      _Predicate __pred,
00348                                      random_access_iterator_tag, 
00349                                      random_access_iterator_tag)
00350     {
00351       if (_GLIBCXX_PARALLEL_CONDITION(true))
00352         {
00353           typedef iterator_traits<_RAIter1> _TraitsType1;
00354           typedef typename _TraitsType1::value_type _ValueType1;
00355 
00356           typedef iterator_traits<_RAIter2> _TraitsType2;
00357           typedef typename _TraitsType2::value_type _ValueType2;
00358 
00359           typedef __gnu_parallel::
00360                   _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
00361                   _EqualFromLessCompare;
00362 
00363           // Longer sequence in first place.
00364           if ((__end1 - __begin1) < (__end2 - __begin2))
00365             {
00366               typedef pair<_RAIter1, _RAIter2> _SpotType;
00367               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 
00368                                              _EqualFromLessCompare(__pred), 
00369                                              random_access_iterator_tag(), 
00370                                              random_access_iterator_tag());
00371 
00372               return (__mm.first == __end1)
00373                         || bool(__pred(*__mm.first, *__mm.second));
00374             }
00375           else
00376             {
00377               typedef pair<_RAIter2, _RAIter1> _SpotType;
00378               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 
00379                                              _EqualFromLessCompare(__pred), 
00380                                              random_access_iterator_tag(), 
00381                                              random_access_iterator_tag());
00382 
00383               return (__mm.first != __end2)
00384                         && bool(__pred(*__mm.second, *__mm.first));
00385             }
00386         }
00387       else
00388         return _GLIBCXX_STD_A::lexicographical_compare(
00389                  __begin1, __end1, __begin2, __end2, __pred);
00390     }
00391 
00392   // Public interface
00393   template<typename _IIter1, typename _IIter2>
00394     inline bool
00395     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00396                             _IIter2 __begin2, _IIter2 __end2)
00397     {
00398       typedef iterator_traits<_IIter1> _TraitsType1;
00399       typedef typename _TraitsType1::value_type _ValueType1;
00400       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00401 
00402       typedef iterator_traits<_IIter2> _TraitsType2;
00403       typedef typename _TraitsType2::value_type _ValueType2;
00404       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00405       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
00406 
00407       return __lexicographical_compare_switch(
00408                __begin1, __end1, __begin2, __end2, _LessType(),
00409                _IteratorCategory1(), _IteratorCategory2());
00410     }
00411 
00412   // Public interface
00413   template<typename _IIter1, typename _IIter2, typename _Predicate>
00414     inline bool
00415     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00416                             _IIter2 __begin2, _IIter2 __end2,
00417                             _Predicate __pred)
00418     {
00419       typedef iterator_traits<_IIter1> _TraitsType1;
00420       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00421 
00422       typedef iterator_traits<_IIter2> _TraitsType2;
00423       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00424 
00425       return __lexicographical_compare_switch(
00426                __begin1, __end1, __begin2, __end2, __pred,
00427                _IteratorCategory1(), _IteratorCategory2());
00428     }
00429 } // end namespace
00430 } // end namespace
00431 
00432 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */