From 5164ba5bd61a581d54cea6a6bfab51407757b1b3 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 12 Nov 2014 16:05:06 +0300 Subject: [PATCH] movable exempt_ptr: LazyList --- cds/container/lazy_kvlist_rcu.h | 23 ++++++----- cds/container/lazy_list_rcu.h | 19 +++++---- cds/intrusive/lazy_list_rcu.h | 39 ++++++++++++------- .../ordered_list/hdr_intrusive_lazy.h | 16 +++++--- tests/test-hdr/ordered_list/hdr_lazy.h | 17 ++++---- tests/test-hdr/ordered_list/hdr_lazy_kv.h | 18 +++++---- 6 files changed, 77 insertions(+), 55 deletions(-) diff --git a/cds/container/lazy_kvlist_rcu.h b/cds/container/lazy_kvlist_rcu.h index b460c6d6..caae0c70 100644 --- a/cds/container/lazy_kvlist_rcu.h +++ b/cds/container/lazy_kvlist_rcu.h @@ -121,9 +121,9 @@ namespace cds { namespace container { public: /// pointer to extracted node - typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer, + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer, cds::urcu::details::conventional_exempt_pair_cast - > exempt_ptr; + >; protected: //@cond @@ -513,13 +513,13 @@ namespace cds { namespace container { /** @anchor cds_nonintrusive_LazyKVList_rcu_extract The function searches an item with key equal to \p key in the list, - unlinks it from the list, and returns pointer to an item found in \p dest argument. - If \p key is not found the function returns \p false. + 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. + You should manually lock RCU before calling this function. \code #include @@ -538,7 +538,8 @@ namespace cds { namespace container { // Now, you can apply extract function // Note that you must not delete the item found inside the RCU lock - if ( theList.extract( p, 10 )) { + p = theList.extract( 10 ); + if ( !p ) { // do something with p ... } @@ -549,10 +550,9 @@ namespace cds { namespace container { \endcode */ template - bool extract( exempt_ptr& dest, K const& key ) + exempt_ptr extract( K const& key ) { - dest = extract_at( head(), key, intrusive_key_comparator() ); - return !dest.empty(); + return exempt_ptr( extract_at( head(), key, intrusive_key_comparator())); } /// Extracts an item from the list using \p pred predicate for searching @@ -563,10 +563,9 @@ namespace cds { namespace container { \p pred must imply the same element order as \ref key_comparator. */ template - bool extract_with( exempt_ptr& dest, K const& key, Less pred ) + exempt_ptr extract_with( K const& key, Less pred ) { - dest = extract_at( head(), key, typename maker::template less_wrapper::type() ); - return !dest.empty(); + return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type() )); } /// Finds the key \p key diff --git a/cds/container/lazy_list_rcu.h b/cds/container/lazy_list_rcu.h index 0d834427..1b0fb60e 100644 --- a/cds/container/lazy_list_rcu.h +++ b/cds/container/lazy_list_rcu.h @@ -129,7 +129,7 @@ namespace cds { namespace container { //@endcond public: - typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer > exempt_ptr; ///< pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; ///< pointer to extracted node private: //@cond @@ -490,8 +490,8 @@ namespace cds { namespace container { /** @anchor cds_nonintrusive_LazyList_rcu_extract The function searches an item with key equal to \p key in the list, - unlinks it from the list, and returns pointer to an item found in \p dest argument. - If the item with the key equal to \p key is not found the function returns \p false. + unlinks it from the list, 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 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 @@ -515,7 +515,8 @@ namespace cds { namespace container { // Now, you can apply extract function // Note that you must not delete the item found inside the RCU lock - if ( theList.extract( p, 10 )) { + p = theList.extract( 10 ); + if ( p ) { // do something with p ... } @@ -526,10 +527,9 @@ namespace cds { namespace container { \endcode */ template - bool extract( exempt_ptr& dest, Q const& key ) + exempt_ptr extract( Q const& key ) { - dest = extract_at( head(), key, intrusive_key_comparator() ); - return !dest.empty(); + return exempt_ptr(extract_at( head(), key, intrusive_key_comparator())); } /// Extracts an item from the list using \p pred predicate for searching @@ -541,10 +541,9 @@ namespace cds { namespace container { \p pred must imply the same element order as \ref key_comparator. */ template - bool extract_with( exempt_ptr& dest, Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - dest = extract_at( head(), key, typename maker::template less_wrapper::type() ); - return !dest.empty(); + return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type())); } /// Finds the key \p key diff --git a/cds/intrusive/lazy_list_rcu.h b/cds/intrusive/lazy_list_rcu.h index 38cae1d9..0d89f940 100644 --- a/cds/intrusive/lazy_list_rcu.h +++ b/cds/intrusive/lazy_list_rcu.h @@ -230,7 +230,8 @@ namespace cds { namespace intrusive { //@endcond public: - typedef cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void > exempt_ptr ; ///< pointer to extracted node + /// pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; protected: //@cond @@ -580,14 +581,13 @@ namespace cds { namespace intrusive { /** \anchor cds_intrusive_LazyList_rcu_extract The function searches an item with key equal to \p key in the list, - unlinks it from the list, and returns pointer to an item found in \p dest parameter. - If the item with the key equal to \p key is not found the function returns \p false, - \p dest is empty. + unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found. + If the item is not found the function returns 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, and you should manually synchronize RCU + and returns a pointer to it. + You should manually lock RCU before calling this function, and you should manually synchronize RCU outside the RCU lock region before reusing returned pointer. \code @@ -607,7 +607,8 @@ namespace cds { namespace intrusive { // Now, you can apply extract function // Note that you must not delete the item found inside the RCU lock - if ( theList.extract( p1, 10 )) { + p1 = theList.extract( 10 ) + if ( p1 ) { // do something with p1 ... } @@ -620,10 +621,9 @@ namespace cds { namespace intrusive { \endcode */ template - bool extract( exempt_ptr& dest, Q const& key ) + exempt_ptr extract( Q const& key ) { - dest = extract_at( &m_Head, key, key_comparator() ); - return !dest.empty(); + return exempt_ptr( extract_at( &m_Head, key, key_comparator() )); } /// Extracts an item from the list using \p pred predicate for searching @@ -635,10 +635,9 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as \ref key_comparator. */ template - bool extract_with( exempt_ptr& dest, Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - dest = extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less() ); - return !dest.empty(); + return exempt_ptr( extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less() )); } /// Finds the key \p key @@ -663,6 +662,13 @@ namespace cds { namespace intrusive { { return find_at( const_cast( &m_Head ), key, key_comparator(), f ); } + //@cond + template + bool find( Q const& key, Func f ) const + { + return find_at( const_cast(&m_Head), key, key_comparator(), f ); + } + //@endcond /// Finds the key \p key using \p pred predicate for searching /** @@ -676,6 +682,13 @@ namespace cds { namespace intrusive { { return find_at( const_cast( &m_Head ), key, cds::opt::details::make_comparator_from_less(), f ); } + //@cond + template + bool find_with( Q const& key, Less pred, Func f ) const + { + return find_at( const_cast(&m_Head), key, cds::opt::details::make_comparator_from_less(), f ); + } + //@endcond /// Finds the key \p key /** \anchor cds_intrusive_LazyList_rcu_find_val diff --git a/tests/test-hdr/ordered_list/hdr_intrusive_lazy.h b/tests/test-hdr/ordered_list/hdr_intrusive_lazy.h index 76198cd6..4d9a3b34 100644 --- a/tests/test-hdr/ordered_list/hdr_intrusive_lazy.h +++ b/tests/test-hdr/ordered_list/hdr_intrusive_lazy.h @@ -558,7 +558,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->nKey == a[i] ); CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract( ep, a[i] )); + 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 ); @@ -567,7 +568,7 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[i] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[i] ) ); + CPPUNIT_CHECK( !l.extract( a[i] ) ); CPPUNIT_CHECK( ep.empty() ); } } @@ -576,7 +577,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[0] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[0] )); + ep = l.extract( a[0] ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } // Apply retired pointer @@ -596,7 +598,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->nKey == a[i] ); CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract_with( ep, itm, other_less() ) ); + 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 ); @@ -605,7 +608,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, itm, other_less() )); + ep = l.extract_with( itm, other_less() ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } } @@ -614,7 +618,7 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, other_item(0), other_less() )); + CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); CPPUNIT_CHECK( ep.empty() ); } // Apply retired pointer diff --git a/tests/test-hdr/ordered_list/hdr_lazy.h b/tests/test-hdr/ordered_list/hdr_lazy.h index fef2592b..360b43c1 100644 --- a/tests/test-hdr/ordered_list/hdr_lazy.h +++ b/tests/test-hdr/ordered_list/hdr_lazy.h @@ -560,7 +560,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->nKey == a[i] ); CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract( ep, a[i] )); + 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 ); @@ -569,8 +570,7 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[i] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[i] )); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.extract( a[i] )); } } CPPUNIT_ASSERT( l.empty() ); @@ -578,7 +578,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[0] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[0] ) ); + ep = l.extract( a[0] ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } @@ -596,7 +597,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->nKey == a[i] ); CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract_with( ep, itm, other_less() )); + 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 ); @@ -605,7 +607,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, itm, other_less() )); + ep = l.extract_with( itm, other_less() ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } } @@ -614,7 +617,7 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, other_item(0), other_less() )); + CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); CPPUNIT_CHECK( ep.empty() ); } } diff --git a/tests/test-hdr/ordered_list/hdr_lazy_kv.h b/tests/test-hdr/ordered_list/hdr_lazy_kv.h index 1aef413f..5c6bbdb0 100644 --- a/tests/test-hdr/ordered_list/hdr_lazy_kv.h +++ b/tests/test-hdr/ordered_list/hdr_lazy_kv.h @@ -387,7 +387,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->first == a[i] ); CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract( ep, a[i] )); + ep = l.extract( a[i] ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == a[i] ); CPPUNIT_CHECK( (*ep).second.m_val == a[i] * 2 ); @@ -396,7 +397,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[i] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[i] )); + ep = l.extract( a[i] ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } } @@ -405,8 +407,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get( a[0] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( ep, a[0] ) ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.extract( a[0] ) ); + //CPPUNIT_CHECK( ep.empty() ); } // extract_with/get_with @@ -423,7 +425,8 @@ namespace ordlist { CPPUNIT_CHECK( pGet->first == a[i] ); CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 ); - CPPUNIT_ASSERT( l.extract_with( ep, itm, other_less() )); + ep = l.extract_with( itm, other_less() ); + CPPUNIT_ASSERT( ep ); CPPUNIT_ASSERT( !ep.empty() ); CPPUNIT_CHECK( ep->first == a[i] ); CPPUNIT_CHECK( ep->second.m_val == a[i] * 2 ); @@ -432,7 +435,8 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( itm, other_less()) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, itm, other_less() )); + ep = l.extract_with( itm, other_less() ); + CPPUNIT_CHECK( !ep ); CPPUNIT_CHECK( ep.empty() ); } } @@ -441,7 +445,7 @@ namespace ordlist { { rcu_lock lock; CPPUNIT_CHECK( l.get_with( 3.14f, other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( ep, 3.14f, other_less() )); + CPPUNIT_CHECK( !l.extract_with( 3.14f, other_less() )); CPPUNIT_CHECK( ep.empty() ); } } -- 2.34.1