The C and C++ Include Header Files

/usr/include/c++/11/pstl/parallel_impl.h


$ cat -n /usr/include/c++/11/pstl/parallel_impl.h

     1	// -*- C++ -*-
     2	//===-- parallel_impl.h ---------------------------------------------------===//
     3	//
     4	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
     5	// See https://llvm.org/LICENSE.txt for license information.
     6	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
     7	//
     8	//===----------------------------------------------------------------------===//
     9	
    10	#ifndef _PSTL_PARALLEL_IMPL_H
    11	#define _PSTL_PARALLEL_IMPL_H
    12	
    13	#include <atomic>
    14	// This header defines the minimum set of parallel routines required to support Parallel STL,
    15	// implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library
    16	
    17	namespace __pstl
    18	{
    19	namespace __internal
    20	{
    21	
    22	//------------------------------------------------------------------------
    23	// parallel_find
    24	//-----------------------------------------------------------------------
    25	/** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last)
    26	Each f[i,j) must return a value in [i,j). */
    27	template <class _ExecutionPolicy, class _Index, class _Brick, class _Compare>
    28	_Index
    29	__parallel_find(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first)
    30	{
    31	    typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
    32	    const _DifferenceType __n = __last - __first;
    33	    _DifferenceType __initial_dist = __b_first ? __n : -1;
    34	    std::atomic<_DifferenceType> __extremum(__initial_dist);
    35	    // TODO: find out what is better here: parallel_for or parallel_reduce
    36	    __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
    37	                                  [__comp, __f, __first, &__extremum](_Index __i, _Index __j) {
    38	                                      // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
    39	                                      // why using a shared variable scales fairly well in this situation.
    40	                                      if (__comp(__i - __first, __extremum))
    41	                                      {
    42	                                          _Index __res = __f(__i, __j);
    43	                                          // If not '__last' returned then we found what we want so put this to extremum
    44	                                          if (__res != __j)
    45	                                          {
    46	                                              const _DifferenceType __k = __res - __first;
    47	                                              for (_DifferenceType __old = __extremum; __comp(__k, __old);
    48	                                                   __old = __extremum)
    49	                                              {
    50	                                                  __extremum.compare_exchange_weak(__old, __k);
    51	                                              }
    52	                                          }
    53	                                      }
    54	                                  });
    55	    return __extremum != __initial_dist ? __first + __extremum : __last;
    56	}
    57	
    58	//------------------------------------------------------------------------
    59	// parallel_or
    60	//------------------------------------------------------------------------
    61	//! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last)
    62	template <class _ExecutionPolicy, class _Index, class _Brick>
    63	bool
    64	__parallel_or(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f)
    65	{
    66	    std::atomic<bool> __found(false);
    67	    __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
    68	                                  [__f, &__found](_Index __i, _Index __j) {
    69	                                      if (!__found.load(std::memory_order_relaxed) && __f(__i, __j))
    70	                                      {
    71	                                          __found.store(true, std::memory_order_relaxed);
    72	                                          __par_backend::__cancel_execution();
    73	                                      }
    74	                                  });
    75	    return __found;
    76	}
    77	
    78	} // namespace __internal
    79	} // namespace __pstl
    80	
    81	#endif /* _PSTL_PARALLEL_IMPL_H */