17 #ifndef __TBB_parallel_scan_H 18 #define __TBB_parallel_scan_H 46 template<
typename Range,
typename Body>
56 my_body(body_,
split())
61 my_range.
begin()->~Range();
64 new( my_range.
begin() ) Range(range_);
65 my_stuff_last = stuff_last_;
71 my_stuff_last->assign(my_body);
78 template<
typename Range,
typename Body>
91 sum_node(
const Range range_,
bool left_is_final_ ) :
96 my_left_is_final(left_is_final_),
119 recycle_as_continuation();
122 task* a = my_left_is_final ? NULL : c.
create_child(my_range,*my_body,my_left,my_incoming,NULL);
123 set_ref_count( (a!=NULL)+(b!=NULL) );
132 template<
typename Range_,
typename Body_,
typename Partitioner_>
135 template<
typename Range_,
typename Body_>
141 template<
typename Range,
typename Body>
155 if( my_right_zombie && my_sum )
158 if( my_right_zombie || my_result.
my_right ) {
159 my_return_slot = &my_result;
161 destroy( my_result );
163 if( my_right_zombie && !my_sum && !my_result.
my_right ) {
164 destroy(*my_right_zombie);
165 my_right_zombie = NULL;
170 finish_scan( sum_node_type*& return_slot_, final_sum_type** sum_, sum_node_type& result_ ) :
172 my_return_slot(return_slot_),
173 my_right_zombie(NULL),
182 template<
typename Range,
typename Body,
typename Partitioner=simple_partitioner>
199 my_body(parent_.my_body),
200 my_sum(parent_.my_sum),
201 my_return_slot(&return_slot_),
202 my_parent_sum(parent_sum_),
203 my_is_final(parent_.my_is_final),
204 my_is_right_child(false),
205 my_range(parent_.my_range,
split()),
206 my_partition(parent_.my_partition,split())
211 start_scan( sum_node_type*& return_slot_,
const Range& range_, final_sum_type& body_,
const Partitioner& partitioner_) :
214 my_return_slot(&return_slot_),
217 my_is_right_child(false),
219 my_partition(partitioner_)
224 static void run(
const Range& range_, Body& body_,
const Partitioner& partitioner_ ) {
225 if( !range_.empty() ) {
226 typedef internal::start_scan<Range,Body,Partitioner> start_pass1_type;
227 internal::sum_node<Range,Body>* root = NULL;
234 temp_body->
my_body.reverse_join(body_);
237 root->my_body = temp_body;
238 root->my_incoming = NULL;
242 body_.assign(temp_body->
my_body);
244 temp_body->destroy(*temp_body);
250 template<
typename Range,
typename Body,
typename Partitioner>
252 typedef internal::finish_scan<Range,Body> finish_pass1_type;
253 finish_pass1_type*
p = my_parent_sum ?
static_cast<finish_pass1_type*
>(
parent() ) : NULL;
257 bool treat_as_stolen = my_is_right_child && (is_stolen_task() || my_body!=p->my_result.my_left_sum);
258 if( treat_as_stolen ) {
260 p->my_right_zombie = my_body =
new( allocate_root() )
final_sum_type(my_body->my_body);
263 task* next_task = NULL;
264 if( (my_is_right_child && !treat_as_stolen) || !my_range.is_divisible() || my_partition.should_execute_range(*
this) ) {
275 result =
new(allocate_additional_child_of(*my_parent_sum))
sum_node_type(my_range,my_is_final);
278 finish_pass1_type& c = *
new( allocate_continuation()) finish_pass1_type(*my_return_slot,my_sum,*result);
285 recycle_as_child_of(c);
289 my_return_slot = &result->
my_left;
290 my_is_right_child =
false;
292 my_parent_sum = result;
298 template<
typename Range,
typename Value,
typename Scan,
typename ReverseJoin>
307 , identity_element(identity)
309 , my_reverse_join(rev_join) {}
312 : my_sum(b.identity_element)
313 , identity_element(b.identity_element)
315 , my_reverse_join(b.my_reverse_join) {}
317 template<
typename Tag>
319 my_sum = my_scan(r, my_sum, tag);
323 my_sum = my_reverse_join(a.
my_sum, my_sum);
359 template<
typename Range,
typename Body>
366 template<
typename Range,
typename Body>
373 template<
typename Range,
typename Body>
380 template<
typename Range,
typename Value,
typename Scan,
typename ReverseJoin>
381 Value
parallel_scan(
const Range& range,
const Value& identity,
const Scan& scan,
const ReverseJoin& reverse_join ) {
382 internal::lambda_scan_body<Range, Value, Scan, ReverseJoin> body(identity, scan, reverse_join);
384 return body.result();
389 template<
typename Range,
typename Value,
typename Scan,
typename ReverseJoin>
391 internal::lambda_scan_body<Range, Value, Scan, ReverseJoin> body(identity, scan, reverse_join);
393 return body.result();
398 template<
typename Range,
typename Value,
typename Scan,
typename ReverseJoin>
400 internal::lambda_scan_body<Range, Value, Scan, ReverseJoin> body(identity, scan, reverse_join);
402 return body.result();
void assign(lambda_scan_body &b)
task * create_child(const Range &range_, final_sum_type &f, sum_node *n, final_sum_type *incoming_, Body *stuff_last_)
final_sum< Range, Body > final_sum_type
final_sum_type * my_left_sum
sum_node_type & my_result
void reverse_join(lambda_scan_body &a)
static internal::allocate_root_proxy allocate_root()
Returns proxy for overloaded new that allocates a root task.
sum_node< Range, Body > sum_node_type
sum_node(const Range range_, bool left_is_final_)
void poison_pointer(T *__TBB_atomic &)
task * execute() __TBB_override
Should be overridden by derived classes.
sum_node_type ** my_return_slot
task * execute() __TBB_override
Should be overridden by derived classes.
final_sum< Range, Body > final_sum_type
aligned_space< Range > my_range
static bool is_final_scan()
final_sum_type **const my_sum
finish_scan(sum_node_type *&return_slot_, final_sum_type **sum_, sum_node_type &result_)
start_scan(sum_node_type *&return_slot_, const Range &range_, final_sum_type &body_, const Partitioner &partitioner_)
Initial task to split the work.
void parallel_scan(const Range &range, Body &body)
Parallel prefix with default partitioner.
task * execute() __TBB_override
Should be overridden by derived classes.
sum_node< Range, Body > sum_node_type
static void spawn_root_and_wait(task &root)
Spawn task allocated by allocate_root, wait for it to complete, and deallocate it.
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 parent
Used to indicate that the final scan is being performed.
lambda_scan_body(const Value &identity, const Scan &scan, const ReverseJoin &rev_join)
Dummy type that distinguishes splitting constructor from copy constructor.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
sum_node_type * my_parent_sum
sum_node_type *& my_return_slot
Partitioner::partition_type my_partition
#define __TBB_DEFAULT_PARTITIONER
task * execute() __TBB_override
Should be overridden by derived classes.
final_sum_type * my_right_zombie
T * begin() const
Pointer to beginning of array.
void operator()(const Range &r, Tag tag)
final_sum< Range, Body > final_sum_type
static bool is_final_scan()
int ref_count() const
The internal reference count.
const Value & identity_element
Base class for user-defined tasks.
lambda_scan_body(lambda_scan_body &b, split)
Split work to be done in the scan.
Used to indicate that the initial scan is being performed.
Base class for types that should not be assigned.
void const char const char int ITT_FORMAT __itt_group_sync p
final_sum_type * my_incoming
Performs final scan for a leaf.
Body * my_stuff_last
Where to put result of last subrange, or NULL if not last subrange.
static void run(const Range &range_, Body &body_, const Partitioner &partitioner_)
void recycle_as_child_of(task &new_parent)
Change this to be a child of new_parent.
const ReverseJoin & my_reverse_join
void finish_construction(const Range &range_, Body *stuff_last_)