00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef __TBB_parallel_do_H
00022 #define __TBB_parallel_do_H
00023
00024 #include "task.h"
00025 #include "aligned_space.h"
00026 #include <iterator>
00027
00028 namespace tbb {
00029
00031 namespace internal {
00032 template<typename Body, typename Item> class parallel_do_feeder_impl;
00033 template<typename Body> class do_group_task;
00034
00036 template<typename T>
00037 struct strip { typedef T type; };
00038 template<typename T>
00039 struct strip<T&> { typedef T type; };
00040 template<typename T>
00041 struct strip<const T&> { typedef T type; };
00042 template<typename T>
00043 struct strip<volatile T&> { typedef T type; };
00044 template<typename T>
00045 struct strip<const volatile T&> { typedef T type; };
00046
00047
00048 template<typename T>
00049 struct strip<const T> { typedef T type; };
00050 template<typename T>
00051 struct strip<volatile T> { typedef T type; };
00052 template<typename T>
00053 struct strip<const volatile T> { typedef T type; };
00054 }
00056
00058
00059 template<typename Item>
00060 class parallel_do_feeder: internal::no_copy
00061 {
00062 parallel_do_feeder() {}
00063 virtual ~parallel_do_feeder () {}
00064 virtual void internal_add( const Item& item ) = 0;
00065 template<typename Body_, typename Item_> friend class internal::parallel_do_feeder_impl;
00066 public:
00068 void add( const Item& item ) {internal_add(item);}
00069 };
00070
00072 namespace internal {
00074
00076 template<class Body, typename Item>
00077 class parallel_do_operator_selector
00078 {
00079 typedef parallel_do_feeder<Item> Feeder;
00080 template<typename A1, typename A2, typename CvItem >
00081 static void internal_call( const Body& obj, A1& arg1, A2&, void (Body::*)(CvItem) const ) {
00082 obj(arg1);
00083 }
00084 template<typename A1, typename A2, typename CvItem >
00085 static void internal_call( const Body& obj, A1& arg1, A2& arg2, void (Body::*)(CvItem, parallel_do_feeder<Item>&) const ) {
00086 obj(arg1, arg2);
00087 }
00088
00089 public:
00090 template<typename A1, typename A2 >
00091 static void call( const Body& obj, A1& arg1, A2& arg2 )
00092 {
00093 internal_call( obj, arg1, arg2, &Body::operator() );
00094 }
00095 };
00096
00098
00100 template<typename Body, typename Item>
00101 class do_iteration_task: public task
00102 {
00103 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
00104
00105 Item my_value;
00106 feeder_type& my_feeder;
00107
00108 do_iteration_task( const Item& value, feeder_type& feeder ) :
00109 my_value(value), my_feeder(feeder)
00110 {}
00111
00112
00113 task* execute()
00114 {
00115 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, my_value, my_feeder);
00116 return NULL;
00117 }
00118
00119 template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
00120 };
00121
00122 template<typename Iterator, typename Body, typename Item>
00123 class do_iteration_task_iter: public task
00124 {
00125 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
00126
00127 Iterator my_iter;
00128 feeder_type& my_feeder;
00129
00130 do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
00131 my_iter(iter), my_feeder(feeder)
00132 {}
00133
00134
00135 task* execute()
00136 {
00137 parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, *my_iter, my_feeder);
00138 return NULL;
00139 }
00140
00141 template<typename Iterator_, typename Body_, typename Item_> friend class do_group_task_forward;
00142 template<typename Body_, typename Item_> friend class do_group_task_input;
00143 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
00144 };
00145
00147
00149 template<class Body, typename Item>
00150 class parallel_do_feeder_impl : public parallel_do_feeder<Item>
00151 {
00152
00153 void internal_add( const Item& item )
00154 {
00155 typedef do_iteration_task<Body, Item> iteration_type;
00156
00157 iteration_type& t = *new (task::self().allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
00158
00159 t.spawn( t );
00160 }
00161 public:
00162 const Body* my_body;
00163 empty_task* my_barrier;
00164 };
00165
00166
00168
00171 template<typename Iterator, typename Body, typename Item>
00172 class do_group_task_forward: public task
00173 {
00174 static const size_t max_arg_size = 4;
00175
00176 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
00177
00178 feeder_type& my_feeder;
00179 Iterator my_first;
00180 size_t my_size;
00181
00182 do_group_task_forward( Iterator first, size_t size, feeder_type& feeder )
00183 : my_feeder(feeder), my_first(first), my_size(size)
00184 {}
00185
00186 task* execute()
00187 {
00188 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
00189 __TBB_ASSERT( my_size>0, NULL );
00190 task_list list;
00191 task* t;
00192 size_t k=0;
00193 for(;;) {
00194 t = new( allocate_child() ) iteration_type( my_first, my_feeder );
00195 ++my_first;
00196 if( ++k==my_size ) break;
00197 list.push_back(*t);
00198 }
00199 set_ref_count(int(k+1));
00200 spawn(list);
00201 spawn_and_wait_for_all(*t);
00202 return NULL;
00203 }
00204
00205 template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
00206 };
00207
00208 template<typename Body, typename Item>
00209 class do_group_task_input: public task
00210 {
00211 static const size_t max_arg_size = 4;
00212
00213 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
00214
00215 feeder_type& my_feeder;
00216 size_t my_size;
00217 aligned_space<Item, max_arg_size> my_arg;
00218
00219 do_group_task_input( feeder_type& feeder )
00220 : my_feeder(feeder), my_size(0)
00221 {}
00222
00223 task* execute()
00224 {
00225 typedef do_iteration_task_iter<Item*, Body, Item> iteration_type;
00226 __TBB_ASSERT( my_size>0, NULL );
00227 task_list list;
00228 task* t;
00229 size_t k=0;
00230 for(;;) {
00231 t = new( allocate_child() ) iteration_type( my_arg.begin() + k, my_feeder );
00232 if( ++k==my_size ) break;
00233 list.push_back(*t);
00234 }
00235 set_ref_count(int(k+1));
00236 spawn(list);
00237 spawn_and_wait_for_all(*t);
00238 return NULL;
00239 }
00240
00241 ~do_group_task_input(){
00242 for( size_t k=0; k<my_size; ++k)
00243 (my_arg.begin() + k)->~Item();
00244 }
00245
00246 template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
00247 };
00248
00250
00252 template<typename Iterator, typename Body, typename Item>
00253 class do_task_iter: public task
00254 {
00255
00256 typedef parallel_do_feeder_impl<Body, Item> feeder_type;
00257
00258 public:
00259 do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) :
00260 my_first(first), my_last(last), my_feeder(feeder)
00261 {}
00262
00263 private:
00264 Iterator my_first;
00265 Iterator my_last;
00266 feeder_type& my_feeder;
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278 task* execute()
00279 {
00280 typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
00281 return run( (iterator_tag*)NULL );
00282 }
00283
00286 inline task* run( void* ) { return run_for_input_iterator(); }
00287
00288 task* run_for_input_iterator() {
00289 typedef do_group_task_input<Body, Item> block_type;
00290
00291 block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
00292 size_t k=0;
00293 while( !(my_first == my_last) ) {
00294 new (t.my_arg.begin() + k) Item(*my_first);
00295 ++my_first;
00296 if( ++k==block_type::max_arg_size ) {
00297 if ( !(my_first == my_last) )
00298 recycle_to_reexecute();
00299 break;
00300 }
00301 }
00302 if( k==0 ) {
00303 destroy(t);
00304 return NULL;
00305 } else {
00306 t.my_size = k;
00307 return &t;
00308 }
00309 }
00310
00311 inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
00312
00313 task* run_for_forward_iterator() {
00314 typedef do_group_task_forward<Iterator, Body, Item> block_type;
00315
00316 Iterator first = my_first;
00317 size_t k=0;
00318 while( !(my_first==my_last) ) {
00319 ++my_first;
00320 if( ++k==block_type::max_arg_size ) {
00321 if ( !(my_first==my_last) )
00322 recycle_to_reexecute();
00323 break;
00324 }
00325 }
00326 return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
00327 }
00328
00329 inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
00330
00331 task* run_for_random_access_iterator() {
00332 typedef do_group_task_forward<Iterator, Body, Item> block_type;
00333 typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
00334
00335 size_t k = static_cast<size_t>(my_last-my_first);
00336 if( k > block_type::max_arg_size ) {
00337 Iterator middle = my_first + k/2;
00338
00339 empty_task& c = *new( allocate_continuation() ) empty_task;
00340 do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
00341 recycle_as_child_of(c);
00342
00343 my_last = middle;
00344 c.set_ref_count(2);
00345 c.spawn(b);
00346 return this;
00347 }else if( k != 0 ) {
00348 task_list list;
00349 task* t;
00350 size_t k1=0;
00351 for(;;) {
00352 t = new( allocate_child() ) iteration_type(my_first, my_feeder);
00353 ++my_first;
00354 if( ++k1==k ) break;
00355 list.push_back(*t);
00356 }
00357 set_ref_count(int(k+1));
00358 spawn(list);
00359 spawn_and_wait_for_all(*t);
00360 }
00361 return NULL;
00362 }
00363 };
00364
00366
00368 template<typename Iterator, typename Body, typename Item>
00369 void run_parallel_do( Iterator first, Iterator last, const Body& body )
00370 {
00371 typedef do_task_iter<Iterator, Body, Item> root_iteration_task;
00372 parallel_do_feeder_impl<Body, Item> feeder;
00373 feeder.my_body = &body;
00374 feeder.my_barrier = new( task::allocate_root() ) empty_task();
00375 __TBB_ASSERT(feeder.my_barrier, "root task allocation failed");
00376
00377 root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
00378
00379 feeder.my_barrier->set_ref_count(2);
00380 feeder.my_barrier->spawn_and_wait_for_all(t);
00381
00382 feeder.my_barrier->destroy(*feeder.my_barrier);
00383 }
00384
00386
00388 template<typename Iterator, typename Body, typename Item>
00389 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const )
00390 {
00391 run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body );
00392 }
00393
00395
00397 template<typename Iterator, typename Body, typename Item, typename _Item>
00398 void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item, parallel_do_feeder<_Item>&) const )
00399 {
00400 run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body );
00401 }
00402
00403 }
00405
00406
00429
00430
00431 template<typename Iterator, typename Body>
00432 void parallel_do( Iterator first, Iterator last, const Body& body )
00433 {
00434 if ( first == last )
00435 return;
00436 internal::select_parallel_do( first, last, body, &Body::operator() );
00437 }
00439
00440 }
00441
00442 #endif