git.sesse.net Git - casparcg/blob - dependencies/tbb/include/tbb/blocked_range.h

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 #ifndef __TBB_blocked_range_H
  30 #define __TBB_blocked_range_H
  31
  32 #include "tbb_stddef.h"
  33
  34 namespace tbb {
  35
  36 /** \page range_req Requirements on range concept
  37     Class \c R implementing the concept of range must define:
  38     - \code R::R( const R& ); \endcode               Copy constructor
  39     - \code R::~R(); \endcode                        Destructor
  40     - \code bool R::is_divisible() const; \endcode   True if range can be partitioned into two subranges
  41     - \code bool R::empty() const; \endcode          True if range is empty
  42     - \code R::R( R& r, split ); \endcode            Split range \c r into two subranges.
  43 **/
  44
  45 //! A range over which to iterate.
  46 /** @ingroup algorithms */
  47 template<typename Value>
  48 class blocked_range {
  49 public:
  50     //! Type of a value
  51     /** Called a const_iterator for sake of algorithms that need to treat a blocked_range
  52         as an STL container. */
  53     typedef Value const_iterator;
  54
  55     //! Type for size of a range
  56     typedef std::size_t size_type;
  57
  58     //! Construct range with default-constructed values for begin and end.
  59     /** Requires that Value have a default constructor. */
  60     blocked_range() : my_end(), my_begin() {}
  61
  62     //! Construct range over half-open interval [begin,end), with the given grainsize.
  63     blocked_range( Value begin_, Value end_, size_type grainsize_=1 ) :
  64         my_end(end_), my_begin(begin_), my_grainsize(grainsize_)
  65     {
  66         __TBB_ASSERT( my_grainsize>0, "grainsize must be positive" );
  67     }
  68
  69     //! Beginning of range.
  70     const_iterator begin() const {return my_begin;}
  71
  72     //! One past last value in range.
  73     const_iterator end() const {return my_end;}
  74
  75     //! Size of the range
  76     /** Unspecified if end()<begin(). */
  77     size_type size() const {
  78         __TBB_ASSERT( !(end()<begin()), "size() unspecified if end()<begin()" );
  79         return size_type(my_end-my_begin);
  80     }
  81
  82     //! The grain size for this range.
  83     size_type grainsize() const {return my_grainsize;}
  84
  85     //------------------------------------------------------------------------
  86     // Methods that implement Range concept
  87     //------------------------------------------------------------------------
  88
  89     //! True if range is empty.
  90     bool empty() const {return !(my_begin<my_end);}
  91
  92     //! True if range is divisible.
  93     /** Unspecified if end()<begin(). */
  94     bool is_divisible() const {return my_grainsize<size();}
  95
  96     //! Split range.
  97     /** The new Range *this has the second half, the old range r has the first half.
  98         Unspecified if end()<begin() or !is_divisible(). */
  99     blocked_range( blocked_range& r, split ) :
 100         my_end(r.my_end),
 101         my_begin(do_split(r)),
 102         my_grainsize(r.my_grainsize)
 103     {}
 104
 105 private:
 106     /** NOTE: my_end MUST be declared before my_begin, otherwise the forking constructor will break. */
 107     Value my_end;
 108     Value my_begin;
 109     size_type my_grainsize;
 110
 111     //! Auxiliary function used by forking constructor.
 112     /** Using this function lets us not require that Value support assignment or default construction. */
 113     static Value do_split( blocked_range& r ) {
 114         __TBB_ASSERT( r.is_divisible(), "cannot split blocked_range that is not divisible" );
 115         Value middle = r.my_begin + (r.my_end-r.my_begin)/2u;
 116         r.my_end = middle;
 117         return middle;
 118     }
 119
 120     template<typename RowValue, typename ColValue>
 121     friend class blocked_range2d;
 122
 123     template<typename RowValue, typename ColValue, typename PageValue>
 124     friend class blocked_range3d;
 125 };
 126
 127 } // namespace tbb
 128
 129 #endif /* __TBB_blocked_range_H */