1 /*
2     Copyright 2005-2014 Intel Corporation.  All Rights Reserved.
3 
4     This file is part of Threading Building Blocks. Threading Building Blocks is free software;
5     you can redistribute it and/or modify it under the terms of the GNU General Public License
6     version 2  as  published  by  the  Free Software Foundation.  Threading Building Blocks is
7     distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
8     implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
9     See  the GNU General Public License for more details.   You should have received a copy of
10     the  GNU General Public License along with Threading Building Blocks; if not, write to the
11     Free Software Foundation, Inc.,  51 Franklin St,  Fifth Floor,  Boston,  MA 02110-1301 USA
12 
13     As a special exception,  you may use this file  as part of a free software library without
14     restriction.  Specifically,  if other files instantiate templates  or use macros or inline
15     functions from this file, or you compile this file and link it with other files to produce
16     an executable,  this file does not by itself cause the resulting executable to be covered
17     by the GNU General Public License. This exception does not however invalidate any other
18     reasons why the executable file might be covered by the GNU General Public License.
19 */
20 
21 #ifndef __TBB_blocked_range_H
22 #define __TBB_blocked_range_H
23 
24 #include "tbb_stddef.h"
25 
26 namespace tbb {
27 
28 /** \page range_req Requirements on range concept
29     Class \c R implementing the concept of range must define:
30     - \code R::R( const R& ); \endcode               Copy constructor
31     - \code R::~R(); \endcode                        Destructor
32     - \code bool R::is_divisible() const; \endcode   True if range can be partitioned into two subranges
33     - \code bool R::empty() const; \endcode          True if range is empty
34     - \code R::R( R& r, split ); \endcode            Split range \c r into two subranges.
35 **/
36 
37 //! A range over which to iterate.
38 /** @ingroup algorithms */
39 template<typename Value>
40 class blocked_range {
41 public:
42     //! Type of a value
43     /** Called a const_iterator for sake of algorithms that need to treat a blocked_range
44         as an STL container. */
45     typedef Value const_iterator;
46 
47     //! Type for size of a range
48     typedef std::size_t size_type;
49 
50     //! Construct range with default-constructed values for begin and end.
51     /** Requires that Value have a default constructor. */
blocked_range()52     blocked_range() : my_end(), my_begin() {}
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 ) :
my_end(end_)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.
begin()62     const_iterator begin() const {return my_begin;}
63 
64     //! One past last value in range.
end()65     const_iterator end() const {return my_end;}
66 
67     //! Size of the range
68     /** Unspecified if end()<begin(). */
size()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.
grainsize()75     size_type grainsize() const {return my_grainsize;}
76 
77     //------------------------------------------------------------------------
78     // Methods that implement Range concept
79     //------------------------------------------------------------------------
80 
81     //! True if range is empty.
empty()82     bool empty() const {return !(my_begin<my_end);}
83 
84     //! True if range is divisible.
85     /** Unspecified if end()<begin(). */
is_divisible()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(). */
blocked_range(blocked_range & r,split)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 #if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES
101     //! Static field to support proportional split
102     static const bool is_divisible_in_proportion = true;
103 
104     //! Split range.
105     /** The new Range *this has the second part split according to specified proportion, the old range r has the first part.
106         Unspecified if end()<begin() or !is_divisible(). */
blocked_range(blocked_range & r,proportional_split & proportion)107     blocked_range( blocked_range& r, proportional_split& proportion ) :
108         my_end(r.my_end),
109         my_begin(do_split(r, proportion)),
110         my_grainsize(r.my_grainsize)
111     {
112         // only comparison 'less than' is required from values of blocked_range objects
113         __TBB_ASSERT( !(my_begin < r.my_end) && !(r.my_end < my_begin), "blocked_range has been split incorrectly" );
114     }
115 #endif /* __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES */
116 
117 private:
118     /** NOTE: my_end MUST be declared before my_begin, otherwise the forking constructor will break. */
119     Value my_end;
120     Value my_begin;
121     size_type my_grainsize;
122 
123     //! Auxiliary function used by forking constructor.
124     /** Using this function lets us not require that Value support assignment or default construction. */
do_split(blocked_range & r,split)125     static Value do_split( blocked_range& r, split )
126     {
127         __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" );
128         Value middle = r.my_begin + (r.my_end - r.my_begin) / 2u;
129         r.my_end = middle;
130         return middle;
131     }
132 
133 #if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES
do_split(blocked_range & r,proportional_split & proportion)134     static Value do_split( blocked_range& r, proportional_split& proportion )
135     {
136         __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" );
137 
138         // usage of 32-bit floating point arithmetic is not enough to handle ranges of
139         // more than 2^24 iterations accurately. However, even on ranges with 2^64
140         // iterations the computational error approximately equals to 0.000001% which
141         // makes small impact on uniform distribution of such range's iterations (assuming
142         // all iterations take equal time to complete). See 'test_partitioner_whitebox'
143         // for implementation of an exact split algorithm
144         size_type right_part = size_type(float(r.size()) * float(proportion.right())
145                                          / float(proportion.left() + proportion.right()) + 0.5f);
146         return r.my_end = Value(r.my_end - right_part);
147     }
148 #endif /* __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES */
149 
150     template<typename RowValue, typename ColValue>
151     friend class blocked_range2d;
152 
153     template<typename RowValue, typename ColValue, typename PageValue>
154     friend class blocked_range3d;
155 };
156 
157 } // namespace tbb
158 
159 #endif /* __TBB_blocked_range_H */
160