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 | |
26 | namespace tbb { |
27 | namespace interface9 { |
28 | //! @cond INTERNAL |
29 | namespace 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 |
55 | namespace 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 */ |
493 | template<typename Iterator, typename Body> |
494 | void 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 | |
508 | template<typename Range, typename Body> |
509 | void parallel_do(Range& rng, const Body& body) { |
510 | parallel_do(tbb::internal::first(rng), tbb::internal::last(rng), body); |
511 | } |
512 | |
513 | template<typename Range, typename Body> |
514 | void 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 */ |
521 | template<typename Iterator, typename Body> |
522 | void 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 | |
529 | template<typename Range, typename Body> |
530 | void 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 | |
534 | template<typename Range, typename Body> |
535 | void 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 | |
543 | using interface9::parallel_do_feeder; |
544 | |
545 | } // namespace |
546 | |
547 | #endif /* __TBB_parallel_do_H */ |
548 | |