/* Copyright (c) 2005-2025 Intel Corporation Copyright (c) 2025 UXL Foundation Contributors Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. */ #ifndef __TBB__flow_graph_join_impl_H #define __TBB__flow_graph_join_impl_H #ifndef __TBB_flow_graph_H #error Do not #include this internal file directly; use public TBB headers instead. #endif // included into namespace tbb::detail::d2 struct forwarding_base : no_assign { forwarding_base(graph &g) : graph_ref(g) {} virtual ~forwarding_base() {} graph& graph_ref; }; struct queueing_forwarding_base : forwarding_base { using forwarding_base::forwarding_base; // decrement_port_count may create a forwarding task. If we cannot handle the task // ourselves, ask decrement_port_count to deal with it. virtual graph_task* decrement_port_count(bool handle_task) = 0; }; struct reserving_forwarding_base : forwarding_base { using forwarding_base::forwarding_base; // decrement_port_count may create a forwarding task. If we cannot handle the task // ourselves, ask decrement_port_count to deal with it. virtual graph_task* decrement_port_count() = 0; virtual void increment_port_count() = 0; }; // specialization that lets us keep a copy of the current_key for building results. // KeyType can be a reference type. template struct matching_forwarding_base : public forwarding_base { typedef typename std::decay::type current_key_type; matching_forwarding_base(graph &g) : forwarding_base(g) { } virtual graph_task* increment_key_count(current_key_type const & /*t*/) = 0; current_key_type current_key; // so ports can refer to FE's desired items }; template< int N > struct join_helper { template< typename TupleType, typename PortType > static inline void set_join_node_pointer(TupleType &my_input, PortType *port) { std::get( my_input ).set_join_node_pointer(port); join_helper::set_join_node_pointer( my_input, port ); } template< typename TupleType > static inline void consume_reservations( TupleType &my_input ) { std::get( my_input ).consume(); join_helper::consume_reservations( my_input ); } template< typename TupleType > static inline void release_my_reservation( TupleType &my_input ) { std::get( my_input ).release(); } template static inline void release_reservations( TupleType &my_input) { join_helper::release_reservations(my_input); release_my_reservation(my_input); } template< typename InputTuple, typename OutputTuple > static inline bool reserve( InputTuple &my_input, OutputTuple &out) { if ( !std::get( my_input ).reserve( std::get( out ) ) ) return false; if ( !join_helper::reserve( my_input, out ) ) { release_my_reservation( my_input ); return false; } return true; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool reserve(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { message_metainfo element_metainfo; if (!std::get(my_input).reserve(std::get(out), element_metainfo)) return false; if (!join_helper::reserve(my_input, out, metainfo)) { release_my_reservation(my_input); return false; } metainfo.merge(element_metainfo); return true; } #endif template static inline bool get_my_item( InputTuple &my_input, OutputTuple &out) { bool res = std::get(my_input).get_item(std::get(out) ); // may fail return join_helper::get_my_item(my_input, out) && res; // do get on other inputs before returning } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool get_my_item(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { message_metainfo element_metainfo; bool res = std::get(my_input).get_item(std::get(out), element_metainfo); metainfo.merge(element_metainfo); return join_helper::get_my_item(my_input, out, metainfo) && res; } #endif template static inline bool get_items(InputTuple &my_input, OutputTuple &out) { return get_my_item(my_input, out); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool get_items(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { return get_my_item(my_input, out, metainfo); } #endif template static inline void reset_my_port(InputTuple &my_input) { join_helper::reset_my_port(my_input); std::get(my_input).reset_port(); } template static inline void reset_ports(InputTuple& my_input) { reset_my_port(my_input); } template static inline void set_key_functors(InputTuple &my_input, KeyFuncTuple &my_key_funcs) { std::get(my_input).set_my_key_func(std::get(my_key_funcs)); std::get(my_key_funcs) = nullptr; join_helper::set_key_functors(my_input, my_key_funcs); } template< typename KeyFuncTuple> static inline void copy_key_functors(KeyFuncTuple &my_inputs, KeyFuncTuple &other_inputs) { __TBB_ASSERT( std::get(other_inputs).get_my_key_func(), "key matching join node should not be instantiated without functors." ); std::get(my_inputs).set_my_key_func(std::get(other_inputs).get_my_key_func()->clone()); join_helper::copy_key_functors(my_inputs, other_inputs); } template static inline void reset_inputs(InputTuple &my_input, reset_flags f) { join_helper::reset_inputs(my_input, f); std::get(my_input).reset_receiver(f); } }; // join_helper template< > struct join_helper<1> { template< typename TupleType, typename PortType > static inline void set_join_node_pointer(TupleType &my_input, PortType *port) { std::get<0>( my_input ).set_join_node_pointer(port); } template< typename TupleType > static inline void consume_reservations( TupleType &my_input ) { std::get<0>( my_input ).consume(); } template< typename TupleType > static inline void release_my_reservation( TupleType &my_input ) { std::get<0>( my_input ).release(); } template static inline void release_reservations( TupleType &my_input) { release_my_reservation(my_input); } template< typename InputTuple, typename OutputTuple > static inline bool reserve( InputTuple &my_input, OutputTuple &out) { return std::get<0>( my_input ).reserve( std::get<0>( out ) ); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool reserve(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { message_metainfo element_metainfo; bool result = std::get<0>(my_input).reserve(std::get<0>(out), element_metainfo); metainfo.merge(element_metainfo); return result; } #endif template static inline bool get_my_item( InputTuple &my_input, OutputTuple &out) { return std::get<0>(my_input).get_item(std::get<0>(out)); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool get_my_item(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { message_metainfo element_metainfo; bool res = std::get<0>(my_input).get_item(std::get<0>(out), element_metainfo); metainfo.merge(element_metainfo); return res; } #endif template static inline bool get_items(InputTuple &my_input, OutputTuple &out) { return get_my_item(my_input, out); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT template static inline bool get_items(InputTuple& my_input, OutputTuple& out, message_metainfo& metainfo) { return get_my_item(my_input, out, metainfo); } #endif template static inline void reset_my_port(InputTuple &my_input) { std::get<0>(my_input).reset_port(); } template static inline void reset_ports(InputTuple& my_input) { reset_my_port(my_input); } template static inline void set_key_functors(InputTuple &my_input, KeyFuncTuple &my_key_funcs) { std::get<0>(my_input).set_my_key_func(std::get<0>(my_key_funcs)); std::get<0>(my_key_funcs) = nullptr; } template< typename KeyFuncTuple> static inline void copy_key_functors(KeyFuncTuple &my_inputs, KeyFuncTuple &other_inputs) { __TBB_ASSERT( std::get<0>(other_inputs).get_my_key_func(), "key matching join node should not be instantiated without functors." ); std::get<0>(my_inputs).set_my_key_func(std::get<0>(other_inputs).get_my_key_func()->clone()); } template static inline void reset_inputs(InputTuple &my_input, reset_flags f) { std::get<0>(my_input).reset_receiver(f); } }; // join_helper<1> //! The two-phase join port template< typename T > class reserving_port : public receiver { public: typedef T input_type; typedef typename receiver::predecessor_type predecessor_type; private: // ----------- Aggregator ------------ enum op_type { reg_pred, rem_pred, res_item, rel_res, con_res }; typedef reserving_port class_type; class reserving_port_operation : public d1::aggregated_operation { public: char type; union { T *my_arg; predecessor_type *my_pred; }; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo* metainfo; #endif reserving_port_operation(const T& e, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo& info)) : type(char(t)), my_arg(const_cast(&e)) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(&info)) {} #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT reserving_port_operation(const T& e, op_type t) : type(char(t)), my_arg(const_cast(&e)), metainfo(nullptr) {} #endif reserving_port_operation(const predecessor_type &s, op_type t) : type(char(t)), my_pred(const_cast(&s)) {} reserving_port_operation(op_type t) : type(char(t)) {} }; typedef d1::aggregating_functor handler_type; friend class d1::aggregating_functor; d1::aggregator my_aggregator; void handle_operations(reserving_port_operation* op_list) { reserving_port_operation *current; bool was_missing_predecessors = false; while(op_list) { current = op_list; op_list = op_list->next; switch(current->type) { case reg_pred: was_missing_predecessors = my_predecessors.empty(); my_predecessors.add(*(current->my_pred)); if ( was_missing_predecessors ) { (void) my_join->decrement_port_count(); // may try to forward } current->status.store( SUCCEEDED, std::memory_order_release); break; case rem_pred: if ( !my_predecessors.empty() ) { my_predecessors.remove(*(current->my_pred)); if ( my_predecessors.empty() ) // was the last predecessor my_join->increment_port_count(); } // TODO: consider returning failure if there were no predecessors to remove current->status.store( SUCCEEDED, std::memory_order_release ); break; case res_item: if ( reserved ) { current->status.store( FAILED, std::memory_order_release); } else { bool reserve_result = false; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT if (current->metainfo) { reserve_result = my_predecessors.try_reserve(*(current->my_arg), *(current->metainfo)); } else #endif { reserve_result = my_predecessors.try_reserve(*(current->my_arg)); } if (reserve_result) { reserved = true; current->status.store( SUCCEEDED, std::memory_order_release); } else { if ( my_predecessors.empty() ) { my_join->increment_port_count(); } current->status.store( FAILED, std::memory_order_release); } } break; case rel_res: reserved = false; my_predecessors.try_release( ); current->status.store( SUCCEEDED, std::memory_order_release); break; case con_res: reserved = false; my_predecessors.try_consume( ); current->status.store( SUCCEEDED, std::memory_order_release); break; } } } protected: template< typename R, typename B > friend class run_and_put_task; template friend class broadcast_cache; template friend class round_robin_cache; graph_task* try_put_task( const T & ) override { return nullptr; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT graph_task* try_put_task(const T&, const message_metainfo&) override { return nullptr; } #endif graph& graph_reference() const override { return my_join->graph_ref; } public: //! Constructor reserving_port() : my_join(nullptr), my_predecessors(this), reserved(false) { my_aggregator.initialize_handler(handler_type(this)); } // copy constructor reserving_port(const reserving_port& /* other */) = delete; void set_join_node_pointer(reserving_forwarding_base *join) { my_join = join; } //! Add a predecessor bool register_predecessor( predecessor_type &src ) override { reserving_port_operation op_data(src, reg_pred); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } //! Remove a predecessor bool remove_predecessor( predecessor_type &src ) override { reserving_port_operation op_data(src, rem_pred); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } //! Reserve an item from the port bool reserve( T &v ) { reserving_port_operation op_data(v, res_item); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool reserve( T& v, message_metainfo& metainfo ) { reserving_port_operation op_data(v, res_item, metainfo); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #endif //! Release the port void release( ) { reserving_port_operation op_data(rel_res); my_aggregator.execute(&op_data); } //! Complete use of the port void consume( ) { reserving_port_operation op_data(con_res); my_aggregator.execute(&op_data); } void reset_receiver( reset_flags f) { if(f & rf_clear_edges) my_predecessors.clear(); else my_predecessors.reset(); reserved = false; __TBB_ASSERT(!(f&rf_clear_edges) || my_predecessors.empty(), "port edges not removed"); } private: #if __TBB_PREVIEW_FLOW_GRAPH_NODE_SET friend class get_graph_helper; #endif reserving_forwarding_base *my_join; reservable_predecessor_cache< T, null_mutex > my_predecessors; bool reserved; }; // reserving_port //! queueing join_port template class queueing_port : public receiver, public item_buffer { public: typedef T input_type; typedef typename receiver::predecessor_type predecessor_type; typedef queueing_port class_type; // ----------- Aggregator ------------ private: enum op_type { get__item, res_port, try__put_task }; class queueing_port_operation : public d1::aggregated_operation { public: char type; T my_val; T* my_arg; graph_task* bypass_t; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo* metainfo; #endif // constructor for value parameter queueing_port_operation(const T& e, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(const message_metainfo& info)) : type(char(t)), my_val(e), my_arg(nullptr) , bypass_t(nullptr) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(const_cast(&info))) {} // constructor for pointer parameter queueing_port_operation(const T* p, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo& info)) : type(char(t)), my_arg(const_cast(p)) , bypass_t(nullptr) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(&info)) {} #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT queueing_port_operation(const T* p, op_type t) : type(char(t)), my_arg(const_cast(p)), bypass_t(nullptr), metainfo(nullptr) {} #endif // constructor with no parameter queueing_port_operation(op_type t) : type(char(t)), my_arg(nullptr) , bypass_t(nullptr) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(nullptr)) {} }; typedef d1::aggregating_functor handler_type; friend class d1::aggregating_functor; d1::aggregator my_aggregator; void handle_operations(queueing_port_operation* op_list) { queueing_port_operation *current; bool was_empty; while(op_list) { current = op_list; op_list = op_list->next; switch(current->type) { case try__put_task: { graph_task* rtask = nullptr; was_empty = this->buffer_empty(); #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT __TBB_ASSERT(current->metainfo, nullptr); this->push_back(current->my_val, *(current->metainfo)); #else this->push_back(current->my_val); #endif if (was_empty) rtask = my_join->decrement_port_count(false); else rtask = SUCCESSFULLY_ENQUEUED; current->bypass_t = rtask; current->status.store( SUCCEEDED, std::memory_order_release); } break; case get__item: if(!this->buffer_empty()) { __TBB_ASSERT(current->my_arg, nullptr); *(current->my_arg) = this->front(); #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT if (current->metainfo) { *(current->metainfo) = this->front_metainfo(); } #endif current->status.store( SUCCEEDED, std::memory_order_release); } else { current->status.store( FAILED, std::memory_order_release); } break; case res_port: __TBB_ASSERT(this->my_item_valid(this->my_head), "No item to reset"); this->destroy_front(); if(this->my_item_valid(this->my_head)) { (void)my_join->decrement_port_count(true); } current->status.store( SUCCEEDED, std::memory_order_release); break; } } } // ------------ End Aggregator --------------- protected: template< typename R, typename B > friend class run_and_put_task; template friend class broadcast_cache; template friend class round_robin_cache; private: graph_task* try_put_task_impl(const T& v __TBB_FLOW_GRAPH_METAINFO_ARG(const message_metainfo& metainfo)) { queueing_port_operation op_data(v, try__put_task __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo)); my_aggregator.execute(&op_data); __TBB_ASSERT(op_data.status == SUCCEEDED || !op_data.bypass_t, "inconsistent return from aggregator"); if(!op_data.bypass_t) return SUCCESSFULLY_ENQUEUED; return op_data.bypass_t; } protected: graph_task* try_put_task(const T &v) override { return try_put_task_impl(v __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo{})); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT graph_task* try_put_task(const T& v, const message_metainfo& metainfo) override { return try_put_task_impl(v, metainfo); } #endif graph& graph_reference() const override { return my_join->graph_ref; } public: //! Constructor queueing_port() : item_buffer() { my_join = nullptr; my_aggregator.initialize_handler(handler_type(this)); } //! copy constructor queueing_port(const queueing_port& /* other */) = delete; //! record parent for tallying available items void set_join_node_pointer(queueing_forwarding_base *join) { my_join = join; } bool get_item( T &v ) { queueing_port_operation op_data(&v, get__item); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool get_item( T& v, message_metainfo& metainfo ) { queueing_port_operation op_data(&v, get__item, metainfo); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #endif // reset_port is called when item is accepted by successor, but // is initiated by join_node. void reset_port() { queueing_port_operation op_data(res_port); my_aggregator.execute(&op_data); return; } void reset_receiver(reset_flags) { item_buffer::reset(); } private: #if __TBB_PREVIEW_FLOW_GRAPH_NODE_SET friend class get_graph_helper; #endif queueing_forwarding_base *my_join; }; // queueing_port #include "_flow_graph_tagged_buffer_impl.h" template struct count_element { K my_key; size_t my_value; }; // method to access the key in the counting table // the ref has already been removed from K template< typename K > struct key_to_count_functor { typedef count_element table_item_type; const K& operator()(const table_item_type& v) { return v.my_key; } }; template struct key_matching_port_base { #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT using type = metainfo_hash_buffer; #else using type = hash_buffer; #endif }; // the ports can have only one template parameter. We wrap the types needed in // a traits type template< class TraitsType > class key_matching_port : public receiver, public key_matching_port_base< typename TraitsType::K, typename TraitsType::T, typename TraitsType::TtoK, typename TraitsType::KHash >::type { public: typedef TraitsType traits; typedef key_matching_port class_type; typedef typename TraitsType::T input_type; typedef typename TraitsType::K key_type; typedef typename std::decay::type noref_key_type; typedef typename receiver::predecessor_type predecessor_type; typedef typename TraitsType::TtoK type_to_key_func_type; typedef typename TraitsType::KHash hash_compare_type; typedef typename key_matching_port_base::type buffer_type; private: // ----------- Aggregator ------------ private: enum op_type { try__put, get__item, res_port }; class key_matching_port_operation : public d1::aggregated_operation { public: char type; input_type my_val; input_type *my_arg; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo* metainfo = nullptr; #endif // constructor for value parameter key_matching_port_operation(const input_type& e, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(const message_metainfo& info)) : type(char(t)), my_val(e), my_arg(nullptr) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(const_cast(&info))) {} // constructor for pointer parameter key_matching_port_operation(const input_type* p, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo& info)) : type(char(t)), my_arg(const_cast(p)) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(&info)) {} // constructor with no parameter key_matching_port_operation(op_type t) : type(char(t)), my_arg(nullptr) {} }; typedef d1::aggregating_functor handler_type; friend class d1::aggregating_functor; d1::aggregator my_aggregator; void handle_operations(key_matching_port_operation* op_list) { key_matching_port_operation *current; while(op_list) { current = op_list; op_list = op_list->next; switch(current->type) { case try__put: { #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT __TBB_ASSERT(current->metainfo, nullptr); bool was_inserted = this->insert_with_key(current->my_val, *(current->metainfo)); #else bool was_inserted = this->insert_with_key(current->my_val); #endif // return failure if a duplicate insertion occurs current->status.store( was_inserted ? SUCCEEDED : FAILED, std::memory_order_release); } break; case get__item: { // use current_key from FE for item __TBB_ASSERT(current->my_arg, nullptr); #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT __TBB_ASSERT(current->metainfo, nullptr); bool find_result = this->find_with_key(my_join->current_key, *(current->my_arg), *(current->metainfo)); #else bool find_result = this->find_with_key(my_join->current_key, *(current->my_arg)); #endif #if TBB_USE_DEBUG if (!find_result) { __TBB_ASSERT(false, "Failed to find item corresponding to current_key."); } #else tbb::detail::suppress_unused_warning(find_result); #endif current->status.store( SUCCEEDED, std::memory_order_release); } break; case res_port: // use current_key from FE for item this->delete_with_key(my_join->current_key); current->status.store( SUCCEEDED, std::memory_order_release); break; } } } // ------------ End Aggregator --------------- protected: template< typename R, typename B > friend class run_and_put_task; template friend class broadcast_cache; template friend class round_robin_cache; private: graph_task* try_put_task_impl(const input_type& v __TBB_FLOW_GRAPH_METAINFO_ARG(const message_metainfo& metainfo)) { key_matching_port_operation op_data(v, try__put __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo)); graph_task* rtask = nullptr; my_aggregator.execute(&op_data); if(op_data.status == SUCCEEDED) { rtask = my_join->increment_key_count((*(this->get_key_func()))(v)); // may spawn // rtask has to reflect the return status of the try_put if(!rtask) rtask = SUCCESSFULLY_ENQUEUED; } return rtask; } protected: graph_task* try_put_task(const input_type& v) override { return try_put_task_impl(v __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo{})); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT graph_task* try_put_task(const input_type& v, const message_metainfo& metainfo) override { return try_put_task_impl(v, metainfo); } #endif graph& graph_reference() const override { return my_join->graph_ref; } public: key_matching_port() : receiver(), buffer_type() { my_join = nullptr; my_aggregator.initialize_handler(handler_type(this)); } // copy constructor key_matching_port(const key_matching_port& /*other*/) = delete; #if __INTEL_COMPILER <= 2021 // Suppress superfluous diagnostic about virtual keyword absence in a destructor of an inherited // class while the parent class has the virtual keyword for the destrocutor. virtual #endif ~key_matching_port() { } void set_join_node_pointer(forwarding_base *join) { my_join = dynamic_cast*>(join); } void set_my_key_func(type_to_key_func_type *f) { this->set_key_func(f); } type_to_key_func_type* get_my_key_func() { return this->get_key_func(); } bool get_item( input_type &v ) { // aggregator uses current_key from FE for Key key_matching_port_operation op_data(&v, get__item); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool get_item( input_type& v, message_metainfo& metainfo ) { // aggregator uses current_key from FE for Key key_matching_port_operation op_data(&v, get__item, metainfo); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #endif // reset_port is called when item is accepted by successor, but // is initiated by join_node. void reset_port() { key_matching_port_operation op_data(res_port); my_aggregator.execute(&op_data); return; } void reset_receiver(reset_flags ) { buffer_type::reset(); } private: // my_join forwarding base used to count number of inputs that // received key. matching_forwarding_base *my_join; }; // key_matching_port using namespace graph_policy_namespace; template class join_node_base; //! join_node_FE : implements input port policy template class join_node_FE; template class join_node_FE : public reserving_forwarding_base { private: static const int N = std::tuple_size::value; typedef OutputTuple output_type; typedef InputTuple input_type; typedef join_node_base base_node_type; // for forwarding public: join_node_FE(graph &g) : reserving_forwarding_base(g), my_node(nullptr) { ports_with_no_inputs = N; join_helper::set_join_node_pointer(my_inputs, this); } join_node_FE(const join_node_FE& other) : reserving_forwarding_base((other.reserving_forwarding_base::graph_ref)), my_node(nullptr) { ports_with_no_inputs = N; join_helper::set_join_node_pointer(my_inputs, this); } void set_my_node(base_node_type *new_my_node) { my_node = new_my_node; } void increment_port_count() override { ++ports_with_no_inputs; } // if all input_ports have predecessors, spawn forward to try and consume tuples graph_task* decrement_port_count() override { if(ports_with_no_inputs.fetch_sub(1) == 1) { if(is_graph_active(this->graph_ref)) { d1::small_object_allocator allocator{}; typedef forward_task_bypass task_type; graph_task* t = allocator.new_object(graph_ref, allocator, *my_node); spawn_in_graph_arena(this->graph_ref, *t); } } return nullptr; } input_type &input_ports() { return my_inputs; } protected: void reset( reset_flags f) { // called outside of parallel contexts ports_with_no_inputs = N; join_helper::reset_inputs(my_inputs, f); } // all methods on input ports should be called under mutual exclusion from join_node_base. bool tuple_build_may_succeed() { return !ports_with_no_inputs; } bool try_to_make_tuple(output_type &out) { if(ports_with_no_inputs) return false; return join_helper::reserve(my_inputs, out); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool try_to_make_tuple(output_type &out, message_metainfo& metainfo) { if (ports_with_no_inputs) return false; return join_helper::reserve(my_inputs, out, metainfo); } #endif void tuple_accepted() { join_helper::consume_reservations(my_inputs); } void tuple_rejected() { join_helper::release_reservations(my_inputs); } input_type my_inputs; base_node_type *my_node; std::atomic ports_with_no_inputs; }; // join_node_FE template class join_node_FE : public queueing_forwarding_base { public: static const int N = std::tuple_size::value; typedef OutputTuple output_type; typedef InputTuple input_type; typedef join_node_base base_node_type; // for forwarding join_node_FE(graph &g) : queueing_forwarding_base(g), my_node(nullptr) { ports_with_no_items = N; join_helper::set_join_node_pointer(my_inputs, this); } join_node_FE(const join_node_FE& other) : queueing_forwarding_base((other.queueing_forwarding_base::graph_ref)), my_node(nullptr) { ports_with_no_items = N; join_helper::set_join_node_pointer(my_inputs, this); } // needed for forwarding void set_my_node(base_node_type *new_my_node) { my_node = new_my_node; } void reset_port_count() { ports_with_no_items = N; } // if all input_ports have items, spawn forward to try and consume tuples graph_task* decrement_port_count(bool handle_task) override { if(ports_with_no_items.fetch_sub(1) == 1) { if(is_graph_active(this->graph_ref)) { d1::small_object_allocator allocator{}; typedef forward_task_bypass task_type; graph_task* t = allocator.new_object(graph_ref, allocator, *my_node); if( !handle_task ) return t; spawn_in_graph_arena(this->graph_ref, *t); } } return nullptr; } input_type &input_ports() { return my_inputs; } protected: void reset( reset_flags f) { reset_port_count(); join_helper::reset_inputs(my_inputs, f ); } // all methods on input ports should be called under mutual exclusion from join_node_base. bool tuple_build_may_succeed() { return !ports_with_no_items; } bool try_to_make_tuple(output_type &out) { if(ports_with_no_items) return false; return join_helper::get_items(my_inputs, out); } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool try_to_make_tuple(output_type &out, message_metainfo& metainfo) { if(ports_with_no_items) return false; return join_helper::get_items(my_inputs, out, metainfo); } #endif void tuple_accepted() { reset_port_count(); join_helper::reset_ports(my_inputs); } void tuple_rejected() { // nothing to do. } input_type my_inputs; base_node_type *my_node; std::atomic ports_with_no_items; }; // join_node_FE // key_matching join front-end. template class join_node_FE, InputTuple, OutputTuple> : public matching_forwarding_base, // buffer of key value counts public hash_buffer< // typedefed below to key_to_count_buffer_type typename std::decay::type&, // force ref type on K count_element::type>, type_to_key_function_body< count_element::type>, typename std::decay::type& >, KHash >, // buffer of output items public item_buffer { public: static const int N = std::tuple_size::value; typedef OutputTuple output_type; typedef InputTuple input_type; typedef K key_type; typedef typename std::decay::type unref_key_type; typedef KHash key_hash_compare; // must use K without ref. typedef count_element count_element_type; // method that lets us refer to the key of this type. typedef key_to_count_functor key_to_count_func; typedef type_to_key_function_body< count_element_type, unref_key_type&> TtoK_function_body_type; typedef type_to_key_function_body_leaf TtoK_function_body_leaf_type; // this is the type of the special table that keeps track of the number of discrete // elements corresponding to each key that we've seen. typedef hash_buffer< unref_key_type&, count_element_type, TtoK_function_body_type, key_hash_compare > key_to_count_buffer_type; typedef item_buffer output_buffer_type; typedef join_node_base, InputTuple, OutputTuple> base_node_type; // for forwarding typedef matching_forwarding_base forwarding_base_type; // ----------- Aggregator ------------ // the aggregator is only needed to serialize the access to the hash table. // and the output_buffer_type base class private: enum op_type { res_count, inc_count, may_succeed, try_make }; typedef join_node_FE, InputTuple, OutputTuple> class_type; class key_matching_FE_operation : public d1::aggregated_operation { public: char type; unref_key_type my_val; output_type* my_output; graph_task* bypass_t; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo* metainfo = nullptr; #endif // constructor for value parameter key_matching_FE_operation(const unref_key_type& e , op_type t) : type(char(t)), my_val(e), my_output(nullptr), bypass_t(nullptr) {} key_matching_FE_operation(output_type *p, op_type t) : type(char(t)), my_output(p), bypass_t(nullptr) {} #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT key_matching_FE_operation(output_type *p, op_type t, message_metainfo& info) : type(char(t)), my_output(p), bypass_t(nullptr), metainfo(&info) {} #endif // constructor with no parameter key_matching_FE_operation(op_type t) : type(char(t)), my_output(nullptr), bypass_t(nullptr) {} }; typedef d1::aggregating_functor handler_type; friend class d1::aggregating_functor; d1::aggregator my_aggregator; // called from aggregator, so serialized // returns a task pointer if the a task would have been enqueued but we asked that // it be returned. Otherwise returns nullptr. graph_task* fill_output_buffer(unref_key_type &t) { output_type l_out; graph_task* rtask = nullptr; bool do_fwd = this->buffer_empty() && is_graph_active(this->graph_ref); this->current_key = t; this->delete_with_key(this->current_key); // remove the key #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo metainfo; #endif if(join_helper::get_items(my_inputs, l_out __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo))) { // <== call back this->push_back(l_out __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo)); if(do_fwd) { // we enqueue if receiving an item from predecessor, not if successor asks for item d1::small_object_allocator allocator{}; typedef forward_task_bypass task_type; rtask = allocator.new_object(this->graph_ref, allocator, *my_node); do_fwd = false; } // retire the input values join_helper::reset_ports(my_inputs); // <== call back } else { __TBB_ASSERT(false, "should have had something to push"); } return rtask; } void handle_operations(key_matching_FE_operation* op_list) { key_matching_FE_operation *current; while(op_list) { current = op_list; op_list = op_list->next; switch(current->type) { case res_count: // called from BE { this->destroy_front(); current->status.store( SUCCEEDED, std::memory_order_release); } break; case inc_count: { // called from input ports count_element_type *p = nullptr; unref_key_type &t = current->my_val; if(!(this->find_ref_with_key(t,p))) { count_element_type ev; ev.my_key = t; ev.my_value = 0; this->insert_with_key(ev); bool found = this->find_ref_with_key(t, p); __TBB_ASSERT_EX(found, "should find key after inserting it"); } if(++(p->my_value) == size_t(N)) { current->bypass_t = fill_output_buffer(t); } } current->status.store( SUCCEEDED, std::memory_order_release); break; case may_succeed: // called from BE current->status.store( this->buffer_empty() ? FAILED : SUCCEEDED, std::memory_order_release); break; case try_make: // called from BE if(this->buffer_empty()) { current->status.store( FAILED, std::memory_order_release); } else { *(current->my_output) = this->front(); #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT if (current->metainfo) { *(current->metainfo) = this->front_metainfo(); } #endif current->status.store( SUCCEEDED, std::memory_order_release); } break; } } } // ------------ End Aggregator --------------- public: template join_node_FE(graph &g, FunctionTuple &TtoK_funcs) : forwarding_base_type(g), my_node(nullptr) { join_helper::set_join_node_pointer(my_inputs, this); join_helper::set_key_functors(my_inputs, TtoK_funcs); my_aggregator.initialize_handler(handler_type(this)); TtoK_function_body_type *cfb = new TtoK_function_body_leaf_type(key_to_count_func()); this->set_key_func(cfb); } join_node_FE(const join_node_FE& other) : forwarding_base_type((other.forwarding_base_type::graph_ref)), key_to_count_buffer_type(), output_buffer_type() { my_node = nullptr; join_helper::set_join_node_pointer(my_inputs, this); join_helper::copy_key_functors(my_inputs, const_cast(other.my_inputs)); my_aggregator.initialize_handler(handler_type(this)); TtoK_function_body_type *cfb = new TtoK_function_body_leaf_type(key_to_count_func()); this->set_key_func(cfb); } // needed for forwarding void set_my_node(base_node_type *new_my_node) { my_node = new_my_node; } void reset_port_count() { // called from BE key_matching_FE_operation op_data(res_count); my_aggregator.execute(&op_data); return; } // if all input_ports have items, spawn forward to try and consume tuples // return a task if we are asked and did create one. graph_task *increment_key_count(unref_key_type const & t) override { // called from input_ports key_matching_FE_operation op_data(t, inc_count); my_aggregator.execute(&op_data); return op_data.bypass_t; } input_type &input_ports() { return my_inputs; } protected: void reset( reset_flags f ) { // called outside of parallel contexts join_helper::reset_inputs(my_inputs, f); key_to_count_buffer_type::reset(); output_buffer_type::reset(); } // all methods on input ports should be called under mutual exclusion from join_node_base. bool tuple_build_may_succeed() { // called from back-end key_matching_FE_operation op_data(may_succeed); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } // cannot lock while calling back to input_ports. current_key will only be set // and reset under the aggregator, so it will remain consistent. bool try_to_make_tuple(output_type &out) { key_matching_FE_operation op_data(&out,try_make); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool try_to_make_tuple(output_type &out, message_metainfo& metainfo) { key_matching_FE_operation op_data(&out, try_make, metainfo); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #endif void tuple_accepted() { reset_port_count(); // reset current_key after ports reset. } void tuple_rejected() { // nothing to do. } input_type my_inputs; // input ports base_node_type *my_node; }; // join_node_FE, InputTuple, OutputTuple> //! join_node_base template class join_node_base : public graph_node, public join_node_FE, public sender { protected: using graph_node::my_graph; public: typedef OutputTuple output_type; typedef typename sender::successor_type successor_type; typedef join_node_FE input_ports_type; using input_ports_type::tuple_build_may_succeed; using input_ports_type::try_to_make_tuple; using input_ports_type::tuple_accepted; using input_ports_type::tuple_rejected; private: // ----------- Aggregator ------------ enum op_type { reg_succ, rem_succ, try__get, do_fwrd, do_fwrd_bypass }; typedef join_node_base class_type; class join_node_base_operation : public d1::aggregated_operation { public: char type; union { output_type *my_arg; successor_type *my_succ; }; graph_task* bypass_t; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo* metainfo; #endif join_node_base_operation(const output_type& e, op_type t __TBB_FLOW_GRAPH_METAINFO_ARG(message_metainfo& info)) : type(char(t)), my_arg(const_cast(&e)), bypass_t(nullptr) __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo(&info)) {} #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT join_node_base_operation(const output_type& e, op_type t) : type(char(t)), my_arg(const_cast(&e)), bypass_t(nullptr), metainfo(nullptr) {} #endif join_node_base_operation(const successor_type &s, op_type t) : type(char(t)), my_succ(const_cast(&s)), bypass_t(nullptr) {} join_node_base_operation(op_type t) : type(char(t)), bypass_t(nullptr) {} }; typedef d1::aggregating_functor handler_type; friend class d1::aggregating_functor; bool forwarder_busy; d1::aggregator my_aggregator; void handle_operations(join_node_base_operation* op_list) { join_node_base_operation *current; while(op_list) { current = op_list; op_list = op_list->next; switch(current->type) { case reg_succ: { my_successors.register_successor(*(current->my_succ)); if(tuple_build_may_succeed() && !forwarder_busy && is_graph_active(my_graph)) { d1::small_object_allocator allocator{}; typedef forward_task_bypass< join_node_base > task_type; graph_task* t = allocator.new_object(my_graph, allocator, *this); spawn_in_graph_arena(my_graph, *t); forwarder_busy = true; } current->status.store( SUCCEEDED, std::memory_order_release); } break; case rem_succ: my_successors.remove_successor(*(current->my_succ)); current->status.store( SUCCEEDED, std::memory_order_release); break; case try__get: if(tuple_build_may_succeed()) { bool make_tuple_result = false; #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT if (current->metainfo) { make_tuple_result = try_to_make_tuple(*(current->my_arg), *(current->metainfo)); } else #endif { make_tuple_result = try_to_make_tuple(*(current->my_arg)); } if(make_tuple_result) { #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT if (current->metainfo) { // Since elements would be removed from queues while calling to tuple_accepted // together with corresponding message_metainfo objects // we need to prolong the wait until the successor would create a task for removed elements for (auto waiter : current->metainfo->waiters()) { waiter->reserve(1); } } #endif tuple_accepted(); current->status.store( SUCCEEDED, std::memory_order_release); } else current->status.store( FAILED, std::memory_order_release); } else current->status.store( FAILED, std::memory_order_release); break; case do_fwrd_bypass: { bool build_succeeded; graph_task *last_task = nullptr; output_type out; // forwarding must be exclusive, because try_to_make_tuple and tuple_accepted // are separate locked methods in the FE. We could conceivably fetch the front // of the FE queue, then be swapped out, have someone else consume the FE's // object, then come back, forward, and then try to remove it from the queue // again. Without reservation of the FE, the methods accessing it must be locked. // We could remember the keys of the objects we forwarded, and then remove // them from the input ports after forwarding is complete? if(tuple_build_may_succeed()) { // checks output queue of FE do { #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT message_metainfo metainfo; #endif // fetch front_end of queue build_succeeded = try_to_make_tuple(out __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo)); if(build_succeeded) { graph_task *new_task = my_successors.try_put_task(out __TBB_FLOW_GRAPH_METAINFO_ARG(metainfo)); last_task = combine_tasks(my_graph, last_task, new_task); if(new_task) { tuple_accepted(); } else { tuple_rejected(); build_succeeded = false; } } } while(build_succeeded); } current->bypass_t = last_task; current->status.store( SUCCEEDED, std::memory_order_release); forwarder_busy = false; } break; } } } // ---------- end aggregator ----------- public: join_node_base(graph &g) : graph_node(g), input_ports_type(g), forwarder_busy(false), my_successors(this) { input_ports_type::set_my_node(this); my_aggregator.initialize_handler(handler_type(this)); } join_node_base(const join_node_base& other) : graph_node(other.graph_node::my_graph), input_ports_type(other), sender(), forwarder_busy(false), my_successors(this) { input_ports_type::set_my_node(this); my_aggregator.initialize_handler(handler_type(this)); } template join_node_base(graph &g, FunctionTuple f) : graph_node(g), input_ports_type(g, f), forwarder_busy(false), my_successors(this) { input_ports_type::set_my_node(this); my_aggregator.initialize_handler(handler_type(this)); } bool register_successor(successor_type &r) override { join_node_base_operation op_data(r, reg_succ); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } bool remove_successor( successor_type &r) override { join_node_base_operation op_data(r, rem_succ); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } bool try_get( output_type &v) override { join_node_base_operation op_data(v, try__get); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #if __TBB_PREVIEW_FLOW_GRAPH_TRY_PUT_AND_WAIT bool try_get( output_type &v, message_metainfo& metainfo) override { join_node_base_operation op_data(v, try__get, metainfo); my_aggregator.execute(&op_data); return op_data.status == SUCCEEDED; } #endif protected: void reset_node(reset_flags f) override { input_ports_type::reset(f); if(f & rf_clear_edges) my_successors.clear(); } private: broadcast_cache my_successors; friend class forward_task_bypass< join_node_base >; graph_task *forward_task() { join_node_base_operation op_data(do_fwrd_bypass); my_aggregator.execute(&op_data); return op_data.bypass_t; } }; // join_node_base // join base class type generator template class PortType, typename OutputTuple, typename JoinPolicy> struct join_base { using type = join_node_base::type, OutputTuple>; }; template struct join_base > { using key_type = K; using key_hash_compare = KHash; using key_traits_type = key_matching; using type = join_node_base::type, OutputTuple>; }; #if __TBB_PREVIEW_MESSAGE_BASED_KEY_MATCHING template struct key_from_message_body { K operator()(const T& t) const { return key_from_message(t); } }; // Adds const to reference type template struct key_from_message_body { const K& operator()(const T& t) const { return key_from_message(t); } }; #endif /* __TBB_PREVIEW_MESSAGE_BASED_KEY_MATCHING */ //! unfolded_join_node : passes input_ports_type to join_node_base. We build the input port type // using tuple_element. The class PortType is the port type (reserving_port, queueing_port, key_matching_port) // and should match the typename. template class PortType, typename OutputTuple, typename JoinPolicy> class unfolded_join_node : public join_base::type { public: using input_ports_type = typename wrap_tuple_elements::type; using output_type = OutputTuple; private: using base_type = join_node_base; public: unfolded_join_node(graph& g) : base_type(g) {} unfolded_join_node(const unfolded_join_node &other) : base_type(other) {} }; // key_matching unfolded_join_node. This must be a separate specialization because the constructors // differ. template class unfolded_join_node, key_matching> : public join_base, key_matching>::type { public: using input_ports_type = typename wrap_key_tuple_elements, std::tuple>::type; using output_type = std::tuple; private: using base_type = join_node_base, input_ports_type, output_type>; using func_initializer_type = std::tuple*...>; public: #if __TBB_PREVIEW_MESSAGE_BASED_KEY_MATCHING unfolded_join_node(graph &g) : base_type(g, func_initializer_type( new type_to_key_function_body_leaf> (key_from_message_body())...)) {} #endif template unfolded_join_node(graph &g, Bodies... bodies) : base_type(g, func_initializer_type( new type_to_key_function_body_leaf(bodies)...)) {} unfolded_join_node(const unfolded_join_node &other) : base_type(other) {} }; //! templated function to refer to input ports of the join node template typename std::tuple_element::type &input_port(JNT &jn) { return std::get(jn.input_ports()); } #endif // __TBB__flow_graph_join_impl_H