/*
- Copyright 2005-2011 Intel Corporation. All Rights Reserved.
-
- This file is part of Threading Building Blocks.
-
- Threading Building Blocks is free software; you can redistribute it
- and/or modify it under the terms of the GNU General Public License
- version 2 as published by the Free Software Foundation.
-
- Threading Building Blocks is distributed in the hope that it will be
- useful, but WITHOUT ANY WARRANTY; without even the implied warranty
- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with Threading Building Blocks; if not, write to the Free Software
- Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
-
- As a special exception, you may use this file as part of a free software
- library without restriction. Specifically, if other files instantiate
- templates or use macros or inline functions from this file, or you compile
- this file and link it with other files to produce an executable, this
- file does not by itself cause the resulting executable to be covered by
- the GNU General Public License. This exception does not however
- invalidate any other reasons why the executable file might be covered by
- the GNU General Public License.
+ Copyright 2005-2014 Intel Corporation. All Rights Reserved.
+
+ This file is part of Threading Building Blocks. Threading Building Blocks is free software;
+ you can redistribute it and/or modify it under the terms of the GNU General Public License
+ version 2 as published by the Free Software Foundation. Threading Building Blocks is
+ distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
+ implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ See the GNU General Public License for more details. You should have received a copy of
+ the GNU General Public License along with Threading Building Blocks; if not, write to the
+ Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+ As a special exception, you may use this file as part of a free software library without
+ restriction. Specifically, if other files instantiate templates or use macros or inline
+ functions from this file, or you compile this file and link it with other files to produce
+ an executable, this file does not by itself cause the resulting executable to be covered
+ by the GNU General Public License. This exception does not however invalidate any other
+ reasons why the executable file might be covered by the GNU General Public License.
*/
#ifndef __TBB_parallel_reduce_H
namespace tbb {
-namespace interface6 {
+namespace interface7 {
//! @cond INTERNAL
namespace internal {
using namespace tbb::internal;
- //! 0 if root, 1 if a left child, 2 if a right child.
+ /** Values for reduction_context. */
+ enum {
+ root_task, left_child, right_child
+ };
+
/** Represented as a char, not enum, for compactness. */
typedef char reduction_context;
- //! Task type use to combine the partial results of parallel_reduce.
+ //! Task type used to combine the partial results of parallel_reduce.
/** @ingroup algorithms */
template<typename Body>
class finish_reduce: public flag_task {
- //! Pointer to body, or NULL if the left child has not yet finished.
+ //! Pointer to body, or NULL if the left child has not yet finished.
bool has_right_zombie;
const reduction_context my_context;
Body* my_body;
- aligned_space<Body,1> zombie_space;
- finish_reduce( reduction_context context_ ) :
+ aligned_space<Body> zombie_space;
+ finish_reduce( reduction_context context_ ) :
has_right_zombie(false), // TODO: substitute by flag_task::child_stolen?
my_context(context_),
my_body(NULL)
{
}
+ ~finish_reduce() {
+ if( has_right_zombie )
+ zombie_space.begin()->~Body();
+ }
task* execute() {
if( has_right_zombie ) {
// Right child was stolen.
Body* s = zombie_space.begin();
my_body->join( *s );
- s->~Body();
+ // Body::join() won't be called if canceled. Defer destruction to destructor
}
- if( my_context==1 ) // left child
+ if( my_context==left_child )
itt_store_word_with_release( static_cast<finish_reduce*>(parent())->my_body, my_body );
return NULL;
}
friend class start_reduce;
};
+ //! allocate right task with new parent
+ void allocate_sibling(task* start_reduce_task, task *tasks[], size_t start_bytes, size_t finish_bytes);
+
//! Task type used to split the work of parallel_reduce.
/** @ingroup algorithms */
template<typename Range, typename Body, typename Partitioner>
Body* my_body;
Range my_range;
typename Partitioner::task_partition_type my_partition;
- reduction_context my_context; // TODO: factor out into start_reduce_base
+ reduction_context my_context;
/*override*/ task* execute();
+ //! Update affinity info, if any
+ /*override*/ void note_affinity( affinity_id id ) {
+ my_partition.note_affinity( id );
+ }
template<typename Body_>
friend class finish_reduce;
-
+
public:
//! Constructor used for root task
start_reduce( const Range& range, Body* body, Partitioner& partitioner ) :
my_body(body),
my_range(range),
my_partition(partitioner),
- my_context(0)
+ my_context(root_task)
{
}
//! Splitting constructor used to generate children.
/** parent_ becomes left child. Newly constructed object is right child. */
- start_reduce( start_reduce& parent_, split ) :
+ start_reduce( start_reduce& parent_, typename Partitioner::split_type& split_obj ) :
my_body(parent_.my_body),
- my_range(parent_.my_range,split()),
- my_partition(parent_.my_partition,split()),
- my_context(2)
+ my_range(parent_.my_range, split_obj),
+ my_partition(parent_.my_partition, split_obj),
+ my_context(right_child)
{
my_partition.set_affinity(*this);
- parent_.my_context = 1;
+ parent_.my_context = left_child;
}
//! Construct right child from the given range as response to the demand.
/** parent_ remains left child. Newly constructed object is right child. */
start_reduce( start_reduce& parent_, const Range& r, depth_t d ) :
my_body(parent_.my_body),
my_range(r),
- my_partition(parent_.my_partition,split()),
- my_context(2) // right leaf mark
+ my_partition(parent_.my_partition, split()),
+ my_context(right_child)
{
my_partition.set_affinity(*this);
- my_partition.align_depth( d );
- parent_.my_context = 1; // left leaf mark
- }
- //! Update affinity info, if any
- /*override*/ void note_affinity( affinity_id id ) {
- my_partition.note_affinity( id );
+ my_partition.align_depth( d ); // TODO: move into constructor of partitioner
+ parent_.my_context = left_child;
}
static void run( const Range& range, Body& body, Partitioner& partitioner ) {
if( !range.empty() ) {
}
#if __TBB_TASK_GROUP_CONTEXT
static void run( const Range& range, Body& body, Partitioner& partitioner, task_group_context& context ) {
- if( !range.empty() )
+ if( !range.empty() )
task::spawn_root_and_wait( *new(task::allocate_root(context)) start_reduce(range,&body,partitioner) );
}
#endif /* __TBB_TASK_GROUP_CONTEXT */
- //! create a continuation task, serve as callback for partitioner
- finish_type *create_continuation() {
- return new( allocate_continuation() ) finish_type(my_context);
- }
//! Run body for range
void run_body( Range &r ) { (*my_body)( r ); }
+
+ //! spawn right task, serves as callback for partitioner
+ // TODO: remove code duplication from 'offer_work' methods
+ void offer_work(typename Partitioner::split_type& split_obj) {
+ task *tasks[2];
+ allocate_sibling(static_cast<task*>(this), tasks, sizeof(start_reduce), sizeof(finish_type));
+ new((void*)tasks[0]) finish_type(my_context);
+ new((void*)tasks[1]) start_reduce(*this, split_obj);
+ spawn(*tasks[1]);
+ }
+ //! spawn right task, serves as callback for partitioner
+ void offer_work(const Range& r, depth_t d = 0) {
+ task *tasks[2];
+ allocate_sibling(static_cast<task*>(this), tasks, sizeof(start_reduce), sizeof(finish_type));
+ new((void*)tasks[0]) finish_type(my_context);
+ new((void*)tasks[1]) start_reduce(*this, r, d);
+ spawn(*tasks[1]);
+ }
};
+
+ //! allocate right task with new parent
+ // TODO: 'inline' here is to avoid multiple definition error but for sake of code size this should not be inlined
+ inline void allocate_sibling(task* start_reduce_task, task *tasks[], size_t start_bytes, size_t finish_bytes) {
+ tasks[0] = &start_reduce_task->allocate_continuation().allocate(finish_bytes);
+ start_reduce_task->set_parent(tasks[0]);
+ tasks[0]->set_ref_count(2);
+ tasks[1] = &tasks[0]->allocate_child().allocate(start_bytes);
+ }
+
template<typename Range, typename Body, typename Partitioner>
task* start_reduce<Range,Body,Partitioner>::execute() {
my_partition.check_being_stolen( *this );
- if( my_context==2 ) { // right child
+ if( my_context==right_child ) {
finish_type* parent_ptr = static_cast<finish_type*>(parent());
if( !itt_load_word_with_acquire(parent_ptr->my_body) ) { // TODO: replace by is_stolen_task() or by parent_ptr->ref_count() == 2???
my_body = new( parent_ptr->zombie_space.begin() ) Body(*my_body,split());
parent_ptr->has_right_zombie = true;
}
- } else __TBB_ASSERT(my_context==0,0);// because left leaf spawns right leafs without recycling
+ } else __TBB_ASSERT(my_context==root_task,NULL);// because left leaf spawns right leafs without recycling
my_partition.execute(*this, my_range);
- if( my_context==1 ) {
+ if( my_context==left_child ) {
finish_type* parent_ptr = static_cast<finish_type*>(parent());
- __TBB_ASSERT(my_body!=parent_ptr->zombie_space.begin(),0);
+ __TBB_ASSERT(my_body!=parent_ptr->zombie_space.begin(),NULL);
itt_store_word_with_release(parent_ptr->my_body, my_body );
}
return NULL;
}
-#if TBB_PREVIEW_DETERMINISTIC_REDUCE
- //! Task type use to combine the partial results of parallel_deterministic_reduce.
+ //! Task type used to combine the partial results of parallel_deterministic_reduce.
/** @ingroup algorithms */
template<typename Body>
class finish_deterministic_reduce: public task {
}
#if __TBB_TASK_GROUP_CONTEXT
static void run( const Range& range, Body& body, task_group_context& context ) {
- if( !range.empty() )
+ if( !range.empty() )
task::spawn_root_and_wait( *new(task::allocate_root(context)) start_deterministic_reduce(range,body) );
}
#endif /* __TBB_TASK_GROUP_CONTEXT */
return this;
}
}
-#endif /* TBB_PREVIEW_DETERMINISTIC_REDUCE */
} // namespace internal
//! @endcond
} //namespace interfaceX
//! @cond INTERNAL
namespace internal {
- using interface6::internal::start_reduce;
-#if TBB_PREVIEW_DETERMINISTIC_REDUCE
- using interface6::internal::start_deterministic_reduce;
-#endif
+ using interface7::internal::start_reduce;
+ using interface7::internal::start_deterministic_reduce;
//! Auxiliary class for parallel_reduce; for internal use only.
/** The adaptor class that implements \ref parallel_reduce_body_req "parallel_reduce Body"
using given \ref parallel_reduce_lambda_req "anonymous function objects".
- \code Body::~Body(); \endcode Destructor
- \code void Body::operator()( Range& r ); \endcode Function call operator applying body to range \c r
and accumulating the result
- - \code void Body::join( Body& b ); \endcode Join results.
+ - \code void Body::join( Body& b ); \endcode Join results.
The result in \c b should be merged into the result of \c this
**/
}
#endif /* __TBB_TASK_GROUP_CONTEXT */
-#if TBB_PREVIEW_DETERMINISTIC_REDUCE
//! Parallel iteration with deterministic reduction and default partitioner.
/** @ingroup algorithms **/
template<typename Range, typename Body>
return body.result();
}
#endif /* __TBB_TASK_GROUP_CONTEXT */
-#endif /* TBB_PREVIEW_DETERMINISTIC_REDUCE */
//@}
} // namespace tbb
#endif /* __TBB_parallel_reduce_H */
-