git.sesse.net Git - casparcg/blob - tbb30_20100406oss/include/tbb/parallel_for.h

   1 /*
   2     Copyright 2005-2010 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_parallel_for_H
  30 #define __TBB_parallel_for_H
  31
  32 #include "task.h"
  33 #include "partitioner.h"
  34 #include "blocked_range.h"
  35 #include <new>
  36 #include "tbb_exception.h"
  37
  38 namespace tbb {
  39
  40 //! @cond INTERNAL
  41 namespace internal {
  42
  43     //! Task type used in parallel_for
  44     /** @ingroup algorithms */
  45     template<typename Range, typename Body, typename Partitioner>
  46     class start_for: public task {
  47         Range my_range;
  48         const Body my_body;
  49         typename Partitioner::partition_type my_partition;
  50         /*override*/ task* execute();
  51
  52         //! Constructor for root task.
  53         start_for( const Range& range, const Body& body, Partitioner& partitioner ) :
  54             my_range(range),
  55             my_body(body),
  56             my_partition(partitioner)
  57         {
  58         }
  59         //! Splitting constructor used to generate children.
  60         /** this becomes left child.  Newly constructed object is right child. */
  61         start_for( start_for& parent_, split ) :
  62             my_range(parent_.my_range,split()),
  63             my_body(parent_.my_body),
  64             my_partition(parent_.my_partition,split())
  65         {
  66             my_partition.set_affinity(*this);
  67         }
  68         //! Update affinity info, if any.
  69         /*override*/ void note_affinity( affinity_id id ) {
  70             my_partition.note_affinity( id );
  71         }
  72     public:
  73         static void run(  const Range& range, const Body& body, const Partitioner& partitioner ) {
  74             if( !range.empty() ) {
  75 #if !__TBB_TASK_GROUP_CONTEXT || TBB_JOIN_OUTER_TASK_GROUP
  76                 start_for& a = *new(task::allocate_root()) start_for(range,body,const_cast<Partitioner&>(partitioner));
  77 #else
  78                 // Bound context prevents exceptions from body to affect nesting or sibling algorithms,
  79                 // and allows users to handle exceptions safely by wrapping parallel_for in the try-block.
  80                 task_group_context context;
  81                 start_for& a = *new(task::allocate_root(context)) start_for(range,body,const_cast<Partitioner&>(partitioner));
  82 #endif /* __TBB_TASK_GROUP_CONTEXT && !TBB_JOIN_OUTER_TASK_GROUP */
  83                 task::spawn_root_and_wait(a);
  84             }
  85         }
  86 #if __TBB_TASK_GROUP_CONTEXT
  87         static void run(  const Range& range, const Body& body, const Partitioner& partitioner, task_group_context& context ) {
  88             if( !range.empty() ) {
  89                 start_for& a = *new(task::allocate_root(context)) start_for(range,body,const_cast<Partitioner&>(partitioner));
  90                 task::spawn_root_and_wait(a);
  91             }
  92         }
  93 #endif /* __TBB_TASK_GROUP_CONTEXT */
  94     };
  95
  96     template<typename Range, typename Body, typename Partitioner>
  97     task* start_for<Range,Body,Partitioner>::execute() {
  98         if( !my_range.is_divisible() || my_partition.should_execute_range(*this) ) {
  99             my_body( my_range );
 100             return my_partition.continue_after_execute_range();
 101         } else {
 102             empty_task& c = *new( this->allocate_continuation() ) empty_task;
 103             recycle_as_child_of(c);
 104             c.set_ref_count(2);
 105             bool delay = my_partition.decide_whether_to_delay();
 106             start_for& b = *new( c.allocate_child() ) start_for(*this,split());
 107             my_partition.spawn_or_delay(delay,b);
 108             return this;
 109         }
 110     }
 111 } // namespace internal
 112 //! @endcond
 113
 114
 115 // Requirements on Range concept are documented in blocked_range.h
 116
 117 /** \page parallel_for_body_req Requirements on parallel_for body
 118     Class \c Body implementing the concept of parallel_for body must define:
 119     - \code Body::Body( const Body& ); \endcode                 Copy constructor
 120     - \code Body::~Body(); \endcode                             Destructor
 121     - \code void Body::operator()( Range& r ) const; \endcode   Function call operator applying the body to range \c r.
 122 **/
 123
 124 /** \name parallel_for
 125     See also requirements on \ref range_req "Range" and \ref parallel_for_body_req "parallel_for Body". **/
 126 //@{
 127
 128 //! Parallel iteration over range with default partitioner.
 129 /** @ingroup algorithms **/
 130 template<typename Range, typename Body>
 131 void parallel_for( const Range& range, const Body& body ) {
 132     internal::start_for<Range,Body,__TBB_DEFAULT_PARTITIONER>::run(range,body,__TBB_DEFAULT_PARTITIONER());
 133 }
 134
 135 //! Parallel iteration over range with simple partitioner.
 136 /** @ingroup algorithms **/
 137 template<typename Range, typename Body>
 138 void parallel_for( const Range& range, const Body& body, const simple_partitioner& partitioner ) {
 139     internal::start_for<Range,Body,simple_partitioner>::run(range,body,partitioner);
 140 }
 141
 142 //! Parallel iteration over range with auto_partitioner.
 143 /** @ingroup algorithms **/
 144 template<typename Range, typename Body>
 145 void parallel_for( const Range& range, const Body& body, const auto_partitioner& partitioner ) {
 146     internal::start_for<Range,Body,auto_partitioner>::run(range,body,partitioner);
 147 }
 148
 149 //! Parallel iteration over range with affinity_partitioner.
 150 /** @ingroup algorithms **/
 151 template<typename Range, typename Body>
 152 void parallel_for( const Range& range, const Body& body, affinity_partitioner& partitioner ) {
 153     internal::start_for<Range,Body,affinity_partitioner>::run(range,body,partitioner);
 154 }
 155
 156 #if __TBB_TASK_GROUP_CONTEXT
 157 //! Parallel iteration over range with simple partitioner and user-supplied context.
 158 /** @ingroup algorithms **/
 159 template<typename Range, typename Body>
 160 void parallel_for( const Range& range, const Body& body, const simple_partitioner& partitioner, task_group_context& context ) {
 161     internal::start_for<Range,Body,simple_partitioner>::run(range, body, partitioner, context);
 162 }
 163
 164 //! Parallel iteration over range with auto_partitioner and user-supplied context.
 165 /** @ingroup algorithms **/
 166 template<typename Range, typename Body>
 167 void parallel_for( const Range& range, const Body& body, const auto_partitioner& partitioner, task_group_context& context ) {
 168     internal::start_for<Range,Body,auto_partitioner>::run(range, body, partitioner, context);
 169 }
 170
 171 //! Parallel iteration over range with affinity_partitioner and user-supplied context.
 172 /** @ingroup algorithms **/
 173 template<typename Range, typename Body>
 174 void parallel_for( const Range& range, const Body& body, affinity_partitioner& partitioner, task_group_context& context ) {
 175     internal::start_for<Range,Body,affinity_partitioner>::run(range,body,partitioner, context);
 176 }
 177 #endif /* __TBB_TASK_GROUP_CONTEXT */
 178 //@}
 179
 180 //! @cond INTERNAL
 181 namespace internal {
 182     //! Calls the function with values from range [begin, end) with a step provided
 183 template<typename Function, typename Index>
 184 class parallel_for_body : internal::no_assign {
 185     const Function &my_func;
 186     const Index my_begin;
 187     const Index my_step;
 188 public:
 189     parallel_for_body( const Function& _func, Index& _begin, Index& _step)
 190         : my_func(_func), my_begin(_begin), my_step(_step) {}
 191
 192     void operator()( tbb::blocked_range<Index>& r ) const {
 193         for( Index i = r.begin(),  k = my_begin + i * my_step; i < r.end(); i++, k = k + my_step)
 194             my_func( k );
 195     }
 196 };
 197 } // namespace internal
 198 //! @endcond
 199
 200 namespace strict_ppl {
 201
 202 //@{
 203 //! Parallel iteration over a range of integers with a step provided
 204 template <typename Index, typename Function>
 205 void parallel_for(Index first, Index last, Index step, const Function& f) {
 206     tbb::task_group_context context;
 207     parallel_for(first, last, step, f, context);
 208 }
 209 template <typename Index, typename Function>
 210 void parallel_for(Index first, Index last, Index step, const Function& f, tbb::task_group_context &context) {
 211     if (step <= 0 )
 212         internal::throw_exception(internal::eid_nonpositive_step); // throws std::invalid_argument
 213     else if (last > first) {
 214         // Above "else" is necessary to prevent "potential divide by zero" warning
 215         Index end = (last - first) / step;
 216         if (first + end * step < last) end++;
 217         tbb::blocked_range<Index> range(static_cast<Index>(0), end);
 218         internal::parallel_for_body<Function, Index> body(f, first, step);
 219         tbb::parallel_for(range, body, tbb::auto_partitioner(), context);
 220     }
 221 }
 222 //! Parallel iteration over a range of integers with a default step value
 223 template <typename Index, typename Function>
 224 void parallel_for(Index first, Index last, const Function& f) {
 225     tbb::task_group_context context;
 226     parallel_for(first, last, static_cast<Index>(1), f, context);
 227 }
 228 template <typename Index, typename Function>
 229 void parallel_for(Index first, Index last, const Function& f, tbb::task_group_context &context) {
 230     parallel_for(first, last, static_cast<Index>(1), f, context);
 231 }
 232
 233 //@}
 234
 235 } // namespace strict_ppl
 236
 237 using strict_ppl::parallel_for;
 238
 239 } // namespace tbb
 240
 241 #endif /* __TBB_parallel_for_H */
 242