1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#ifndef __TBB_parallel_do_H
18#define __TBB_parallel_do_H
19
20#include "internal/_range_iterator.h"
21#include "internal/_template_helpers.h"
22#include "task.h"
23#include "aligned_space.h"
24#include <iterator>
25
26namespace tbb {
27namespace interface9 {
28//! @cond INTERNAL
29namespace internal {
30 template<typename Body, typename Item> class parallel_do_feeder_impl;
31} // namespace internal
32//! @endcond
33
34//! Class the user supplied algorithm body uses to add new tasks
35/** \param Item Work item type **/
36 template<typename Item>
37 class parallel_do_feeder: ::tbb::internal::no_copy
38 {
39 parallel_do_feeder() {}
40 virtual ~parallel_do_feeder () {}
41 virtual void internal_add_copy( const Item& item ) = 0;
42#if __TBB_CPP11_RVALUE_REF_PRESENT
43 virtual void internal_add_move( Item&& item ) = 0;
44#endif
45 template<typename Body_, typename Item_> friend class internal::parallel_do_feeder_impl;
46 public:
47 //! Add a work item to a running parallel_do.
48 void add( const Item& item ) {internal_add_copy(item);}
49#if __TBB_CPP11_RVALUE_REF_PRESENT
50 void add( Item&& item ) {internal_add_move(std::move(item));}
51#endif
52 };
53
54//! @cond INTERNAL
55namespace internal {
56 template<typename Body> class do_group_task;
57
58 //! For internal use only.
59 /** Selects one of the two possible forms of function call member operator.
60 @ingroup algorithms **/
61 template<class Body, typename Item>
62 class parallel_do_operator_selector
63 {
64 typedef parallel_do_feeder<Item> Feeder;
65 template<typename A1, typename A2, typename CvItem >
66 static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2&, void (Body::*)(CvItem) const ) {
67 obj(tbb::internal::forward<A1>(arg1));
68 }
69 template<typename A1, typename A2, typename CvItem >
70 static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2, void (Body::*)(CvItem, parallel_do_feeder<Item>&) const ) {
71 obj(tbb::internal::forward<A1>(arg1), arg2);
72 }
73 template<typename A1, typename A2, typename CvItem >
74 static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2&, void (Body::*)(CvItem&) const ) {
75 obj(arg1);
76 }
77 template<typename A1, typename A2, typename CvItem >
78 static void internal_call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2, void (Body::*)(CvItem&, parallel_do_feeder<Item>&) const ) {
79 obj(arg1, arg2);
80 }
81 public:
82 template<typename A1, typename A2>
83 static void call( const Body& obj, __TBB_FORWARDING_REF(A1) arg1, A2& arg2 )
84 {
85 internal_call( obj, tbb::internal::forward<A1>(arg1), arg2, &Body::operator() );
86 }
87 };
88
89 //! For internal use only.
90 /** Executes one iteration of a do.
91 @ingroup algorithms */
92 template<typename Body, typename Item>
93 class do_iteration_task: public task
94 {
95 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
96
97 Item my_value;
98 feeder_type& my_feeder;
99
100 do_iteration_task( const Item& value, feeder_type& feeder ) :
101 my_value(value), my_feeder(feeder)
102 {}
103
104#if __TBB_CPP11_RVALUE_REF_PRESENT
105 do_iteration_task( Item&& value, feeder_type& feeder ) :
106 my_value(std::move(value)), my_feeder(feeder)
107 {}
108#endif
109
110 task* execute() __TBB_override
111 {
112 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, tbb::internal::move(my_value), my_feeder);
113 return NULL;
114 }
115
116 template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
117 }; // class do_iteration_task
118
119 template<typename Iterator, typename Body, typename Item>
120 class do_iteration_task_iter: public task
121 {
122 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
123
124 Iterator my_iter;
125 feeder_type& my_feeder;
126
127 do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
128 my_iter(iter), my_feeder(feeder)
129 {}
130
131 task* execute() __TBB_override
132 {
133 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, *my_iter, my_feeder);
134 return NULL;
135 }
136
137 template<typename Iterator_, typename Body_, typename Item_> friend class do_group_task_forward;
138 template<typename Body_, typename Item_> friend class do_group_task_input;
139 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
140 }; // class do_iteration_task_iter
141
142 //! For internal use only.
143 /** Implements new task adding procedure.
144 @ingroup algorithms **/
145 template<class Body, typename Item>
146 class parallel_do_feeder_impl : public parallel_do_feeder<Item>
147 {
148#if __TBB_CPP11_RVALUE_REF_PRESENT
149 //Avoiding use of copy constructor in a virtual method if the type does not support it
150 void internal_add_copy_impl(std::true_type, const Item& item) {
151 typedef do_iteration_task<Body, Item> iteration_type;
152 iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
153 task::spawn(t);
154 }
155 void internal_add_copy_impl(std::false_type, const Item&) {
156 __TBB_ASSERT(false, "Overloading for r-value reference doesn't work or it's not movable and not copyable object");
157 }
158 void internal_add_copy( const Item& item ) __TBB_override
159 {
160#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
161 internal_add_copy_impl(typename std::is_copy_constructible<Item>::type(), item);
162#else
163 internal_add_copy_impl(std::true_type(), item);
164#endif
165 }
166 void internal_add_move( Item&& item ) __TBB_override
167 {
168 typedef do_iteration_task<Body, Item> iteration_type;
169 iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(std::move(item), *this);
170 task::spawn(t);
171 }
172#else /* ! __TBB_CPP11_RVALUE_REF_PRESENT */
173 void internal_add_copy(const Item& item) __TBB_override {
174 typedef do_iteration_task<Body, Item> iteration_type;
175 iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
176 task::spawn(t);
177 }
178#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
179 public:
180 const Body* my_body;
181 empty_task* my_barrier;
182
183 parallel_do_feeder_impl()
184 {
185 my_barrier = new( task::allocate_root() ) empty_task();
186 __TBB_ASSERT(my_barrier, "root task allocation failed");
187 }
188
189#if __TBB_TASK_GROUP_CONTEXT
190 parallel_do_feeder_impl(tbb::task_group_context &context)
191 {
192 my_barrier = new( task::allocate_root(context) ) empty_task();
193 __TBB_ASSERT(my_barrier, "root task allocation failed");
194 }
195#endif
196
197 ~parallel_do_feeder_impl()
198 {
199 my_barrier->destroy(*my_barrier);
200 }
201 }; // class parallel_do_feeder_impl
202
203
204 //! For internal use only
205 /** Unpacks a block of iterations.
206 @ingroup algorithms */
207
208 template<typename Iterator, typename Body, typename Item>
209 class do_group_task_forward: public task
210 {
211 static const size_t max_arg_size = 4;
212
213 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
214
215 feeder_type& my_feeder;
216 Iterator my_first;
217 size_t my_size;
218
219 do_group_task_forward( Iterator first, size_t size, feeder_type& feeder )
220 : my_feeder(feeder), my_first(first), my_size(size)
221 {}
222
223 task* execute() __TBB_override
224 {
225 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
226 __TBB_ASSERT( my_size>0, NULL );
227 task_list list;
228 task* t;
229 size_t k=0;
230 for(;;) {
231 t = new( allocate_child() ) iteration_type( my_first, my_feeder );
232 ++my_first;
233 if( ++k==my_size ) break;
234 list.push_back(*t);
235 }
236 set_ref_count(int(k+1));
237 spawn(list);
238 spawn_and_wait_for_all(*t);
239 return NULL;
240 }
241
242 template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
243 }; // class do_group_task_forward
244
245 template<typename Body, typename Item>
246 class do_group_task_input: public task
247 {
248 static const size_t max_arg_size = 4;
249
250 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
251
252 feeder_type& my_feeder;
253 size_t my_size;
254 aligned_space<Item, max_arg_size> my_arg;
255
256 do_group_task_input( feeder_type& feeder )
257 : my_feeder(feeder), my_size(0)
258 {}
259
260 task* execute() __TBB_override
261 {
262#if __TBB_CPP11_RVALUE_REF_PRESENT
263 typedef std::move_iterator<Item*> Item_iterator;
264#else
265 typedef Item* Item_iterator;
266#endif
267 typedef do_iteration_task_iter<Item_iterator, Body, Item> iteration_type;
268 __TBB_ASSERT( my_size>0, NULL );
269 task_list list;
270 task* t;
271 size_t k=0;
272 for(;;) {
273 t = new( allocate_child() ) iteration_type( Item_iterator(my_arg.begin() + k), my_feeder );
274 if( ++k==my_size ) break;
275 list.push_back(*t);
276 }
277 set_ref_count(int(k+1));
278 spawn(list);
279 spawn_and_wait_for_all(*t);
280 return NULL;
281 }
282
283 ~do_group_task_input(){
284 for( size_t k=0; k<my_size; ++k)
285 (my_arg.begin() + k)->~Item();
286 }
287
288 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
289 }; // class do_group_task_input
290
291 //! For internal use only.
292 /** Gets block of iterations and packages them into a do_group_task.
293 @ingroup algorithms */
294 template<typename Iterator, typename Body, typename Item>
295 class do_task_iter: public task
296 {
297 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
298
299 public:
300 do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) :
301 my_first(first), my_last(last), my_feeder(feeder)
302 {}
303
304 private:
305 Iterator my_first;
306 Iterator my_last;
307 feeder_type& my_feeder;
308
309 /* Do not merge run(xxx) and run_xxx() methods. They are separated in order
310 to make sure that compilers will eliminate unused argument of type xxx
311 (that is will not put it on stack). The sole purpose of this argument
312 is overload resolution.
313
314 An alternative could be using template functions, but explicit specialization
315 of member function templates is not supported for non specialized class
316 templates. Besides template functions would always fall back to the least
317 efficient variant (the one for input iterators) in case of iterators having
318 custom tags derived from basic ones. */
319 task* execute() __TBB_override
320 {
321 typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
322 return run( (iterator_tag*)NULL );
323 }
324
325 /** This is the most restricted variant that operates on input iterators or
326 iterators with unknown tags (tags not derived from the standard ones). **/
327 inline task* run( void* ) { return run_for_input_iterator(); }
328
329 task* run_for_input_iterator() {
330 typedef do_group_task_input<Body, Item> block_type;
331
332 block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
333 size_t k=0;
334 while( !(my_first == my_last) ) {
335 // Move semantics are automatically used when supported by the iterator
336 new (t.my_arg.begin() + k) Item(*my_first);
337 ++my_first;
338 if( ++k==block_type::max_arg_size ) {
339 if ( !(my_first == my_last) )
340 recycle_to_reexecute();
341 break;
342 }
343 }
344 if( k==0 ) {
345 destroy(t);
346 return NULL;
347 } else {
348 t.my_size = k;
349 return &t;
350 }
351 }
352
353 inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
354
355 task* run_for_forward_iterator() {
356 typedef do_group_task_forward<Iterator, Body, Item> block_type;
357
358 Iterator first = my_first;
359 size_t k=0;
360 while( !(my_first==my_last) ) {
361 ++my_first;
362 if( ++k==block_type::max_arg_size ) {
363 if ( !(my_first==my_last) )
364 recycle_to_reexecute();
365 break;
366 }
367 }
368 return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
369 }
370
371 inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
372
373 task* run_for_random_access_iterator() {
374 typedef do_group_task_forward<Iterator, Body, Item> block_type;
375 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
376
377 size_t k = static_cast<size_t>(my_last-my_first);
378 if( k > block_type::max_arg_size ) {
379 Iterator middle = my_first + k/2;
380
381 empty_task& c = *new( allocate_continuation() ) empty_task;
382 do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
383 recycle_as_child_of(c);
384
385 my_last = middle;
386 c.set_ref_count(2);
387 c.spawn(b);
388 return this;
389 }else if( k != 0 ) {
390 task_list list;
391 task* t;
392 size_t k1=0;
393 for(;;) {
394 t = new( allocate_child() ) iteration_type(my_first, my_feeder);
395 ++my_first;
396 if( ++k1==k ) break;
397 list.push_back(*t);
398 }
399 set_ref_count(int(k+1));
400 spawn(list);
401 spawn_and_wait_for_all(*t);
402 }
403 return NULL;
404 }
405 }; // class do_task_iter
406
407 //! For internal use only.
408 /** Implements parallel iteration over a range.
409 @ingroup algorithms */
410 template<typename Iterator, typename Body, typename Item>
411 void run_parallel_do( Iterator first, Iterator last, const Body& body
412#if __TBB_TASK_GROUP_CONTEXT
413 , task_group_context& context
414#endif
415 )
416 {
417 typedef do_task_iter<Iterator, Body, Item> root_iteration_task;
418#if __TBB_TASK_GROUP_CONTEXT
419 parallel_do_feeder_impl<Body, Item> feeder(context);
420#else
421 parallel_do_feeder_impl<Body, Item> feeder;
422#endif
423 feeder.my_body = &body;
424
425 root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
426
427 feeder.my_barrier->set_ref_count(2);
428 feeder.my_barrier->spawn_and_wait_for_all(t);
429 }
430
431 //! For internal use only.
432 /** Detects types of Body's operator function arguments.
433 @ingroup algorithms **/
434 template<typename Iterator, typename Body, typename Item>
435 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const
436#if __TBB_TASK_GROUP_CONTEXT
437 , task_group_context& context
438#endif
439 )
440 {
441 run_parallel_do<Iterator, Body, typename ::tbb::internal::strip<Item>::type>( first, last, body
442#if __TBB_TASK_GROUP_CONTEXT
443 , context
444#endif
445 );
446 }
447
448 //! For internal use only.
449 /** Detects types of Body's operator function arguments.
450 @ingroup algorithms **/
451 template<typename Iterator, typename Body, typename Item, typename _Item>
452 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item, parallel_do_feeder<_Item>&) const
453#if __TBB_TASK_GROUP_CONTEXT
454 , task_group_context& context
455#endif
456 )
457 {
458 run_parallel_do<Iterator, Body, typename ::tbb::internal::strip<Item>::type>( first, last, body
459#if __TBB_TASK_GROUP_CONTEXT
460 , context
461#endif
462 );
463 }
464
465} // namespace internal
466} // namespace interface9
467//! @endcond
468
469/** \page parallel_do_body_req Requirements on parallel_do body
470 Class \c Body implementing the concept of parallel_do body must define:
471 - \code
472 B::operator()(
473 cv_item_type item,
474 parallel_do_feeder<item_type>& feeder
475 ) const
476
477 OR
478
479 B::operator()( cv_item_type& item ) const
480 \endcode Process item.
481 May be invoked concurrently for the same \c this but different \c item.
482
483 - \code item_type( const item_type& ) \endcode
484 Copy a work item.
485 - \code ~item_type() \endcode Destroy a work item
486**/
487
488/** \name parallel_do
489 See also requirements on \ref parallel_do_body_req "parallel_do Body". **/
490//@{
491//! Parallel iteration over a range, with optional addition of more work.
492/** @ingroup algorithms */
493template<typename Iterator, typename Body>
494void parallel_do( Iterator first, Iterator last, const Body& body )
495{
496 if ( first == last )
497 return;
498#if __TBB_TASK_GROUP_CONTEXT
499 task_group_context context(internal::PARALLEL_DO);
500#endif
501 interface9::internal::select_parallel_do( first, last, body, &Body::operator()
502#if __TBB_TASK_GROUP_CONTEXT
503 , context
504#endif
505 );
506}
507
508template<typename Range, typename Body>
509void parallel_do(Range& rng, const Body& body) {
510 parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body);
511}
512
513template<typename Range, typename Body>
514void parallel_do(const Range& rng, const Body& body) {
515 parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body);
516}
517
518#if __TBB_TASK_GROUP_CONTEXT
519//! Parallel iteration over a range, with optional addition of more work and user-supplied context
520/** @ingroup algorithms */
521template<typename Iterator, typename Body>
522void parallel_do( Iterator first, Iterator last, const Body& body, task_group_context& context )
523{
524 if ( first == last )
525 return;
526 interface9::internal::select_parallel_do( first, last, body, &Body::operator(), context );
527}
528
529template<typename Range, typename Body>
530void parallel_do(Range& rng, const Body& body, task_group_context& context) {
531 parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body, context);
532}
533
534template<typename Range, typename Body>
535void parallel_do(const Range& rng, const Body& body, task_group_context& context) {
536 parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body, context);
537}
538
539#endif // __TBB_TASK_GROUP_CONTEXT
540
541//@}
542
543using interface9::parallel_do_feeder;
544
545} // namespace
546
547#endif /* __TBB_parallel_do_H */
548