git.sesse.net Git - casparcg/blob - tbb30_20100406oss/include/tbb/parallel_do.h

   1 /*
   2     Copyright 2005-2010 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   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.
   9
  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.
  14
  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
  18
  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.
  27 */
  28
  29 #ifndef __TBB_parallel_do_H
  30 #define __TBB_parallel_do_H
  31
  32 #include "task.h"
  33 #include "aligned_space.h"
  34 #include <iterator>
  35
  36 namespace tbb {
  37
  38 //! @cond INTERNAL
  39 namespace internal {
  40     template<typename Body, typename Item> class parallel_do_feeder_impl;
  41     template<typename Body> class do_group_task;
  42
  43     //! Strips its template type argument from 'cv' and '&' qualifiers
  44     template<typename T>
  45     struct strip { typedef T type; };
  46     template<typename T>
  47     struct strip<T&> { typedef T type; };
  48     template<typename T>
  49     struct strip<const T&> { typedef T type; };
  50     template<typename T>
  51     struct strip<volatile T&> { typedef T type; };
  52     template<typename T>
  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.
  56     template<typename T>
  57     struct strip<const T> { typedef T type; };
  58     template<typename T>
  59     struct strip<volatile T> { typedef T type; };
  60     template<typename T>
  61     struct strip<const volatile T> { typedef T type; };
  62 } // namespace internal
  63 //! @endcond
  64
  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
  69 {
  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;
  74 public:
  75     //! Add a work item to a running parallel_do.
  76     void add( const Item& item ) {internal_add(item);}
  77 };
  78
  79 //! @cond INTERNAL
  80 namespace internal {
  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
  86     {
  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 ) {
  90             obj(arg1);
  91         }
  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 ) {
  94             obj(arg1, arg2);
  95         }
  96
  97     public:
  98         template<typename A1, typename A2 >
  99         static void call( const Body& obj, A1& arg1, A2& arg2 )
 100         {
 101             internal_call( obj, arg1, arg2, &Body::operator() );
 102         }
 103     };
 104
 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
 110     {
 111         typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 112
 113         Item my_value;
 114         feeder_type& my_feeder;
 115
 116         do_iteration_task( const Item& value, feeder_type& feeder ) :
 117             my_value(value), my_feeder(feeder)
 118         {}
 119
 120         /*override*/
 121         task* execute()
 122         {
 123             parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, my_value, my_feeder);
 124             return NULL;
 125         }
 126
 127         template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
 128     }; // class do_iteration_task
 129
 130     template<typename Iterator, typename Body, typename Item>
 131     class do_iteration_task_iter: public task
 132     {
 133         typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 134
 135         Iterator my_iter;
 136         feeder_type& my_feeder;
 137
 138         do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) :
 139             my_iter(iter), my_feeder(feeder)
 140         {}
 141
 142         /*override*/
 143         task* execute()
 144         {
 145             parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, *my_iter, my_feeder);
 146             return NULL;
 147         }
 148
 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
 153
 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>
 159     {
 160         /*override*/
 161         void internal_add( const Item& item )
 162         {
 163             typedef do_iteration_task<Body, Item> iteration_type;
 164
 165             iteration_type& t = *new (task::allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
 166
 167             t.spawn( t );
 168         }
 169     public:
 170         const Body* my_body;
 171         empty_task* my_barrier;
 172
 173         parallel_do_feeder_impl()
 174         {
 175             my_barrier = new( task::allocate_root() ) empty_task();
 176             __TBB_ASSERT(my_barrier, "root task allocation failed");
 177         }
 178
 179 #if __TBB_TASK_GROUP_CONTEXT
 180         parallel_do_feeder_impl(tbb::task_group_context &context)
 181         {
 182             my_barrier = new( task::allocate_root(context) ) empty_task();
 183             __TBB_ASSERT(my_barrier, "root task allocation failed");
 184         }
 185 #endif
 186
 187         ~parallel_do_feeder_impl()
 188         {
 189             my_barrier->destroy(*my_barrier);
 190         }
 191     }; // class parallel_do_feeder_impl
 192
 193
 194     //! For internal use only
 195     /** Unpacks a block of iterations.
 196         @ingroup algorithms */
 197
 198     template<typename Iterator, typename Body, typename Item>
 199     class do_group_task_forward: public task
 200     {
 201         static const size_t max_arg_size = 4;
 202
 203         typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 204
 205         feeder_type& my_feeder;
 206         Iterator my_first;
 207         size_t my_size;
 208
 209         do_group_task_forward( Iterator first, size_t size, feeder_type& feeder )
 210             : my_feeder(feeder), my_first(first), my_size(size)
 211         {}
 212
 213         /*override*/ task* execute()
 214         {
 215             typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
 216             __TBB_ASSERT( my_size>0, NULL );
 217             task_list list;
 218             task* t;
 219             size_t k=0;
 220             for(;;) {
 221                 t = new( allocate_child() ) iteration_type( my_first, my_feeder );
 222                 ++my_first;
 223                 if( ++k==my_size ) break;
 224                 list.push_back(*t);
 225             }
 226             set_ref_count(int(k+1));
 227             spawn(list);
 228             spawn_and_wait_for_all(*t);
 229             return NULL;
 230         }
 231
 232         template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
 233     }; // class do_group_task_forward
 234
 235     template<typename Body, typename Item>
 236     class do_group_task_input: public task
 237     {
 238         static const size_t max_arg_size = 4;
 239
 240         typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 241
 242         feeder_type& my_feeder;
 243         size_t my_size;
 244         aligned_space<Item, max_arg_size> my_arg;
 245
 246         do_group_task_input( feeder_type& feeder )
 247             : my_feeder(feeder), my_size(0)
 248         {}
 249
 250         /*override*/ task* execute()
 251         {
 252             typedef do_iteration_task_iter<Item*, Body, Item> iteration_type;
 253             __TBB_ASSERT( my_size>0, NULL );
 254             task_list list;
 255             task* t;
 256             size_t k=0;
 257             for(;;) {
 258                 t = new( allocate_child() ) iteration_type( my_arg.begin() + k, my_feeder );
 259                 if( ++k==my_size ) break;
 260                 list.push_back(*t);
 261             }
 262             set_ref_count(int(k+1));
 263             spawn(list);
 264             spawn_and_wait_for_all(*t);
 265             return NULL;
 266         }
 267
 268         ~do_group_task_input(){
 269             for( size_t k=0; k<my_size; ++k)
 270                 (my_arg.begin() + k)->~Item();
 271         }
 272
 273         template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
 274     }; // class do_group_task_input
 275
 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
 281     {
 282         typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 283
 284     public:
 285         do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) :
 286             my_first(first), my_last(last), my_feeder(feeder)
 287         {}
 288
 289     private:
 290         Iterator my_first;
 291         Iterator my_last;
 292         feeder_type& my_feeder;
 293
 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.
 298
 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()
 305         {
 306             typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
 307             return run( (iterator_tag*)NULL );
 308         }
 309
 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(); }
 313
 314         task* run_for_input_iterator() {
 315             typedef do_group_task_input<Body, Item> block_type;
 316
 317             block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
 318             size_t k=0;
 319             while( !(my_first == my_last) ) {
 320                 new (t.my_arg.begin() + k) Item(*my_first);
 321                 ++my_first;
 322                 if( ++k==block_type::max_arg_size ) {
 323                     if ( !(my_first == my_last) )
 324                         recycle_to_reexecute();
 325                     break;
 326                 }
 327             }
 328             if( k==0 ) {
 329                 destroy(t);
 330                 return NULL;
 331             } else {
 332                 t.my_size = k;
 333                 return &t;
 334             }
 335         }
 336
 337         inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
 338
 339         task* run_for_forward_iterator() {
 340             typedef do_group_task_forward<Iterator, Body, Item> block_type;
 341
 342             Iterator first = my_first;
 343             size_t k=0;
 344             while( !(my_first==my_last) ) {
 345                 ++my_first;
 346                 if( ++k==block_type::max_arg_size ) {
 347                     if ( !(my_first==my_last) )
 348                         recycle_to_reexecute();
 349                     break;
 350                 }
 351             }
 352             return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
 353         }
 354
 355         inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
 356
 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;
 360
 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;
 364
 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);
 368
 369                 my_last = middle;
 370                 c.set_ref_count(2);
 371                 c.spawn(b);
 372                 return this;
 373             }else if( k != 0 ) {
 374                 task_list list;
 375                 task* t;
 376                 size_t k1=0;
 377                 for(;;) {
 378                     t = new( allocate_child() ) iteration_type(my_first, my_feeder);
 379                     ++my_first;
 380                     if( ++k1==k ) break;
 381                     list.push_back(*t);
 382                 }
 383                 set_ref_count(int(k+1));
 384                 spawn(list);
 385                 spawn_and_wait_for_all(*t);
 386             }
 387             return NULL;
 388         }
 389     }; // class do_task_iter
 390
 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
 398 #endif
 399         )
 400     {
 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);
 404 #else
 405         parallel_do_feeder_impl<Body, Item> feeder;
 406 #endif
 407         feeder.my_body = &body;
 408
 409         root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
 410
 411         feeder.my_barrier->set_ref_count(2);
 412         feeder.my_barrier->spawn_and_wait_for_all(t);
 413     }
 414
 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
 423         )
 424     {
 425         run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
 426 #if __TBB_TASK_GROUP_CONTEXT
 427             , context
 428 #endif // __TBB_TASK_GROUP_CONTEXT
 429             );
 430     }
 431
 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
 440         )
 441     {
 442         run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
 443 #if __TBB_TASK_GROUP_CONTEXT
 444             , context
 445 #endif // __TBB_TASK_GROUP_CONTEXT
 446             );
 447     }
 448
 449 } // namespace internal
 450 //! @endcond
 451
 452
 453 /** \page parallel_do_body_req Requirements on parallel_do body
 454     Class \c Body implementing the concept of parallel_do body must define:
 455     - \code
 456         B::operator()(
 457                 cv_item_type item,
 458                 parallel_do_feeder<item_type>& feeder
 459         ) const
 460
 461         OR
 462
 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.
 466
 467     - \code item_type( const item_type& ) \endcode
 468                                                                     Copy a work item.
 469     - \code ~item_type() \endcode                            Destroy a work item
 470 **/
 471
 472 /** \name parallel_do
 473     See also requirements on \ref parallel_do_body_req "parallel_do Body". **/
 474 //@{
 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 )
 479 {
 480     if ( first == last )
 481         return;
 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
 487         , context
 488 #endif // __TBB_TASK_GROUP_CONTEXT
 489         );
 490 }
 491
 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  )
 497 {
 498     if ( first == last )
 499         return;
 500     internal::select_parallel_do( first, last, body, &Body::operator(), context );
 501 }
 502 #endif // __TBB_TASK_GROUP_CONTEXT
 503
 504 //@}
 505
 506 } // namespace
 507
 508 #endif /* __TBB_parallel_do_H */