From c193d140a834c07dbd629610de9bceda0428a2cd Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 17 Nov 2014 20:33:26 +0300 Subject: [PATCH] movable guarded_ptr: EllenBinTree --- cds/container/impl/ellen_bintree_map.h | 72 ++++++++++------- cds/container/impl/ellen_bintree_set.h | 70 +++++++++------- cds/gc/details/hp.h | 2 +- cds/gc/guarded_ptr.h | 59 ++++++++++---- cds/gc/impl/hp_decl.h | 2 +- cds/intrusive/impl/ellen_bintree.h | 81 +++++++++++-------- tests/test-hdr/tree/hdr_ellenbintree_map.h | 34 ++++---- tests/test-hdr/tree/hdr_ellenbintree_set.h | 32 ++++---- tests/test-hdr/tree/hdr_intrusive_bintree.h | 61 ++++++++------ ...hdr_intrusive_ellen_bintree_dhp_member.cpp | 2 +- .../tree/hdr_intrusive_ellen_bintree_hp.cpp | 2 +- 11 files changed, 252 insertions(+), 165 deletions(-) diff --git a/cds/container/impl/ellen_bintree_map.h b/cds/container/impl/ellen_bintree_map.h index 3187f55b..7f0b6451 100644 --- a/cds/container/impl/ellen_bintree_map.h +++ b/cds/container/impl/ellen_bintree_map.h @@ -318,70 +318,78 @@ 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 minimum value. - If the map is empty, the function returns \p false, \p result is left unchanged. + If the map is not empty, the function returns an guarded pointer to minimum value. + If the map is empty, the function returns an empty \p guarded_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. 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 tree traversing. - The guarded pointer \p result prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_min( guarded_ptr& result ) + guarded_ptr extract_min() { - return base_class::extract_min_( result.guard() ); + guarded_ptr gp; + base_class::extract_min_( gp.guard() ); + return gp; } /// 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 maximal value. - If the map is empty, the function returns \p false, \p result is left unchanged. + If the map is not empty, the function returns a guarded pointer to maximal value. + If the map is empty, the function returns an empty \p guarded_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. During unlinking, a concurrent thread may insert an item with key great than leftmost item's key. So, the function returns the item with maximum key at the moment of tree traversing. - The guarded pointer \p result prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_max( guarded_ptr& result ) + guarded_ptr extract_max() { - return base_class::extract_max_( result.guard() ); + guarded_ptr gp; + base_class::extract_max_( gp.guard() ); + return gp; } /// Extracts an item from the tree /** \anchor cds_nonintrusive_EllenBinTreeMap_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 is not found the function returns \p false. + unlinks it, and returns a guarded pointer to an item found. + If the item is not found the function returns an empty \p guarded_ptr. - The guarded pointer \p result prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool extract( guarded_ptr& result, Q const& key ) + guarded_ptr extract( Q const& key ) { - return base_class::extract_( result.guard(), key ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key ); + return gp; } /// Extracts an item from the map using \p pred for searching /** - The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(guarded_ptr&, Q const&)" + The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(Q const&)" but \p pred is used for key compare. \p Less has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( guarded_ptr& result, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { - return base_class::extract_with_( result.guard(), key, + guarded_ptr gp; + base_class::extract_with_( gp.guard(), key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >()); + return gp; } /// Find the key \p key @@ -447,31 +455,35 @@ namespace cds { namespace container { /// Finds \p key and returns the item found /** @anchor cds_nonintrusive_EllenBinTreeMap_get - The function searches the item with key equal to \p key and returns the item found in \p result parameter. - The function returns \p true if \p key is found, \p false otherwise. + The function searches the item with key equal to \p key and returns the item found as a guarded pointer. + If \p key is not foudn the function returns an empty \p guarded_ptr. - The guarded pointer \p result prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool get( guarded_ptr& result, Q const& key ) + guarded_ptr get( Q const& key ) { - return base_class::get_( result.guard(), key ); + guarded_ptr gp; + base_class::get_( gp.guard(), key ); + return gp; } /// Finds \p key with predicate \p pred and returns the item found /** - The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(guarded_ptr&, Q const&)" + The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(Q const&)" but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the map. */ template - bool get_with( guarded_ptr& result, Q const& key, Less pred ) + guarded_ptr get_with( Q const& key, Less pred ) { - return base_class::get_with_( result.guard(), key, + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() ); + return gp; } /// Clears the map (not atomic) diff --git a/cds/container/impl/ellen_bintree_set.h b/cds/container/impl/ellen_bintree_set.h index 432947ed..72c5f4ec 100644 --- a/cds/container/impl/ellen_bintree_set.h +++ b/cds/container/impl/ellen_bintree_set.h @@ -332,70 +332,78 @@ 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 minimum value. - If the set is empty, the function returns \p false, \p result is left unchanged. + If the set is not empty, the function returns a guarded pointer to minimum value. + If the set is empty, the function returns an empty \p guarded_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. 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 tree traversing. - The guarded pointer \p dest prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_min( guarded_ptr& result ) + guarded_ptr extract_min() { - return base_class::extract_min_( result.guard() ); + guarded_ptr gp; + base_class::extract_min_( gp.guard() ); + return gp; } /// 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 maximal value. - If the set is empty, the function returns \p false, \p result is left unchanged. + If the set is not empty, the function returns a guarded pointer to maximal value. + If the set is empty, the function returns an empty \p guarded_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. During unlinking, a concurrent thread may insert an item with key great than leftmost item's key. So, the function returns the item with maximum key at the moment of tree traversing. - The guarded pointer \p dest prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_max( guarded_ptr& result ) + guarded_ptr extract_max() { - return base_class::extract_max_( result.guard() ); + guarded_ptr gp; + base_class::extract_max_( gp.guard() ); + return gp; } /// Extracts an item from the tree /** \anchor cds_nonintrusive_EllenBinTreeSet_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 is not found the function returns \p false. + unlinks it, and returns an guarded pointer to it. + If the item is not found the function returns an empty \p guarded_ptr. - The guarded pointer \p dest prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool extract( guarded_ptr& result, Q const& key ) + guarded_ptr extract( Q const& key ) { - return base_class::extract_( result.guard(), key ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key ); + return gp; } /// Extracts an item from the set using \p pred for searching /** - The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(guarded_ptr& dest, Q const&)" + The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(Q const&)" but \p pred is used for key compare. \p Less has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the set. */ template - bool extract_with( guarded_ptr& result, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { - return base_class::extract_with_( result.guard(), key, + guarded_ptr gp; + base_class::extract_with_( gp.guard(), key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >()); + return gp; } /// Find the key \p key @@ -489,31 +497,35 @@ namespace cds { namespace container { /// Finds \p key and returns the item found /** @anchor cds_nonintrusive_EllenBinTreeSet_get - The function searches the item with key equal to \p key and returns the item found in \p result parameter. + The function searches the item with key equal to \p key and returns the item found as an guarded pointer. The function returns \p true if \p key is found, \p false otherwise. - The guarded pointer \p dest prevents deallocation of returned item, - see cds::gc::guarded_ptr for explanation. + The guarded pointer prevents deallocation of returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool get( guarded_ptr& result, Q const& key ) + guarded_ptr get( Q const& key ) { - return base_class::get_( result.guard(), key ); + guarded_ptr gp; + base_class::get_( gp.guard(), key ); + return gp; } /// Finds \p key with predicate \p pred and returns the item found /** - The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(guarded_ptr&, Q const&)" + The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(Q const&)" but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the set. */ template - bool get_with( guarded_ptr& result, Q const& key, Less pred ) + guarded_ptr get_with( Q const& key, Less pred ) { - return base_class::get_with_( result.guard(), key, + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() ); + return gp; } /// Clears the set (not atomic) diff --git a/cds/gc/details/hp.h b/cds/gc/details/hp.h index 9e191b09..ab475a3a 100644 --- a/cds/gc/details/hp.h +++ b/cds/gc/details/hp.h @@ -613,7 +613,7 @@ namespace cds { */ class guard { - details::hp_guard& m_hp ; ///< Hazard pointer guarded + details::hp_guard& m_hp ; ///< Hazard pointer guarded ThreadGC& m_gc ; ///< Thread GC public: diff --git a/cds/gc/guarded_ptr.h b/cds/gc/guarded_ptr.h index b5781039..82925e0f 100644 --- a/cds/gc/guarded_ptr.h +++ b/cds/gc/guarded_ptr.h @@ -15,7 +15,7 @@ namespace cds { namespace gc { After destructing \p %guarded_ptr object the pointer can be automatically disposed (freed) at any time. Template arguments: - - \p GC - a garbage collector type like cds::gc::HP and any other from cds::gc namespace + - \p GC - a garbage collector type like \p cds::gc::HP and any other from cds::gc namespace - \p GuardedType - a type which the guard stores - \p ValueType - a value type - \p Cast - a functor for converting GuardedType* to ValueType*. Default is \p void (no casting). @@ -52,10 +52,10 @@ namespace cds { namespace gc { { //TODO: use moce semantics and explicit operator bool! public: - typedef GC gc ; ///< Garbage collector like cds::gc::HP and any other from cds::gc namespace - typedef GuardedType guarded_type; ///< Guarded type - typedef ValueType value_type ; ///< Value type - typedef Cast value_cast ; ///< Functor for casting \p guarded_type to \p value_type + typedef GC gc; ///< Garbage collector like cds::gc::HP and any other from cds::gc namespace + typedef GuardedType guarded_type; ///< Guarded type + typedef ValueType value_type; ///< Value type + typedef Cast value_cast; ///< Functor for casting \p guarded_type to \p value_type private: //@cond @@ -67,18 +67,26 @@ namespace cds { namespace gc { guarded_ptr() CDS_NOEXCEPT {} + //@cond /// Initializes guarded pointer with \p p guarded_ptr( guarded_type * p ) CDS_NOEXCEPT { m_guard.assign( p ); } + guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT + {} + //@endcond - /// Copy constructor - guarded_ptr( guarded_ptr const& gp ) CDS_NOEXCEPT + /// Move ctor + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT { - m_guard.copy( gp.m_guard ); + m_guard.assign( gp.m_guard.get_native() ); + gp.release(); } + /// The guarded pointer is not copy-constructible + guarded_ptr( guarded_ptr const& gp ) = delete; + /// Clears the guarded pointer /** \ref release is called if guarded pointer is not \ref empty @@ -88,13 +96,17 @@ namespace cds { namespace gc { release(); } - /// Assignment operator - guarded_ptr& operator=( guarded_ptr const& gp ) CDS_NOEXCEPT + /// Move-assignment operator + guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT { - m_guard.copy( gp.m_guard ); + m_guard.assign( gp.m_guard.get_native() ); + gp.release(); return *this; } + /// The guarded pointer is not copy-assignable + guarded_ptr& operator=(guarded_ptr const& gp) = delete; + /// Returns a pointer to guarded value value_type * operator ->() const CDS_NOEXCEPT { @@ -121,6 +133,12 @@ namespace cds { namespace gc { return m_guard.template get() == nullptr; } + /// \p bool operator returns !empty() + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + /// Clears guarded pointer /** If the guarded pointer has been released, the pointer can be disposed (freed) at any time. @@ -163,22 +181,28 @@ namespace cds { namespace gc { m_guard.assign( p ); } - guarded_ptr( guarded_ptr const& gp ) CDS_NOEXCEPT + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT { - m_guard.copy( gp.m_guard ); + m_guard.assign( gp.m_guard.get_native() ); + gp.release(); } + guarded_ptr( guarded_ptr const& gp ) = delete; + ~guarded_ptr() CDS_NOEXCEPT { release(); } - guarded_ptr& operator=( guarded_ptr const& gp ) CDS_NOEXCEPT + guarded_ptr& operator=(guarded_ptr&& gp) CDS_NOEXCEPT { - m_guard.copy( gp.m_guard ); + m_guard.assign( gp.m_guard.get_native() ); + gp.release(); return *this; } + guarded_ptr& operator=(guarded_ptr const& gp) = delete; + value_type * operator ->() const CDS_NOEXCEPT { return m_guard.template get(); @@ -201,6 +225,11 @@ namespace cds { namespace gc { return m_guard.template get() == nullptr; } + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + void release() CDS_NOEXCEPT { m_guard.clear(); diff --git a/cds/gc/impl/hp_decl.h b/cds/gc/impl/hp_decl.h index 14c98314..c139736a 100644 --- a/cds/gc/impl/hp_decl.h +++ b/cds/gc/impl/hp_decl.h @@ -146,7 +146,7 @@ namespace cds { namespace gc { to the HP slot repeatedly until the guard's value equals \p toGuard. The function is useful for intrusive containers when \p toGuard is a node pointer - that should be converted to a pointer to the value type before protecting. + that should be converted to a pointer to the value before protecting. The parameter \p f of type Func is a functor that makes this conversion: \code struct functor { diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index e6f2e993..38df2b5b 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -549,70 +549,78 @@ 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 dest parameter. - If the tree is empty the function returns \p false. + The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found. + If the tree is empty the function returns an empty guarded pointer. @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. 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 tree traversing. - The guarded pointer \p dest prevents disposer invocation for returned item, - see cds::gc::guarded_ptr for explanation. + The returned \p guarded_ptr prevents disposer invocation for returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_min( guarded_ptr& dest ) + guarded_ptr extract_min() { - return extract_min_( dest.guard()); + guarded_ptr gp; + extract_min_( gp.guard() ); + return gp; } /// 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 dest parameter. - If the tree is empty the function returns \p false. + The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found. + If the tree is empty the function returns an empty \p guarded_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. During unlinking, a concurrent thread may insert an item with key great than rightmost item's key. So, the function returns the item with maximal key at the moment of tree traversing. - The guarded pointer \p dest prevents disposer invocation for returned item, + The returned \p guarded_ptr prevents disposer invocation for returned item, see cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ - bool extract_max( guarded_ptr& dest ) + guarded_ptr extract_max() { - return extract_max_( dest.guard() ); + guarded_ptr gp; + extract_max_( gp.guard()); + return gp; } /// Extracts an item from the tree /** \anchor cds_intrusive_EllenBinTree_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 dest parameter. - If the item is not found the function returns \p false. + unlinks it, and returns a guarded pointer to an item found. + If the item is not found the function returns an empty \p guarded_ptr. - The guarded pointer \p dest prevents disposer invocation for returned item, + \p guarded_ptr prevents disposer invocation for returned item, see cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool extract( guarded_ptr& dest, Q const& key ) + guarded_ptr extract( Q const& key ) { - return extract_( dest.guard(), key ); + guarded_ptr gp; + extract_( gp.guard(), key ); + return gp; } /// Extracts an item from the tree using \p pred for searching /** - The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)" + The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)" but \p pred is used for key compare. \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less "Predicate requirements". \p pred must imply the same element order as the comparator used for building the tree. */ template - bool extract_with( guarded_ptr& dest, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { - return extract_with_( dest.guard(), key, pred ); + guarded_ptr gp; + extract_with_( gp.guard(), key, pred ); + return gp; } /// Finds the key \p key @@ -718,31 +726,35 @@ namespace cds { namespace intrusive { /// Finds \p key and returns the item found /** @anchor cds_intrusive_EllenBinTree_get - The function searches the item with key equal to \p key and returns the item found in \p dest parameter. - The function returns \p true if \p key is found, \p false otherwise. + The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object. + The function returns an empty guarded pointer is \p key is not found. - The guarded pointer \p dest prevents disposer invocation for returned item, - see cds::gc::guarded_ptr for explanation. + \p guarded_ptr prevents disposer invocation for returned item, + see \p cds::gc::guarded_ptr for explanation. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. */ template - bool get( guarded_ptr& dest, Q const& key ) const + guarded_ptr get( Q const& key ) const { - return get_( dest.guard(), key ); + guarded_ptr gp; + get_( gp.guard(), key ); + return gp; } /// Finds \p key with predicate \p pred and returns the item found /** - The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)" + The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)" but \p pred is used for key comparing. \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less "Predicate requirements". \p pred must imply the same element order as the comparator used for building the tree. */ template - bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const + guarded_ptr get_with( Q const& key, Less pred ) const { - return get_with_( dest.guard(), key, pred ); + guarded_ptr gp; + get_with_( gp.guard(), key, pred ); + return gp; } /// Checks if the tree is empty @@ -767,7 +779,9 @@ namespace cds { namespace intrusive { void clear() { guarded_ptr gp; - while ( extract_min(gp)); + do { + gp = extract_min(); + } while ( gp ); } /// Clears the tree (not thread safe) @@ -1315,6 +1329,7 @@ namespace cds { namespace intrusive { template bool extract_( typename gc::Guard& guard, Q const& key ) { + guarded_ptr gp; return erase_( key, node_compare(), []( Q const&, leaf_node const& ) -> bool { return true; }, [&guard]( value_type& found ) { guard.assign( &found ); } ); @@ -1335,7 +1350,7 @@ namespace cds { namespace intrusive { [&guard]( value_type& found ) { guard.assign( &found ); } ); } - bool extract_max_( typename gc::Guard& guard ) + bool extract_max_( typename gc::Guard& gp ) { update_desc * pOp = nullptr; search_result res; @@ -1381,11 +1396,11 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMaxSuccess(); - guard.assign( node_traits::to_value_ptr( res.pLeaf ) ); + gp.assign( node_traits::to_value_ptr( res.pLeaf )); return true; } - bool extract_min_( typename gc::Guard& guard ) + bool extract_min_( typename gc::Guard& gp ) { update_desc * pOp = nullptr; search_result res; @@ -1431,7 +1446,7 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMinSuccess(); - guard.assign( node_traits::to_value_ptr( res.pLeaf )); + gp.assign( node_traits::to_value_ptr( res.pLeaf )); return true; } diff --git a/tests/test-hdr/tree/hdr_ellenbintree_map.h b/tests/test-hdr/tree/hdr_ellenbintree_map.h index cf0ccaf8..d4849aa2 100644 --- a/tests/test-hdr/tree/hdr_ellenbintree_map.h +++ b/tests/test-hdr/tree/hdr_ellenbintree_map.h @@ -386,11 +386,11 @@ namespace tree { int i = 0; std::pair v; while ( !m.empty() ) { - CPPUNIT_ASSERT( m.extract_min( gp ) ); + gp = m.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_ASSERT( gp->first == i ); ++i; - gp.release(); } CPPUNIT_ASSERT( m.empty() ); CPPUNIT_ASSERT( check_size( m, 0 )); @@ -399,11 +399,11 @@ namespace tree { fill_map( m, arr ); i = (int) c_nItemCount - 1; while ( !m.empty() ) { - CPPUNIT_ASSERT( m.extract_max( gp ) ); + gp = m.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_ASSERT( gp->first == i ); --i; - gp.release(); } CPPUNIT_ASSERT( m.empty() ); CPPUNIT_ASSERT( check_size( m, 0 )); @@ -411,19 +411,20 @@ namespace tree { fill_map( m, arr ); for ( int i = 0; i < static_cast( c_nItemCount ); ++i ) { int nKey = arr[i]; - CPPUNIT_ASSERT( m.get( gp, nKey )); + gp = m.get( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); - gp.release(); - CPPUNIT_ASSERT( m.extract( gp, nKey )); + gp = m.extract( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); - gp.release(); - CPPUNIT_CHECK( !m.get( gp, nKey )); + gp = m.get( nKey ); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty()); - CPPUNIT_CHECK( !m.extract( gp, nKey )); + CPPUNIT_CHECK( !m.extract( nKey )); CPPUNIT_CHECK( gp.empty()); } CPPUNIT_ASSERT( m.empty() ); @@ -432,19 +433,20 @@ namespace tree { fill_map( m, arr ); for ( int i = 0; i < static_cast( c_nItemCount ); ++i ) { int nKey = arr[i]; - CPPUNIT_ASSERT( m.get_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = m.get_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); - gp.release(); - CPPUNIT_ASSERT( m.extract_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = m.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); - gp.release(); - CPPUNIT_CHECK( !m.get_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = m.get_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty()); - CPPUNIT_CHECK( !m.extract_with( gp, wrapped_int(nKey), wrapped_less() )); + CPPUNIT_CHECK( !m.extract_with( wrapped_int(nKey), wrapped_less() )); CPPUNIT_CHECK( gp.empty()); } diff --git a/tests/test-hdr/tree/hdr_ellenbintree_set.h b/tests/test-hdr/tree/hdr_ellenbintree_set.h index 12dc8606..08658ef5 100644 --- a/tests/test-hdr/tree/hdr_ellenbintree_set.h +++ b/tests/test-hdr/tree/hdr_ellenbintree_set.h @@ -495,7 +495,8 @@ namespace tree { int i = 0; while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_min( gp ) ); + gp = s.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( gp->nKey == i ); ++i; } @@ -505,7 +506,8 @@ namespace tree { fill_set( s, arr ); i = (int) c_nItemCount - 1; while ( !s.empty() ) { - CPPUNIT_ASSERT( s.extract_max( gp ) ); + gp = s.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( gp->nKey == i ); --i; } @@ -515,19 +517,20 @@ namespace tree { fill_set( s, arr ); for ( int i = 0; i < static_cast( c_nItemCount ); ++i ) { int nKey = arr[i]; - CPPUNIT_ASSERT( s.get( gp, nKey )); + gp = s.get( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); - gp.release(); - CPPUNIT_ASSERT( s.extract( gp, nKey )); + gp = s.extract( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); - gp.release(); - CPPUNIT_CHECK( !s.get( gp, nKey )); + gp = s.get( nKey ); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty()); - CPPUNIT_CHECK( !s.extract( gp, nKey )); + CPPUNIT_CHECK( !s.extract( nKey )); CPPUNIT_CHECK( gp.empty()); } CPPUNIT_ASSERT( s.empty() ); @@ -536,19 +539,20 @@ namespace tree { fill_set( s, arr ); for ( int i = 0; i < static_cast( c_nItemCount ); ++i ) { int nKey = arr[i]; - CPPUNIT_ASSERT( s.get_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = s.get_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); - gp.release(); - CPPUNIT_ASSERT( s.extract_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = s.extract_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); - gp.release(); - CPPUNIT_CHECK( !s.get_with( gp, wrapped_int(nKey), wrapped_less() )); + gp = s.get_with( wrapped_int( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty()); - CPPUNIT_CHECK( !s.extract_with( gp, wrapped_int(nKey), wrapped_less() )); + CPPUNIT_CHECK( !s.extract_with( wrapped_int(nKey), wrapped_less() )); CPPUNIT_CHECK( gp.empty()); } CPPUNIT_ASSERT( s.empty() ); diff --git a/tests/test-hdr/tree/hdr_intrusive_bintree.h b/tests/test-hdr/tree/hdr_intrusive_bintree.h index bbc010cc..78a17c50 100644 --- a/tests/test-hdr/tree/hdr_intrusive_bintree.h +++ b/tests/test-hdr/tree/hdr_intrusive_bintree.h @@ -673,50 +673,58 @@ namespace tree { { typename tree_type::guarded_ptr gp; - CPPUNIT_ASSERT( t.get( gp, v2.nKey )); + gp = t.get( v2.nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == v2.nKey ); - gp.release(); - CPPUNIT_ASSERT( t.extract( gp, v2.nKey )); + gp = t.extract( v2.nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 4 )); CPPUNIT_ASSERT( gp->nKey == v2.nKey ); - CPPUNIT_ASSERT( !t.extract( gp, v2.nKey )); - CPPUNIT_CHECK( !t.get( gp, v2.nKey )); + gp = t.extract( v2.nKey ); + CPPUNIT_ASSERT( !gp ); + gp = t.get( v2.nKey ); + CPPUNIT_CHECK( !gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 4 )); - CPPUNIT_ASSERT( t.extract_min(gp)); + gp = t.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 3 )); CPPUNIT_ASSERT( gp->nKey == v5.nKey ); - CPPUNIT_ASSERT( t.extract_min(gp)); + gp = t.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 2 )); CPPUNIT_ASSERT( gp->nKey == v1.nKey ); - CPPUNIT_ASSERT( t.extract_min(gp)); + gp = t.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 1 )); CPPUNIT_ASSERT( gp->nKey == v4.nKey ); - CPPUNIT_ASSERT( t.extract_min(gp)); + gp = t.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 0 )); CPPUNIT_ASSERT( gp->nKey == v3.nKey ); - CPPUNIT_ASSERT( !t.extract_min(gp)); - CPPUNIT_ASSERT( !t.extract_max(gp)); - CPPUNIT_ASSERT( !t.extract( gp, v1.nKey )); + gp = t.extract_min(); + CPPUNIT_ASSERT( !gp ); + CPPUNIT_ASSERT( !t.extract_max()); + CPPUNIT_ASSERT( !t.extract( v1.nKey )); } tree_type::gc::force_dispose(); @@ -733,38 +741,45 @@ namespace tree { CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 5 )); - CPPUNIT_ASSERT( t.get_with( gp, wrapped_int(v4.nKey), wrapped_less() )); + gp = t.get_with( wrapped_int( v4.nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == v4.nKey ); - CPPUNIT_ASSERT( t.extract_with( gp, wrapped_int(v4.nKey), wrapped_less() )); + gp = t.extract_with( wrapped_int( v4.nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 4 )); CPPUNIT_ASSERT( gp->nKey == v4.nKey ); - CPPUNIT_ASSERT( !t.extract_with( gp, v4.nKey, less() ) ); + gp = t.extract_with( v4.nKey, less()); + CPPUNIT_ASSERT( !gp ); CPPUNIT_ASSERT( t.check_consistency() ); - CPPUNIT_ASSERT( !t.get_with( gp, v4.nKey, less() ) ); + CPPUNIT_ASSERT( !t.get_with( v4.nKey, less() ) ); - CPPUNIT_ASSERT( t.extract_max(gp)); + gp = t.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 3 )); CPPUNIT_ASSERT( gp->nKey == v3.nKey ); - CPPUNIT_ASSERT( t.extract_max(gp) ); + gp = t.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 2 )); CPPUNIT_ASSERT( gp->nKey == v2.nKey ); - CPPUNIT_ASSERT( t.extract_max(gp) ); + gp = t.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( !t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 1 )); CPPUNIT_ASSERT( gp->nKey == v1.nKey ); - CPPUNIT_ASSERT( t.extract_max(gp) ); + gp = t.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( t.check_consistency() ); CPPUNIT_ASSERT( t.empty() ); CPPUNIT_ASSERT( misc::check_size( t, 0 )); @@ -783,8 +798,7 @@ namespace tree { CPPUNIT_ASSERT( t.ensure( *p, ensure_functor()).second ); } for ( int n = 0; n < (int) c_nItemCount; ++n ) { - typename tree_type::guarded_ptr gp; - CPPUNIT_ASSERT( t.extract_min(gp)); + typename tree_type::guarded_ptr gp( t.extract_min() ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == n ); } @@ -793,8 +807,7 @@ namespace tree { CPPUNIT_ASSERT( t.insert( *p ) ); } for ( int n = (int) c_nItemCount - 1; n >= 0; --n ) { - typename tree_type::guarded_ptr gp; - CPPUNIT_ASSERT( t.extract_max(gp)); + typename tree_type::guarded_ptr gp( t.extract_max()); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == n ); } diff --git a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp_member.cpp b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp_member.cpp index f07e18cd..79b37656 100644 --- a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp_member.cpp +++ b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp_member.cpp @@ -24,7 +24,7 @@ namespace tree { }; typedef ci::ellen_bintree::internal_node< IntrusiveBinTreeHdrTest::key_type, leaf_node > internal_node; - typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc; + typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc; } void IntrusiveBinTreeHdrTest::EllenBinTree_dhp_member_less() diff --git a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp index 2134c976..d813cb28 100644 --- a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp +++ b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp @@ -22,7 +22,7 @@ namespace tree { }; typedef ci::ellen_bintree::internal_node< IntrusiveBinTreeHdrTest::key_type, leaf_node > internal_node; - typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc; + typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc; } void IntrusiveBinTreeHdrTest::EllenBinTree_hp_base_less() -- 2.34.1