l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.4/include/parallel/algobase.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file parallel/algobase.h
  26  *  @brief Parallel STL function calls corresponding to the
  27  *  stl_algobase.h header.  The functions defined here mainly do case
  28  *  switches and call the actual parallelized versions in other files.
  29  *  Inlining policy: Functions that basically only contain one
  30  *  function call, are declared inline.
  31  *  This file is a GNU parallel extension to the Standard C++ Library.
  32  */
  33
  34 // Written by Johannes Singler and Felix Putze.
  35
  36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
  37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
  38
  39 #include <bits/stl_algobase.h>
  40 #include <parallel/base.h>
  41 #include <parallel/tags.h>
  42 #include <parallel/settings.h>
  43 #include <parallel/find.h>
  44 #include <parallel/find_selectors.h>
  45
  46 namespace std
  47 {
  48 namespace __parallel
  49 {
  50   // NB: equal and lexicographical_compare require mismatch.
  51
  52   // Sequential fallback
  53   template<typename InputIterator1, typename InputIterator2>
  54     inline pair<InputIterator1, InputIterator2>
  55     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
  56              __gnu_parallel::sequential_tag)
  57     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
  58
  59   // Sequential fallback
  60   template<typename InputIterator1, typename InputIterator2,
  61            typename Predicate>
  62     inline pair<InputIterator1, InputIterator2>
  63     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
  64              Predicate pred, __gnu_parallel::sequential_tag)
  65     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
  66
  67   // Sequential fallback for input iterator case
  68   template<typename InputIterator1, typename InputIterator2,
  69            typename Predicate, typename IteratorTag1, typename IteratorTag2>
  70     inline pair<InputIterator1, InputIterator2>
  71     mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
  72                     InputIterator2 begin2, Predicate pred, IteratorTag1,
  73                     IteratorTag2)
  74     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
  75
  76   // Parallel mismatch for random access iterators
  77   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
  78            typename Predicate>
  79     pair<RandomAccessIterator1, RandomAccessIterator2>
  80     mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
  81                     RandomAccessIterator2 begin2, Predicate pred,
  82                     random_access_iterator_tag, random_access_iterator_tag)
  83     {
  84       if (_GLIBCXX_PARALLEL_CONDITION(true))
  85         {
  86           RandomAccessIterator1 res =
  87             __gnu_parallel::find_template(begin1, end1, begin2, pred,
  88                                           __gnu_parallel::
  89                                           mismatch_selector()).first;
  90           return make_pair(res , begin2 + (res - begin1));
  91         }
  92       else
  93         return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
  94     }
  95
  96   // Public interface
  97   template<typename InputIterator1, typename InputIterator2>
  98     inline pair<InputIterator1, InputIterator2>
  99     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 100     {
 101       typedef std::iterator_traits<InputIterator1> iterator1_traits;
 102       typedef std::iterator_traits<InputIterator2> iterator2_traits;
 103       typedef typename iterator1_traits::value_type value1_type;
 104       typedef typename iterator2_traits::value_type value2_type;
 105       typedef typename iterator1_traits::iterator_category iterator1_category;
 106       typedef typename iterator2_traits::iterator_category iterator2_category;
 107
 108       typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
 109
 110       return mismatch_switch(begin1, end1, begin2, equal_to_type(),
 111                              iterator1_category(), iterator2_category());
 112     }
 113
 114   // Public interface
 115   template<typename InputIterator1, typename InputIterator2,
 116            typename Predicate>
 117     inline pair<InputIterator1, InputIterator2>
 118     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 119              Predicate pred)
 120     {
 121       typedef std::iterator_traits<InputIterator1> iterator1_traits;
 122       typedef std::iterator_traits<InputIterator2> iterator2_traits;
 123       typedef typename iterator1_traits::iterator_category iterator1_category;
 124       typedef typename iterator2_traits::iterator_category iterator2_category;
 125
 126       return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
 127                              iterator2_category());
 128     }
 129
 130   // Sequential fallback
 131   template<typename InputIterator1, typename InputIterator2>
 132     inline bool
 133     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 134           __gnu_parallel::sequential_tag)
 135     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
 136
 137   // Sequential fallback
 138   template<typename InputIterator1, typename InputIterator2,
 139            typename Predicate>
 140     inline bool
 141     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 142           Predicate pred, __gnu_parallel::sequential_tag)
 143     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
 144
 145   // Public interface
 146   template<typename InputIterator1, typename InputIterator2>
 147     inline bool
 148     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 149     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2).first == end1; }
 150
 151   // Public interface
 152   template<typename InputIterator1, typename InputIterator2,
 153            typename Predicate>
 154     inline bool
 155     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 156           Predicate pred)
 157     {
 158       return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred).first
 159                   == end1;
 160     }
 161
 162   // Sequential fallback
 163   template<typename InputIterator1, typename InputIterator2>
 164     inline bool
 165     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 166                             InputIterator2 begin2, InputIterator2 end2,
 167                             __gnu_parallel::sequential_tag)
 168     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 169                                                      begin2, end2); }
 170
 171   // Sequential fallback
 172   template<typename InputIterator1, typename InputIterator2,
 173            typename Predicate>
 174     inline bool
 175     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 176                             InputIterator2 begin2, InputIterator2 end2,
 177                             Predicate pred, __gnu_parallel::sequential_tag)
 178     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 179                                                      begin2, end2, pred); }
 180
 181   // Sequential fallback for input iterator case
 182   template<typename InputIterator1, typename InputIterator2,
 183            typename Predicate, typename IteratorTag1, typename IteratorTag2>
 184     inline bool
 185     lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
 186                                    InputIterator2 begin2, InputIterator2 end2,
 187                                    Predicate pred, IteratorTag1, IteratorTag2)
 188     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 189                                                      begin2, end2, pred); }
 190
 191   // Parallel lexicographical_compare for random access iterators
 192   // Limitation: Both valuetypes must be the same
 193   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 194            typename Predicate>
 195     bool
 196     lexicographical_compare_switch(RandomAccessIterator1 begin1,
 197                                    RandomAccessIterator1 end1,
 198                                    RandomAccessIterator2 begin2,
 199                                    RandomAccessIterator2 end2, Predicate pred,
 200                                    random_access_iterator_tag,
 201                                    random_access_iterator_tag)
 202     {
 203       if (_GLIBCXX_PARALLEL_CONDITION(true))
 204         {
 205           typedef iterator_traits<RandomAccessIterator1> traits1_type;
 206           typedef typename traits1_type::value_type value1_type;
 207
 208           typedef iterator_traits<RandomAccessIterator2> traits2_type;
 209           typedef typename traits2_type::value_type value2_type;
 210
 211           typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
 212                                                   value2_type> equal_type;
 213
 214           // Longer sequence in first place.
 215           if ((end1 - begin1) < (end2 - begin2))
 216             {
 217               typedef pair<RandomAccessIterator1, RandomAccessIterator2>
 218                 pair_type;
 219               pair_type mm = mismatch_switch(begin1, end1, begin2,
 220                                              equal_type(pred),
 221                                              random_access_iterator_tag(),
 222                                              random_access_iterator_tag());
 223
 224               return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
 225             }
 226           else
 227             {
 228               typedef pair<RandomAccessIterator2, RandomAccessIterator1>
 229                 pair_type;
 230               pair_type mm = mismatch_switch(begin2, end2, begin1,
 231                                              equal_type(pred),
 232                                              random_access_iterator_tag(),
 233                                              random_access_iterator_tag());
 234
 235               return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
 236             }
 237         }
 238       else
 239         return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 240                                                        begin2, end2, pred);
 241     }
 242
 243   // Public interface
 244   template<typename InputIterator1, typename InputIterator2>
 245     inline bool
 246     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 247                             InputIterator2 begin2, InputIterator2 end2)
 248     {
 249       typedef iterator_traits<InputIterator1> traits1_type;
 250       typedef typename traits1_type::value_type value1_type;
 251       typedef typename traits1_type::iterator_category iterator1_category;
 252
 253       typedef iterator_traits<InputIterator2> traits2_type;
 254       typedef typename traits2_type::value_type value2_type;
 255       typedef typename traits2_type::iterator_category iterator2_category;
 256       typedef __gnu_parallel::less<value1_type, value2_type> less_type;
 257
 258       return lexicographical_compare_switch(begin1, end1, begin2, end2,
 259                                             less_type(), iterator1_category(),
 260                                             iterator2_category());
 261     }
 262
 263   // Public interface
 264   template<typename InputIterator1, typename InputIterator2,
 265            typename Predicate>
 266     inline bool
 267     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 268                             InputIterator2 begin2, InputIterator2 end2,
 269                             Predicate pred)
 270     {
 271       typedef iterator_traits<InputIterator1> traits1_type;
 272       typedef typename traits1_type::iterator_category iterator1_category;
 273
 274       typedef iterator_traits<InputIterator2> traits2_type;
 275       typedef typename traits2_type::iterator_category iterator2_category;
 276
 277       return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
 278                                             iterator1_category(),
 279                                             iterator2_category());
 280     }
 281 } // end namespace
 282 } // end namespace
 283
 284 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */