libstdc++-v3/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 _IIter1, typename _IIter2>
  54     inline pair<_IIter1, _IIter2>
  55     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  56              __gnu_parallel::sequential_tag)
  57     { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2); }
  58
  59   // Sequential fallback
  60   template<typename _IIter1, typename _IIter2,
  61            typename _Predicate>
  62     inline pair<_IIter1, _IIter2>
  63     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __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 _IIter1, typename _IIter2,
  69            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  70     inline pair<_IIter1, _IIter2>
  71     __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
  72                     _IIter2 __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 _RAIter1, typename _RAIter2,
  78            typename _Predicate>
  79     pair<_RAIter1, _RAIter2>
  80     __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
  81                     _RAIter2 __begin2, _Predicate __pred,
  82                     random_access_iterator_tag, random_access_iterator_tag)
  83     {
  84       if (_GLIBCXX_PARALLEL_CONDITION(true))
  85         {
  86           _RAIter1 __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 _IIter1, typename _IIter2>
  98     inline pair<_IIter1, _IIter2>
  99     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
 100     {
 101       typedef std::iterator_traits<_IIter1> iterator1_traits;
 102       typedef std::iterator_traits<_IIter2> iterator2_traits;
 103       typedef typename iterator1_traits::value_type _ValueType1;
 104       typedef typename iterator2_traits::value_type _ValueType2;
 105       typedef typename iterator1_traits::iterator_category _IteratorCategory1;
 106       typedef typename iterator2_traits::iterator_category _IteratorCategory2;
 107
 108       typedef __gnu_parallel::equal_to<_ValueType1, _ValueType2> equal_to_type;
 109
 110       return __mismatch_switch(__begin1, __end1, __begin2, equal_to_type(),
 111                              _IteratorCategory1(), _IteratorCategory2());
 112     }
 113
 114   // Public interface
 115   template<typename _IIter1, typename _IIter2,
 116            typename _Predicate>
 117     inline pair<_IIter1, _IIter2>
 118     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 119              _Predicate __pred)
 120     {
 121       typedef std::iterator_traits<_IIter1> iterator1_traits;
 122       typedef std::iterator_traits<_IIter2> iterator2_traits;
 123       typedef typename iterator1_traits::iterator_category _IteratorCategory1;
 124       typedef typename iterator2_traits::iterator_category _IteratorCategory2;
 125
 126       return __mismatch_switch(__begin1, __end1, __begin2, __pred, _IteratorCategory1(),
 127                              _IteratorCategory2());
 128     }
 129
 130   // Sequential fallback
 131   template<typename _IIter1, typename _IIter2>
 132     inline bool
 133     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 134           __gnu_parallel::sequential_tag)
 135     { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2); }
 136
 137   // Sequential fallback
 138   template<typename _IIter1, typename _IIter2,
 139            typename _Predicate>
 140     inline bool
 141     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __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 _IIter1, typename _IIter2>
 147     inline bool
 148     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
 149     { return mismatch(__begin1, __end1, __begin2).first == __end1; }
 150
 151   // Public interface
 152   template<typename _IIter1, typename _IIter2,
 153            typename _Predicate>
 154     inline bool
 155     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 156           _Predicate __pred)
 157     { return mismatch(__begin1, __end1, __begin2, __pred).first == __end1; }
 158
 159   // Sequential fallback
 160   template<typename _IIter1, typename _IIter2>
 161     inline bool
 162     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 163                             _IIter2 __begin2, _IIter2 __end2,
 164                             __gnu_parallel::sequential_tag)
 165     { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
 166                                                      __begin2, __end2); }
 167
 168   // Sequential fallback
 169   template<typename _IIter1, typename _IIter2,
 170            typename _Predicate>
 171     inline bool
 172     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 173                             _IIter2 __begin2, _IIter2 __end2,
 174                             _Predicate __pred, __gnu_parallel::sequential_tag)
 175     { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
 176                                                      __begin2, __end2, __pred); }
 177
 178   // Sequential fallback for input iterator case
 179   template<typename _IIter1, typename _IIter2,
 180            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
 181     inline bool
 182     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
 183                                    _IIter2 __begin2, _IIter2 __end2,
 184                                    _Predicate __pred, _IteratorTag1, _IteratorTag2)
 185     { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
 186                                                      __begin2, __end2, __pred); }
 187
 188   // Parallel lexicographical_compare for random access iterators
 189   // Limitation: Both valuetypes must be the same
 190   template<typename _RAIter1, typename _RAIter2,
 191            typename _Predicate>
 192     bool
 193     __lexicographical_compare_switch(_RAIter1 __begin1,
 194                                    _RAIter1 __end1,
 195                                    _RAIter2 __begin2,
 196                                    _RAIter2 __end2, _Predicate __pred,
 197                                    random_access_iterator_tag,
 198                                    random_access_iterator_tag)
 199     {
 200       if (_GLIBCXX_PARALLEL_CONDITION(true))
 201         {
 202           typedef iterator_traits<_RAIter1> _TraitsType1;
 203           typedef typename _TraitsType1::value_type _ValueType1;
 204
 205           typedef iterator_traits<_RAIter2> _TraitsType2;
 206           typedef typename _TraitsType2::value_type _ValueType2;
 207
 208           typedef __gnu_parallel::_EqualFromLess<_Predicate, _ValueType1,
 209                                                   _ValueType2> _EqualFromLessCompare;
 210
 211           // Longer sequence in first place.
 212           if ((__end1 - __begin1) < (__end2 - __begin2))
 213             {
 214               typedef pair<_RAIter1, _RAIter2>
 215                 _SpotType;
 216               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
 217                                              _EqualFromLessCompare(__pred),
 218                                              random_access_iterator_tag(),
 219                                              random_access_iterator_tag());
 220
 221               return (__mm.first == __end1) || bool(__pred(*__mm.first, *__mm.second));
 222             }
 223           else
 224             {
 225               typedef pair<_RAIter2, _RAIter1>
 226                 _SpotType;
 227               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
 228                                              _EqualFromLessCompare(__pred),
 229                                              random_access_iterator_tag(),
 230                                              random_access_iterator_tag());
 231
 232               return (__mm.first != __end2) && bool(__pred(*__mm.second, *__mm.first));
 233             }
 234         }
 235       else
 236         return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
 237                                                        __begin2, __end2, __pred);
 238     }
 239
 240   // Public interface
 241   template<typename _IIter1, typename _IIter2>
 242     inline bool
 243     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 244                             _IIter2 __begin2, _IIter2 __end2)
 245     {
 246       typedef iterator_traits<_IIter1> _TraitsType1;
 247       typedef typename _TraitsType1::value_type _ValueType1;
 248       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 249
 250       typedef iterator_traits<_IIter2> _TraitsType2;
 251       typedef typename _TraitsType2::value_type _ValueType2;
 252       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 253       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
 254
 255       return __lexicographical_compare_switch(__begin1, __end1, __begin2, __end2,
 256                                             _LessType(), _IteratorCategory1(),
 257                                             _IteratorCategory2());
 258     }
 259
 260   // Public interface
 261   template<typename _IIter1, typename _IIter2,
 262            typename _Predicate>
 263     inline bool
 264     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 265                             _IIter2 __begin2, _IIter2 __end2,
 266                             _Predicate __pred)
 267     {
 268       typedef iterator_traits<_IIter1> _TraitsType1;
 269       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 270
 271       typedef iterator_traits<_IIter2> _TraitsType2;
 272       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 273
 274       return __lexicographical_compare_switch(__begin1, __end1, __begin2, __end2, __pred,
 275                                             _IteratorCategory1(),
 276                                             _IteratorCategory2());
 277     }
 278 } // end namespace
 279 } // end namespace
 280
 281 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */