libstdc++-v3/include/parallel/algobase.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/algobase.h
  32  *  @brief Parallel STL function calls corresponding to the
  33  *  stl_algobase.h header.  The functions defined here mainly do case
  34  *  switches and call the actual parallelized versions in other files.
  35  *  Inlining policy: Functions that basically only contain one
  36  *  function call, are declared inline.
  37  *  This file is a GNU parallel extension to the Standard C++ Library.
  38  */
  39
  40 // Written by Johannes Singler and Felix Putze.
  41
  42 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
  43 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
  44
  45 #include <parallel/algorithmfwd.h>
  46 #include <bits/stl_algobase.h>
  47 #include <parallel/base.h>
  48 #include <parallel/tags.h>
  49 #include <parallel/settings.h>
  50 #include <parallel/find.h>
  51 #include <parallel/find_selectors.h>
  52 #include <parallel/for_each.h>
  53 #include <parallel/for_each_selectors.h>
  54
  55 namespace std
  56 {
  57 namespace __parallel
  58 {
  59   // Sequential fallback
  60   template<typename InputIterator1, typename InputIterator2>
  61   inline bool
  62   equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, __gnu_parallel::sequential_tag)
  63   {
  64     return _GLIBCXX_STD_P::equal<InputIterator1, InputIterator2>(begin1, end1, begin2);
  65   }
  66
  67   // Sequential fallback
  68   template<typename InputIterator1, typename InputIterator2, typename Predicate>
  69   inline bool
  70   equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, Predicate pred, __gnu_parallel::sequential_tag)
  71   { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
  72
  73   // Public interface
  74   template<typename InputIterator1, typename InputIterator2>
  75   inline bool
  76   equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
  77   { return mismatch(begin1, end1, begin2).first == end1; }
  78
  79   // Public interface
  80   template<typename InputIterator1, typename InputIterator2, typename Predicate>
  81   inline bool
  82   equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, Predicate pred)
  83   { return mismatch(begin1, end1, begin2, pred).first == end1; }
  84
  85   // NB: lexicographical_compare equires mismatch.
  86
  87   // Sequential fallback
  88   template<typename InputIterator1, typename InputIterator2>
  89   inline pair<InputIterator1, InputIterator2>
  90   mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, __gnu_parallel::sequential_tag)
  91   {
  92     return _GLIBCXX_STD_P::mismatch<InputIterator1, InputIterator2>(begin1, end1, begin2);
  93   }
  94
  95   // Sequential fallback
  96   template<typename InputIterator1, typename InputIterator2, typename Predicate>
  97   inline pair<InputIterator1, InputIterator2>
  98   mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, Predicate pred, __gnu_parallel::sequential_tag)
  99   { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
 100
 101   // Sequential fallback for input iterator case
 102   template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
 103   inline pair<InputIterator1, InputIterator2>
 104   mismatch_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, Predicate pred, IteratorTag1, IteratorTag2)
 105   { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
 106
 107   // Parallel mismatch for random access iterators
 108   template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
 109   pair<RandomAccessIterator1, RandomAccessIterator2>
 110   mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Predicate pred, random_access_iterator_tag, random_access_iterator_tag)
 111   {
 112     if (_GLIBCXX_PARALLEL_CONDITION(true))
 113       {
 114         RandomAccessIterator1 res_first =
 115           __gnu_parallel::find_template(begin1, end1, begin2, pred, __gnu_parallel::mismatch_selector()).first;
 116         return make_pair(res_first, begin2 + (res_first - begin1));
 117       }
 118     else
 119       return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
 120   }
 121
 122   // Public interface
 123   template<typename InputIterator1, typename InputIterator2>
 124   inline pair<InputIterator1, InputIterator2>
 125   mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 126   {
 127     typedef std::iterator_traits<InputIterator1> iterator1_traits;
 128     typedef std::iterator_traits<InputIterator2> iterator2_traits;
 129     typedef typename iterator1_traits::value_type value1_type;
 130     typedef typename iterator2_traits::value_type value2_type;
 131     typedef typename iterator1_traits::iterator_category iterator1_category;
 132     typedef typename iterator2_traits::iterator_category iterator2_category;
 133
 134     return mismatch_switch(begin1, end1, begin2, __gnu_parallel::equal_to<value1_type, value2_type>(), iterator1_category(), iterator2_category());
 135   }
 136
 137   // Public interface
 138   template<typename InputIterator1, typename InputIterator2, typename Predicate>
 139   inline pair<InputIterator1, InputIterator2>
 140   mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 141            Predicate pred)
 142   {
 143     typedef std::iterator_traits<InputIterator1> iterator1_traits;
 144     typedef std::iterator_traits<InputIterator2> iterator2_traits;
 145     typedef typename iterator1_traits::iterator_category iterator1_category;
 146     typedef typename iterator2_traits::iterator_category iterator2_category;
 147
 148     return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), iterator2_category());
 149   }
 150
 151   // Sequential fallback
 152   template<typename InputIterator1, typename InputIterator2>
 153   inline bool
 154   lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, __gnu_parallel::sequential_tag)
 155   {
 156     return _GLIBCXX_STD_P::lexicographical_compare<InputIterator1, InputIterator2>(begin1, end1, begin2, end2);
 157   }
 158
 159   // Sequential fallback
 160   template<typename InputIterator1, typename InputIterator2, typename Predicate>
 161   inline bool
 162   lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Predicate pred, __gnu_parallel::sequential_tag)
 163   {
 164     return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2, pred);
 165   }
 166
 167   // Sequential fallback for input iterator case
 168   template<typename InputIterator1, typename InputIterator2, typename Predicate, typename IteratorTag1, typename IteratorTag2>
 169   inline bool
 170   lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Predicate pred, IteratorTag1, IteratorTag2)
 171   {
 172     return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2, pred);
 173   }
 174
 175   // Parallel lexicographical_compare for random access iterators
 176   // Limitation: Both valuetypes must be the same
 177   template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Predicate>
 178   bool
 179   lexicographical_compare_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, Predicate pred, random_access_iterator_tag, random_access_iterator_tag)
 180   {
 181     if (_GLIBCXX_PARALLEL_CONDITION(true))
 182       {
 183         typedef iterator_traits<RandomAccessIterator1> traits1_type;
 184         typedef typename traits1_type::value_type value1_type;
 185
 186         typedef iterator_traits<RandomAccessIterator2> traits2_type;
 187         typedef typename traits2_type::value_type value2_type;
 188
 189         typedef __gnu_parallel::equal_from_less<Predicate, value1_type, value2_type> equal_type;
 190
 191         // Longer sequence in first place.
 192         if ((end1 - begin1) < (end2 - begin2))
 193           {
 194             typedef pair<RandomAccessIterator1, RandomAccessIterator2> pair_type;
 195             pair_type mm = mismatch_switch(begin1, end1, begin2, equal_type(pred), random_access_iterator_tag(), random_access_iterator_tag());
 196
 197             // Less because shorter.
 198             const bool lbs = mm.first == end1;
 199
 200             // Less because differing elements less.
 201             const bool lbdel = pred(*mm.first, *mm.second);
 202
 203             return lbs || lbdel;
 204           }
 205         else
 206           {
 207             typedef pair<RandomAccessIterator2, RandomAccessIterator1> pair_type;
 208             pair_type mm = mismatch_switch(begin2, end2, begin1, equal_type(pred), random_access_iterator_tag(), random_access_iterator_tag());
 209
 210             // Less because shorter.
 211             const bool lbs = mm.first != end2;
 212
 213             // Less because differing element less.
 214             const bool lbdel = pred(*mm.second, *mm.first);
 215
 216             return lbs && lbdel;
 217           }
 218       }
 219     else
 220       return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, begin2, end2, pred);
 221   }
 222
 223   // Public interface
 224   template<typename InputIterator1, typename InputIterator2>
 225   inline bool
 226   lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2)
 227   {
 228     typedef iterator_traits<InputIterator1> traits1_type;
 229     typedef typename traits1_type::value_type value1_type;
 230     typedef typename traits1_type::iterator_category iterator1_category;
 231
 232     typedef iterator_traits<InputIterator2> traits2_type;
 233     typedef typename traits2_type::value_type value2_type;
 234     typedef typename traits2_type::iterator_category iterator2_category;
 235     typedef __gnu_parallel::less<value1_type, value2_type> less_type;
 236
 237     return lexicographical_compare_switch(begin1, end1, begin2, end2, less_type(), iterator1_category(), iterator2_category());
 238   }
 239
 240   // Public interface
 241   template<typename InputIterator1, typename InputIterator2, typename Predicate>
 242   inline bool
 243   lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Predicate pred)
 244   {
 245     typedef iterator_traits<InputIterator1> traits1_type;
 246     typedef typename traits1_type::iterator_category iterator1_category;
 247
 248     typedef iterator_traits<InputIterator2> traits2_type;
 249     typedef typename traits2_type::iterator_category iterator2_category;
 250
 251     return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, iterator1_category(), iterator2_category());
 252   }
 253 } // end namespace
 254 } // end namespace
 255
 256 #endif /* _GLIBCXX_ALGOBASE_H */