From 4c813fdf503db098d4e782513823de62501e5c08 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 13 Nov 2014 15:13:48 +0300 Subject: [PATCH] movable exempt_ptr: SkipList --- cds/container/skip_list_map_rcu.h | 49 +++-- cds/container/skip_list_set_rcu.h | 50 ++--- cds/intrusive/skip_list_rcu.h | 191 +++++++----------- tests/test-hdr/map/hdr_skiplist_map_rcu.h | 28 +-- .../set/hdr_intrusive_skiplist_set_rcu.h | 46 +++-- tests/test-hdr/set/hdr_skiplist_set_rcu.h | 27 +-- tests/unit/map2/map_delodd.cpp | 21 +- tests/unit/set2/set_delodd.cpp | 12 +- tests/unit/set2/set_insdel_string.cpp | 20 +- 9 files changed, 215 insertions(+), 229 deletions(-) diff --git a/cds/container/skip_list_map_rcu.h b/cds/container/skip_list_map_rcu.h index 25087d94..129e85f1 100644 --- a/cds/container/skip_list_map_rcu.h +++ b/cds/container/skip_list_map_rcu.h @@ -138,7 +138,7 @@ namespace cds { namespace container { static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; /// pointer to extracted node - typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr; + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >; protected: //@cond @@ -408,8 +408,8 @@ namespace cds { namespace container { /// Extracts the item from the map with specified \p key /** \anchor cds_nonintrusive_SkipListMap_rcu_extract The function searches an item with key equal to \p key in the map, - unlinks it from the set, and returns it in \p result parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item is not found the function returns an empty \p exempt_ptr Note the compare functor from \p Traits class' template argument should accept a parameter of type \p K that can be not the same as \p key_type. @@ -417,14 +417,13 @@ namespace cds { namespace container { RCU \p synchronize() method can be called. RCU should NOT be locked. The function does not free the item found. - The item will be implicitly freed 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 item will be implicitly freed when the returned object is destroyed or when + its \p release() member function is called. */ template - bool extract( exempt_ptr& result, K const& key ) + exempt_ptr extract( K const& key ) { - return base_class::do_extract( result, key ); + return exempt_ptr( base_class::do_extract( key )); } /// Extracts the item from the map with comparing functor \p pred @@ -435,43 +434,43 @@ 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, K const& key, Less pred ) + exempt_ptr extract_with( K const& key, Less pred ) { - return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()); + return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >())); } /// Extracts an item with minimal key from the map /** - The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter. - If the skip-list 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 item. + If the skip-list is empty the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item found. - The item will be implicitly freed 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 item will be implicitly freed 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::do_extract_min(result); + return exempt_ptr( base_class::do_extract_min()); } /// Extracts an item with maximal key from the map /** - The function searches an item with maximal key, unlinks it from the set, and returns the item found - in \p result parameter. If the skip-list is empty the function returns \p false. + The function searches an item with maximal key, unlinks it from the set, + and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item. + If the skip-list is empty the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. The function does not free the item found. - The item will be implicitly freed 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. - */ - bool extract_max( exempt_ptr& result ) + The item will be implicitly freed when the returned object is destroyed or when + its \p release() member function is called. + */ + exempt_ptr extract_max() { - return base_class::do_extract_max(result); + return exempt_ptr( base_class::do_extract_max()); } /// Find the key \p key diff --git a/cds/container/skip_list_set_rcu.h b/cds/container/skip_list_set_rcu.h index 82b7b838..e0c15e2b 100644 --- a/cds/container/skip_list_set_rcu.h +++ b/cds/container/skip_list_set_rcu.h @@ -185,7 +185,7 @@ namespace cds { namespace container { static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; /// pointer to extracted node - typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer > exempt_ptr; + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; protected: //@cond @@ -441,22 +441,22 @@ namespace cds { namespace container { /// Extracts the item from the set with specified \p key /** \anchor cds_nonintrusive_SkipListSet_rcu_extract The function searches an item with key equal to \p key in the set, - unlinks it from the set, and returns it in \p result parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item is not found the function returns an empty \p exempt_ptr Note the compare functor from \p Traits class' template argument should accept a parameter of type \p Q that can be not the same as \p value_type. RCU \p synchronize method can be called. RCU should NOT be locked. + The function does not free the item found. - The item will be implicitly freed when \p result object is destroyed or when - result.release() is called, see \p cds::urcu::exempt_ptr for explanation. - @note Before reusing \p result object you should call its \p release() method. + The item will be implicitly freed 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::do_extract( result, key ); + return exempt_ptr( base_class::do_extract( key )); } /// Extracts the item from the set with comparing functor \p pred @@ -467,41 +467,43 @@ 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& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()); + return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >())); } /// Extracts an item with minimal key from the set /** - The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter. - If the skip-list 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 item. + If the skip-list is empty the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. + The function does not free the item found. - The item will be implicitly freed 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 item will be implicitly freed 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::do_extract_min(result); + return exempt_ptr( base_class::do_extract_min()); } /// Extracts an item with maximal key from the set /** - The function searches an item with maximal key, unlinks it from the set, and returns the item found - in \p result parameter. If the skip-list is empty the function returns \p false. + The function searches an item with maximal key, unlinks it from the set, + and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item. + If the skip-list is empty the function returns an empty \p exempt_ptr. RCU \p synchronize method can be called. RCU should NOT be locked. + The function does not free the item found. - The item will be implicitly freed 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 item will be implicitly freed 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::do_extract_max(result); + return exempt_ptr( base_class::do_extract_max()); } /// Find the key \p val diff --git a/cds/intrusive/skip_list_rcu.h b/cds/intrusive/skip_list_rcu.h index 3b9bb82d..d8223573 100644 --- a/cds/intrusive/skip_list_rcu.h +++ b/cds/intrusive/skip_list_rcu.h @@ -614,7 +614,7 @@ namespace cds { namespace intrusive { //@endcond public: - typedef cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void > exempt_ptr; ///< pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void >; ///< pointer to extracted node protected: //@cond @@ -1133,136 +1133,105 @@ retry: return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } - template - bool do_extract( ExemptPtr& result, Q const& key ) + template + value_type * do_extract( Q const& key ) { check_deadlock_policy::check(); - - bool bReturn; + value_type * pDel = nullptr; { rcu_lock l; - value_type * pDel = do_extract_key( key, key_comparator() ); - bReturn = pDel != nullptr; - if ( bReturn ) - result = pDel; + pDel = do_extract_key( key, key_comparator() ); } dispose_deferred(); - return bReturn; + return pDel; } - template - bool do_extract_with( ExemptPtr& result, Q const& key, Less pred ) + template + value_type * do_extract_with( Q const& key, Less pred ) { check_deadlock_policy::check(); + value_type * pDel = nullptr; - bool bReturn; { rcu_lock l; - value_type * pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less() ); - bReturn = pDel != nullptr; - if ( bReturn ) - result = pDel; + pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less() ); } dispose_deferred(); - return bReturn; + return pDel; } - node_type * do_extract_min() + value_type * do_extract_min() { - assert( gc::is_locked() ); + assert( !gc::is_locked() ); position pos; node_type * pDel; - if ( !find_min_position( pos ) ) { - m_Stat.onExtractMinFailed(); - pDel = nullptr; - } - else { - pDel = pos.pCur; - unsigned int const nHeight = pDel->height(); + { + rcu_lock l; - if ( try_remove_at( pDel, pos, [](value_type const&) {}, true )) { - --m_ItemCounter; - m_Stat.onRemoveNode( nHeight ); - m_Stat.onExtractMinSuccess(); - } - else { + if ( !find_min_position( pos ) ) { m_Stat.onExtractMinFailed(); pDel = nullptr; } - } - - defer_chain( pos ); - return pDel; - } + else { + pDel = pos.pCur; + unsigned int const nHeight = pDel->height(); - template - bool do_extract_min( ExemptPtr& result ) - { - check_deadlock_policy::check(); + if ( try_remove_at( pDel, pos, []( value_type const& ) {}, true ) ) { + --m_ItemCounter; + m_Stat.onRemoveNode( nHeight ); + m_Stat.onExtractMinSuccess(); + } + else { + m_Stat.onExtractMinFailed(); + pDel = nullptr; + } + } - bool bReturn; - { - rcu_lock l; - node_type * pDel = do_extract_min(); - bReturn = pDel != nullptr; - if ( bReturn ) - result = node_traits::to_value_ptr(pDel); + defer_chain( pos ); } dispose_deferred(); - return bReturn; + return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } - node_type * do_extract_max() + value_type * do_extract_max() { - assert( gc::is_locked() ); + assert( !gc::is_locked() ); position pos; node_type * pDel; - if ( !find_max_position( pos ) ) { - m_Stat.onExtractMaxFailed(); - pDel = nullptr; - } - else { - pDel = pos.pCur; - unsigned int const nHeight = pDel->height(); + { + rcu_lock l; - if ( try_remove_at( pDel, pos, [](value_type const&) {}, true )) { - --m_ItemCounter; - m_Stat.onRemoveNode( nHeight ); - m_Stat.onExtractMaxSuccess(); - } - else { + if ( !find_max_position( pos ) ) { m_Stat.onExtractMaxFailed(); pDel = nullptr; } - } - - defer_chain( pos ); - return pDel; - } + else { + pDel = pos.pCur; + unsigned int const nHeight = pDel->height(); - template - bool do_extract_max( ExemptPtr& result ) - { - check_deadlock_policy::check(); + if ( try_remove_at( pDel, pos, []( value_type const& ) {}, true ) ) { + --m_ItemCounter; + m_Stat.onRemoveNode( nHeight ); + m_Stat.onExtractMaxSuccess(); + } + else { + m_Stat.onExtractMaxFailed(); + pDel = nullptr; + } + } - bool bReturn; - { - rcu_lock l; - node_type * pDel = do_extract_max(); - bReturn = pDel != nullptr; - if ( bReturn ) - result = node_traits::to_value_ptr(pDel); + defer_chain( pos ); } dispose_deferred(); - return bReturn; + return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } void increase_height( unsigned int nHeight ) @@ -1645,24 +1614,23 @@ retry: /// Extracts the item from the set with specified \p key /** \anchor cds_intrusive_SkipListSet_rcu_extract The function searches an item with key equal to \p key in the set, - unlinks it from the set, places it to \p result parameter, and returns \p true. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. 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. Example: \code typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list; skip_list theList; // ... - typename skip_list::exempt_ptr ep; - if ( theList.extract( ep, 5 ) ) { + typename skip_list::exempt_ptr ep( theList.extract( 5 )); + if ( ep ) { // Deal with ep //... @@ -1672,9 +1640,9 @@ retry: \endcode */ template - bool extract( exempt_ptr& result, Q const& key ) + exempt_ptr extract( Q const& key ) { - return do_extract( result, key ); + return exempt_ptr( do_extract( key )); } /// Extracts the item from the set with comparing functor \p pred @@ -1685,29 +1653,28 @@ retry: \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& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - return do_extract_with( result, key, pred ); + return exempt_ptr( do_extract_with( key, pred )); } /// Extracts an item with minimal key from the list /** - The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter. - If the skip-list 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 item. + If the skip-list is empty the function returns an 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 manually called. Example: \code typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list; skip_list theList; // ... - typename skip_list::exempt_ptr ep; - if ( theList.extract_min(ep)) { + typename skip_list::exempt_ptr ep(theList.extract_min()); + if ( ep ) { // Deal with ep //... @@ -1721,29 +1688,28 @@ retry: During unlinking, a concurrent thread may insert an item with key less than leftmost item's key. So, the function returns the item with minimum key at the moment of list traversing. */ - bool extract_min( exempt_ptr& result ) + exempt_ptr extract_min() { - return do_extract_min( result ); + return exempt_ptr( do_extract_min()); } /// Extracts an item with maximal key from the list /** - The function searches an item with maximal key, unlinks it, and returns the item found in \p result parameter. - If the skip-list 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 item. + If the skip-list is empty the function returns an 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 manually called. Example: \code typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list; skip_list theList; // ... - typename skip_list::exempt_ptr ep; - if ( theList.extract_max(ep) ) { + typename skip_list::exempt_ptr ep( theList.extract_max() ); + if ( ep ) { // Deal with ep //... // Dispose returned item. @@ -1756,9 +1722,9 @@ retry: During unlinking, a concurrent thread can insert an item with key greater than rightmost item's key. So, the function returns the item with maximum key at the moment of list traversing. */ - bool extract_max( exempt_ptr& result ) + exempt_ptr extract_max() { - return do_extract_max( result ); + return exempt_ptr( do_extract_max()); } /// Deletes the item from the set @@ -1990,8 +1956,7 @@ retry: void clear() { exempt_ptr ep; - while ( extract_min(ep) ) - ep.release(); + while ( (ep = extract_min()) ); } /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32. diff --git a/tests/test-hdr/map/hdr_skiplist_map_rcu.h b/tests/test-hdr/map/hdr_skiplist_map_rcu.h index f4cd7b51..c3a5d436 100644 --- a/tests/test-hdr/map/hdr_skiplist_map_rcu.h +++ b/tests/test-hdr/map/hdr_skiplist_map_rcu.h @@ -174,17 +174,18 @@ namespace map { CPPUNIT_CHECK( pVal->second.m_val == nKey * 2 ); } - CPPUNIT_ASSERT( m.extract( ep, nKey )); + ep = m.extract( nKey ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == nKey ); CPPUNIT_CHECK( ep->second.m_val == nKey * 2 ); - ep.release(); { rcu_lock l; CPPUNIT_CHECK( m.get( nKey ) == nullptr ); } - CPPUNIT_CHECK( !m.extract(ep, nKey) ); + ep = m.extract( nKey ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_ASSERT( m.empty() ); @@ -202,17 +203,18 @@ namespace map { CPPUNIT_CHECK( pVal->second.m_val == nKey * 2 ); } - CPPUNIT_ASSERT( m.extract_with( ep, wrapped_item(nKey), wrapped_less() )); + ep = m.extract_with( wrapped_item( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == nKey ); CPPUNIT_CHECK( ep->second.m_val == nKey * 2 ); - ep.release(); { rcu_lock l; CPPUNIT_CHECK( m.get_with( wrapped_item(nKey), wrapped_less() ) == nullptr ); } - CPPUNIT_CHECK( !m.extract_with(ep, wrapped_item(nKey), wrapped_less()) ); + ep = m.extract_with( wrapped_item( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_ASSERT( m.empty() ); @@ -220,27 +222,29 @@ namespace map { for ( int i = 0; i < nLimit; ++i ) CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) ); for ( int i = 0; i < nLimit; ++i ) { - CPPUNIT_ASSERT( m.extract_min(ep)); + ep = m.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == i ); CPPUNIT_CHECK( ep->second.m_val == i * 2 ); - ep.release(); } CPPUNIT_ASSERT( m.empty() ); - CPPUNIT_CHECK( !m.extract_min(ep) ); + ep = m.extract_min(); + CPPUNIT_CHECK( !ep ); // extract_max for ( int i = 0; i < nLimit; ++i ) CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) ); for ( int i = nLimit-1; i >= 0; --i ) { - CPPUNIT_ASSERT( m.extract_max(ep)); + ep = m.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == i ); CPPUNIT_CHECK( ep->second.m_val == i * 2 ); - ep.release(); } CPPUNIT_ASSERT( m.empty() ); - CPPUNIT_CHECK( !m.extract_max(ep) ); + ep = m.extract_max(); + CPPUNIT_CHECK( !ep ); } CPPUNIT_MSG( PrintStat()(m, nullptr) ); diff --git a/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h b/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h index 973cea29..cd7d0ffd 100644 --- a/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h +++ b/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h @@ -268,17 +268,19 @@ namespace set { pVal->nVal *= 2; } - CPPUNIT_ASSERT( s.extract( ep, i )); + ep = s.extract( i ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == i ); CPPUNIT_CHECK( ep->nVal == i * 4 ); - ep.release(); + //ep.release(); { rcu_lock l; CPPUNIT_CHECK( s.get( i ) == nullptr ); } - CPPUNIT_CHECK( !s.extract( ep, i ) ); + ep = s.extract( i ); + CPPUNIT_CHECK( !ep ); CPPUNIT_ASSERT( ep.empty() ); } CPPUNIT_CHECK( s.empty() ); @@ -298,17 +300,19 @@ namespace set { pVal->nVal *= 2; } - CPPUNIT_ASSERT( s.extract_with( ep, other_key(i), other_key_less() )); + ep = s.extract_with( other_key( i ), other_key_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == i ); CPPUNIT_CHECK( ep->nVal == i * 4 ); - ep.release(); + //ep.release(); { rcu_lock l; CPPUNIT_CHECK( s.get_with( other_key( i ), other_key_less() ) == nullptr ); } - CPPUNIT_CHECK( !s.extract_with( ep, other_key(i), other_key_less() )); + ep = s.extract_with( other_key( i ), other_key_less() ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_CHECK( s.empty() ); } @@ -319,21 +323,24 @@ namespace set { fill_skiplist( s, v ); int nPrevKey; - CPPUNIT_ASSERT( s.extract_min(ep)); + ep = s.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); nPrevKey = ep->nKey; - ep.release(); + //ep.release(); while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_min(ep) ); + ep = s.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == nPrevKey + 1 ); CPPUNIT_CHECK( ep->nVal == (nPrevKey + 1) * 2 ); nPrevKey = ep->nKey; - ep.release(); + //ep.release(); } - CPPUNIT_CHECK( !s.extract_min(ep) ); - CPPUNIT_CHECK( !s.extract_max(ep) ); + ep = s.extract_min(); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( !s.extract_max() ); } Set::gc::force_dispose(); @@ -342,23 +349,26 @@ namespace set { fill_skiplist( s, v ); int nPrevKey; - CPPUNIT_ASSERT( s.extract_max(ep)); + ep = s.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); nPrevKey = ep->nKey; - ep.release(); + //ep.release(); while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_max(ep)); + ep = s.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty()); CPPUNIT_CHECK( ep->nKey == nPrevKey - 1 ); CPPUNIT_CHECK( ep->nVal == (nPrevKey - 1) * 2 ); nPrevKey = ep->nKey; - ep.release(); + //ep.release(); } + ep = s.extract_min(); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( !s.extract_max() ); } Set::gc::force_dispose(); - CPPUNIT_CHECK( !s.extract_min(ep) ); - CPPUNIT_CHECK( !s.extract_max(ep) ); } CPPUNIT_MSG( PrintStat()(s, nullptr) ); diff --git a/tests/test-hdr/set/hdr_skiplist_set_rcu.h b/tests/test-hdr/set/hdr_skiplist_set_rcu.h index ff99ebdb..ad10c40d 100644 --- a/tests/test-hdr/set/hdr_skiplist_set_rcu.h +++ b/tests/test-hdr/set/hdr_skiplist_set_rcu.h @@ -168,17 +168,18 @@ namespace set { CPPUNIT_CHECK( pVal->nVal == nKey * 2 ); } - CPPUNIT_ASSERT( s.extract( ep, nKey )); + ep = s.extract( nKey ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == nKey ); CPPUNIT_CHECK( ep->nVal == nKey * 2 ); - ep.release(); { rcu_lock l; CPPUNIT_CHECK( s.get( nKey ) == nullptr ); } - CPPUNIT_CHECK( !s.extract( ep, nKey )); + ep = s.extract( nKey ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_CHECK( s.empty()); @@ -196,17 +197,18 @@ namespace set { CPPUNIT_CHECK( pVal->nVal == nKey ); } - CPPUNIT_ASSERT( s.extract_with( ep, wrapped_item(nKey), wrapped_less() )); + ep = s.extract_with( wrapped_item( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == nKey ); CPPUNIT_CHECK( ep->nVal == nKey ); - ep.release(); { rcu_lock l; CPPUNIT_CHECK( s.get_with( wrapped_item( nKey ), wrapped_less() ) == nullptr ); } - CPPUNIT_CHECK( !s.extract_with( ep, wrapped_item(nKey), wrapped_less() )); + ep = s.extract_with( wrapped_item( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !ep ); } CPPUNIT_CHECK( s.empty()); @@ -215,12 +217,12 @@ namespace set { CPPUNIT_ASSERT( s.insert( arrRandom[i]) ); for ( int i = 0; i < nLimit; ++i ) { - CPPUNIT_ASSERT( s.extract_min(ep) ); + ep = s.extract_min(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == i ); CPPUNIT_CHECK( ep->nVal == i ); CPPUNIT_CHECK( !s.find(i) ); - ep.release(); } CPPUNIT_CHECK( s.empty()); @@ -229,16 +231,17 @@ namespace set { CPPUNIT_ASSERT( s.insert( arrRandom[i]) ); for ( int i = nLimit-1; i >= 0; --i ) { - CPPUNIT_ASSERT( s.extract_max(ep) ); + ep = s.extract_max(); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->nKey == i ); CPPUNIT_CHECK( ep->nVal == i ); CPPUNIT_CHECK( !s.find(i) ); - ep.release(); } CPPUNIT_CHECK( s.empty()); - CPPUNIT_CHECK( !s.extract_min(ep) ); - CPPUNIT_CHECK( !s.extract_max(ep) ); + ep = s.extract_min(); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( !s.extract_max() ); } CPPUNIT_MSG( PrintStat()(s, nullptr) ); diff --git a/tests/unit/map2/map_delodd.cpp b/tests/unit/map2/map_delodd.cpp index 4eb1512d..e450051f 100644 --- a/tests/unit/map2/map_delodd.cpp +++ b/tests/unit/map2/map_delodd.cpp @@ -435,22 +435,21 @@ namespace map2 { if ( Map::c_bExtractLockExternal ) { { typename Map::rcu_lock l; - if ( rMap.extract_with( xp, arrData[i], key_less() )) { + xp = rMap.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nDeleteSuccess; - } else ++m_nDeleteFailed; } - xp.release(); } else { - if ( rMap.extract_with( xp, arrData[i], key_less() )) { + xp = rMap.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nDeleteSuccess; - xp.release(); - } else ++m_nDeleteFailed; } + xp.release(); } } if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) @@ -464,21 +463,21 @@ namespace map2 { if ( Map::c_bExtractLockExternal ) { { typename Map::rcu_lock l; - if ( rMap.extract_with( xp, arrData[i], key_less() )) + xp = rMap.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nDeleteSuccess; else ++m_nDeleteFailed; } - xp.release(); } else { - if ( rMap.extract_with( xp, arrData[i], key_less() )) { + xp = rMap.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nDeleteSuccess; - xp.release(); - } else ++m_nDeleteFailed; } + xp.release(); } } if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) diff --git a/tests/unit/set2/set_delodd.cpp b/tests/unit/set2/set_delodd.cpp index 29782a66..82bc58ee 100644 --- a/tests/unit/set2/set_delodd.cpp +++ b/tests/unit/set2/set_delodd.cpp @@ -475,13 +475,15 @@ namespace set2 { if ( arrData[i] & 1 ) { if ( Set::c_bExtractLockExternal ) { typename Set::rcu_lock l; - if ( rSet.extract_with( xp, arrData[i], key_less() )) + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; } else { - if ( rSet.extract_with( xp, arrData[i], key_less() )) + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; @@ -499,13 +501,15 @@ namespace set2 { if ( arrData[i] & 1 ) { if ( Set::c_bExtractLockExternal ) { typename Set::rcu_lock l; - if ( rSet.extract_with( xp, arrData[i], key_less() )) + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; } else { - if ( rSet.extract_with( xp, arrData[i], key_less() )) + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; diff --git a/tests/unit/set2/set_insdel_string.cpp b/tests/unit/set2/set_insdel_string.cpp index 4b117918..3f5ffcdd 100644 --- a/tests/unit/set2/set_insdel_string.cpp +++ b/tests/unit/set2/set_insdel_string.cpp @@ -272,21 +272,21 @@ namespace set2 { if ( Set::c_bExtractLockExternal ) { { typename Set::rcu_lock l; - if ( rSet.extract( xp, arrString[nItem % nArrSize] ) ) + xp = rSet.extract( arrString[nItem % nArrSize] ); + if ( xp ) ++m_nDeleteSuccess; else ++m_nDeleteFailed; } - xp.release(); } else { - if ( rSet.extract( xp, arrString[nItem % nArrSize] ) ) { + xp = rSet.extract( arrString[nItem % nArrSize] ); + if ( xp ) ++m_nDeleteSuccess; - xp.release(); - } else ++m_nDeleteFailed; } + xp.release(); } } } @@ -296,21 +296,21 @@ namespace set2 { if ( Set::c_bExtractLockExternal ) { { typename Set::rcu_lock l; - if ( rSet.extract( xp, arrString[nItem % nArrSize] ) ) + xp = rSet.extract( arrString[nItem % nArrSize] ); + if ( xp ) ++m_nDeleteSuccess; else ++m_nDeleteFailed; } - xp.release(); } else { - if ( rSet.extract( xp, arrString[nItem % nArrSize] ) ) { + xp = rSet.extract( arrString[nItem % nArrSize] ); + if ( xp ) ++m_nDeleteSuccess; - xp.release(); - } else ++m_nDeleteFailed; } + xp.release(); } } } -- 2.34.1