Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
parallel_do.h
Go to the documentation of this file.
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 
22 #include "task.h"
23 #include "aligned_space.h"
24 #include <iterator>
25 
26 namespace tbb {
27 namespace interface9 {
29 namespace internal {
30  template<typename Body, typename Item> class parallel_do_feeder_impl;
31 } // namespace internal
33 
35 
36  template<typename Item>
38  {
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:
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 
55 namespace internal {
56  template<typename Body> class do_group_task;
57 
59 
61  template<class Body, typename Item>
63  {
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 
90 
92  template<typename Body, typename Item>
93  class do_iteration_task: public task
94  {
96 
97  Item my_value;
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 
111  {
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>
121  {
123 
124  Iterator my_iter;
126 
127  do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
128  my_iter(iter), my_feeder(feeder)
129  {}
130 
132  {
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 
143 
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  }
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
162 #else
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;
182 
184  {
186  __TBB_ASSERT(my_barrier, "root task allocation failed");
187  }
188 
189 #if __TBB_TASK_GROUP_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 
198  {
199  my_barrier->destroy(*my_barrier);
200  }
201  }; // class parallel_do_feeder_impl
202 
203 
205 
208  template<typename Iterator, typename Body, typename Item>
210  {
211  static const size_t max_arg_size = 4;
212 
214 
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 
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);
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 
251 
253  size_t my_size;
255 
257  : my_feeder(feeder), my_size(0)
258  {}
259 
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
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);
280  return NULL;
281  }
282 
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 
292 
294  template<typename Iterator, typename Body, typename Item>
295  class do_task_iter: public task
296  {
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;
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. */
320  {
321  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
322  return run( (iterator_tag*)NULL );
323  }
324 
327  inline task* run( void* ) { return run_for_input_iterator(); }
328 
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) )
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 
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) )
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 
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 
382  do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
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);
402  }
403  return NULL;
404  }
405  }; // class do_task_iter
406 
408 
410  template<typename Iterator, typename Body, typename Item>
411  void run_parallel_do( Iterator first, Iterator last, const Body& body
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
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 
432 
434  template<typename Iterator, typename Body, typename Item>
435  void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const
437  , task_group_context& context
438 #endif
439  )
440  {
442 #if __TBB_TASK_GROUP_CONTEXT
443  , context
444 #endif
445  );
446  }
447 
449 
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
454  , task_group_context& context
455 #endif
456  )
457  {
459 #if __TBB_TASK_GROUP_CONTEXT
460  , context
461 #endif
462  );
463  }
464 
465 } // namespace internal
466 } // namespace interface9
468 
491 
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()
503  , context
504 #endif
505  );
506 }
507 
508 template<typename Range, typename Body>
509 void parallel_do(Range& rng, const Body& body) {
511 }
512 
513 template<typename Range, typename Body>
514 void parallel_do(const Range& rng, const Body& body) {
516 }
517 
518 #if __TBB_TASK_GROUP_CONTEXT
519 
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 
542 
543 using interface9::parallel_do_feeder;
544 
545 } // namespace
546 
547 #endif /* __TBB_parallel_do_H */
void run_parallel_do(Iterator first, Iterator last, const Body &body, task_group_context &context)
For internal use only.
Definition: parallel_do.h:411
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
virtual void internal_add_move(Item &&item)=0
Class the user supplied algorithm body uses to add new tasks.
Definition: parallel_do.h:37
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:319
static void call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2)
Definition: parallel_do.h:83
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
internal::allocate_continuation_proxy & allocate_continuation()
Returns proxy for overloaded new that allocates a continuation task of *this.
Definition: task.h:646
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:223
do_task_iter(Iterator first, Iterator last, feeder_type &feeder)
Definition: parallel_do.h:300
void select_parallel_do(Iterator first, Iterator last, const Body &body, void(Body::*)(Item) const, task_group_context &context)
For internal use only.
Definition: parallel_do.h:435
task that does nothing. Useful for synchronization.
Definition: task.h:964
void recycle_to_reexecute()
Schedule this for reexecution after current execute() returns.
Definition: task.h:711
Used to form groups of tasks.
Definition: task.h:332
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &, void(Body::*)(CvItem) const)
Definition: parallel_do.h:66
friend class internal::parallel_do_feeder_impl
Definition: parallel_do.h:45
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:131
#define __TBB_FORWARDING_REF(A)
Definition: tbb_stddef.h:496
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:331
void parallel_do(Iterator first, Iterator last, const Body &body)
Parallel iteration over a range, with optional addition of more work.
Definition: parallel_do.h:494
void add(const Item &item)
Add a work item to a running parallel_do.
Definition: parallel_do.h:48
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
#define __TBB_override
Definition: tbb_stddef.h:240
A list of children.
Definition: task.h:995
Base class for user-defined tasks.
Definition: task.h:589
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:110
The graph class.
aligned_space< Item, max_arg_size > my_arg
Definition: parallel_do.h:254
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:122
void internal_add_move(Item &&item) __TBB_override
Definition: parallel_do.h:166
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t size
void internal_add_copy_impl(std::false_type, const Item &)
Definition: parallel_do.h:155
task * run(std::forward_iterator_tag *)
Definition: parallel_do.h:353
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:297
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2, void(Body::*)(CvItem &, parallel_do_feeder< Item > &) const)
Definition: parallel_do.h:78
do_iteration_task(const Item &value, feeder_type &feeder)
Definition: parallel_do.h:100
do_group_task_forward(Iterator first, size_t size, feeder_type &feeder)
Definition: parallel_do.h:219
auto first(Container &c) -> decltype(begin(c))
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &arg2, void(Body::*)(CvItem, parallel_do_feeder< Item > &) const)
Definition: parallel_do.h:70
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:250
virtual void internal_add_copy(const Item &item)=0
void push_back(task &task)
Push task onto back of list.
Definition: task.h:1012
parallel_do_feeder_impl(tbb::task_group_context &context)
Definition: parallel_do.h:190
T * begin() const
Pointer to beginning of array.
Definition: aligned_space.h:35
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
Definition: tbb_stddef.h:469
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:95
static void internal_call(const Body &obj, __TBB_FORWARDING_REF(A1) arg1, A2 &, void(Body::*)(CvItem &) const)
Definition: parallel_do.h:74
bool_constant< true > true_type
Definition: tbb_stddef.h:468
void recycle_as_child_of(task &new_parent)
Change this to be a child of new_parent.
Definition: task.h:695
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: parallel_do.h:260
void internal_add_copy(const Item &item) __TBB_override
Definition: parallel_do.h:158
#define __TBB_TASK_GROUP_CONTEXT
Definition: tbb_config.h:535
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
do_iteration_task_iter(const Iterator &iter, feeder_type &feeder)
Definition: parallel_do.h:127
void internal_add_copy_impl(std::true_type, const Item &item)
Definition: parallel_do.h:150
void spawn_and_wait_for_all(task &child)
Similar to spawn followed by wait_for_all, but more efficient.
Definition: task.h:770
internal::allocate_child_proxy & allocate_child()
Returns proxy for overloaded new that allocates a child task of *this.
Definition: task.h:651
do_iteration_task(Item &&value, feeder_type &feeder)
Definition: parallel_do.h:105
void set_ref_count(int count)
Set reference count.
Definition: task.h:731
parallel_do_feeder_impl< Body, Item > feeder_type
Definition: parallel_do.h:213
task * run(std::random_access_iterator_tag *)
Definition: parallel_do.h:371
static internal::allocate_root_proxy allocate_root()
Returns proxy for overloaded new that allocates a root task.
Definition: task.h:633

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.