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

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