algobase.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 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
00047 {
00048 namespace __parallel
00049 {
00050   // NB: equal and lexicographical_compare require mismatch.
00051 
00052   // Sequential fallback
00053   template<typename InputIterator1, typename InputIterator2>
00054     inline pair<InputIterator1, InputIterator2>
00055     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00056          __gnu_parallel::sequential_tag)
00057     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
00058 
00059   // Sequential fallback
00060   template<typename InputIterator1, typename InputIterator2,
00061        typename Predicate>
00062     inline pair<InputIterator1, InputIterator2>
00063     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00064          Predicate pred, __gnu_parallel::sequential_tag)
00065     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00066 
00067   // Sequential fallback for input iterator case
00068   template<typename InputIterator1, typename InputIterator2,
00069        typename Predicate, typename IteratorTag1, typename IteratorTag2>
00070     inline pair<InputIterator1, InputIterator2>
00071     mismatch_switch(InputIterator1 begin1, InputIterator1 end1, 
00072             InputIterator2 begin2, Predicate pred, IteratorTag1, 
00073             IteratorTag2)
00074     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00075 
00076   // Parallel mismatch for random access iterators
00077   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00078        typename Predicate>
00079     pair<RandomAccessIterator1, RandomAccessIterator2>
00080     mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00081             RandomAccessIterator2 begin2, Predicate pred, 
00082             random_access_iterator_tag, random_access_iterator_tag)
00083     {
00084       if (_GLIBCXX_PARALLEL_CONDITION(true))
00085     {
00086       RandomAccessIterator1 res =
00087         __gnu_parallel::find_template(begin1, end1, begin2, pred,
00088                       __gnu_parallel::
00089                       mismatch_selector()).first;
00090       return make_pair(res , begin2 + (res - begin1));
00091     }
00092       else
00093     return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
00094     }
00095 
00096   // Public interface
00097   template<typename InputIterator1, typename InputIterator2>
00098     inline pair<InputIterator1, InputIterator2>
00099     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00100     {
00101       typedef std::iterator_traits<InputIterator1> iterator1_traits;
00102       typedef std::iterator_traits<InputIterator2> iterator2_traits;
00103       typedef typename iterator1_traits::value_type value1_type;
00104       typedef typename iterator2_traits::value_type value2_type;
00105       typedef typename iterator1_traits::iterator_category iterator1_category;
00106       typedef typename iterator2_traits::iterator_category iterator2_category;
00107 
00108       typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
00109 
00110       return mismatch_switch(begin1, end1, begin2, equal_to_type(),
00111                  iterator1_category(), iterator2_category());
00112     }
00113 
00114   // Public interface
00115   template<typename InputIterator1, typename InputIterator2,
00116        typename Predicate>
00117     inline pair<InputIterator1, InputIterator2>
00118     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00119          Predicate pred)
00120     {
00121       typedef std::iterator_traits<InputIterator1> iterator1_traits;
00122       typedef std::iterator_traits<InputIterator2> iterator2_traits;
00123       typedef typename iterator1_traits::iterator_category iterator1_category;
00124       typedef typename iterator2_traits::iterator_category iterator2_category;
00125 
00126       return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), 
00127                  iterator2_category());
00128     }
00129 
00130   // Sequential fallback
00131   template<typename InputIterator1, typename InputIterator2>
00132     inline bool
00133     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00134       __gnu_parallel::sequential_tag)
00135     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
00136 
00137   // Sequential fallback
00138   template<typename InputIterator1, typename InputIterator2,
00139        typename Predicate>
00140     inline bool
00141     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00142       Predicate pred, __gnu_parallel::sequential_tag)
00143     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
00144 
00145   // Public interface
00146   template<typename InputIterator1, typename InputIterator2>
00147     inline bool
00148     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00149     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2).first == end1; }
00150 
00151   // Public interface
00152   template<typename InputIterator1, typename InputIterator2,
00153        typename Predicate>
00154     inline bool
00155     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00156       Predicate pred)
00157     {
00158       return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred).first
00159                   == end1;
00160     }
00161 
00162   // Sequential fallback
00163   template<typename InputIterator1, typename InputIterator2>
00164     inline bool
00165     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00166                 InputIterator2 begin2, InputIterator2 end2, 
00167                 __gnu_parallel::sequential_tag)
00168     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00169                              begin2, end2); }
00170 
00171   // Sequential fallback
00172   template<typename InputIterator1, typename InputIterator2,
00173        typename Predicate>
00174     inline bool
00175     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00176                 InputIterator2 begin2, InputIterator2 end2, 
00177                 Predicate pred, __gnu_parallel::sequential_tag)
00178     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00179                              begin2, end2, pred); }
00180 
00181   // Sequential fallback for input iterator case
00182   template<typename InputIterator1, typename InputIterator2,
00183        typename Predicate, typename IteratorTag1, typename IteratorTag2>
00184     inline bool
00185     lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, 
00186                    InputIterator2 begin2, InputIterator2 end2, 
00187                    Predicate pred, IteratorTag1, IteratorTag2)
00188     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00189                              begin2, end2, pred); }
00190 
00191   // Parallel lexicographical_compare for random access iterators
00192   // Limitation: Both valuetypes must be the same
00193   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00194        typename Predicate>
00195     bool
00196     lexicographical_compare_switch(RandomAccessIterator1 begin1, 
00197                    RandomAccessIterator1 end1, 
00198                    RandomAccessIterator2 begin2, 
00199                    RandomAccessIterator2 end2, Predicate pred, 
00200                    random_access_iterator_tag, 
00201                    random_access_iterator_tag)
00202     {
00203       if (_GLIBCXX_PARALLEL_CONDITION(true))
00204     {
00205       typedef iterator_traits<RandomAccessIterator1> traits1_type;
00206       typedef typename traits1_type::value_type value1_type;
00207 
00208       typedef iterator_traits<RandomAccessIterator2> traits2_type;
00209       typedef typename traits2_type::value_type value2_type;
00210 
00211       typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
00212                                               value2_type> equal_type;
00213 
00214       // Longer sequence in first place.
00215       if ((end1 - begin1) < (end2 - begin2))
00216         {
00217           typedef pair<RandomAccessIterator1, RandomAccessIterator2>
00218         pair_type;
00219           pair_type mm = mismatch_switch(begin1, end1, begin2, 
00220                          equal_type(pred), 
00221                          random_access_iterator_tag(), 
00222                          random_access_iterator_tag());
00223 
00224           return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
00225         }
00226       else
00227         {
00228           typedef pair<RandomAccessIterator2, RandomAccessIterator1>
00229         pair_type;
00230           pair_type mm = mismatch_switch(begin2, end2, begin1, 
00231                          equal_type(pred), 
00232                          random_access_iterator_tag(), 
00233                          random_access_iterator_tag());
00234 
00235           return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
00236         }
00237     }
00238       else
00239     return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00240                                begin2, end2, pred);
00241     }
00242 
00243   // Public interface
00244   template<typename InputIterator1, typename InputIterator2>
00245     inline bool
00246     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00247                 InputIterator2 begin2, InputIterator2 end2)
00248     {
00249       typedef iterator_traits<InputIterator1> traits1_type;
00250       typedef typename traits1_type::value_type value1_type;
00251       typedef typename traits1_type::iterator_category iterator1_category;
00252 
00253       typedef iterator_traits<InputIterator2> traits2_type;
00254       typedef typename traits2_type::value_type value2_type;
00255       typedef typename traits2_type::iterator_category iterator2_category;
00256       typedef __gnu_parallel::less<value1_type, value2_type> less_type;
00257 
00258       return lexicographical_compare_switch(begin1, end1, begin2, end2, 
00259                         less_type(), iterator1_category(), 
00260                         iterator2_category());
00261     }
00262 
00263   // Public interface
00264   template<typename InputIterator1, typename InputIterator2,
00265        typename Predicate>
00266     inline bool
00267     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00268                 InputIterator2 begin2, InputIterator2 end2,
00269                 Predicate pred)
00270     {
00271       typedef iterator_traits<InputIterator1> traits1_type;
00272       typedef typename traits1_type::iterator_category iterator1_category;
00273 
00274       typedef iterator_traits<InputIterator2> traits2_type;
00275       typedef typename traits2_type::iterator_category iterator2_category;
00276 
00277       return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, 
00278                         iterator1_category(), 
00279                         iterator2_category());
00280     }
00281 } // end namespace
00282 } // end namespace
00283 
00284 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1