2 Copyright 2005-2011 Intel Corporation. All Rights Reserved.
4 This file is part of Threading Building Blocks.
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.
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.
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
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.
29 #ifndef __TBB_parallel_do_H
30 #define __TBB_parallel_do_H
33 #include "aligned_space.h"
40 template<typename Body, typename Item> class parallel_do_feeder_impl;
41 template<typename Body> class do_group_task;
43 //! Strips its template type argument from 'cv' and '&' qualifiers
45 struct strip { typedef T type; };
47 struct strip<T&> { typedef T type; };
49 struct strip<const T&> { typedef T type; };
51 struct strip<volatile T&> { typedef T type; };
53 struct strip<const volatile T&> { typedef T type; };
54 // Most of the compilers remove cv-qualifiers from non-reference function argument types.
55 // But unfortunately there are those that don't.
57 struct strip<const T> { typedef T type; };
59 struct strip<volatile T> { typedef T type; };
61 struct strip<const volatile T> { typedef T type; };
62 } // namespace internal
65 //! Class the user supplied algorithm body uses to add new tasks
66 /** \param Item Work item type **/
67 template<typename Item>
68 class parallel_do_feeder: internal::no_copy
70 parallel_do_feeder() {}
71 virtual ~parallel_do_feeder () {}
72 virtual void internal_add( const Item& item ) = 0;
73 template<typename Body_, typename Item_> friend class internal::parallel_do_feeder_impl;
75 //! Add a work item to a running parallel_do.
76 void add( const Item& item ) {internal_add(item);}
81 //! For internal use only.
82 /** Selects one of the two possible forms of function call member operator.
83 @ingroup algorithms **/
84 template<class Body, typename Item>
85 class parallel_do_operator_selector
87 typedef parallel_do_feeder<Item> Feeder;
88 template<typename A1, typename A2, typename CvItem >
89 static void internal_call( const Body& obj, A1& arg1, A2&, void (Body::*)(CvItem) const ) {
92 template<typename A1, typename A2, typename CvItem >
93 static void internal_call( const Body& obj, A1& arg1, A2& arg2, void (Body::*)(CvItem, parallel_do_feeder<Item>&) const ) {
98 template<typename A1, typename A2 >
99 static void call( const Body& obj, A1& arg1, A2& arg2 )
101 internal_call( obj, arg1, arg2, &Body::operator() );
105 //! For internal use only.
106 /** Executes one iteration of a do.
107 @ingroup algorithms */
108 template<typename Body, typename Item>
109 class do_iteration_task: public task
111 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
114 feeder_type& my_feeder;
116 do_iteration_task( const Item& value, feeder_type& feeder ) :
117 my_value(value), my_feeder(feeder)
123 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, my_value, my_feeder);
127 template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
128 }; // class do_iteration_task
130 template<typename Iterator, typename Body, typename Item>
131 class do_iteration_task_iter: public task
133 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
136 feeder_type& my_feeder;
138 do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
139 my_iter(iter), my_feeder(feeder)
145 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, *my_iter, my_feeder);
149 template<typename Iterator_, typename Body_, typename Item_> friend class do_group_task_forward;
150 template<typename Body_, typename Item_> friend class do_group_task_input;
151 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
152 }; // class do_iteration_task_iter
154 //! For internal use only.
155 /** Implements new task adding procedure.
156 @ingroup algorithms **/
157 template<class Body, typename Item>
158 class parallel_do_feeder_impl : public parallel_do_feeder<Item>
161 void internal_add( const Item& item )
163 typedef do_iteration_task<Body, Item> iteration_type;
165 iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
171 empty_task* my_barrier;
173 parallel_do_feeder_impl()
175 my_barrier = new( task::allocate_root() ) empty_task();
176 __TBB_ASSERT(my_barrier, "root task allocation failed");
179 #if __TBB_TASK_GROUP_CONTEXT
180 parallel_do_feeder_impl(tbb::task_group_context &context)
182 my_barrier = new( task::allocate_root(context) ) empty_task();
183 __TBB_ASSERT(my_barrier, "root task allocation failed");
187 ~parallel_do_feeder_impl()
189 my_barrier->destroy(*my_barrier);
191 }; // class parallel_do_feeder_impl
194 //! For internal use only
195 /** Unpacks a block of iterations.
196 @ingroup algorithms */
198 template<typename Iterator, typename Body, typename Item>
199 class do_group_task_forward: public task
201 static const size_t max_arg_size = 4;
203 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
205 feeder_type& my_feeder;
209 do_group_task_forward( Iterator first, size_t size, feeder_type& feeder )
210 : my_feeder(feeder), my_first(first), my_size(size)
213 /*override*/ task* execute()
215 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
216 __TBB_ASSERT( my_size>0, NULL );
221 t = new( allocate_child() ) iteration_type( my_first, my_feeder );
223 if( ++k==my_size ) break;
226 set_ref_count(int(k+1));
228 spawn_and_wait_for_all(*t);
232 template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
233 }; // class do_group_task_forward
235 template<typename Body, typename Item>
236 class do_group_task_input: public task
238 static const size_t max_arg_size = 4;
240 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
242 feeder_type& my_feeder;
244 aligned_space<Item, max_arg_size> my_arg;
246 do_group_task_input( feeder_type& feeder )
247 : my_feeder(feeder), my_size(0)
250 /*override*/ task* execute()
252 typedef do_iteration_task_iter<Item*, Body, Item> iteration_type;
253 __TBB_ASSERT( my_size>0, NULL );
258 t = new( allocate_child() ) iteration_type( my_arg.begin() + k, my_feeder );
259 if( ++k==my_size ) break;
262 set_ref_count(int(k+1));
264 spawn_and_wait_for_all(*t);
268 ~do_group_task_input(){
269 for( size_t k=0; k<my_size; ++k)
270 (my_arg.begin() + k)->~Item();
273 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
274 }; // class do_group_task_input
276 //! For internal use only.
277 /** Gets block of iterations and packages them into a do_group_task.
278 @ingroup algorithms */
279 template<typename Iterator, typename Body, typename Item>
280 class do_task_iter: public task
282 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
285 do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) :
286 my_first(first), my_last(last), my_feeder(feeder)
292 feeder_type& my_feeder;
294 /* Do not merge run(xxx) and run_xxx() methods. They are separated in order
295 to make sure that compilers will eliminate unused argument of type xxx
296 (that is will not put it on stack). The sole purpose of this argument
297 is overload resolution.
299 An alternative could be using template functions, but explicit specialization
300 of member function templates is not supported for non specialized class
301 templates. Besides template functions would always fall back to the least
302 efficient variant (the one for input iterators) in case of iterators having
303 custom tags derived from basic ones. */
304 /*override*/ task* execute()
306 typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
307 return run( (iterator_tag*)NULL );
310 /** This is the most restricted variant that operates on input iterators or
311 iterators with unknown tags (tags not derived from the standard ones). **/
312 inline task* run( void* ) { return run_for_input_iterator(); }
314 task* run_for_input_iterator() {
315 typedef do_group_task_input<Body, Item> block_type;
317 block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
319 while( !(my_first == my_last) ) {
320 new (t.my_arg.begin() + k) Item(*my_first);
322 if( ++k==block_type::max_arg_size ) {
323 if ( !(my_first == my_last) )
324 recycle_to_reexecute();
337 inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
339 task* run_for_forward_iterator() {
340 typedef do_group_task_forward<Iterator, Body, Item> block_type;
342 Iterator first = my_first;
344 while( !(my_first==my_last) ) {
346 if( ++k==block_type::max_arg_size ) {
347 if ( !(my_first==my_last) )
348 recycle_to_reexecute();
352 return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
355 inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
357 task* run_for_random_access_iterator() {
358 typedef do_group_task_forward<Iterator, Body, Item> block_type;
359 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
361 size_t k = static_cast<size_t>(my_last-my_first);
362 if( k > block_type::max_arg_size ) {
363 Iterator middle = my_first + k/2;
365 empty_task& c = *new( allocate_continuation() ) empty_task;
366 do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
367 recycle_as_child_of(c);
378 t = new( allocate_child() ) iteration_type(my_first, my_feeder);
383 set_ref_count(int(k+1));
385 spawn_and_wait_for_all(*t);
389 }; // class do_task_iter
391 //! For internal use only.
392 /** Implements parallel iteration over a range.
393 @ingroup algorithms */
394 template<typename Iterator, typename Body, typename Item>
395 void run_parallel_do( Iterator first, Iterator last, const Body& body
396 #if __TBB_TASK_GROUP_CONTEXT
397 , task_group_context& context
401 typedef do_task_iter<Iterator, Body, Item> root_iteration_task;
402 #if __TBB_TASK_GROUP_CONTEXT
403 parallel_do_feeder_impl<Body, Item> feeder(context);
405 parallel_do_feeder_impl<Body, Item> feeder;
407 feeder.my_body = &body;
409 root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
411 feeder.my_barrier->set_ref_count(2);
412 feeder.my_barrier->spawn_and_wait_for_all(t);
415 //! For internal use only.
416 /** Detects types of Body's operator function arguments.
417 @ingroup algorithms **/
418 template<typename Iterator, typename Body, typename Item>
419 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const
420 #if __TBB_TASK_GROUP_CONTEXT
421 , task_group_context& context
422 #endif // __TBB_TASK_GROUP_CONTEXT
425 run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
426 #if __TBB_TASK_GROUP_CONTEXT
428 #endif // __TBB_TASK_GROUP_CONTEXT
432 //! For internal use only.
433 /** Detects types of Body's operator function arguments.
434 @ingroup algorithms **/
435 template<typename Iterator, typename Body, typename Item, typename _Item>
436 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item, parallel_do_feeder<_Item>&) const
437 #if __TBB_TASK_GROUP_CONTEXT
438 , task_group_context& context
439 #endif // __TBB_TASK_GROUP_CONTEXT
442 run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
443 #if __TBB_TASK_GROUP_CONTEXT
445 #endif // __TBB_TASK_GROUP_CONTEXT
449 } // namespace internal
453 /** \page parallel_do_body_req Requirements on parallel_do body
454 Class \c Body implementing the concept of parallel_do body must define:
458 parallel_do_feeder<item_type>& feeder
463 B::operator()( cv_item_type& item ) const
464 \endcode Process item.
465 May be invoked concurrently for the same \c this but different \c item.
467 - \code item_type( const item_type& ) \endcode
469 - \code ~item_type() \endcode Destroy a work item
472 /** \name parallel_do
473 See also requirements on \ref parallel_do_body_req "parallel_do Body". **/
475 //! Parallel iteration over a range, with optional addition of more work.
476 /** @ingroup algorithms */
477 template<typename Iterator, typename Body>
478 void parallel_do( Iterator first, Iterator last, const Body& body )
482 #if __TBB_TASK_GROUP_CONTEXT
483 task_group_context context;
484 #endif // __TBB_TASK_GROUP_CONTEXT
485 internal::select_parallel_do( first, last, body, &Body::operator()
486 #if __TBB_TASK_GROUP_CONTEXT
488 #endif // __TBB_TASK_GROUP_CONTEXT
492 #if __TBB_TASK_GROUP_CONTEXT
493 //! Parallel iteration over a range, with optional addition of more work and user-supplied context
494 /** @ingroup algorithms */
495 template<typename Iterator, typename Body>
496 void parallel_do( Iterator first, Iterator last, const Body& body, task_group_context& context )
500 internal::select_parallel_do( first, last, body, &Body::operator(), context );
502 #endif // __TBB_TASK_GROUP_CONTEXT
508 #endif /* __TBB_parallel_do_H */