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
22namespace tbb {
23
24namespace internal {
25
26// blocked_rangeNd_impl forward declaration in tbb::internal namespace to
27// name it as a friend for a tbb::blocked_range.
28template<typename Value, unsigned int N, typename>
29class 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 */
44template<typename Value>
45class blocked_range {
46public:
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
124private:
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