1 /*
2     Copyright (c) 2005-2021 Intel Corporation
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8         http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15 */
16 
17 #ifndef __TBB_detail__range_common_H
18 #define __TBB_detail__range_common_H
19 
20 #include "_config.h"
21 #include "_utils.h"
22 #if __TBB_CPP20_CONCEPTS_PRESENT
23 #include <concepts>
24 #endif
25 #include <iterator>
26 
27 namespace tbb {
28 namespace detail {
29 inline namespace d0 {
30 
31 //! Dummy type that distinguishes splitting constructor from copy constructor.
32 /**
33  * See description of parallel_for and parallel_reduce for example usages.
34  * @ingroup algorithms
35  */
36 class split {};
37 
38 //! Type enables transmission of splitting proportion from partitioners to range objects
39 /**
40  * In order to make use of such facility Range objects must implement
41  * splitting constructor with this type passed.
42  */
43 class proportional_split : no_assign {
44 public:
my_left(_left)45     proportional_split(size_t _left = 1, size_t _right = 1) : my_left(_left), my_right(_right) { }
46 
left()47     size_t left() const { return my_left; }
right()48     size_t right() const { return my_right; }
49 
50     // used when range does not support proportional split
split()51     explicit operator split() const { return split(); }
52 
53 private:
54     size_t my_left, my_right;
55 };
56 
57 template <typename Range, typename = void>
58 struct range_split_object_provider {
59     template <typename PartitionerSplitType>
getrange_split_object_provider60     static split get( PartitionerSplitType& ) { return split(); }
61 };
62 
63 template <typename Range>
64 struct range_split_object_provider<Range,
65                                    typename std::enable_if<std::is_constructible<Range, Range&, proportional_split&>::value>::type> {
66     template <typename PartitionerSplitType>
67     static PartitionerSplitType& get( PartitionerSplitType& split_obj ) { return split_obj; }
68 };
69 
70 template <typename Range, typename PartitionerSplitType>
71 auto get_range_split_object( PartitionerSplitType& split_obj )
72 -> decltype(range_split_object_provider<Range>::get(split_obj)) {
73     return range_split_object_provider<Range>::get(split_obj);
74 }
75 
76 template <typename Range>
77 using range_iterator_type = decltype(std::begin(std::declval<Range&>()));
78 
79 #if __TBB_CPP20_CONCEPTS_PRESENT
80 template <typename Iterator>
81 using iterator_reference_type = typename std::iterator_traits<Iterator>::reference;
82 
83 template <typename Range>
84 using range_reference_type = iterator_reference_type<range_iterator_type<Range>>;
85 
86 template <typename Value>
87 concept blocked_range_value = std::copyable<Value> &&
88                               requires( const std::remove_reference_t<Value>& lhs, const std::remove_reference_t<Value>& rhs ) {
89                                   { lhs < rhs } -> relaxed_convertible_to<bool>;
90                                   { lhs - rhs } -> std::convertible_to<std::size_t>;
91                                   { lhs + (rhs - lhs) } -> std::convertible_to<Value>;
92                               };
93 
94 template <typename T>
95 concept splittable = std::constructible_from<T, T&, tbb::detail::split>;
96 
97 template <typename Range>
98 concept tbb_range = std::copy_constructible<Range> &&
99                     splittable<Range> &&
100                     requires( const std::remove_reference_t<Range>& range ) {
101                         { range.empty() } -> relaxed_convertible_to<bool>;
102                         { range.is_divisible() } -> relaxed_convertible_to<bool>;
103                     };
104 
105 template <typename Iterator>
106 constexpr bool iterator_concept_helper( std::input_iterator_tag ) {
107     return std::input_iterator<Iterator>;
108 }
109 
110 template <typename Iterator>
111 constexpr bool iterator_concept_helper( std::random_access_iterator_tag ) {
112     return std::random_access_iterator<Iterator>;
113 }
114 
115 template <typename Iterator, typename IteratorTag>
116 concept iterator_satisfies = requires (IteratorTag tag) {
117     requires iterator_concept_helper<Iterator>(tag);
118 };
119 
120 template <typename Sequence, typename IteratorTag>
121 concept container_based_sequence = requires( Sequence& seq ) {
122     { std::begin(seq) } -> iterator_satisfies<IteratorTag>;
123     { std::end(seq) } -> iterator_satisfies<IteratorTag>;
124 };
125 #endif // __TBB_CPP20_CONCEPTS_PRESENT
126 } // namespace d0
127 } // namespace detail
128 } // namespace tbb
129 
130 #endif // __TBB_detail__range_common_H
131