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 27 namespace tbb { 28 namespace detail { 29 namespace 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 */ 42 template<typename Value> __TBB_requires(blocked_range_value<Value>)43 __TBB_requires(blocked_range_value<Value>) 44 class blocked_range { 45 public: 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 112 private: 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 161 inline namespace v1 { 162 using detail::d1::blocked_range; 163 // Split types 164 using detail::split; 165 using detail::proportional_split; 166 } // namespace v1 167 168 } // namespace tbb 169 170 #endif /* __TBB_blocked_range_H */ 171