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 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     { return mismatch(begin1, end1, begin2, pred).first == end1; }
00158 
00159   // Sequential fallback
00160   template<typename InputIterator1, typename InputIterator2>
00161     inline bool
00162     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00163                 InputIterator2 begin2, InputIterator2 end2, 
00164                 __gnu_parallel::sequential_tag)
00165     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00166                              begin2, end2); }
00167 
00168   // Sequential fallback
00169   template<typename InputIterator1, typename InputIterator2,
00170        typename Predicate>
00171     inline bool
00172     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00173                 InputIterator2 begin2, InputIterator2 end2, 
00174                 Predicate pred, __gnu_parallel::sequential_tag)
00175     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00176                              begin2, end2, pred); }
00177 
00178   // Sequential fallback for input iterator case
00179   template<typename InputIterator1, typename InputIterator2,
00180        typename Predicate, typename IteratorTag1, typename IteratorTag2>
00181     inline bool
00182     lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, 
00183                    InputIterator2 begin2, InputIterator2 end2, 
00184                    Predicate pred, IteratorTag1, IteratorTag2)
00185     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00186                              begin2, end2, pred); }
00187 
00188   // Parallel lexicographical_compare for random access iterators
00189   // Limitation: Both valuetypes must be the same
00190   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00191        typename Predicate>
00192     bool
00193     lexicographical_compare_switch(RandomAccessIterator1 begin1, 
00194                    RandomAccessIterator1 end1, 
00195                    RandomAccessIterator2 begin2, 
00196                    RandomAccessIterator2 end2, Predicate pred, 
00197                    random_access_iterator_tag, 
00198                    random_access_iterator_tag)
00199     {
00200       if (_GLIBCXX_PARALLEL_CONDITION(true))
00201     {
00202       typedef iterator_traits<RandomAccessIterator1> traits1_type;
00203       typedef typename traits1_type::value_type value1_type;
00204 
00205       typedef iterator_traits<RandomAccessIterator2> traits2_type;
00206       typedef typename traits2_type::value_type value2_type;
00207 
00208       typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
00209                                               value2_type> equal_type;
00210 
00211       // Longer sequence in first place.
00212       if ((end1 - begin1) < (end2 - begin2))
00213         {
00214           typedef pair<RandomAccessIterator1, RandomAccessIterator2>
00215         pair_type;
00216           pair_type mm = mismatch_switch(begin1, end1, begin2, 
00217                          equal_type(pred), 
00218                          random_access_iterator_tag(), 
00219                          random_access_iterator_tag());
00220 
00221           return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
00222         }
00223       else
00224         {
00225           typedef pair<RandomAccessIterator2, RandomAccessIterator1>
00226         pair_type;
00227           pair_type mm = mismatch_switch(begin2, end2, begin1, 
00228                          equal_type(pred), 
00229                          random_access_iterator_tag(), 
00230                          random_access_iterator_tag());
00231 
00232           return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
00233         }
00234     }
00235       else
00236     return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00237                                begin2, end2, pred);
00238     }
00239 
00240   // Public interface
00241   template<typename InputIterator1, typename InputIterator2>
00242     inline bool
00243     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00244                 InputIterator2 begin2, InputIterator2 end2)
00245     {
00246       typedef iterator_traits<InputIterator1> traits1_type;
00247       typedef typename traits1_type::value_type value1_type;
00248       typedef typename traits1_type::iterator_category iterator1_category;
00249 
00250       typedef iterator_traits<InputIterator2> traits2_type;
00251       typedef typename traits2_type::value_type value2_type;
00252       typedef typename traits2_type::iterator_category iterator2_category;
00253       typedef __gnu_parallel::less<value1_type, value2_type> less_type;
00254 
00255       return lexicographical_compare_switch(begin1, end1, begin2, end2, 
00256                         less_type(), iterator1_category(), 
00257                         iterator2_category());
00258     }
00259 
00260   // Public interface
00261   template<typename InputIterator1, typename InputIterator2,
00262        typename Predicate>
00263     inline bool
00264     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00265                 InputIterator2 begin2, InputIterator2 end2,
00266                 Predicate pred)
00267     {
00268       typedef iterator_traits<InputIterator1> traits1_type;
00269       typedef typename traits1_type::iterator_category iterator1_category;
00270 
00271       typedef iterator_traits<InputIterator2> traits2_type;
00272       typedef typename traits2_type::iterator_category iterator2_category;
00273 
00274       return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, 
00275                         iterator1_category(), 
00276                         iterator2_category());
00277     }
00278 } // end namespace
00279 } // end namespace
00280 
00281 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */

Generated on Tue Apr 21 13:13:24 2009 for libstdc++ by  doxygen 1.5.8