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