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

source code of include/oneapi/tbb/blocked_range.h