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