X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_kvlist_rcu.h;h=6c4f61b8be612dc54307ac0df5203ad6a34b9cc1;hb=c90d4632599270326b394f71942cc452b6678bc7;hp=7545e48c7fcb0b0b1f8086f4e209b1da3072591c;hpb=6e2784d24f15873dc5b971499276cc8e4147fd46;p=libcds.git diff --git a/cds/container/michael_kvlist_rcu.h b/cds/container/michael_kvlist_rcu.h index 7545e48c..6c4f61b8 100644 --- a/cds/container/michael_kvlist_rcu.h +++ b/cds/container/michael_kvlist_rcu.h @@ -1,7 +1,7 @@ //$$CDS-header$$ -#ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H -#define __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H +#ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H +#define CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H #include #include // ref @@ -105,15 +105,15 @@ namespace cds { namespace container { #endif typedef Traits traits; ///< List traits - typedef typename base_class::back_off back_off; ///< Back-off strategy - typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes - typedef typename base_class::item_counter item_counter; ///< Item counting policy - typedef typename maker::key_comparator key_comparator; ///< key comparison functor - typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p michael_list::traits::memory_model + typedef typename base_class::back_off back_off; ///< Back-off strategy + typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes + typedef typename base_class::item_counter item_counter; ///< Item counting policy + typedef typename maker::key_comparator key_comparator; ///< key comparison functor + typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p michael_list::traits::memory_model typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock - static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking + static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking protected: //@cond @@ -131,6 +131,31 @@ namespace cds { namespace container { cds::urcu::details::conventional_exempt_pair_cast >; + private: + //@cond + struct raw_ptr_converter + { + value_type * operator()( node_type * p ) const + { + return p ? &p->m_Data : nullptr; + } + + value_type& operator()( node_type& n ) const + { + return n.m_Data; + } + + value_type const& operator()( node_type const& n ) const + { + return n.m_Data; + } + }; + //@endcond + + public: + /// Result of \p get(), \p get_with() functions - pointer to the node found + typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr; + protected: //@cond template @@ -327,7 +352,7 @@ namespace cds { namespace container { In trivial case, \p K is equal to \ref key_type. - The \ref mapped_type should be default-constructible. - The function makes RCU lock internally. + The function applies RCU lock internally. Returns \p true if inserting successful, \p false otherwise. */ @@ -345,7 +370,7 @@ namespace cds { namespace container { - The \ref key_type should be constructible from \p key of type \p K. - The \ref mapped_type should be constructible from \p val of type \p V. - The function makes RCU lock internally. + The function applies RCU lock internally. Returns \p true if inserting successful, \p false otherwise. */ @@ -380,14 +405,14 @@ namespace cds { namespace container { This can be useful if complete initialization of object of \p mapped_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. - The function makes RCU lock internally. + The function applies RCU lock internally. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - bool insert_key( const K& key, Func func ) + bool insert_with( const K& key, Func func ) { - return insert_key_at( head(), key, func ); + return insert_with_at( head(), key, func ); } /// Ensures that the \p key exists in the list @@ -417,7 +442,7 @@ namespace cds { namespace container { however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - The function makes RCU lock internally. + The function applies RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key @@ -435,7 +460,7 @@ namespace cds { namespace container { /** Returns \p true if inserting successful, \p false otherwise. - The function makes RCU lock internally. + The function applies RCU lock internally. */ template bool emplace( K&& key, Args&&... args ) @@ -477,7 +502,7 @@ namespace cds { namespace container { The functor \p Func interface: \code - struct extractor { + struct functor { void operator()(value_type& val) { ... } }; \endcode @@ -515,10 +540,9 @@ namespace cds { namespace container { unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. If \p key is not found the function returns an empty \p exempt_ptr. - @note The function does NOT call RCU read-side lock or synchronization, - and does NOT dispose the item found. It just excludes the item from the list - and returns a pointer to item found. - You should lock RCU before calling this function. + @note The function does NOT dispose the item found. + It just excludes the item from the list and returns a pointer to item found. + You shouldn't lock RCU before calling this function. \code #include @@ -531,19 +555,18 @@ namespace cds { namespace container { // ... rcu_michael_list::exempt_ptr p; - { - // first, we should lock RCU - rcu_michael_list::rcu_lock sl; - - // Now, you can apply extract function - // Note that you must not delete the item found inside the RCU lock - p = theList.extract( 10 ); - if ( p ) { - // do something with p - ... - } + + // The RCU should NOT be locked when extract() is called! + assert( !rcu::is_locked() ); + + // extract() call + p = theList.extract( 10 ); + if ( p ) { + // do something with p + ... } - // Outside RCU lock section we may safely release extracted pointer. + + // we may safely release extracted pointer here. // release() passes the pointer to RCU reclamation cycle. p.release(); \endcode @@ -556,7 +579,7 @@ namespace cds { namespace container { /// Extracts an item from the list using \p pred predicate for searching /** - This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)". + This function is the analog for \p extract(K const&). The \p pred is a predicate used for key comparing. \p Less has the interface like \p std::less. \p pred must imply the same element order as \ref key_comparator. @@ -577,7 +600,7 @@ namespace cds { namespace container { The function makes RCU lock internally. */ template - bool find( Q const& key ) const + bool find( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } @@ -590,7 +613,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) const + bool find_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); @@ -617,7 +640,7 @@ namespace cds { namespace container { The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( Q const& key, Func f ) const + bool find( Q const& key, Func f ) { return find_at( head(), key, intrusive_key_comparator(), f ); } @@ -630,7 +653,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred, Func f ) const + bool find_with( Q const& key, Less pred, Func f ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type(), f ); @@ -639,7 +662,7 @@ namespace cds { namespace container { /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelKVList_rcu_get The function searches the item with \p key and returns the pointer to item found. - If \p key is not found it returns \p nullptr. + If \p key is not found it returns an empty \p raw_ptr object. Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type. @@ -649,22 +672,24 @@ namespace cds { namespace container { typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list; ord_list theList; // ... + tyename ord_list::raw_ptr rp; { // Lock RCU ord_list::rcu_lock lock; - ord_list::value_type * pVal = theList.get( 5 ); - if ( pVal ) { - // Deal with pVal + rp = theList.get( 5 ); + if ( rp ) { + // Deal with rp //... } // Unlock RCU by rcu_lock destructor - // pVal can be freed at any time after RCU has been unlocked } + // rp can be released at any time after RCU has been unlocked + rp.release(); \endcode */ template - value_type * get( K const& key ) const + raw_ptr get( K const& key ) { return get_at( head(), key, intrusive_key_comparator()); } @@ -679,7 +704,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - value_type * get_with( K const& key, Less pred ) const + raw_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); return get_at( head(), key, typename maker::template less_wrapper::type() ); @@ -739,7 +764,7 @@ namespace cds { namespace container { } template - bool insert_key_at( head_type& refHead, const K& key, Func f ) + bool insert_with_at( head_type& refHead, const K& key, Func f ) { scoped_node_ptr pNode( alloc_node( key )); @@ -788,22 +813,21 @@ namespace cds { namespace container { } template - bool find_at( head_type& refHead, K const& key, Compare cmp ) const + bool find_at( head_type& refHead, K const& key, Compare cmp ) { return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} ); } template - bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const + bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) { return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); }); } template - value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const + raw_ptr get_at( head_type& refHead, K const& val, Compare cmp ) { - node_type * pNode = base_class::get_at( refHead, val, cmp ); - return pNode ? &pNode->m_Data : nullptr; + return raw_ptr( base_class::get_at( refHead, val, cmp )); } //@endcond @@ -811,4 +835,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H +#endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H