The C and C++ Include Header Files

/usr/include/c++/11/parallel/algobase.h


$ cat -n /usr/include/c++/11/parallel/algobase.h

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2021 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	    _GLIBCXX20_CONSTEXPR
   218	    inline bool
   219	    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
   220	    {
   221	#if __cplusplus > 201703L
   222	      if (std::is_constant_evaluated())
   223		return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
   224	#endif
   225	
   226	      return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
   227	              == __end1;
   228	    }
   229	
   230	  // Public interface
   231	  template<typename _IIter1, typename _IIter2, typename _Predicate>
   232	    _GLIBCXX20_CONSTEXPR
   233	    inline bool
   234	    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
   235	          _Predicate __pred)
   236	    {
   237	#if __cplusplus > 201703L
   238	      if (std::is_constant_evaluated())
   239		return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
   240	#endif
   241	
   242	      return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
   243	              == __end1;
   244	    }
   245	
   246	#if __cplusplus > 201103L
   247	  // Sequential fallback
   248	  template<typename _IIter1, typename _IIter2>
   249	    inline bool
   250	    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
   251		  __gnu_parallel::sequential_tag)
   252	    {
   253	      return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
   254	    }
   255	
   256	  // Sequential fallback
   257	  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
   258	    inline bool
   259	    equal(_IIter1 __begin1, _IIter1 __end1,
   260		  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
   261		  __gnu_parallel::sequential_tag)
   262	    {
   263	      return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
   264					   __binary_pred);
   265	    }
   266	
   267	  // Sequential fallback for input iterator case
   268	  template<typename _IIter1, typename _IIter2,
   269	           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
   270	    inline bool
   271	    __equal_switch(_IIter1 __begin1, _IIter1 __end1,
   272			   _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
   273			   _IteratorTag1, _IteratorTag2)
   274	    {
   275	      return _GLIBCXX_STD_A::equal(__begin1, __end1,
   276					   __begin2, __end2, __pred);
   277	    }
   278	
   279	  // Parallel equal for random access iterators
   280	  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
   281	    inline bool
   282	    __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
   283			   _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred, 
   284			   random_access_iterator_tag, random_access_iterator_tag)
   285	    {
   286	      if (_GLIBCXX_PARALLEL_CONDITION(true))
   287	        {
   288		  if (std::distance(__begin1, __end1)
   289		      != std::distance(__begin2, __end2))
   290		    return false;
   291	
   292		  return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
   293						  __pred).first == __end1;
   294	        }
   295	      else
   296	        return _GLIBCXX_STD_A::equal(__begin1, __end1,
   297					     __begin2, __end2, __pred);
   298	    }
   299	
   300	  template<typename _IIter1, typename _IIter2>
   301	    _GLIBCXX20_CONSTEXPR
   302	    inline bool
   303	    equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
   304	    {
   305	#if __cplusplus > 201703L
   306	      if (std::is_constant_evaluated())
   307		return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
   308	#endif
   309	
   310	      typedef __gnu_parallel::_EqualTo<
   311		typename std::iterator_traits<_IIter1>::value_type,
   312		typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
   313	
   314	      return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
   315				    std::__iterator_category(__begin1),
   316				    std::__iterator_category(__begin2));
   317	    }
   318	
   319	  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
   320	    _GLIBCXX20_CONSTEXPR
   321	    inline bool
   322	    equal(_IIter1 __begin1, _IIter1 __end1,
   323		  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
   324	    {
   325	#if __cplusplus > 201703L
   326	      if (std::is_constant_evaluated())
   327		return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
   328					     __binary_pred);
   329	#endif
   330	
   331	      return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
   332				    std::__iterator_category(__begin1),
   333				    std::__iterator_category(__begin2));
   334	    }
   335	#endif // C++14
   336	
   337	  // Sequential fallback
   338	  template<typename _IIter1, typename _IIter2>
   339	    inline bool
   340	    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
   341	                            _IIter2 __begin2, _IIter2 __end2, 
   342	                            __gnu_parallel::sequential_tag)
   343	    { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
   344	                                                     __begin2, __end2); }
   345	
   346	  // Sequential fallback
   347	  template<typename _IIter1, typename _IIter2, typename _Predicate>
   348	    inline bool
   349	    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 
   350	                            _IIter2 __begin2, _IIter2 __end2, 
   351	                            _Predicate __pred, __gnu_parallel::sequential_tag)
   352	    { return _GLIBCXX_STD_A::lexicographical_compare(
   353	               __begin1, __end1, __begin2, __end2, __pred); }
   354	
   355	  // Sequential fallback for input iterator case
   356	  template<typename _IIter1, typename _IIter2,
   357	           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
   358	    inline bool
   359	    __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
   360	                                     _IIter2 __begin2, _IIter2 __end2, 
   361	                                     _Predicate __pred,
   362	                                     _IteratorTag1, _IteratorTag2)
   363	    { return _GLIBCXX_STD_A::lexicographical_compare(
   364	               __begin1, __end1, __begin2, __end2, __pred); }
   365	
   366	  // Parallel lexicographical_compare for random access iterators
   367	  // Limitation: Both valuetypes must be the same
   368	  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
   369	    bool
   370	    __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
   371	                                     _RAIter2 __begin2, _RAIter2 __end2,
   372	                                     _Predicate __pred,
   373	                                     random_access_iterator_tag, 
   374	                                     random_access_iterator_tag)
   375	    {
   376	      if (_GLIBCXX_PARALLEL_CONDITION(true))
   377	        {
   378	          typedef iterator_traits<_RAIter1> _TraitsType1;
   379	          typedef typename _TraitsType1::value_type _ValueType1;
   380	
   381	          typedef iterator_traits<_RAIter2> _TraitsType2;
   382	          typedef typename _TraitsType2::value_type _ValueType2;
   383	
   384	          typedef __gnu_parallel::
   385	                  _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
   386	                  _EqualFromLessCompare;
   387	
   388	          // Longer sequence in first place.
   389	          if ((__end1 - __begin1) < (__end2 - __begin2))
   390	            {
   391	              typedef pair<_RAIter1, _RAIter2> _SpotType;
   392	              _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 
   393	                                             _EqualFromLessCompare(__pred), 
   394	                                             random_access_iterator_tag(), 
   395	                                             random_access_iterator_tag());
   396	
   397	              return (__mm.first == __end1)
   398	                        || bool(__pred(*__mm.first, *__mm.second));
   399	            }
   400	          else
   401	            {
   402	              typedef pair<_RAIter2, _RAIter1> _SpotType;
   403	              _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 
   404	                                             _EqualFromLessCompare(__pred), 
   405	                                             random_access_iterator_tag(), 
   406	                                             random_access_iterator_tag());
   407	
   408	              return (__mm.first != __end2)
   409	                        && bool(__pred(*__mm.second, *__mm.first));
   410	            }
   411	        }
   412	      else
   413	        return _GLIBCXX_STD_A::lexicographical_compare(
   414	                 __begin1, __end1, __begin2, __end2, __pred);
   415	    }
   416	
   417	  // Public interface
   418	  template<typename _IIter1, typename _IIter2>
   419	    _GLIBCXX20_CONSTEXPR
   420	    inline bool
   421	    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
   422	                            _IIter2 __begin2, _IIter2 __end2)
   423	    {
   424	#if __cplusplus > 201703L
   425	      if (std::is_constant_evaluated())
   426		return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
   427							       __begin2, __end2);
   428	#endif
   429	
   430	      typedef iterator_traits<_IIter1> _TraitsType1;
   431	      typedef typename _TraitsType1::value_type _ValueType1;
   432	      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
   433	
   434	      typedef iterator_traits<_IIter2> _TraitsType2;
   435	      typedef typename _TraitsType2::value_type _ValueType2;
   436	      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
   437	      typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
   438	
   439	      return __lexicographical_compare_switch(
   440	               __begin1, __end1, __begin2, __end2, _LessType(),
   441	               _IteratorCategory1(), _IteratorCategory2());
   442	    }
   443	
   444	  // Public interface
   445	  template<typename _IIter1, typename _IIter2, typename _Predicate>
   446	    _GLIBCXX20_CONSTEXPR
   447	    inline bool
   448	    lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
   449	                            _IIter2 __begin2, _IIter2 __end2,
   450	                            _Predicate __pred)
   451	    {
   452	#if __cplusplus > 201703L
   453	      if (std::is_constant_evaluated())
   454		return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
   455							       __begin2, __end2,
   456							       __pred);
   457	#endif
   458	
   459	      typedef iterator_traits<_IIter1> _TraitsType1;
   460	      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
   461	
   462	      typedef iterator_traits<_IIter2> _TraitsType2;
   463	      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
   464	
   465	      return __lexicographical_compare_switch(
   466	               __begin1, __end1, __begin2, __end2, __pred,
   467	               _IteratorCategory1(), _IteratorCategory2());
   468	    }
   469	
   470	#if __cpp_lib_three_way_comparison
   471	  using _GLIBCXX_STD_A::lexicographical_compare_three_way;
   472	#endif
   473	} // end namespace
   474	} // end namespace
   475	
   476	#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */