1 // -*- C++ -*-
2 // -*-===----------------------------------------------------------------------===//
3 //
4 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5 //
6 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
7 // See https://llvm.org/LICENSE.txt for license information.
8 //
9 //===----------------------------------------------------------------------===//
10
11 #ifndef _PSTL_INTERNAL_OMP_PARALLEL_MERGE_H
12 #define _PSTL_INTERNAL_OMP_PARALLEL_MERGE_H
13
14 #include "util.h"
15
16 namespace __pstl
17 {
18 namespace __omp_backend
19 {
20
21 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
22 typename _Compare, typename _LeafMerge>
23 void
__parallel_merge_body(std::size_t __size_x,std::size_t __size_y,_RandomAccessIterator1 __xs,_RandomAccessIterator1 __xe,_RandomAccessIterator2 __ys,_RandomAccessIterator2 __ye,_RandomAccessIterator3 __zs,_Compare __comp,_LeafMerge __leaf_merge)24 __parallel_merge_body(std::size_t __size_x, std::size_t __size_y, _RandomAccessIterator1 __xs,
25 _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, _RandomAccessIterator2 __ye,
26 _RandomAccessIterator3 __zs, _Compare __comp, _LeafMerge __leaf_merge)
27 {
28
29 if (__size_x + __size_y <= __omp_backend::__default_chunk_size)
30 {
31 __leaf_merge(__xs, __xe, __ys, __ye, __zs, __comp);
32 return;
33 }
34
35 _RandomAccessIterator1 __xm;
36 _RandomAccessIterator2 __ym;
37
38 if (__size_x < __size_y)
39 {
40 __ym = __ys + (__size_y / 2);
41 __xm = std::upper_bound(__xs, __xe, *__ym, __comp);
42 }
43 else
44 {
45 __xm = __xs + (__size_x / 2);
46 __ym = std::lower_bound(__ys, __ye, *__xm, __comp);
47 }
48
49 auto __zm = __zs + (__xm - __xs) + (__ym - __ys);
50
51 _PSTL_PRAGMA(omp task untied mergeable default(none)
52 firstprivate(__xs, __xm, __ys, __ym, __zs, __comp, __leaf_merge))
53 __pstl::__omp_backend::__parallel_merge_body(__xm - __xs, __ym - __ys, __xs, __xm, __ys, __ym, __zs, __comp,
54 __leaf_merge);
55
56 _PSTL_PRAGMA(omp task untied mergeable default(none)
57 firstprivate(__xm, __xe, __ym, __ye, __zm, __comp, __leaf_merge))
58 __pstl::__omp_backend::__parallel_merge_body(__xe - __xm, __ye - __ym, __xm, __xe, __ym, __ye, __zm, __comp,
59 __leaf_merge);
60
61 _PSTL_PRAGMA(omp taskwait)
62 }
63
64 template <class _ExecutionPolicy, typename _RandomAccessIterator1, typename _RandomAccessIterator2,
65 typename _RandomAccessIterator3, typename _Compare, typename _LeafMerge>
66 void
__parallel_merge(__pstl::__internal::__openmp_backend_tag,_ExecutionPolicy &&,_RandomAccessIterator1 __xs,_RandomAccessIterator1 __xe,_RandomAccessIterator2 __ys,_RandomAccessIterator2 __ye,_RandomAccessIterator3 __zs,_Compare __comp,_LeafMerge __leaf_merge)67 __parallel_merge(__pstl::__internal::__openmp_backend_tag, _ExecutionPolicy&& /*__exec*/, _RandomAccessIterator1 __xs,
68 _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, _RandomAccessIterator2 __ye,
69 _RandomAccessIterator3 __zs, _Compare __comp, _LeafMerge __leaf_merge)
70
71 {
72 std::size_t __size_x = __xe - __xs;
73 std::size_t __size_y = __ye - __ys;
74
75 /*
76 * Run the merge in parallel by chunking it up. Use the smaller range (if any) as the iteration range, and the
77 * larger range as the search range.
78 */
79
80 if (omp_in_parallel())
81 {
82 __pstl::__omp_backend::__parallel_merge_body(__size_x, __size_y, __xs, __xe, __ys, __ye, __zs, __comp,
83 __leaf_merge);
84 }
85 else
86 {
87 _PSTL_PRAGMA(omp parallel)
88 {
89 _PSTL_PRAGMA(omp single nowait)
90 __pstl::__omp_backend::__parallel_merge_body(__size_x, __size_y, __xs, __xe, __ys, __ye, __zs, __comp,
91 __leaf_merge);
92 }
93 }
94 }
95
96 } // namespace __omp_backend
97 } // namespace __pstl
98 #endif // _PSTL_INTERNAL_OMP_PARALLEL_MERGE_H
99