oneapi/tbb/parallel_for_each.h

0001 /*
0002     Copyright (c) 2005-2023 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_parallel_for_each_H
0018 #define __TBB_parallel_for_each_H
0019
0020 #include "detail/_config.h"
0021 #include "detail/_namespace_injection.h"
0022 #include "detail/_exception.h"
0023 #include "detail/_task.h"
0024 #include "detail/_aligned_space.h"
0025 #include "detail/_small_object_pool.h"
0026 #include "detail/_utils.h"
0027
0028 #include "parallel_for.h"
0029 #include "task_group.h" // task_group_context
0030
0031 #include <iterator>
0032 #include <type_traits>
0033
0034 namespace tbb {
0035 namespace detail {
0036 #if __TBB_CPP20_CONCEPTS_PRESENT
0037 namespace d1 {
0038 template <typename Item>
0039 class feeder;
0040
0041 } // namespace d1
0042 inline namespace d0 {
0043
0044 template <typename Body, typename ItemType, typename FeederItemType>
0045 concept parallel_for_each_body = std::invocable<const std::remove_reference_t<Body>&, ItemType&&> ||
0046                                  std::invocable<const std::remove_reference_t<Body>&, ItemType&&, tbb::detail::d1::feeder<FeederItemType>&>;
0047
0048 } // namespace d0
0049 #endif // __TBB_CPP20_CONCEPTS_PRESENT
0050 namespace d2 {
0051 template<typename Body, typename Item> class feeder_impl;
0052 } // namespace d2
0053
0054 namespace d1 {
0055 //! Class the user supplied algorithm body uses to add new tasks
0056 template<typename Item>
0057 class feeder {
0058     feeder() {}
0059     feeder(const feeder&) = delete;
0060     void operator=( const feeder&) = delete;
0061
0062     virtual ~feeder () {}
0063     virtual void internal_add_copy(const Item& item) = 0;
0064     virtual void internal_add_move(Item&& item) = 0;
0065
0066     template<typename Body_, typename Item_> friend class d2::feeder_impl;
0067 public:
0068     //! Add a work item to a running parallel_for_each.
0069     void add(const Item& item) {internal_add_copy(item);}
0070     void add(Item&& item) {internal_add_move(std::move(item));}
0071 };
0072
0073 } // namespace d1
0074
0075 namespace d2 {
0076 using namespace tbb::detail::d1;
0077 /** Selects one of the two possible forms of function call member operator.
0078     @ingroup algorithms **/
0079 template<class Body>
0080 struct parallel_for_each_operator_selector {
0081 public:
0082     template<typename ItemArg, typename FeederArg>
0083     static auto call(const Body& body, ItemArg&& item, FeederArg*)
0084     -> decltype(tbb::detail::invoke(body, std::forward<ItemArg>(item)), void()) {
0085         #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
0086         // Suppression of Microsoft non-standard extension warnings
0087         #pragma warning (push)
0088         #pragma warning (disable: 4239)
0089         #endif
0090
0091         tbb::detail::invoke(body, std::forward<ItemArg>(item));
0092
0093         #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
0094         #pragma warning (pop)
0095         #endif
0096     }
0097
0098     template<typename ItemArg, typename FeederArg>
0099     static auto call(const Body& body, ItemArg&& item, FeederArg* feeder)
0100     -> decltype(tbb::detail::invoke(body, std::forward<ItemArg>(item), *feeder), void()) {
0101         #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
0102         // Suppression of Microsoft non-standard extension warnings
0103         #pragma warning (push)
0104         #pragma warning (disable: 4239)
0105         #endif
0106         __TBB_ASSERT(feeder, "Feeder was not created but should be");
0107
0108         tbb::detail::invoke(body, std::forward<ItemArg>(item), *feeder);
0109
0110         #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
0111         #pragma warning (pop)
0112         #endif
0113     }
0114 };
0115
0116 template<typename Body, typename Item>
0117 struct feeder_item_task: public task {
0118     using feeder_type = feeder_impl<Body, Item>;
0119
0120     template <typename ItemType>
0121     feeder_item_task(ItemType&& input_item, feeder_type& feeder, small_object_allocator& alloc) :
0122         item(std::forward<ItemType>(input_item)),
0123         my_feeder(feeder),
0124         my_allocator(alloc)
0125     {}
0126
0127     void finalize(const execution_data& ed) {
0128         my_feeder.my_wait_context.release();
0129         my_allocator.delete_object(this, ed);
0130     }
0131
0132     //! Hack for resolve ambiguity between calls to the body with and without moving the stored copy
0133     //! Executing body with moving the copy should have higher priority
0134     using first_priority = int;
0135     using second_priority = double;
0136
0137     template <typename BodyType, typename ItemType, typename FeederType>
0138     static auto call(const BodyType& call_body, ItemType& call_item, FeederType& call_feeder, first_priority)
0139     -> decltype(parallel_for_each_operator_selector<Body>::call(call_body, std::move(call_item), &call_feeder), void())
0140     {
0141         parallel_for_each_operator_selector<Body>::call(call_body, std::move(call_item), &call_feeder);
0142     }
0143
0144     template <typename BodyType, typename ItemType, typename FeederType>
0145     static void call(const BodyType& call_body, ItemType& call_item, FeederType& call_feeder, second_priority) {
0146         parallel_for_each_operator_selector<Body>::call(call_body, call_item, &call_feeder);
0147     }
0148
0149     task* execute(execution_data& ed) override {
0150         call(my_feeder.my_body, item, my_feeder, first_priority{});
0151         finalize(ed);
0152         return nullptr;
0153     }
0154
0155     task* cancel(execution_data& ed) override {
0156         finalize(ed);
0157         return nullptr;
0158     }
0159
0160     Item item;
0161     feeder_type& my_feeder;
0162     small_object_allocator my_allocator;
0163 }; // class feeder_item_task
0164
0165 /** Implements new task adding procedure.
0166     @ingroup algorithms **/
0167 template<typename Body, typename Item>
0168 class feeder_impl : public feeder<Item> {
0169     // Avoiding use of copy constructor in a virtual method if the type does not support it
0170     void internal_add_copy_impl(std::true_type, const Item& item) {
0171         using feeder_task = feeder_item_task<Body, Item>;
0172         small_object_allocator alloc;
0173         auto task = alloc.new_object<feeder_task>(item, *this, alloc);
0174
0175         my_wait_context.reserve();
0176         spawn(*task, my_execution_context);
0177     }
0178
0179     void internal_add_copy_impl(std::false_type, const Item&) {
0180         __TBB_ASSERT(false, "Overloading for r-value reference doesn't work or it's not movable and not copyable object");
0181     }
0182
0183     void internal_add_copy(const Item& item) override {
0184         internal_add_copy_impl(typename std::is_copy_constructible<Item>::type(), item);
0185     }
0186
0187     void internal_add_move(Item&& item) override {
0188         using feeder_task = feeder_item_task<Body, Item>;
0189         small_object_allocator alloc{};
0190         auto task = alloc.new_object<feeder_task>(std::move(item), *this, alloc);
0191
0192         my_wait_context.reserve();
0193         spawn(*task, my_execution_context);
0194     }
0195 public:
0196     feeder_impl(const Body& body, wait_context& w_context, task_group_context &context)
0197       : my_body(body),
0198         my_wait_context(w_context)
0199       , my_execution_context(context)
0200     {}
0201
0202     const Body& my_body;
0203     wait_context& my_wait_context;
0204     task_group_context& my_execution_context;
0205 }; // class feeder_impl
0206
0207 /** Execute computation under one element of the range
0208     @ingroup algorithms **/
0209 template<typename Iterator, typename Body, typename Item>
0210 struct for_each_iteration_task: public task {
0211     using feeder_type = feeder_impl<Body, Item>;
0212
0213     for_each_iteration_task(Iterator input_item_ptr, const Body& body, feeder_impl<Body, Item>* feeder_ptr, wait_context& wait_context) :
0214         item_ptr(input_item_ptr), my_body(body), my_feeder_ptr(feeder_ptr), parent_wait_context(wait_context)
0215     {}
0216
0217     void finalize() {
0218         parent_wait_context.release();
0219     }
0220
0221     task* execute(execution_data&) override {
0222         parallel_for_each_operator_selector<Body>::call(my_body, *item_ptr, my_feeder_ptr);
0223         finalize();
0224         return nullptr;
0225     }
0226
0227     task* cancel(execution_data&) override {
0228         finalize();
0229         return nullptr;
0230     }
0231
0232     Iterator item_ptr;
0233     const Body& my_body;
0234     feeder_impl<Body, Item>* my_feeder_ptr;
0235     wait_context& parent_wait_context;
0236 }; // class for_each_iteration_task
0237
0238 // Helper to get the type of the iterator to the internal sequence of copies
0239 // If the element can be passed to the body as an rvalue - this iterator should be move_iterator
0240 template <typename Body, typename Item, typename = void>
0241 struct input_iteration_task_iterator_helper {
0242     // For input iterators we pass const lvalue reference to the body
0243     // It is prohibited to take non-constant lvalue references for input iterators
0244     using type = const Item*;
0245 };
0246
0247 template <typename Body, typename Item>
0248 struct input_iteration_task_iterator_helper<Body, Item,
0249     tbb::detail::void_t<decltype(parallel_for_each_operator_selector<Body>::call(std::declval<const Body&>(),
0250                                                                                  std::declval<Item&&>(),
0251                                                                                  std::declval<feeder_impl<Body, Item>*>()))>>
0252 {
0253     using type = std::move_iterator<Item*>;
0254 };
0255
0256 /** Split one block task to several(max_block_size) iteration tasks for input iterators
0257     @ingroup algorithms **/
0258 template <typename Body, typename Item>
0259 struct input_block_handling_task : public task {
0260     static constexpr size_t max_block_size = 4;
0261
0262     using feeder_type = feeder_impl<Body, Item>;
0263     using iteration_task_iterator_type = typename input_iteration_task_iterator_helper<Body, Item>::type;
0264     using iteration_task = for_each_iteration_task<iteration_task_iterator_type, Body, Item>;
0265
0266     input_block_handling_task(wait_context& root_wait_context, task_group_context& e_context,
0267                               const Body& body, feeder_impl<Body, Item>* feeder_ptr, small_object_allocator& alloc)
0268         :my_size(0), my_wait_context(0), my_root_wait_context(root_wait_context),
0269          my_execution_context(e_context), my_allocator(alloc)
0270     {
0271         auto item_it = block_iteration_space.begin();
0272         for (auto* it = task_pool.begin(); it != task_pool.end(); ++it) {
0273             new (it) iteration_task(iteration_task_iterator_type(item_it++), body, feeder_ptr, my_wait_context);
0274         }
0275     }
0276
0277     void finalize(const execution_data& ed) {
0278         my_root_wait_context.release();
0279         my_allocator.delete_object(this, ed);
0280     }
0281
0282     task* execute(execution_data& ed) override {
0283         __TBB_ASSERT( my_size > 0, "Negative size was passed to task");
0284         for (std::size_t counter = 1; counter < my_size; ++counter) {
0285             my_wait_context.reserve();
0286             spawn(*(task_pool.begin() + counter), my_execution_context);
0287         }
0288         my_wait_context.reserve();
0289         execute_and_wait(*task_pool.begin(), my_execution_context,
0290                          my_wait_context,    my_execution_context);
0291
0292         // deallocate current task after children execution
0293         finalize(ed);
0294         return nullptr;
0295     }
0296
0297     task* cancel(execution_data& ed) override {
0298         finalize(ed);
0299         return nullptr;
0300     }
0301
0302     ~input_block_handling_task() {
0303         for(std::size_t counter = 0; counter < max_block_size; ++counter) {
0304             (task_pool.begin() + counter)->~iteration_task();
0305             if (counter < my_size) {
0306                 (block_iteration_space.begin() + counter)->~Item();
0307             }
0308         }
0309     }
0310
0311     aligned_space<Item, max_block_size> block_iteration_space;
0312     aligned_space<iteration_task, max_block_size> task_pool;
0313     std::size_t my_size;
0314     wait_context my_wait_context;
0315     wait_context& my_root_wait_context;
0316     task_group_context& my_execution_context;
0317     small_object_allocator my_allocator;
0318 }; // class input_block_handling_task
0319
0320 /** Split one block task to several(max_block_size) iteration tasks for forward iterators
0321     @ingroup algorithms **/
0322 template <typename Iterator, typename Body, typename Item>
0323 struct forward_block_handling_task : public task {
0324     static constexpr size_t max_block_size = 4;
0325
0326     using iteration_task = for_each_iteration_task<Iterator, Body, Item>;
0327
0328     forward_block_handling_task(Iterator first, std::size_t size,
0329                                 wait_context& w_context, task_group_context& e_context,
0330                                 const Body& body, feeder_impl<Body, Item>* feeder_ptr,
0331                                 small_object_allocator& alloc)
0332         : my_size(size), my_wait_context(0), my_root_wait_context(w_context),
0333           my_execution_context(e_context), my_allocator(alloc)
0334     {
0335         auto* task_it = task_pool.begin();
0336         for (std::size_t i = 0; i < size; i++) {
0337             new (task_it++) iteration_task(first, body, feeder_ptr, my_wait_context);
0338             ++first;
0339         }
0340     }
0341
0342     void finalize(const execution_data& ed) {
0343         my_root_wait_context.release();
0344         my_allocator.delete_object(this, ed);
0345     }
0346
0347     task* execute(execution_data& ed) override {
0348         __TBB_ASSERT( my_size > 0, "Negative size was passed to task");
0349         for(std::size_t counter = 1; counter < my_size; ++counter) {
0350             my_wait_context.reserve();
0351             spawn(*(task_pool.begin() + counter), my_execution_context);
0352         }
0353         my_wait_context.reserve();
0354         execute_and_wait(*task_pool.begin(), my_execution_context,
0355                          my_wait_context,    my_execution_context);
0356
0357         // deallocate current task after children execution
0358         finalize(ed);
0359         return nullptr;
0360     }
0361
0362     task* cancel(execution_data& ed) override {
0363         finalize(ed);
0364         return nullptr;
0365     }
0366
0367     ~forward_block_handling_task() {
0368         for(std::size_t counter = 0; counter < my_size; ++counter) {
0369             (task_pool.begin() + counter)->~iteration_task();
0370         }
0371     }
0372
0373     aligned_space<iteration_task, max_block_size> task_pool;
0374     std::size_t my_size;
0375     wait_context my_wait_context;
0376     wait_context& my_root_wait_context;
0377     task_group_context& my_execution_context;
0378     small_object_allocator my_allocator;
0379 }; // class forward_block_handling_task
0380
0381 /** Body for parallel_for algorithm.
0382   * Allows to redirect operations under random access iterators range to the parallel_for algorithm.
0383     @ingroup algorithms **/
0384 template <typename Iterator, typename Body, typename Item>
0385 class parallel_for_body_wrapper {
0386     Iterator my_first;
0387     const Body& my_body;
0388     feeder_impl<Body, Item>* my_feeder_ptr;
0389 public:
0390     parallel_for_body_wrapper(Iterator first, const Body& body, feeder_impl<Body, Item>* feeder_ptr)
0391         : my_first(first), my_body(body), my_feeder_ptr(feeder_ptr) {}
0392
0393     void operator()(tbb::blocked_range<std::size_t> range) const {
0394 #if __INTEL_COMPILER
0395 #pragma ivdep
0396 #endif
0397         for (std::size_t count = range.begin(); count != range.end(); count++) {
0398             parallel_for_each_operator_selector<Body>::call(my_body, *(my_first + count),
0399                                                             my_feeder_ptr);
0400         }
0401     }
0402 }; // class parallel_for_body_wrapper
0403
0404
0405 /** Helper for getting iterators tag including inherited custom tags
0406     @ingroup algorithms */
0407 template<typename It>
0408 using tag = typename std::iterator_traits<It>::iterator_category;
0409
0410 #if __TBB_CPP20_PRESENT
0411 template <typename It>
0412 struct move_iterator_dispatch_helper {
0413     using type = It;
0414 };
0415
0416 // Until C++23, std::move_iterator::iterator_concept always defines
0417 // to std::input_iterator_tag and hence std::forward_iterator concept
0418 // always evaluates to false, so std::move_iterator dispatch should be
0419 // made according to the base iterator type.
0420 template <typename It>
0421 struct move_iterator_dispatch_helper<std::move_iterator<It>> {
0422     using type = It;
0423 };
0424
0425 template <typename It>
0426 using iterator_tag_dispatch_impl =
0427     std::conditional_t<std::random_access_iterator<It>,
0428                        std::random_access_iterator_tag,
0429                        std::conditional_t<std::forward_iterator<It>,
0430                                           std::forward_iterator_tag,
0431                                           std::input_iterator_tag>>;
0432
0433 template <typename It>
0434 using iterator_tag_dispatch =
0435     iterator_tag_dispatch_impl<typename move_iterator_dispatch_helper<It>::type>;
0436
0437 #else
0438 template<typename It>
0439 using iterator_tag_dispatch = typename
0440     std::conditional<
0441         std::is_base_of<std::random_access_iterator_tag, tag<It>>::value,
0442         std::random_access_iterator_tag,
0443         typename std::conditional<
0444             std::is_base_of<std::forward_iterator_tag, tag<It>>::value,
0445             std::forward_iterator_tag,
0446             std::input_iterator_tag
0447         >::type
0448     >::type;
0449 #endif // __TBB_CPP20_PRESENT
0450
0451 template <typename Body, typename Iterator, typename Item>
0452 using feeder_is_required = tbb::detail::void_t<decltype(tbb::detail::invoke(std::declval<const Body>(),
0453                                                                             std::declval<typename std::iterator_traits<Iterator>::reference>(),
0454                                                                             std::declval<feeder<Item>&>()))>;
0455
0456 // Creates feeder object only if the body can accept it
0457 template <typename Iterator, typename Body, typename Item, typename = void>
0458 struct feeder_holder {
0459     feeder_holder( wait_context&, task_group_context&, const Body& ) {}
0460
0461     feeder_impl<Body, Item>* feeder_ptr() { return nullptr; }
0462 }; // class feeder_holder
0463
0464 template <typename Iterator, typename Body, typename Item>
0465 class feeder_holder<Iterator, Body, Item, feeder_is_required<Body, Iterator, Item>> {
0466 public:
0467     feeder_holder( wait_context& w_context, task_group_context& context, const Body& body )
0468         : my_feeder(body, w_context, context) {}
0469
0470     feeder_impl<Body, Item>* feeder_ptr() { return &my_feeder; }
0471 private:
0472     feeder_impl<Body, Item> my_feeder;
0473 }; // class feeder_holder
0474
0475 template <typename Iterator, typename Body, typename Item>
0476 class for_each_root_task_base : public task {
0477 public:
0478     for_each_root_task_base(Iterator first, Iterator last, const Body& body, wait_context& w_context, task_group_context& e_context)
0479         : my_first(first), my_last(last), my_wait_context(w_context), my_execution_context(e_context),
0480           my_body(body), my_feeder_holder(my_wait_context, my_execution_context, my_body)
0481     {
0482         my_wait_context.reserve();
0483     }
0484 private:
0485     task* cancel(execution_data&) override {
0486         this->my_wait_context.release();
0487         return nullptr;
0488     }
0489 protected:
0490     Iterator my_first;
0491     Iterator my_last;
0492     wait_context& my_wait_context;
0493     task_group_context& my_execution_context;
0494     const Body& my_body;
0495     feeder_holder<Iterator, Body, Item> my_feeder_holder;
0496 }; // class for_each_root_task_base
0497
0498 /** parallel_for_each algorithm root task - most generic version
0499   * Splits input range to blocks
0500     @ingroup algorithms **/
0501 template <typename Iterator, typename Body, typename Item, typename IteratorTag = iterator_tag_dispatch<Iterator>>
0502 class for_each_root_task : public for_each_root_task_base<Iterator, Body, Item>
0503 {
0504     using base_type = for_each_root_task_base<Iterator, Body, Item>;
0505 public:
0506     using base_type::base_type;
0507 private:
0508     task* execute(execution_data& ed) override {
0509         using block_handling_type = input_block_handling_task<Body, Item>;
0510
0511         if (this->my_first == this->my_last) {
0512             this->my_wait_context.release();
0513             return nullptr;
0514         }
0515
0516         this->my_wait_context.reserve();
0517         small_object_allocator alloc{};
0518         auto block_handling_task = alloc.new_object<block_handling_type>(ed, this->my_wait_context, this->my_execution_context,
0519                                                                          this->my_body, this->my_feeder_holder.feeder_ptr(),
0520                                                                          alloc);
0521
0522         auto* block_iterator = block_handling_task->block_iteration_space.begin();
0523         for (; !(this->my_first == this->my_last) && block_handling_task->my_size < block_handling_type::max_block_size; ++this->my_first) {
0524             // Move semantics are automatically used when supported by the iterator
0525             new (block_iterator++) Item(*this->my_first);
0526             ++block_handling_task->my_size;
0527         }
0528
0529         // Do not access this after spawn to avoid races
0530         spawn(*this, this->my_execution_context);
0531         return block_handling_task;
0532     }
0533 }; // class for_each_root_task - most generic implementation
0534
0535 /** parallel_for_each algorithm root task - forward iterator based specialization
0536   * Splits input range to blocks
0537     @ingroup algorithms **/
0538 template <typename Iterator, typename Body, typename Item>
0539 class for_each_root_task<Iterator, Body, Item, std::forward_iterator_tag>
0540     : public for_each_root_task_base<Iterator, Body, Item>
0541 {
0542     using base_type = for_each_root_task_base<Iterator, Body, Item>;
0543 public:
0544     using base_type::base_type;
0545 private:
0546     task* execute(execution_data& ed) override {
0547         using block_handling_type = forward_block_handling_task<Iterator, Body, Item>;
0548         if (this->my_first == this->my_last) {
0549             this->my_wait_context.release();
0550             return nullptr;
0551         }
0552
0553         std::size_t block_size{0};
0554         Iterator first_block_element = this->my_first;
0555         for (; !(this->my_first == this->my_last) && block_size < block_handling_type::max_block_size; ++this->my_first) {
0556             ++block_size;
0557         }
0558
0559         this->my_wait_context.reserve();
0560         small_object_allocator alloc{};
0561         auto block_handling_task = alloc.new_object<block_handling_type>(ed, first_block_element, block_size,
0562                                                                          this->my_wait_context, this->my_execution_context,
0563                                                                          this->my_body, this->my_feeder_holder.feeder_ptr(), alloc);
0564
0565         // Do not access this after spawn to avoid races
0566         spawn(*this, this->my_execution_context);
0567         return block_handling_task;
0568     }
0569 }; // class for_each_root_task - forward iterator based specialization
0570
0571 /** parallel_for_each algorithm root task - random access iterator based specialization
0572   * Splits input range to blocks
0573     @ingroup algorithms **/
0574 template <typename Iterator, typename Body, typename Item>
0575 class for_each_root_task<Iterator, Body, Item, std::random_access_iterator_tag>
0576     : public for_each_root_task_base<Iterator, Body, Item>
0577 {
0578     using base_type = for_each_root_task_base<Iterator, Body, Item>;
0579 public:
0580     using base_type::base_type;
0581 private:
0582     task* execute(execution_data&) override {
0583         tbb::parallel_for(
0584             tbb::blocked_range<std::size_t>(0, std::distance(this->my_first, this->my_last)),
0585             parallel_for_body_wrapper<Iterator, Body, Item>(this->my_first, this->my_body, this->my_feeder_holder.feeder_ptr())
0586             , this->my_execution_context
0587         );
0588
0589         this->my_wait_context.release();
0590         return nullptr;
0591     }
0592 }; // class for_each_root_task - random access iterator based specialization
0593
0594 /** Helper for getting item type. If item type can be deduced from feeder - got it from feeder,
0595     if feeder is generic - got item type from range.
0596     @ingroup algorithms */
0597 template<typename Body, typename Item, typename FeederArg>
0598 auto feeder_argument_parser(void (Body::*)(Item, feeder<FeederArg>&) const) -> FeederArg;
0599
0600 template<typename Body, typename>
0601 decltype(feeder_argument_parser<Body>(&Body::operator())) get_item_type_impl(int); // for (T, feeder<T>)
0602 template<typename Body, typename Item> Item get_item_type_impl(...); // stub
0603
0604 template <typename Body, typename Item>
0605 using get_item_type = decltype(get_item_type_impl<Body, Item>(0));
0606
0607 #if __TBB_CPP20_CONCEPTS_PRESENT
0608 template <typename Body, typename ItemType>
0609 using feeder_item_type = std::remove_cvref_t<get_item_type<Body, ItemType>>;
0610
0611 template <typename Body, typename Iterator>
0612 concept parallel_for_each_iterator_body =
0613     parallel_for_each_body<Body, iterator_reference_type<Iterator>, feeder_item_type<Body, iterator_reference_type<Iterator>>>;
0614
0615 template <typename Body, typename Range>
0616 concept parallel_for_each_range_body =
0617     parallel_for_each_body<Body, range_reference_type<Range>, feeder_item_type<Body, range_reference_type<Range>>>;
0618 #endif
0619
0620 /** Implements parallel iteration over a range.
0621     @ingroup algorithms */
0622 template<typename Iterator, typename Body>
0623 void run_parallel_for_each( Iterator first, Iterator last, const Body& body, task_group_context& context)
0624 {
0625     if (!(first == last)) {
0626         using ItemType = get_item_type<Body, typename std::iterator_traits<Iterator>::value_type>;
0627         wait_context w_context(0);
0628
0629         for_each_root_task<Iterator, Body, ItemType> root_task(first, last, body, w_context, context);
0630
0631         execute_and_wait(root_task, context, w_context, context);
0632     }
0633 }
0634
0635 /** \page parallel_for_each_body_req Requirements on parallel_for_each body
0636     Class \c Body implementing the concept of parallel_for_each body must define:
0637     - \code
0638         B::operator()(
0639                 cv_item_type item,
0640                 feeder<item_type>& feeder
0641         ) const
0642
0643         OR
0644
0645         B::operator()( cv_item_type& item ) const
0646       \endcode                                               Process item.
0647                                                              May be invoked concurrently  for the same \c this but different \c item.
0648
0649     - \code item_type( const item_type& ) \endcode
0650                                                              Copy a work item.
0651     - \code ~item_type() \endcode                            Destroy a work item
0652 **/
0653
0654 /** \name parallel_for_each
0655     See also requirements on \ref parallel_for_each_body_req "parallel_for_each Body". **/
0656 //@{
0657 //! Parallel iteration over a range, with optional addition of more work.
0658 /** @ingroup algorithms */
0659 template<typename Iterator, typename Body>
0660     __TBB_requires(std::input_iterator<Iterator> && parallel_for_each_iterator_body<Body, Iterator>)
0661 void parallel_for_each(Iterator first, Iterator last, const Body& body) {
0662     task_group_context context(PARALLEL_FOR_EACH);
0663     run_parallel_for_each<Iterator, Body>(first, last, body, context);
0664 }
0665
0666 template<typename Range, typename Body>
0667     __TBB_requires(container_based_sequence<Range, std::input_iterator_tag> && parallel_for_each_range_body<Body, Range>)
0668 void parallel_for_each(Range& rng, const Body& body) {
0669     parallel_for_each(std::begin(rng), std::end(rng), body);
0670 }
0671
0672 template<typename Range, typename Body>
0673     __TBB_requires(container_based_sequence<Range, std::input_iterator_tag> && parallel_for_each_range_body<Body, Range>)
0674 void parallel_for_each(const Range& rng, const Body& body) {
0675     parallel_for_each(std::begin(rng), std::end(rng), body);
0676 }
0677
0678 //! Parallel iteration over a range, with optional addition of more work and user-supplied context
0679 /** @ingroup algorithms */
0680 template<typename Iterator, typename Body>
0681     __TBB_requires(std::input_iterator<Iterator> && parallel_for_each_iterator_body<Body, Iterator>)
0682 void parallel_for_each(Iterator first, Iterator last, const Body& body, task_group_context& context) {
0683     run_parallel_for_each<Iterator, Body>(first, last, body, context);
0684 }
0685
0686 template<typename Range, typename Body>
0687     __TBB_requires(container_based_sequence<Range, std::input_iterator_tag> && parallel_for_each_range_body<Body, Range>)
0688 void parallel_for_each(Range& rng, const Body& body, task_group_context& context) {
0689     parallel_for_each(std::begin(rng), std::end(rng), body, context);
0690 }
0691
0692 template<typename Range, typename Body>
0693     __TBB_requires(container_based_sequence<Range, std::input_iterator_tag> && parallel_for_each_range_body<Body, Range>)
0694 void parallel_for_each(const Range& rng, const Body& body, task_group_context& context) {
0695     parallel_for_each(std::begin(rng), std::end(rng), body, context);
0696 }
0697
0698 } // namespace d2
0699 } // namespace detail
0700 //! @endcond
0701 //@}
0702
0703 inline namespace v1 {
0704 using detail::d2::parallel_for_each;
0705 using detail::d1::feeder;
0706 } // namespace v1
0707
0708 } // namespace tbb
0709
0710 #endif /* __TBB_parallel_for_each_H */