From 3ed53ab71e945f28e9e026901637d9aea74b8aec Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 23 May 2015 12:03:33 +0300 Subject: [PATCH] Added urcu::raw_ptr adapter for non-intrusive containers Applied raw_ptr to non-intrusive MichaelList --- cds/container/michael_list_rcu.h | 45 ++++++++++---- cds/intrusive/michael_list_rcu.h | 13 ++-- cds/urcu/raw_ptr.h | 99 +++++++++++++++++++++++++++++++ tests/test-hdr/list/hdr_michael.h | 73 ++++++++++++----------- 4 files changed, 181 insertions(+), 49 deletions(-) diff --git a/cds/container/michael_list_rcu.h b/cds/container/michael_list_rcu.h index ee2904a8..6d0b5daf 100644 --- a/cds/container/michael_list_rcu.h +++ b/cds/container/michael_list_rcu.h @@ -138,6 +138,29 @@ namespace cds { namespace container { public: using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; ///< pointer to extracted node + private: + struct raw_ptr_converter + { + value_type * operator()( node_type * p ) const + { + return p ? &p->m_Value : nullptr; + } + + value_type& operator()( node_type& n ) const + { + return n.m_Value; + } + + value_type const& operator()( node_type const& n ) const + { + return n.m_Value; + } + }; + + 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; + private: //@cond static value_type& node_to_value( node_type& n ) @@ -630,7 +653,7 @@ namespace cds { namespace container { /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_MichaelList_rcu_get The function searches the item with key equal to \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. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -640,22 +663,25 @@ namespace cds { namespace container { typedef cds::container::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list; ord_list theList; // ... + typename ord_list::raw_ptr rp; { // Lock RCU ord_list::rcu_lock lock; - foo * 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 + // A value owned by rp can be freed at any time after RCU has been unlocked } + // You can manually release rp after RCU-locked section + rp.release(); \endcode */ template - value_type * get( Q const& key ) + raw_ptr get( Q const& key ) { return get_at( head(), key, intrusive_key_comparator()); } @@ -670,7 +696,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( Q const& key, Less pred ) + raw_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); return get_at( head(), key, typename maker::template less_wrapper::type()); @@ -777,10 +803,9 @@ namespace cds { namespace container { } template - value_type * get_at( head_type& refHead, Q const& val, Compare cmp ) + raw_ptr get_at( head_type& refHead, Q const& val, Compare cmp ) { - node_type * pNode = base_class::get_at( refHead, val, cmp ); - return pNode ? &pNode->m_Value : nullptr; + return raw_ptr( base_class::get_at( refHead, val, cmp )); } //@endcond diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index e09ddafa..4fd11dd9 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -743,7 +743,7 @@ namespace cds { namespace intrusive { /// Finds \p key and return the item found /** \anchor cds_intrusive_MichaelList_rcu_get The function searches the item with key equal to \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 empty \p raw_ptr object. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -753,18 +753,21 @@ namespace cds { namespace intrusive { typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list; ord_list theList; // ... + typename ord_list::raw_ptr rp; { // Lock RCU ord_list::rcu_lock lock; - foo * 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 retired by disposer at any time after RCU has been unlocked + // Node owned by rp can be retired by disposer at any time after RCU has been unlocked } + // You can manually release rp after RCU-locked section + rp.release(); \endcode */ template diff --git a/cds/urcu/raw_ptr.h b/cds/urcu/raw_ptr.h index 6455c9e7..ea8f98eb 100644 --- a/cds/urcu/raw_ptr.h +++ b/cds/urcu/raw_ptr.h @@ -170,6 +170,105 @@ namespace cds { namespace urcu { } }; + //@cond + /// Adapter \p raw_ptr for non-intrusive containers based on intrusive counterpart + template < + typename ValueType, + typename RawPtr, + typename Converter + > + class raw_ptr_adaptor: private RawPtr + { + public: + typedef RawPtr intrusive_raw_ptr; + typedef ValueType value_type; + typedef typename intrusive_raw_ptr::value_type node_type; + typedef Converter converter_type; + + public: + /// Constructs an empty raw pointer + raw_ptr_adaptor() + : intrusive_raw_ptr() + {} + + /// Move ctor + raw_ptr_adaptor( intrusive_raw_ptr&& p ) + : intrusive_raw_ptr( std::move(p)) + {} + + /// Move ctor + raw_ptr_adaptor( raw_ptr_adaptor&& p ) + : intrusive_raw_ptr( std::move(p)) + {} + + /// Copy ctor is prohibited + raw_ptr_adaptor( raw_ptr_adaptor const& ) = delete; + + /// Releases the raw pointer + ~raw_ptr_adaptor() + { + release(); + } + + public: + /// Move assignment operator + /** + This operator may be called only inside RCU-lock. + The \p this should be empty. + + In general, move assignment is intented for internal use. + */ + raw_ptr_adaptor& operator=( raw_ptr_adaptor&& p ) CDS_NOEXCEPT + { + intrusive_raw_ptr::operator =(std::move(p)); + return *this; + } + + /// Copy assignment is prohibited + raw_ptr_adaptor& operator=( raw_ptr_adaptor const& ) = delete; + + /// Returns a pointer to stored value + value_type * operator ->() const CDS_NOEXCEPT + { + return converter_type()( intrusive_raw_ptr::operator->()); + } + + /// Returns a reference to stored value + value_type& operator *() + { + return converter_type()( intrusive_raw_ptr::operator*()); + } + + /// Returns a reference to stored value + value_type const& operator *() const + { + return converter_type()( intrusive_raw_ptr::operator*()); + } + + /// Checks if the \p %raw_ptr is \p nullptr + bool empty() const CDS_NOEXCEPT + { + return intrusive_raw_ptr::empty(); + } + + /// Checks if the \p %raw_ptr is not empty + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + + /// Releases the \p %raw_ptr object + /** + This function may be called only outside RCU section. + After \p %release() the object can be reused. + */ + void release() + { + intrusive_raw_ptr::release(); + } + }; + //@endcond + }} // namespace cds::urcu #endif // #ifndef CDSLIB_URCU_RAW_PTR_H diff --git a/tests/test-hdr/list/hdr_michael.h b/tests/test-hdr/list/hdr_michael.h index 06a666b1..ec1307aa 100644 --- a/tests/test-hdr/list/hdr_michael.h +++ b/tests/test-hdr/list/hdr_michael.h @@ -560,38 +560,41 @@ namespace ordlist { CPPUNIT_ASSERT( l.insert( a[i] ) ); typename OrdList::exempt_ptr ep; + typename OrdList::raw_ptr rp; for ( int i = 0; i < nLimit; ++i ) { { rcu_lock lock; - value_type * pGet = l.get( a[i] ); - CPPUNIT_ASSERT( pGet != nullptr ); - CPPUNIT_CHECK( pGet->nKey == a[i] ); - CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - - ep = l.extract( a[i] ); - CPPUNIT_ASSERT( ep ); - CPPUNIT_ASSERT( !ep.empty() ); - CPPUNIT_CHECK( ep->nKey == a[i] ); - CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 ); + rp = l.get( a[i] ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == a[i] ); + CPPUNIT_CHECK( rp->nVal == a[i] * 2 ); } + rp.release(); + + ep = l.extract( a[i] ); + CPPUNIT_ASSERT( ep ); + CPPUNIT_ASSERT( !ep.empty() ); + CPPUNIT_CHECK( ep->nKey == a[i] ); + CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 ); ep.release(); + { rcu_lock lock; - CPPUNIT_CHECK( l.get( a[i] ) == nullptr ); - ep = l.extract( a[i] ); - CPPUNIT_CHECK( !ep ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get( a[i] )); } + ep = l.extract( a[i] ); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( ep.empty() ); } CPPUNIT_ASSERT( l.empty() ); { rcu_lock lock; - CPPUNIT_CHECK( l.get( a[0] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( a[0] ) ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get( a[0] )); } + CPPUNIT_CHECK( !l.extract( a[0] ) ); + CPPUNIT_CHECK( ep.empty() ); // extract_with/get_with for ( int i = 0; i < nLimit; ++i ) { @@ -602,34 +605,36 @@ namespace ordlist { other_item itm( a[i] ); { rcu_lock lock; - value_type * pGet = l.get_with( itm, other_less() ); - CPPUNIT_ASSERT( pGet != nullptr ); - CPPUNIT_CHECK( pGet->nKey == a[i] ); - CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - - ep = l.extract_with( itm, other_less() ); - CPPUNIT_ASSERT( ep ); - CPPUNIT_ASSERT( !ep.empty() ); - CPPUNIT_CHECK( ep->nKey == a[i] ); - CPPUNIT_CHECK( ep->nVal == a[i] * 2 ); + rp = l.get_with( itm, other_less() ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == a[i] ); + CPPUNIT_CHECK( rp->nVal == a[i] * 2 ); } + rp.release(); + + ep = l.extract_with( itm, other_less() ); + CPPUNIT_ASSERT( ep ); + CPPUNIT_ASSERT( !ep.empty() ); + CPPUNIT_CHECK( ep->nKey == a[i] ); + CPPUNIT_CHECK( ep->nVal == a[i] * 2 ); ep.release(); + { rcu_lock lock; - CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr ); - ep = l.extract_with( itm, other_less() ); - CPPUNIT_CHECK( !ep ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get_with( itm, other_less())); } + ep = l.extract_with( itm, other_less() ); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( ep.empty() ); } CPPUNIT_ASSERT( l.empty() ); { rcu_lock lock; - CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get_with( other_item( 0 ), other_less())); } + CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); + CPPUNIT_CHECK( ep.empty() ); } } -- 2.34.1