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
17namespace __pstl
18{
19namespace __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)
26Each f[i,j) must return a value in [i,j). */
27template <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)
62template <class _ExecutionPolicy, class _Index, class _Brick>
63bool
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(m: std::memory_order_relaxed) && __f(__i, __j))
70 {
71 __found.store(i: true, m: 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 */
82

source code of include/c++/11/pstl/parallel_impl.h