libstdc++
algobase.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 std::iterator_traits<_IIter1> _Iterator1Traits;
00098       typedef std::iterator_traits<_IIter2> _Iterator2Traits;
00099       typedef typename _Iterator1Traits::value_type _ValueType1;
00100       typedef typename _Iterator2Traits::value_type _ValueType2;
00101       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
00102       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
00103 
00104       typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
00105 
00106       return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
00107                                _IteratorCategory1(), _IteratorCategory2());
00108     }
00109 
00110   // Public interface
00111   template<typename _IIter1, typename _IIter2, typename _Predicate>
00112     inline pair<_IIter1, _IIter2>
00113     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00114              _Predicate __pred)
00115     {
00116       typedef std::iterator_traits<_IIter1> _Iterator1Traits;
00117       typedef std::iterator_traits<_IIter2> _Iterator2Traits;
00118       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
00119       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
00120 
00121       return __mismatch_switch(__begin1, __end1, __begin2, __pred,
00122                                _IteratorCategory1(), _IteratorCategory2());
00123     }
00124 
00125   // Sequential fallback
00126   template<typename _IIter1, typename _IIter2>
00127     inline bool
00128     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00129           __gnu_parallel::sequential_tag)
00130     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
00131 
00132   // Sequential fallback
00133   template<typename _IIter1, typename _IIter2, typename _Predicate>
00134     inline bool
00135     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00136           _Predicate __pred, __gnu_parallel::sequential_tag)
00137     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
00138 
00139   // Public interface
00140   template<typename _IIter1, typename _IIter2>
00141     inline bool
00142     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
00143     {
00144       return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
00145               == __end1;
00146     }
00147 
00148   // Public interface
00149   template<typename _IIter1, typename _IIter2, typename _Predicate>
00150     inline bool
00151     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
00152           _Predicate __pred)
00153     {
00154       return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
00155               == __end1;
00156     }
00157 
00158   // Sequential fallback
00159   template<typename _IIter1, typename _IIter2>
00160     inline bool
00161     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
00162                             _IIter2 __begin2, _IIter2 __end2, 
00163                             __gnu_parallel::sequential_tag)
00164     { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
00165                                                      __begin2, __end2); }
00166 
00167   // Sequential fallback
00168   template<typename _IIter1, typename _IIter2, typename _Predicate>
00169     inline bool
00170     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
00171                             _IIter2 __begin2, _IIter2 __end2, 
00172                             _Predicate __pred, __gnu_parallel::sequential_tag)
00173     { return _GLIBCXX_STD_A::lexicographical_compare(
00174                __begin1, __end1, __begin2, __end2, __pred); }
00175 
00176   // Sequential fallback for input iterator case
00177   template<typename _IIter1, typename _IIter2,
00178            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00179     inline bool
00180     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
00181                                      _IIter2 __begin2, _IIter2 __end2, 
00182                                      _Predicate __pred,
00183                                      _IteratorTag1, _IteratorTag2)
00184     { return _GLIBCXX_STD_A::lexicographical_compare(
00185                __begin1, __end1, __begin2, __end2, __pred); }
00186 
00187   // Parallel lexicographical_compare for random access iterators
00188   // Limitation: Both valuetypes must be the same
00189   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00190     bool
00191     __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
00192                                      _RAIter2 __begin2, _RAIter2 __end2,
00193                                      _Predicate __pred,
00194                                      random_access_iterator_tag, 
00195                                      random_access_iterator_tag)
00196     {
00197       if (_GLIBCXX_PARALLEL_CONDITION(true))
00198         {
00199           typedef iterator_traits<_RAIter1> _TraitsType1;
00200           typedef typename _TraitsType1::value_type _ValueType1;
00201 
00202           typedef iterator_traits<_RAIter2> _TraitsType2;
00203           typedef typename _TraitsType2::value_type _ValueType2;
00204 
00205           typedef __gnu_parallel::
00206                   _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
00207                   _EqualFromLessCompare;
00208 
00209           // Longer sequence in first place.
00210           if ((__end1 - __begin1) < (__end2 - __begin2))
00211             {
00212               typedef pair<_RAIter1, _RAIter2> _SpotType;
00213               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 
00214                                              _EqualFromLessCompare(__pred), 
00215                                              random_access_iterator_tag(), 
00216                                              random_access_iterator_tag());
00217 
00218               return (__mm.first == __end1)
00219                         || bool(__pred(*__mm.first, *__mm.second));
00220             }
00221           else
00222             {
00223               typedef pair<_RAIter2, _RAIter1> _SpotType;
00224               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 
00225                                              _EqualFromLessCompare(__pred), 
00226                                              random_access_iterator_tag(), 
00227                                              random_access_iterator_tag());
00228 
00229               return (__mm.first != __end2)
00230                         && bool(__pred(*__mm.second, *__mm.first));
00231             }
00232         }
00233       else
00234         return _GLIBCXX_STD_A::lexicographical_compare(
00235                  __begin1, __end1, __begin2, __end2, __pred);
00236     }
00237 
00238   // Public interface
00239   template<typename _IIter1, typename _IIter2>
00240     inline bool
00241     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00242                             _IIter2 __begin2, _IIter2 __end2)
00243     {
00244       typedef iterator_traits<_IIter1> _TraitsType1;
00245       typedef typename _TraitsType1::value_type _ValueType1;
00246       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00247 
00248       typedef iterator_traits<_IIter2> _TraitsType2;
00249       typedef typename _TraitsType2::value_type _ValueType2;
00250       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00251       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
00252 
00253       return __lexicographical_compare_switch(
00254                __begin1, __end1, __begin2, __end2, _LessType(),
00255                _IteratorCategory1(), _IteratorCategory2());
00256     }
00257 
00258   // Public interface
00259   template<typename _IIter1, typename _IIter2, typename _Predicate>
00260     inline bool
00261     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00262                             _IIter2 __begin2, _IIter2 __end2,
00263                             _Predicate __pred)
00264     {
00265       typedef iterator_traits<_IIter1> _TraitsType1;
00266       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00267 
00268       typedef iterator_traits<_IIter2> _TraitsType2;
00269       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00270 
00271       return __lexicographical_compare_switch(
00272                __begin1, __end1, __begin2, __end2, __pred,
00273                _IteratorCategory1(), _IteratorCategory2());
00274     }
00275 } // end namespace
00276 } // end namespace
00277 
00278 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */