From f20ee4054966a5a1af3b90440248557d04c5481f Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 12 Nov 2014 15:37:02 +0300 Subject: [PATCH] movable exempt_ptr: EllenBinTree --- cds/container/ellen_bintree_map_rcu.h | 50 +++++----- cds/container/ellen_bintree_set_rcu.h | 51 +++++----- cds/intrusive/ellen_bintree_rcu.h | 87 +++++++++-------- cds/urcu/exempt_ptr.h | 102 ++++++++++++++------ tests/test-hdr/tree/hdr_ellenbintree_map.h | 32 +++--- tests/test-hdr/tree/hdr_ellenbintree_set.h | 27 ++++-- tests/test-hdr/tree/hdr_intrusive_bintree.h | 38 ++++---- 7 files changed, 220 insertions(+), 167 deletions(-) diff --git a/cds/container/ellen_bintree_map_rcu.h b/cds/container/ellen_bintree_map_rcu.h index d5852f66..bbc76592 100644 --- a/cds/container/ellen_bintree_map_rcu.h +++ b/cds/container/ellen_bintree_map_rcu.h @@ -110,9 +110,9 @@ namespace cds { namespace container { typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock /// pointer to extracted node - typedef cds::urcu::exempt_ptr< gc, leaf_node, value_type, typename maker::intrusive_traits::disposer, - cds::urcu::details::conventional_exempt_member_cast - > exempt_ptr; + using exempt_ptr = cds::urcu::exempt_ptr < gc, leaf_node, value_type, typename maker::intrusive_traits::disposer, + cds::urcu::details::conventional_exempt_member_cast < leaf_node, value_type > + >; public: /// Default constructor @@ -332,8 +332,8 @@ namespace cds { namespace container { /// Extracts an item with minimal key from the map /** - If the map is not empty, the function returns \p true, \p result contains a pointer to value. - If the map is empty, the function returns \p false, \p result is left unchanged. + Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly minimum key. It means that the function gets leftmost leaf of the tree and tries to unlink it. @@ -342,19 +342,18 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. - The deallocator will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The deallocator will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ - bool extract_min( exempt_ptr& result ) + exempt_ptr extract_min() { - return base_class::extract_min_( result ); + return exempt_ptr( base_class::extract_min_()); } /// Extracts an item with maximal key from the map /** - If the map is not empty, the function returns \p true, \p result contains a pointer to extracted item. - If the map is empty, the function returns \p false, \p result is left unchanged. + Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the map, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -363,31 +362,30 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. - The deallocator will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. + The deallocator will be implicitly invoked when the returned object is destroyed or when + its \p release() is called. @note Before reusing \p result object you should call its \p release() method. */ - bool extract_max( exempt_ptr& result ) + exempt_ptr extract_max() { - return base_class::extract_max_( result ); + return exempt_ptr( base_class::extract_max_()); } /// Extracts an item from the map /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_extract The function searches an item with key equal to \p key in the tree, - unlinks it, and returns pointer to an item found in \p result parameter. - If \p key is not found the function returns \p false. + unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found. + If \p key is not found the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not destroy the item found. - The dealloctor will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The dealloctor will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ template - bool extract( exempt_ptr& result, Q const& key ) + exempt_ptr extract( Q const& key ) { - return base_class::extract_( result, key, typename base_class::node_compare()); + return exempt_ptr( base_class::extract_( key, typename base_class::node_compare())); } /// Extracts an item from the map using \p pred for searching @@ -399,10 +397,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( exempt_ptr& result, Q const& val, Less pred ) + exempt_ptr extract_with( Q const& val, Less pred ) { - return base_class::extract_with_( result, val, - cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() ); + return exempt_ptr( base_class::extract_with_( val, + cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() )); } /// Find the key \p key diff --git a/cds/container/ellen_bintree_set_rcu.h b/cds/container/ellen_bintree_set_rcu.h index 4c802c93..02baa883 100644 --- a/cds/container/ellen_bintree_set_rcu.h +++ b/cds/container/ellen_bintree_set_rcu.h @@ -145,9 +145,9 @@ namespace cds { namespace container { typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock /// pointer to extracted node - typedef cds::urcu::exempt_ptr< gc, leaf_node, value_type, typename maker::intrusive_traits::disposer, - cds::urcu::details::conventional_exempt_member_cast - > exempt_ptr; + using exempt_ptr = cds::urcu::exempt_ptr < gc, leaf_node, value_type, typename maker::intrusive_traits::disposer, + cds::urcu::details::conventional_exempt_member_cast < leaf_node, value_type > + > ; public: /// Default constructor @@ -347,8 +347,8 @@ namespace cds { namespace container { /// Extracts an item with minimal key from the set /** - If the set is not empty, the function returns \p true, \p result contains a pointer to value. - If the set is empty, the function returns \p false, \p result is left unchanged. + Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the set, the function extracts nearly minimum key. It means that the function gets leftmost leaf of the tree and tries to unlink it. @@ -357,19 +357,18 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. - The deallocator will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The deallocator will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ - bool extract_min( exempt_ptr& result ) + exempt_ptr extract_min() { - return base_class::extract_min_( result ); + return exempt_ptr( base_class::extract_min_()); } /// Extracts an item with maximal key from the set /** - If the set is not empty, the function returns \p true, \p result contains a pointer to extracted item. - If the set is empty, the function returns \p false, \p result is left unchanged. + Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item. + If the set is empty, returns empty \p exempt_ptr. @note Due the concurrent nature of the set, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -378,31 +377,29 @@ namespace cds { namespace container { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item. - The deallocator will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The deallocator will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ - bool extract_max( exempt_ptr& result ) + exempt_ptr extract_max() { - return base_class::extract_max_( result ); + return exempt_ptr( base_class::extract_max_()); } /// Extracts an item from the set /** \anchor cds_nonintrusive_EllenBinTreeSet_rcu_extract The function searches an item with key equal to \p key in the tree, - unlinks it, and returns pointer to an item found in \p result parameter. - If \p key is not found the function returns \p false. + unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found. + If \p key is not found the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not destroy the item found. - The dealloctor will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The dealloctor will be implicitly invoked when the returned object is destroyed or when + its release() member function is called. */ template - bool extract( exempt_ptr& result, Q const& key ) + exempt_ptr extract( Q const& key ) { - return base_class::extract_( result, key, typename base_class::node_compare()); + return exempt_ptr( base_class::extract_( key, typename base_class::node_compare())); } /// Extracts an item from the set using \p pred for searching @@ -414,10 +411,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the set. */ template - bool extract_with( exempt_ptr& result, Q const& val, Less pred ) + exempt_ptr extract_with( Q const& val, Less pred ) { - return base_class::extract_with_( result, val, - cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() ); + return exempt_ptr( base_class::extract_with_( val, + cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() )); } /// Find the key \p key diff --git a/cds/intrusive/ellen_bintree_rcu.h b/cds/intrusive/ellen_bintree_rcu.h index 55e80511..20ec705d 100644 --- a/cds/intrusive/ellen_bintree_rcu.h +++ b/cds/intrusive/ellen_bintree_rcu.h @@ -448,7 +448,7 @@ namespace cds { namespace intrusive { //@endcond public: - typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node public: # ifdef CDS_DOXYGEN_INVOKED @@ -965,8 +965,9 @@ namespace cds { namespace intrusive { /// Extracts an item with minimal key from the tree /** - The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter. - If the tree is empty the function returns \p false. + The function searches an item with minimal key, unlinks it, and returns + \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item. + If the tree is empty the function returns empty \p exempt_ptr. @note Due the concurrent nature of the tree, the function extracts nearly minimum key. It means that the function gets leftmost leaf of the tree and tries to unlink it. @@ -975,19 +976,19 @@ namespace cds { namespace intrusive { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. - The disposer will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The disposer will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ - bool extract_min(exempt_ptr& result) + exempt_ptr extract_min() { - return extract_min_(result); + return exempt_ptr( extract_min_() ); } /// Extracts an item with maximal key from the tree /** - The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter. - If the tree is empty the function returns \p false. + The function searches an item with maximal key, unlinks it, and returns + \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item. + If the tree is empty the function returns empty \p exempt_ptr. @note Due the concurrent nature of the tree, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -996,31 +997,29 @@ namespace cds { namespace intrusive { RCU \p synchronize method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. - The disposer will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The disposer will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ - bool extract_max(exempt_ptr& result) + exempt_ptr extract_max() { - return extract_max_(result); + return exempt_ptr( extract_max_() ); } /// Extracts an item from the tree /** \anchor cds_intrusive_EllenBinTree_rcu_extract The function searches an item with key equal to \p key in the tree, - unlinks it, and returns pointer to an item found in \p result parameter. - If the item with the key equal to \p key is not found the function returns \p false. + unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found. + If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. - The disposer will be implicitly invoked when \p result object is destroyed or when - result.release() is called, see cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The disposer will be implicitly invoked when the returned object is destroyed or when + its \p release() member function is called. */ template - bool extract( exempt_ptr& result, Q const& key ) + exempt_ptr extract( Q const& key ) { - return extract_( result, key, node_compare() ); + return exempt_ptr( extract_( key, node_compare() )); } /// Extracts an item from the set using \p pred for searching @@ -1032,9 +1031,9 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool extract_with( exempt_ptr& dest, Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - return extract_with_( dest, key, pred ); + return exempt_ptr( extract_with_( key, pred )); } /// Finds the key \p key @@ -1203,8 +1202,7 @@ namespace cds { namespace intrusive { */ void clear() { - exempt_ptr ep; - while ( extract_min(ep) ) + for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() ) ep.release(); } @@ -1639,8 +1637,8 @@ namespace cds { namespace intrusive { return true; } - template - bool extract_with_( ExemptPtr& dest, Q const& val, Less pred ) + template + value_type * extract_with_( Q const& val, Less pred ) { typedef ellen_bintree::details::compare< key_type, @@ -1649,11 +1647,11 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return extract_( dest, val, compare_functor() ); + return extract_( val, compare_functor() ); } - template - bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp ) + template + value_type * extract_( Q const& val, Compare cmp ) { check_deadlock_policy::check(); @@ -1661,6 +1659,7 @@ namespace cds { namespace intrusive { update_desc * pOp = nullptr; search_result res; back_off bkoff; + value_type * pResult; { rcu_lock l; @@ -1669,7 +1668,7 @@ namespace cds { namespace intrusive { if ( pOp ) retire_update_desc( pOp, updRetire, false ); m_Stat.onEraseFailed(); - return false; + return nullptr; } if ( res.updGrandParent.bits() != update_desc::Clean ) @@ -1693,7 +1692,7 @@ namespace cds { namespace intrusive { memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { if ( help_delete( pOp, updRetire )) { - ptr = node_traits::to_value_ptr( res.pLeaf ); + pResult = node_traits::to_value_ptr( res.pLeaf ); break; } pOp = nullptr; @@ -1712,12 +1711,11 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onEraseSuccess(); - return true; + return pResult; } - template - bool extract_max_( ExemptPtr& result ) + value_type * extract_max_() { check_deadlock_policy::check(); @@ -1725,6 +1723,7 @@ namespace cds { namespace intrusive { update_desc * pOp = nullptr; search_result res; back_off bkoff; + value_type * pResult; { rcu_lock l; @@ -1734,7 +1733,7 @@ namespace cds { namespace intrusive { if ( pOp ) retire_update_desc( pOp, updRetire, false ); m_Stat.onExtractMaxFailed(); - return false; + return nullptr; } if ( res.updGrandParent.bits() != update_desc::Clean ) @@ -1758,7 +1757,7 @@ namespace cds { namespace intrusive { memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { if ( help_delete( pOp, updRetire )) { - result = node_traits::to_value_ptr( res.pLeaf ); + pResult = node_traits::to_value_ptr( res.pLeaf ); break; } pOp = nullptr; @@ -1777,11 +1776,10 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMaxSuccess(); - return true; + return pResult; } - template - bool extract_min_(ExemptPtr& result) + value_type * extract_min_() { check_deadlock_policy::check(); @@ -1789,6 +1787,7 @@ namespace cds { namespace intrusive { update_desc * pOp = nullptr; search_result res; back_off bkoff; + value_type * pResult; { rcu_lock l; @@ -1798,7 +1797,7 @@ namespace cds { namespace intrusive { if ( pOp ) retire_update_desc( pOp, updRetire, false ); m_Stat.onExtractMinFailed(); - return false; + return nullptr; } if ( res.updGrandParent.bits() != update_desc::Clean ) @@ -1822,7 +1821,7 @@ namespace cds { namespace intrusive { memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { if ( help_delete( pOp, updRetire )) { - result = node_traits::to_value_ptr( res.pLeaf ); + pResult = node_traits::to_value_ptr( res.pLeaf ); break; } pOp = nullptr; @@ -1841,7 +1840,7 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMinSuccess(); - return true; + return pResult; } template diff --git a/cds/urcu/exempt_ptr.h b/cds/urcu/exempt_ptr.h index 5d65455b..e86103a1 100644 --- a/cds/urcu/exempt_ptr.h +++ b/cds/urcu/exempt_ptr.h @@ -33,18 +33,19 @@ namespace cds { namespace urcu { /** This special pointer class is intended for returning extracted node from RCU-based container. The destructor (and \p release() member function) invokes RCU::retire_ptr< Disposer >() function to dispose the node. - For non-intrusive containers from \p cds::container namespace \p Disposer is an invocation + For non-intrusive containers from \p cds::container namespace \p Disposer is usually an invocation of node deallocator. For intrusive containers the disposer can be empty or it can trigger an event "node can be reused safely". In any case, the exempt pointer concept keeps RCU semantics. - You don't need use this helper class directly. Any RCU-based container defines a proper typedef for this template. + You don't need use this helper class directly. Any RCU-based container typedefs a simplified version of this template. Template arguments: - \p RCU - one of \ref cds_urcu_gc "RCU type" - \p NodeType - container's node type - \p ValueType - value type stored in container's node. For intrusive containers it is the same as \p NodeType - \p Disposer - a disposer functor - - \p Cast - a functor for casting from \p NodeType to \p ValueType. Usually, for intrusive containers \p Cast may be \p void. + - \p Cast - a functor for casting from \p NodeType to \p ValueType. For intrusive containers + the casting is usually disabled, i.e. \p Cast is \p void. */ template < class RCU, @@ -59,7 +60,6 @@ namespace cds { namespace urcu { > class exempt_ptr { - //TODO: use move semantics and explicit operator bool! public: typedef RCU rcu ; ///< RCU type - one of cds::urcu::gc< ... > typedef NodeType node_type ; ///< Node type @@ -72,19 +72,32 @@ namespace cds { namespace urcu { node_type * m_pNode; //@endcond - private: - //@cond - // No copy-constructible - exempt_ptr( exempt_ptr const& ); - exempt_ptr& operator=( exempt_ptr const& ); - //@endcond - public: /// Constructs empty pointer exempt_ptr() CDS_NOEXCEPT : m_pNode( nullptr ) {} + //@cond + /// Creates exempt pointer for \p pNode. Only for internal use. + explicit exempt_ptr( node_type * pNode ) CDS_NOEXCEPT + : m_pNode( pNode ) + {} + explicit exempt_ptr( std::nullptr_t ) CDS_NOEXCEPT + : m_pNode( nullptr ) + {} + //@endcond + + /// Move ctor + exempt_ptr( exempt_ptr&& p ) CDS_NOEXCEPT + : m_pNode( p.m_pNode ) + { + p.m_pNode = nullptr; + } + + /// The exempt pointer is not copy-constructible + exempt_ptr( exempt_ptr const& ) = delete; + /// Releases the pointer ~exempt_ptr() { @@ -97,6 +110,12 @@ namespace cds { namespace urcu { return m_pNode == nullptr; } + /// \p bool operator returns !empty() + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + /// Dereference operator value_type * operator->() const CDS_NOEXCEPT { @@ -110,17 +129,17 @@ namespace cds { namespace urcu { return *node_to_value_cast()( m_pNode ); } - //@cond - /// Assignment operator, the object should be empty. For internal use only - exempt_ptr& operator =( node_type * pNode ) + /// Move assignment. Can be called only outside of RCU critical section + exempt_ptr& operator =( exempt_ptr&& p ) CDS_NOEXCEPT { - // release() cannot be called in this point since RCU should be locked - assert( empty() ); - assert( rcu::is_locked() ); - m_pNode = pNode; + release(); + m_pNode = p.m_pNode; + p.m_pNode = nullptr; return *this; } - //@endcond + + /// The exempt pointer is not copy-assignable + exempt_ptr& operator=(exempt_ptr const&) = delete; /// Disposes the pointer. Should be called only outside of RCU critical section void release() @@ -142,7 +161,6 @@ namespace cds { namespace urcu { > class exempt_ptr< RCU, NodeType, NodeType, Disposer, void > { - //TODO: use move semantics and explicit operator bool! public: typedef RCU rcu ; ///< RCU type - one of cds::urcu::gc< ... > typedef NodeType node_type ; ///< Node type @@ -153,17 +171,31 @@ namespace cds { namespace urcu { private: node_type * m_pNode; - private: - // No copy-constructible - exempt_ptr( exempt_ptr const& ); - exempt_ptr& operator=( exempt_ptr const& ); - public: /// Constructs empty pointer exempt_ptr() CDS_NOEXCEPT : m_pNode( nullptr ) {} + /// Creates exempt pointer for \p pNode. Only for internal use. + explicit exempt_ptr( node_type * pNode ) CDS_NOEXCEPT + : m_pNode( pNode ) + {} + explicit exempt_ptr( std::nullptr_t ) CDS_NOEXCEPT + : m_pNode( nullptr ) + {} + + /// Move ctor + exempt_ptr( exempt_ptr&& p ) CDS_NOEXCEPT + : m_pNode( p.m_pNode ) + { + p.m_pNode = nullptr; + } + + + /// The exempt pointer is not copy-constructible + exempt_ptr( exempt_ptr const& ) = delete; + /// Releases the pointer ~exempt_ptr() { @@ -176,6 +208,12 @@ namespace cds { namespace urcu { return m_pNode == nullptr; } + /// \p bool operator returns !empty() + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + /// Dereference operator. value_type * operator->() const CDS_NOEXCEPT { @@ -189,16 +227,18 @@ namespace cds { namespace urcu { return *m_pNode; } - /// Assignment operator, the object should be empty. For internal use only - exempt_ptr& operator =( node_type * pNode ) + /// Move assignment. Can be called only outside of RCU critical section + exempt_ptr& operator =(exempt_ptr&& p) CDS_NOEXCEPT { - // release() cannot be called in this point since RCU should be locked - assert( empty() ); - assert( rcu::is_locked() ); - m_pNode = pNode; + release(); + m_pNode = p.m_pNode; + p.m_pNode = nullptr; return *this; } + /// The exempt pointer is not copy-assignable + exempt_ptr& operator=(exempt_ptr const&) = delete; + /// Disposes the pointer. Should be called only outside of RCU critical section void release() { diff --git a/tests/test-hdr/tree/hdr_ellenbintree_map.h b/tests/test-hdr/tree/hdr_ellenbintree_map.h index 033db4e3..cf0ccaf8 100644 --- a/tests/test-hdr/tree/hdr_ellenbintree_map.h +++ b/tests/test-hdr/tree/hdr_ellenbintree_map.h @@ -476,29 +476,33 @@ namespace tree { int i = 0; while ( !m.empty() ) { - CPPUNIT_ASSERT( m.extract_min( ep ) ); + ep = m.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_ASSERT(ep->first == i ); ++i; - ep.release(); + //ep.release(); } CPPUNIT_ASSERT( m.empty() ); CPPUNIT_ASSERT( check_size( m, 0 )); - CPPUNIT_ASSERT( !m.extract_min( ep ) ); + ep = m.extract_min(); + CPPUNIT_ASSERT( !ep ); CPPUNIT_ASSERT( ep.empty()); fill_map( m, arr ); i = (int) c_nItemCount - 1; while ( !m.empty() ) { - CPPUNIT_ASSERT( m.extract_max( ep ) ); + ep = m.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_ASSERT( ep->first == i ); --i; - ep.release(); + //ep.release(); } CPPUNIT_ASSERT( m.empty() ); CPPUNIT_ASSERT( check_size( m, 0 )); - CPPUNIT_ASSERT( !m.extract_max( ep ) ); + ep = m.extract_max(); + CPPUNIT_ASSERT( !ep ); CPPUNIT_ASSERT( ep.empty()); fill_map( m, arr ); @@ -510,12 +514,14 @@ namespace tree { CPPUNIT_ASSERT( pVal != nullptr ); CPPUNIT_CHECK( pVal->first == nKey); } - CPPUNIT_ASSERT( m.extract( ep, nKey )); + ep = m.extract( nKey ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->first == nKey); - ep.release(); + //ep.release(); - CPPUNIT_ASSERT( !m.extract( ep, nKey )); + ep = m.extract( nKey ); + CPPUNIT_ASSERT( !ep ); CPPUNIT_ASSERT( ep.empty()); { typename map_type::rcu_lock l; @@ -534,12 +540,14 @@ namespace tree { CPPUNIT_ASSERT( pVal != nullptr ); CPPUNIT_CHECK( pVal->first == nKey); } - CPPUNIT_ASSERT( m.extract_with( ep, wrapped_int(nKey), wrapped_less() )); + ep = m.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->first == nKey); - ep.release(); + //ep.release(); - CPPUNIT_ASSERT( !m.extract_with( ep, wrapped_int(nKey), wrapped_less() )); + ep = m.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( !ep ); CPPUNIT_ASSERT( ep.empty()); { typename map_type::rcu_lock l; diff --git a/tests/test-hdr/tree/hdr_ellenbintree_set.h b/tests/test-hdr/tree/hdr_ellenbintree_set.h index 91065a09..12dc8606 100644 --- a/tests/test-hdr/tree/hdr_ellenbintree_set.h +++ b/tests/test-hdr/tree/hdr_ellenbintree_set.h @@ -580,24 +580,28 @@ namespace tree { int i = 0; value_type v; while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_min( ep ) ); + ep = s.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == i ); ++i; - ep.release(); + //ep.release(); } + ep.release(); CPPUNIT_ASSERT( s.empty() ); CPPUNIT_ASSERT( check_size( s, 0 )); fill_set( s, arr ); i = (int) c_nItemCount - 1; while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_max( ep ) ); + ep = s.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == i ); --i; - ep.release(); + //ep.release(); } + ep.release(); CPPUNIT_ASSERT( s.empty() ); CPPUNIT_ASSERT( check_size( s, 0 )); @@ -610,16 +614,17 @@ namespace tree { CPPUNIT_ASSERT( p != nullptr ); CPPUNIT_CHECK( p->nKey == nKey ); } - CPPUNIT_ASSERT( s.extract( ep, nKey )); + ep = s.extract( nKey ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == nKey); - ep.release(); + //ep.release(); { typename set_type::rcu_lock l; CPPUNIT_CHECK( s.get( nKey ) == nullptr ); } - CPPUNIT_CHECK( !s.extract( ep, nKey )); + ep = s.extract( nKey ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_ASSERT( s.empty() ); CPPUNIT_ASSERT( check_size( s, 0 )); @@ -633,16 +638,18 @@ namespace tree { CPPUNIT_ASSERT( p != nullptr ); CPPUNIT_CHECK( p->nKey == nKey ); } - CPPUNIT_ASSERT( s.extract_with( ep, wrapped_int(nKey), wrapped_less() )); + ep = s.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == nKey); - ep.release(); + //ep.release(); { typename set_type::rcu_lock l; CPPUNIT_CHECK( s.get_with( wrapped_int( nKey ), wrapped_less() ) == nullptr ); } - CPPUNIT_CHECK( !s.extract_with( ep, wrapped_int(nKey), wrapped_less() )); + ep = s.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_ASSERT( s.empty() ); CPPUNIT_ASSERT( check_size( s, 0 )); diff --git a/tests/test-hdr/tree/hdr_intrusive_bintree.h b/tests/test-hdr/tree/hdr_intrusive_bintree.h index af3424ba..f048f42f 100644 --- a/tests/test-hdr/tree/hdr_intrusive_bintree.h +++ b/tests/test-hdr/tree/hdr_intrusive_bintree.h @@ -841,7 +841,7 @@ namespace tree { CPPUNIT_ASSERT( pVal != nullptr ); CPPUNIT_CHECK( pVal == &v1 ); } - CPPUNIT_ASSERT( t.extract( ep, v1.nKey )); + ep = t.extract( v1.nKey ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == v1.nKey ); { @@ -849,18 +849,22 @@ namespace tree { CPPUNIT_CHECK( t.get( v1.nKey ) == nullptr ); } ep.release(); - CPPUNIT_ASSERT( !t.extract( ep, v1.nKey )); + ep = t.extract( v1.nKey ); + CPPUNIT_ASSERT( ep.empty()); - CPPUNIT_ASSERT( t.extract_min(ep)); + ep = t.extract_min(); + CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == v5.nKey ); { typename tree_type::rcu_lock l; CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr ); } - ep.release(); - CPPUNIT_ASSERT( !t.extract( ep, v5.nKey )); - CPPUNIT_ASSERT( t.extract_max(ep)); + ep = t.extract( v5.nKey ); + CPPUNIT_ASSERT( ep.empty() ); + + ep = t.extract_max(); + CPPUNIT_ASSERT( ep.empty()); CPPUNIT_CHECK( ep->nKey == v3.nKey ); { typename tree_type::rcu_lock l; @@ -874,19 +878,19 @@ namespace tree { CPPUNIT_ASSERT( pVal != nullptr ); CPPUNIT_CHECK( pVal == &v2 ); } - CPPUNIT_ASSERT( t.extract_with( ep, wrapped_int(v2.nKey), wrapped_less() )); - CPPUNIT_ASSERT( !ep.empty()); + ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less() ); + CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == v2.nKey ); { typename tree_type::rcu_lock l; CPPUNIT_CHECK( t.get_with( wrapped_int( v2.nKey ), wrapped_less() ) == nullptr ); } - ep.release(); - CPPUNIT_CHECK( !t.extract_with( ep, wrapped_int(v2.nKey), wrapped_less() )); + //ep.release(); + ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less() ); CPPUNIT_CHECK( ep.empty()); - CPPUNIT_ASSERT( t.extract( ep, v4.nKey )); - CPPUNIT_ASSERT( !ep.empty()); + ep = t.extract( v4.nKey ); + CPPUNIT_ASSERT( ep ); CPPUNIT_CHECK( ep->nKey == v4.nKey ); ep.release(); @@ -904,11 +908,11 @@ namespace tree { CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr ); } - CPPUNIT_CHECK( !t.extract(ep, v1.nKey)); - CPPUNIT_CHECK( !t.extract(ep, v2.nKey)); - CPPUNIT_CHECK( !t.extract(ep, v3.nKey)); - CPPUNIT_CHECK( !t.extract(ep, v4.nKey)); - CPPUNIT_CHECK( !t.extract(ep, v5.nKey)); + CPPUNIT_CHECK( !t.extract(v1.nKey)); + CPPUNIT_CHECK( !t.extract(v2.nKey)); + CPPUNIT_CHECK( !t.extract(v3.nKey)); + CPPUNIT_CHECK( !t.extract(v4.nKey)); + CPPUNIT_CHECK( !t.extract(v5.nKey)); tree_type::gc::force_dispose(); } -- 2.34.1