algobase.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/algobase.h
00032  *  @brief Parallel STL function calls corresponding to the
00033  *  stl_algobase.h header.  The functions defined here mainly do case
00034  *  switches and call the actual parallelized versions in other files.
00035  *  Inlining policy: Functions that basically only contain one
00036  *  function call, are declared inline.
00037  *  This file is a GNU parallel extension to the Standard C++ Library.
00038  */
00039 
00040 // Written by Johannes Singler and Felix Putze.
00041 
00042 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
00043 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
00044 
00045 #include <bits/stl_algobase.h>
00046 #include <parallel/base.h>
00047 #include <parallel/tags.h>
00048 #include <parallel/settings.h>
00049 #include <parallel/find.h>
00050 #include <parallel/find_selectors.h>
00051 
00052 namespace std
00053 {
00054 namespace __parallel
00055 {
00056   // NB: equal and lexicographical_compare require mismatch.
00057 
00058   // Sequential fallback
00059   template<typename InputIterator1, typename InputIterator2>
00060     inline pair<InputIterator1, InputIterator2>
00061     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00062          __gnu_parallel::sequential_tag)
00063     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
00064 
00065   // Sequential fallback
00066   template<typename InputIterator1, typename InputIterator2,
00067        typename Predicate>
00068     inline pair<InputIterator1, InputIterator2>
00069     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00070          Predicate pred, __gnu_parallel::sequential_tag)
00071     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00072 
00073   // Sequential fallback for input iterator case
00074   template<typename InputIterator1, typename InputIterator2,
00075        typename Predicate, typename IteratorTag1, typename IteratorTag2>
00076     inline pair<InputIterator1, InputIterator2>
00077     mismatch_switch(InputIterator1 begin1, InputIterator1 end1, 
00078             InputIterator2 begin2, Predicate pred, IteratorTag1, 
00079             IteratorTag2)
00080     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00081 
00082   // Parallel mismatch for random access iterators
00083   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00084        typename Predicate>
00085     pair<RandomAccessIterator1, RandomAccessIterator2>
00086     mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00087             RandomAccessIterator2 begin2, Predicate pred, 
00088             random_access_iterator_tag, random_access_iterator_tag)
00089     {
00090       if (_GLIBCXX_PARALLEL_CONDITION(true))
00091     {
00092       RandomAccessIterator1 res =
00093         __gnu_parallel::find_template(begin1, end1, begin2, pred,
00094                       __gnu_parallel::
00095                       mismatch_selector()).first;
00096       return make_pair(res , begin2 + (res - begin1));
00097     }
00098       else
00099     return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
00100     }
00101 
00102   // Public interface
00103   template<typename InputIterator1, typename InputIterator2>
00104     inline pair<InputIterator1, InputIterator2>
00105     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00106     {
00107       typedef std::iterator_traits<InputIterator1> iterator1_traits;
00108       typedef std::iterator_traits<InputIterator2> iterator2_traits;
00109       typedef typename iterator1_traits::value_type value1_type;
00110       typedef typename iterator2_traits::value_type value2_type;
00111       typedef typename iterator1_traits::iterator_category iterator1_category;
00112       typedef typename iterator2_traits::iterator_category iterator2_category;
00113 
00114       typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
00115 
00116       return mismatch_switch(begin1, end1, begin2, equal_to_type(),
00117                  iterator1_category(), iterator2_category());
00118     }
00119 
00120   // Public interface
00121   template<typename InputIterator1, typename InputIterator2,
00122        typename Predicate>
00123     inline pair<InputIterator1, InputIterator2>
00124     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00125          Predicate pred)
00126     {
00127       typedef std::iterator_traits<InputIterator1> iterator1_traits;
00128       typedef std::iterator_traits<InputIterator2> iterator2_traits;
00129       typedef typename iterator1_traits::iterator_category iterator1_category;
00130       typedef typename iterator2_traits::iterator_category iterator2_category;
00131 
00132       return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), 
00133                  iterator2_category());
00134     }
00135 
00136   // Sequential fallback
00137   template<typename InputIterator1, typename InputIterator2>
00138     inline bool
00139     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00140       __gnu_parallel::sequential_tag)
00141     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
00142 
00143   // Sequential fallback
00144   template<typename InputIterator1, typename InputIterator2,
00145        typename Predicate>
00146     inline bool
00147     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00148       Predicate pred, __gnu_parallel::sequential_tag)
00149     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
00150 
00151   // Public interface
00152   template<typename InputIterator1, typename InputIterator2>
00153     inline bool
00154     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00155     { return mismatch(begin1, end1, begin2).first == end1; }
00156 
00157   // Public interface
00158   template<typename InputIterator1, typename InputIterator2,
00159        typename Predicate>
00160     inline bool
00161     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
00162       Predicate pred)
00163     { return mismatch(begin1, end1, begin2, pred).first == end1; }
00164 
00165   // Sequential fallback
00166   template<typename InputIterator1, typename InputIterator2>
00167     inline bool
00168     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00169                 InputIterator2 begin2, InputIterator2 end2, 
00170                 __gnu_parallel::sequential_tag)
00171     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00172                              begin2, end2); }
00173 
00174   // Sequential fallback
00175   template<typename InputIterator1, typename InputIterator2,
00176        typename Predicate>
00177     inline bool
00178     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 
00179                 InputIterator2 begin2, InputIterator2 end2, 
00180                 Predicate pred, __gnu_parallel::sequential_tag)
00181     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00182                              begin2, end2, pred); }
00183 
00184   // Sequential fallback for input iterator case
00185   template<typename InputIterator1, typename InputIterator2,
00186        typename Predicate, typename IteratorTag1, typename IteratorTag2>
00187     inline bool
00188     lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, 
00189                    InputIterator2 begin2, InputIterator2 end2, 
00190                    Predicate pred, IteratorTag1, IteratorTag2)
00191     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 
00192                              begin2, end2, pred); }
00193 
00194   // Parallel lexicographical_compare for random access iterators
00195   // Limitation: Both valuetypes must be the same
00196   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00197        typename Predicate>
00198     bool
00199     lexicographical_compare_switch(RandomAccessIterator1 begin1, 
00200                    RandomAccessIterator1 end1, 
00201                    RandomAccessIterator2 begin2, 
00202                    RandomAccessIterator2 end2, Predicate pred, 
00203                    random_access_iterator_tag, 
00204                    random_access_iterator_tag)
00205     {
00206       if (_GLIBCXX_PARALLEL_CONDITION(true))
00207     {
00208       typedef iterator_traits<RandomAccessIterator1> traits1_type;
00209       typedef typename traits1_type::value_type value1_type;
00210 
00211       typedef iterator_traits<RandomAccessIterator2> traits2_type;
00212       typedef typename traits2_type::value_type value2_type;
00213 
00214       typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
00215                                               value2_type> equal_type;
00216 
00217       // Longer sequence in first place.
00218       if ((end1 - begin1) < (end2 - begin2))
00219         {
00220           typedef pair<RandomAccessIterator1, RandomAccessIterator2>
00221         pair_type;
00222           pair_type mm = mismatch_switch(begin1, end1, begin2, 
00223                          equal_type(pred), 
00224                          random_access_iterator_tag(), 
00225                          random_access_iterator_tag());
00226 
00227           return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
00228         }
00229       else
00230         {
00231           typedef pair<RandomAccessIterator2, RandomAccessIterator1>
00232         pair_type;
00233           pair_type mm = mismatch_switch(begin2, end2, begin1, 
00234                          equal_type(pred), 
00235                          random_access_iterator_tag(), 
00236                          random_access_iterator_tag());
00237 
00238           return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
00239         }
00240     }
00241       else
00242     return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00243                                begin2, end2, pred);
00244     }
00245 
00246   // Public interface
00247   template<typename InputIterator1, typename InputIterator2>
00248     inline bool
00249     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00250                 InputIterator2 begin2, InputIterator2 end2)
00251     {
00252       typedef iterator_traits<InputIterator1> traits1_type;
00253       typedef typename traits1_type::value_type value1_type;
00254       typedef typename traits1_type::iterator_category iterator1_category;
00255 
00256       typedef iterator_traits<InputIterator2> traits2_type;
00257       typedef typename traits2_type::value_type value2_type;
00258       typedef typename traits2_type::iterator_category iterator2_category;
00259       typedef __gnu_parallel::less<value1_type, value2_type> less_type;
00260 
00261       return lexicographical_compare_switch(begin1, end1, begin2, end2, 
00262                         less_type(), iterator1_category(), 
00263                         iterator2_category());
00264     }
00265 
00266   // Public interface
00267   template<typename InputIterator1, typename InputIterator2,
00268        typename Predicate>
00269     inline bool
00270     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00271                 InputIterator2 begin2, InputIterator2 end2,
00272                 Predicate pred)
00273     {
00274       typedef iterator_traits<InputIterator1> traits1_type;
00275       typedef typename traits1_type::iterator_category iterator1_category;
00276 
00277       typedef iterator_traits<InputIterator2> traits2_type;
00278       typedef typename traits2_type::iterator_category iterator2_category;
00279 
00280       return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, 
00281                         iterator1_category(), 
00282                         iterator2_category());
00283     }
00284 } // end namespace
00285 } // end namespace
00286 
00287 #endif /* _GLIBCXX_ALGOBASE_H */

Generated on Sat Oct 25 05:08:57 2008 for libstdc++ by  doxygen 1.5.6