Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2007-2015 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 __gnu_parallel::_EqualTo<
  98.         typename std::iterator_traits<_IIter1>::value_type,
  99.         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
  100.  
  101.       return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
  102.                                std::__iterator_category(__begin1),
  103.                                std::__iterator_category(__begin2));
  104.     }
  105.  
  106.   // Public interface
  107.   template<typename _IIter1, typename _IIter2, typename _Predicate>
  108.     inline pair<_IIter1, _IIter2>
  109.     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  110.              _Predicate __pred)
  111.     {
  112.       return __mismatch_switch(__begin1, __end1, __begin2, __pred,
  113.                                std::__iterator_category(__begin1),
  114.                                std::__iterator_category(__begin2));
  115.     }
  116.  
  117. #if __cplusplus > 201103L
  118.   // Sequential fallback.
  119.   template<typename _InputIterator1, typename _InputIterator2>
  120.     inline pair<_InputIterator1, _InputIterator2>
  121.     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
  122.              _InputIterator2 __first2, _InputIterator2 __last2,
  123.              __gnu_parallel::sequential_tag)
  124.     { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
  125.  
  126.   // Sequential fallback.
  127.   template<typename _InputIterator1, typename _InputIterator2,
  128.            typename _BinaryPredicate>
  129.     inline pair<_InputIterator1, _InputIterator2>
  130.     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
  131.              _InputIterator2 __first2, _InputIterator2 __last2,
  132.              _BinaryPredicate __binary_pred,
  133.              __gnu_parallel::sequential_tag)
  134.     {
  135.       return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
  136.                                       __binary_pred);
  137.     }
  138.  
  139.   // Sequential fallback for input iterator case
  140.   template<typename _IIter1, typename _IIter2,
  141.            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  142.     inline pair<_IIter1, _IIter2>
  143.     __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
  144.                       _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
  145.                       _IteratorTag1, _IteratorTag2)
  146.     {
  147.       return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
  148.                                       __begin2, __end2, __pred);
  149.     }
  150.  
  151.   // Parallel mismatch for random access iterators
  152.   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
  153.     pair<_RAIter1, _RAIter2>
  154.     __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
  155.                       _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
  156.                       random_access_iterator_tag, random_access_iterator_tag)
  157.     {
  158.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  159.         {
  160.           if ((__end2 - __begin2) < (__end1 - __begin1))
  161.             __end1 = __begin1 + (__end2 - __begin2);
  162.  
  163.           _RAIter1 __res =
  164.             __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
  165.                                             __gnu_parallel::
  166.                                             __mismatch_selector()).first;
  167.           return make_pair(__res , __begin2 + (__res - __begin1));
  168.         }
  169.       else
  170.         return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
  171.                                         __begin2, __end2, __pred);
  172.     }
  173.  
  174.   template<typename _IIter1, typename _IIter2>
  175.     inline pair<_IIter1, _IIter2>
  176.     mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
  177.     {
  178.       typedef __gnu_parallel::_EqualTo<
  179.         typename std::iterator_traits<_IIter1>::value_type,
  180.         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
  181.  
  182.       return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
  183.                                std::__iterator_category(__begin1),
  184.                                std::__iterator_category(__begin2));
  185.     }
  186.  
  187.   template<typename _InputIterator1, typename _InputIterator2,
  188.            typename _BinaryPredicate>
  189.     inline pair<_InputIterator1, _InputIterator2>
  190.     mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
  191.              _InputIterator2 __begin2, _InputIterator2 __end2,
  192.              _BinaryPredicate __binary_pred)
  193.     {
  194.       return __mismatch_switch(__begin1, __end1, __begin2, __end2,
  195.                                __binary_pred,
  196.                                std::__iterator_category(__begin1),
  197.                                std::__iterator_category(__begin2));
  198.     }
  199. #endif
  200.  
  201.   // Sequential fallback
  202.   template<typename _IIter1, typename _IIter2>
  203.     inline bool
  204.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  205.           __gnu_parallel::sequential_tag)
  206.     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
  207.  
  208.   // Sequential fallback
  209.   template<typename _IIter1, typename _IIter2, typename _Predicate>
  210.     inline bool
  211.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  212.           _Predicate __pred, __gnu_parallel::sequential_tag)
  213.     { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
  214.  
  215.   // Public interface
  216.   template<typename _IIter1, typename _IIter2>
  217.     inline bool
  218.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
  219.     {
  220.       return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
  221.               == __end1;
  222.     }
  223.  
  224.   // Public interface
  225.   template<typename _IIter1, typename _IIter2, typename _Predicate>
  226.     inline bool
  227.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  228.           _Predicate __pred)
  229.     {
  230.       return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
  231.               == __end1;
  232.     }
  233.  
  234. #if __cplusplus > 201103L
  235.   // Sequential fallback
  236.   template<typename _IIter1, typename _IIter2>
  237.     inline bool
  238.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
  239.           __gnu_parallel::sequential_tag)
  240.     {
  241.       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
  242.     }
  243.  
  244.   // Sequential fallback
  245.   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
  246.     inline bool
  247.     equal(_IIter1 __begin1, _IIter1 __end1,
  248.           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
  249.           __gnu_parallel::sequential_tag)
  250.     {
  251.       return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
  252.                                    __binary_pred);
  253.     }
  254.  
  255.   // Sequential fallback for input iterator case
  256.   template<typename _IIter1, typename _IIter2,
  257.            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  258.     inline bool
  259.     __equal_switch(_IIter1 __begin1, _IIter1 __end1,
  260.                    _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
  261.                    _IteratorTag1, _IteratorTag2)
  262.     {
  263.       return _GLIBCXX_STD_A::equal(__begin1, __end1,
  264.                                    __begin2, __end2, __pred);
  265.     }
  266.  
  267.   // Parallel equal for random access iterators
  268.   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
  269.     inline bool
  270.     __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
  271.                    _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
  272.                    random_access_iterator_tag, random_access_iterator_tag)
  273.     {
  274.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  275.         {
  276.           if (std::distance(__begin1, __end1)
  277.               != std::distance(__begin2, __end2))
  278.             return false;
  279.  
  280.           return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
  281.                                           __pred).first == __end1;
  282.         }
  283.       else
  284.         return _GLIBCXX_STD_A::equal(__begin1, __end1,
  285.                                      __begin2, __end2, __pred);
  286.     }
  287.  
  288.   template<typename _IIter1, typename _IIter2>
  289.     inline bool
  290.     equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
  291.     {
  292.       typedef __gnu_parallel::_EqualTo<
  293.         typename std::iterator_traits<_IIter1>::value_type,
  294.         typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
  295.  
  296.       return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
  297.                             std::__iterator_category(__begin1),
  298.                             std::__iterator_category(__begin2));
  299.     }
  300.  
  301.   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
  302.     inline bool
  303.     equal(_IIter1 __begin1, _IIter1 __end1,
  304.           _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
  305.     {
  306.       return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
  307.                             std::__iterator_category(__begin1),
  308.                             std::__iterator_category(__begin2));
  309.     }
  310. #endif
  311.  
  312.   // Sequential fallback
  313.   template<typename _IIter1, typename _IIter2>
  314.     inline bool
  315.     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
  316.                             _IIter2 __begin2, _IIter2 __end2,
  317.                             __gnu_parallel::sequential_tag)
  318.     { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
  319.                                                      __begin2, __end2); }
  320.  
  321.   // Sequential fallback
  322.   template<typename _IIter1, typename _IIter2, typename _Predicate>
  323.     inline bool
  324.     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
  325.                             _IIter2 __begin2, _IIter2 __end2,
  326.                             _Predicate __pred, __gnu_parallel::sequential_tag)
  327.     { return _GLIBCXX_STD_A::lexicographical_compare(
  328.                __begin1, __end1, __begin2, __end2, __pred); }
  329.  
  330.   // Sequential fallback for input iterator case
  331.   template<typename _IIter1, typename _IIter2,
  332.            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  333.     inline bool
  334.     __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
  335.                                      _IIter2 __begin2, _IIter2 __end2,
  336.                                      _Predicate __pred,
  337.                                      _IteratorTag1, _IteratorTag2)
  338.     { return _GLIBCXX_STD_A::lexicographical_compare(
  339.                __begin1, __end1, __begin2, __end2, __pred); }
  340.  
  341.   // Parallel lexicographical_compare for random access iterators
  342.   // Limitation: Both valuetypes must be the same
  343.   template<typename _RAIter1, typename _RAIter2, typename _Predicate>
  344.     bool
  345.     __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
  346.                                      _RAIter2 __begin2, _RAIter2 __end2,
  347.                                      _Predicate __pred,
  348.                                      random_access_iterator_tag,
  349.                                      random_access_iterator_tag)
  350.     {
  351.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  352.         {
  353.           typedef iterator_traits<_RAIter1> _TraitsType1;
  354.           typedef typename _TraitsType1::value_type _ValueType1;
  355.  
  356.           typedef iterator_traits<_RAIter2> _TraitsType2;
  357.           typedef typename _TraitsType2::value_type _ValueType2;
  358.  
  359.           typedef __gnu_parallel::
  360.                   _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
  361.                   _EqualFromLessCompare;
  362.  
  363.           // Longer sequence in first place.
  364.           if ((__end1 - __begin1) < (__end2 - __begin2))
  365.             {
  366.               typedef pair<_RAIter1, _RAIter2> _SpotType;
  367.               _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
  368.                                              _EqualFromLessCompare(__pred),
  369.                                              random_access_iterator_tag(),
  370.                                              random_access_iterator_tag());
  371.  
  372.               return (__mm.first == __end1)
  373.                         || bool(__pred(*__mm.first, *__mm.second));
  374.             }
  375.           else
  376.             {
  377.               typedef pair<_RAIter2, _RAIter1> _SpotType;
  378.               _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
  379.                                              _EqualFromLessCompare(__pred),
  380.                                              random_access_iterator_tag(),
  381.                                              random_access_iterator_tag());
  382.  
  383.               return (__mm.first != __end2)
  384.                         && bool(__pred(*__mm.second, *__mm.first));
  385.             }
  386.         }
  387.       else
  388.         return _GLIBCXX_STD_A::lexicographical_compare(
  389.                  __begin1, __end1, __begin2, __end2, __pred);
  390.     }
  391.  
  392.   // Public interface
  393.   template<typename _IIter1, typename _IIter2>
  394.     inline bool
  395.     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
  396.                             _IIter2 __begin2, _IIter2 __end2)
  397.     {
  398.       typedef iterator_traits<_IIter1> _TraitsType1;
  399.       typedef typename _TraitsType1::value_type _ValueType1;
  400.       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
  401.  
  402.       typedef iterator_traits<_IIter2> _TraitsType2;
  403.       typedef typename _TraitsType2::value_type _ValueType2;
  404.       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
  405.       typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
  406.  
  407.       return __lexicographical_compare_switch(
  408.                __begin1, __end1, __begin2, __end2, _LessType(),
  409.                _IteratorCategory1(), _IteratorCategory2());
  410.     }
  411.  
  412.   // Public interface
  413.   template<typename _IIter1, typename _IIter2, typename _Predicate>
  414.     inline bool
  415.     lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
  416.                             _IIter2 __begin2, _IIter2 __end2,
  417.                             _Predicate __pred)
  418.     {
  419.       typedef iterator_traits<_IIter1> _TraitsType1;
  420.       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
  421.  
  422.       typedef iterator_traits<_IIter2> _TraitsType2;
  423.       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
  424.  
  425.       return __lexicographical_compare_switch(
  426.                __begin1, __end1, __begin2, __end2, __pred,
  427.                _IteratorCategory1(), _IteratorCategory2());
  428.     }
  429. } // end namespace
  430. } // end namespace
  431.  
  432. #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
  433.