oneapi/tbb/blocked_range.h

0001 /*
0002     Copyright (c) 2005-2021 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_blocked_range_H
0018 #define __TBB_blocked_range_H
0019
0020 #include <cstddef>
0021
0022 #include "detail/_range_common.h"
0023 #include "detail/_namespace_injection.h"
0024
0025 #include "version.h"
0026
0027 namespace tbb {
0028 namespace detail {
0029 namespace d1 {
0030
0031 /** \page range_req Requirements on range concept
0032     Class \c R implementing the concept of range must define:
0033     - \code R::R( const R& ); \endcode               Copy constructor
0034     - \code R::~R(); \endcode                        Destructor
0035     - \code bool R::is_divisible() const; \endcode   True if range can be partitioned into two subranges
0036     - \code bool R::empty() const; \endcode          True if range is empty
0037     - \code R::R( R& r, split ); \endcode            Split range \c r into two subranges.
0038 **/
0039
0040 //! A range over which to iterate.
0041 /** @ingroup algorithms */
0042 template<typename Value>
0043     __TBB_requires(blocked_range_value<Value>)
0044 class blocked_range {
0045 public:
0046     //! Type of a value
0047     /** Called a const_iterator for sake of algorithms that need to treat a blocked_range
0048         as an STL container. */
0049     using const_iterator = Value;
0050
0051     //! Type for size of a range
0052     using size_type = std::size_t;
0053
0054     //! Construct range over half-open interval [begin,end), with the given grainsize.
0055     blocked_range( Value begin_, Value end_, size_type grainsize_=1 ) :
0056         my_end(end_), my_begin(begin_), my_grainsize(grainsize_)
0057     {
0058         __TBB_ASSERT( my_grainsize>0, "grainsize must be positive" );
0059     }
0060
0061     //! Beginning of range.
0062     const_iterator begin() const { return my_begin; }
0063
0064     //! One past last value in range.
0065     const_iterator end() const { return my_end; }
0066
0067     //! Size of the range
0068     /** Unspecified if end()<begin(). */
0069     size_type size() const {
0070         __TBB_ASSERT( !(end()<begin()), "size() unspecified if end()<begin()" );
0071         return size_type(my_end-my_begin);
0072     }
0073
0074     //! The grain size for this range.
0075     size_type grainsize() const { return my_grainsize; }
0076
0077     //------------------------------------------------------------------------
0078     // Methods that implement Range concept
0079     //------------------------------------------------------------------------
0080
0081     //! True if range is empty.
0082     bool empty() const { return !(my_begin<my_end); }
0083
0084     //! True if range is divisible.
0085     /** Unspecified if end()<begin(). */
0086     bool is_divisible() const { return my_grainsize<size(); }
0087
0088     //! Split range.
0089     /** The new Range *this has the second part, the old range r has the first part.
0090         Unspecified if end()<begin() or !is_divisible(). */
0091     blocked_range( blocked_range& r, split ) :
0092         my_end(r.my_end),
0093         my_begin(do_split(r, split())),
0094         my_grainsize(r.my_grainsize)
0095     {
0096         // only comparison 'less than' is required from values of blocked_range objects
0097         __TBB_ASSERT( !(my_begin < r.my_end) && !(r.my_end < my_begin), "blocked_range has been split incorrectly" );
0098     }
0099
0100     //! Split range.
0101     /** The new Range *this has the second part split according to specified proportion, the old range r has the first part.
0102         Unspecified if end()<begin() or !is_divisible(). */
0103     blocked_range( blocked_range& r, proportional_split& proportion ) :
0104         my_end(r.my_end),
0105         my_begin(do_split(r, proportion)),
0106         my_grainsize(r.my_grainsize)
0107     {
0108         // only comparison 'less than' is required from values of blocked_range objects
0109         __TBB_ASSERT( !(my_begin < r.my_end) && !(r.my_end < my_begin), "blocked_range has been split incorrectly" );
0110     }
0111
0112 private:
0113     /** NOTE: my_end MUST be declared before my_begin, otherwise the splitting constructor will break. */
0114     Value my_end;
0115     Value my_begin;
0116     size_type my_grainsize;
0117
0118     //! Auxiliary function used by the splitting constructor.
0119     static Value do_split( blocked_range& r, split )
0120     {
0121         __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" );
0122         Value middle = r.my_begin + (r.my_end - r.my_begin) / 2u;
0123         r.my_end = middle;
0124         return middle;
0125     }
0126
0127     static Value do_split( blocked_range& r, proportional_split& proportion )
0128     {
0129         __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" );
0130
0131         // usage of 32-bit floating point arithmetic is not enough to handle ranges of
0132         // more than 2^24 iterations accurately. However, even on ranges with 2^64
0133         // iterations the computational error approximately equals to 0.000001% which
0134         // makes small impact on uniform distribution of such range's iterations (assuming
0135         // all iterations take equal time to complete). See 'test_partitioner_whitebox'
0136         // for implementation of an exact split algorithm
0137         size_type right_part = size_type(float(r.size()) * float(proportion.right())
0138                                          / float(proportion.left() + proportion.right()) + 0.5f);
0139         return r.my_end = Value(r.my_end - right_part);
0140     }
0141
0142     template<typename RowValue, typename ColValue>
0143         __TBB_requires(blocked_range_value<RowValue> &&
0144                        blocked_range_value<ColValue>)
0145     friend class blocked_range2d;
0146
0147     template<typename RowValue, typename ColValue, typename PageValue>
0148         __TBB_requires(blocked_range_value<RowValue> &&
0149                        blocked_range_value<ColValue> &&
0150                        blocked_range_value<PageValue>)
0151     friend class blocked_range3d;
0152
0153     template<typename DimValue, unsigned int N, typename>
0154         __TBB_requires(blocked_range_value<DimValue>)
0155     friend class blocked_rangeNd_impl;
0156 };
0157
0158 } // namespace d1
0159 } // namespace detail
0160
0161 inline namespace v1 {
0162 using detail::d1::blocked_range;
0163 // Split types
0164 using detail::split;
0165 using detail::proportional_split;
0166 } // namespace v1
0167
0168 } // namespace tbb
0169
0170 #endif /* __TBB_blocked_range_H */