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