1 | /* |
2 | Copyright (c) 2005-2019 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_blocked_range_H |
18 | #define __TBB_blocked_range_H |
19 | |
20 | #include "tbb_stddef.h" |
21 | |
22 | namespace tbb { |
23 | |
24 | namespace internal { |
25 | |
26 | // blocked_rangeNd_impl forward declaration in tbb::internal namespace to |
27 | // name it as a friend for a tbb::blocked_range. |
28 | template<typename Value, unsigned int N, typename> |
29 | class blocked_rangeNd_impl; |
30 | |
31 | } // namespace internal |
32 | |
33 | /** \page range_req Requirements on range concept |
34 | Class \c R implementing the concept of range must define: |
35 | - \code R::R( const R& ); \endcode Copy constructor |
36 | - \code R::~R(); \endcode Destructor |
37 | - \code bool R::is_divisible() const; \endcode True if range can be partitioned into two subranges |
38 | - \code bool R::empty() const; \endcode True if range is empty |
39 | - \code R::R( R& r, split ); \endcode Split range \c r into two subranges. |
40 | **/ |
41 | |
42 | //! A range over which to iterate. |
43 | /** @ingroup algorithms */ |
44 | template<typename Value> |
45 | class blocked_range { |
46 | public: |
47 | //! Type of a value |
48 | /** Called a const_iterator for sake of algorithms that need to treat a blocked_range |
49 | as an STL container. */ |
50 | typedef Value const_iterator; |
51 | |
52 | //! Type for size of a range |
53 | typedef std::size_t size_type; |
54 | |
55 | #if __TBB_DEPRECATED_BLOCKED_RANGE_DEFAULT_CTOR |
56 | //! Construct range with default-constructed values for begin, end, and grainsize. |
57 | /** Requires that Value have a default constructor. */ |
58 | blocked_range() : my_end(), my_begin(), my_grainsize() {} |
59 | #endif |
60 | |
61 | //! Construct range over half-open interval [begin,end), with the given grainsize. |
62 | blocked_range( Value begin_, Value end_, size_type grainsize_=1 ) : |
63 | my_end(end_), my_begin(begin_), my_grainsize(grainsize_) |
64 | { |
65 | __TBB_ASSERT( my_grainsize>0, "grainsize must be positive" ); |
66 | } |
67 | |
68 | //! Beginning of range. |
69 | const_iterator begin() const {return my_begin;} |
70 | |
71 | //! One past last value in range. |
72 | const_iterator end() const {return my_end;} |
73 | |
74 | //! Size of the range |
75 | /** Unspecified if end()<begin(). */ |
76 | size_type size() const { |
77 | __TBB_ASSERT( !(end()<begin()), "size() unspecified if end()<begin()" ); |
78 | return size_type(my_end-my_begin); |
79 | } |
80 | |
81 | //! The grain size for this range. |
82 | size_type grainsize() const {return my_grainsize;} |
83 | |
84 | //------------------------------------------------------------------------ |
85 | // Methods that implement Range concept |
86 | //------------------------------------------------------------------------ |
87 | |
88 | //! True if range is empty. |
89 | bool empty() const {return !(my_begin<my_end);} |
90 | |
91 | //! True if range is divisible. |
92 | /** Unspecified if end()<begin(). */ |
93 | bool is_divisible() const {return my_grainsize<size();} |
94 | |
95 | //! Split range. |
96 | /** The new Range *this has the second part, the old range r has the first part. |
97 | Unspecified if end()<begin() or !is_divisible(). */ |
98 | blocked_range( blocked_range& r, split ) : |
99 | my_end(r.my_end), |
100 | my_begin(do_split(r, split())), |
101 | my_grainsize(r.my_grainsize) |
102 | { |
103 | // only comparison 'less than' is required from values of blocked_range objects |
104 | __TBB_ASSERT( !(my_begin < r.my_end) && !(r.my_end < my_begin), "blocked_range has been split incorrectly" ); |
105 | } |
106 | |
107 | #if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES |
108 | //! Static field to support proportional split |
109 | static const bool is_splittable_in_proportion = true; |
110 | |
111 | //! Split range. |
112 | /** The new Range *this has the second part split according to specified proportion, the old range r has the first part. |
113 | Unspecified if end()<begin() or !is_divisible(). */ |
114 | blocked_range( blocked_range& r, proportional_split& proportion ) : |
115 | my_end(r.my_end), |
116 | my_begin(do_split(r, proportion)), |
117 | my_grainsize(r.my_grainsize) |
118 | { |
119 | // only comparison 'less than' is required from values of blocked_range objects |
120 | __TBB_ASSERT( !(my_begin < r.my_end) && !(r.my_end < my_begin), "blocked_range has been split incorrectly" ); |
121 | } |
122 | #endif /* __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES */ |
123 | |
124 | private: |
125 | /** NOTE: my_end MUST be declared before my_begin, otherwise the splitting constructor will break. */ |
126 | Value my_end; |
127 | Value my_begin; |
128 | size_type my_grainsize; |
129 | |
130 | //! Auxiliary function used by the splitting constructor. |
131 | static Value do_split( blocked_range& r, split ) |
132 | { |
133 | __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" ); |
134 | Value middle = r.my_begin + (r.my_end - r.my_begin) / 2u; |
135 | r.my_end = middle; |
136 | return middle; |
137 | } |
138 | |
139 | #if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES |
140 | static Value do_split( blocked_range& r, proportional_split& proportion ) |
141 | { |
142 | __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" ); |
143 | |
144 | // usage of 32-bit floating point arithmetic is not enough to handle ranges of |
145 | // more than 2^24 iterations accurately. However, even on ranges with 2^64 |
146 | // iterations the computational error approximately equals to 0.000001% which |
147 | // makes small impact on uniform distribution of such range's iterations (assuming |
148 | // all iterations take equal time to complete). See 'test_partitioner_whitebox' |
149 | // for implementation of an exact split algorithm |
150 | size_type right_part = size_type(float(r.size()) * float(proportion.right()) |
151 | / float(proportion.left() + proportion.right()) + 0.5f); |
152 | return r.my_end = Value(r.my_end - right_part); |
153 | } |
154 | #endif /* __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES */ |
155 | |
156 | template<typename RowValue, typename ColValue> |
157 | friend class blocked_range2d; |
158 | |
159 | template<typename RowValue, typename ColValue, typename PageValue> |
160 | friend class blocked_range3d; |
161 | |
162 | template<typename DimValue, unsigned int N, typename> |
163 | friend class internal::blocked_rangeNd_impl; |
164 | }; |
165 | |
166 | } // namespace tbb |
167 | |
168 | #endif /* __TBB_blocked_range_H */ |
169 | |