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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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/algorithmfwd.h>
  42 #include <parallel/find.h>
  43 #include <parallel/find_selectors.h>
  44
  45 namespace std _GLIBCXX_VISIBILITY(default)
  46 {
  47 namespace __parallel
  48 {
  49   // NB: equal and lexicographical_compare require mismatch.
  50
  51   // Sequential fallback
  52   template<typename _IIter1, typename _IIter2>
  53     inline pair<_IIter1, _IIter2>
  54     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  55              __gnu_parallel::sequential_tag)
  56     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }
  57
  58   // Sequential fallback
  59   template<typename _IIter1, typename _IIter2, typename _Predicate>
  60     inline pair<_IIter1, _IIter2>
  61     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  62              _Predicate __pred, __gnu_parallel::sequential_tag)
  63     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
  64
  65   // Sequential fallback for input iterator case
  66   template<typename _IIter1, typename _IIter2,
  67            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  68     inline pair<_IIter1, _IIter2>
  69     __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  70                       _Predicate __pred, _IteratorTag1, _IteratorTag2)
  71     { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
  72
  73   // Parallel mismatch for random access iterators
  74   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
  75     pair<_RAIter1, _RAIter2>
  76     __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
  77                       _RAIter2 __begin2, _Predicate __pred,
  78                       random_access_iterator_tag, random_access_iterator_tag)
  79     {
  80       if (_GLIBCXX_PARALLEL_CONDITION(true))
  81         {
  82           _RAIter1 __res =
  83             __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
  84                                             __gnu_parallel::
  85                                             __mismatch_selector()).first;
  86           return make_pair(__res , __begin2 + (__res - __begin1));
  87         }
  88       else
  89         return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
  90     }
  91
  92   // Public interface
  93   template<typename _IIter1, typename _IIter2>
  94     inline pair<_IIter1, _IIter2>
  95     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
  96     {
  97       typedef std::iterator_traits<_IIter1> _Iterator1Traits;
  98       typedef std::iterator_traits<_IIter2> _Iterator2Traits;
  99       typedef typename _Iterator1Traits::value_type _ValueType1;
 100       typedef typename _Iterator2Traits::value_type _ValueType2;
 101       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
 102       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
 103
 104       typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
 105
 106       return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
 107                                _IteratorCategory1(), _IteratorCategory2());
 108     }
 109
 110   // Public interface
 111   template<typename _IIter1, typename _IIter2, typename _Predicate>
 112     inline pair<_IIter1, _IIter2>
 113     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 114              _Predicate __pred)
 115     {
 116       typedef std::iterator_traits<_IIter1> _Iterator1Traits;
 117       typedef std::iterator_traits<_IIter2> _Iterator2Traits;
 118       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
 119       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
 120
 121       return __mismatch_switch(__begin1, __end1, __begin2, __pred,
 122                                _IteratorCategory1(), _IteratorCategory2());
 123     }
 124
 125   // Sequential fallback
 126   template<typename _IIter1, typename _IIter2>
 127     inline bool
 128     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 129           __gnu_parallel::sequential_tag)
 130     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
 131
 132   // Sequential fallback
 133   template<typename _IIter1, typename _IIter2, typename _Predicate>
 134     inline bool
 135     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 136           _Predicate __pred, __gnu_parallel::sequential_tag)
 137     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
 138
 139   // Public interface
 140   template<typename _IIter1, typename _IIter2>
 141     inline bool
 142     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
 143     {
 144       return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
 145               == __end1;
 146     }
 147
 148   // Public interface
 149   template<typename _IIter1, typename _IIter2, typename _Predicate>
 150     inline bool
 151     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
 152           _Predicate __pred)
 153     {
 154       return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
 155               == __end1;
 156     }
 157
 158   // Sequential fallback
 159   template<typename _IIter1, typename _IIter2>
 160     inline bool
 161     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 162                             _IIter2 __begin2, _IIter2 __end2,
 163                             __gnu_parallel::sequential_tag)
 164     { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
 165                                                      __begin2, __end2); }
 166
 167   // Sequential fallback
 168   template<typename _IIter1, typename _IIter2, typename _Predicate>
 169     inline bool
 170     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 171                             _IIter2 __begin2, _IIter2 __end2,
 172                             _Predicate __pred, __gnu_parallel::sequential_tag)
 173     { return _GLIBCXX_STD_A::lexicographical_compare(
 174                __begin1, __end1, __begin2, __end2, __pred); }
 175
 176   // Sequential fallback for input iterator case
 177   template<typename _IIter1, typename _IIter2,
 178            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
 179     inline bool
 180     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
 181                                      _IIter2 __begin2, _IIter2 __end2,
 182                                      _Predicate __pred,
 183                                      _IteratorTag1, _IteratorTag2)
 184     { return _GLIBCXX_STD_A::lexicographical_compare(
 185                __begin1, __end1, __begin2, __end2, __pred); }
 186
 187   // Parallel lexicographical_compare for random access iterators
 188   // Limitation: Both valuetypes must be the same
 189   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
 190     bool
 191     __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
 192                                      _RAIter2 __begin2, _RAIter2 __end2,
 193                                      _Predicate __pred,
 194                                      random_access_iterator_tag,
 195                                      random_access_iterator_tag)
 196     {
 197       if (_GLIBCXX_PARALLEL_CONDITION(true))
 198         {
 199           typedef iterator_traits<_RAIter1> _TraitsType1;
 200           typedef typename _TraitsType1::value_type _ValueType1;
 201
 202           typedef iterator_traits<_RAIter2> _TraitsType2;
 203           typedef typename _TraitsType2::value_type _ValueType2;
 204
 205           typedef __gnu_parallel::
 206                   _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
 207                   _EqualFromLessCompare;
 208
 209           // Longer sequence in first place.
 210           if ((__end1 - __begin1) < (__end2 - __begin2))
 211             {
 212               typedef pair<_RAIter1, _RAIter2> _SpotType;
 213               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
 214                                              _EqualFromLessCompare(__pred),
 215                                              random_access_iterator_tag(),
 216                                              random_access_iterator_tag());
 217
 218               return (__mm.first == __end1)
 219                         || bool(__pred(*__mm.first, *__mm.second));
 220             }
 221           else
 222             {
 223               typedef pair<_RAIter2, _RAIter1> _SpotType;
 224               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
 225                                              _EqualFromLessCompare(__pred),
 226                                              random_access_iterator_tag(),
 227                                              random_access_iterator_tag());
 228
 229               return (__mm.first != __end2)
 230                         && bool(__pred(*__mm.second, *__mm.first));
 231             }
 232         }
 233       else
 234         return _GLIBCXX_STD_A::lexicographical_compare(
 235                  __begin1, __end1, __begin2, __end2, __pred);
 236     }
 237
 238   // Public interface
 239   template<typename _IIter1, typename _IIter2>
 240     inline bool
 241     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 242                             _IIter2 __begin2, _IIter2 __end2)
 243     {
 244       typedef iterator_traits<_IIter1> _TraitsType1;
 245       typedef typename _TraitsType1::value_type _ValueType1;
 246       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 247
 248       typedef iterator_traits<_IIter2> _TraitsType2;
 249       typedef typename _TraitsType2::value_type _ValueType2;
 250       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 251       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
 252
 253       return __lexicographical_compare_switch(
 254                __begin1, __end1, __begin2, __end2, _LessType(),
 255                _IteratorCategory1(), _IteratorCategory2());
 256     }
 257
 258   // Public interface
 259   template<typename _IIter1, typename _IIter2, typename _Predicate>
 260     inline bool
 261     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
 262                             _IIter2 __begin2, _IIter2 __end2,
 263                             _Predicate __pred)
 264     {
 265       typedef iterator_traits<_IIter1> _TraitsType1;
 266       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 267
 268       typedef iterator_traits<_IIter2> _TraitsType2;
 269       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 270
 271       return __lexicographical_compare_switch(
 272                __begin1, __end1, __begin2, __end2, __pred,
 273                _IteratorCategory1(), _IteratorCategory2());
 274     }
 275 } // end namespace
 276 } // end namespace
 277
 278 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */