From 35a035d8d6c7b53a1b3bc1fbb268ca72fa61e387 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 19 Nov 2014 23:41:49 +0300 Subject: [PATCH] movable guarded_ptr: SkipList --- cds/container/impl/skip_list_map.h | 81 +++++++------ cds/container/impl/skip_list_set.h | 79 +++++++------ cds/intrusive/impl/skip_list.h | 106 ++++++++++-------- tests/test-hdr/map/hdr_skiplist_map.h | 42 ++++--- .../test-hdr/set/hdr_intrusive_skiplist_set.h | 48 ++++---- tests/test-hdr/set/hdr_skiplist_set.h | 71 ++++++------ 6 files changed, 236 insertions(+), 191 deletions(-) diff --git a/cds/container/impl/skip_list_map.h b/cds/container/impl/skip_list_map.h index c84a73f6..0d311726 100644 --- a/cds/container/impl/skip_list_map.h +++ b/cds/container/impl/skip_list_map.h @@ -144,7 +144,7 @@ namespace cds { namespace container { public: /// Guarded pointer - typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; protected: //@cond @@ -399,13 +399,13 @@ namespace cds { namespace container { /// Extracts the item from the map with specified \p key /** \anchor cds_nonintrusive_SkipListMap_hp_extract The function searches an item with key equal to \p key in the map, - unlinks it from the map, and returns it in \p ptr parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the map, and returns a guarded pointer to the item found. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type. The item extracted is freed automatically by garbage collector \p GC - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -414,8 +414,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract( gp, 5 ) ) { + skip_list::guarded_ptr gp( theList.extract( 5 )); + if ( gp ) { // Deal with gp // ... } @@ -424,9 +424,11 @@ namespace cds { namespace container { \endcode */ template - bool extract( guarded_ptr& ptr, K const& key ) + guarded_ptr extract( K const& key ) { - return base_class::extract_( ptr.guard(), key, typename base_class::key_comparator() ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key, typename base_class::key_comparator() ); + return gp; } /// Extracts the item from the map with comparing functor \p pred @@ -439,20 +441,22 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( guarded_ptr& ptr, K const& key, Less pred ) + guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less; - return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less() ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); + return gp; } /// 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 ptr parameter. - If the skip-list is empty the function returns \p false. + The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found. + If the skip-list is empty the function returns an empty guarded pointer. The item extracted is freed automatically by garbage collector \p GC - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -461,8 +465,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_min( gp )) { + skip_list::guarded_ptr gp( theList.extract_min()); + if ( gp ) { // Deal with gp //... } @@ -470,18 +474,20 @@ namespace cds { namespace container { } \endcode */ - bool extract_min( guarded_ptr& ptr) + guarded_ptr extract_min() { - return base_class::extract_min_( ptr.guard() ); + guarded_ptr gp; + base_class::extract_min_( gp.guard() ); + return gp; } /// Extracts an item with maximal key from the map /** - The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p ptr parameter. - If the skip-list is empty the function returns empty \p guarded_ptr. + The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found. + If the skip-list is empty the function returns an empty \p guarded_ptr. The item found is freed by garbage collector \p GC automatically - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -490,8 +496,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_max( gp )) { + skip_list::guarded_ptr gp( theList.extract_max()); + if ( gp ) { // Deal with gp //... } @@ -499,9 +505,11 @@ namespace cds { namespace container { } \endcode */ - bool extract_max( guarded_ptr& dest ) + guarded_ptr extract_max() { - return base_class::extract_max_( dest.guard() ); + guarded_ptr gp; + base_class::extract_max_( gp.guard() ); + return gp; } /// Find the key \p key @@ -571,11 +579,10 @@ namespace cds { namespace container { /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_SkipListMap_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns an guarded pointer to the item found. + If \p key is not found the function returns an empty guarded pointer. - It is safe when a concurrent thread erases the item returned in \p ptr guarded pointer. + It is safe when a concurrent thread erases the item returned as \p guarded_ptr. In this case the item will be freed later by garbage collector \p GC automatically when \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -586,8 +593,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.get( gp, 5 ) ) { + skip_list::guarded_ptr gp( theList.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -599,14 +606,16 @@ namespace cds { namespace container { should accept a parameter of type \p K that can be not the same as \p value_type. */ template - bool get( guarded_ptr& ptr, K const& key ) + guarded_ptr get( K const& key ) { - return base_class::get_with_( ptr.guard(), key, typename base_class::key_comparator() ); + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() ); + return gp; } /// Finds the key \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( guarded_ptr& ptr, K const&)" + The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K @@ -614,11 +623,13 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - bool get_with( guarded_ptr& ptr, K const& key, Less pred ) + guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less; - return base_class::get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); + return gp; } /// Clears the map diff --git a/cds/container/impl/skip_list_set.h b/cds/container/impl/skip_list_set.h index 9f699af9..3f424544 100644 --- a/cds/container/impl/skip_list_set.h +++ b/cds/container/impl/skip_list_set.h @@ -134,7 +134,7 @@ namespace cds { namespace container { public: /// Guarded pointer - typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; protected: //@cond @@ -375,13 +375,13 @@ namespace cds { namespace container { /// Extracts the item from the set with specified \p key /** \anchor cds_nonintrusive_SkipListSet_hp_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 it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. The item extracted is freed automatically by garbage collector \p GC - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -390,8 +390,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract( gp, 5 ) ) { + skip_list::guarded_ptr gp(theList.extract( 5 )) + if ( gp ) { // Deal with gp // ... } @@ -400,9 +400,11 @@ namespace cds { namespace container { \endcode */ template - bool extract( guarded_ptr& result, Q const& key ) + guarded_ptr extract( Q const& key ) { - return base_class::extract_( result.guard(), key, typename base_class::key_comparator() ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key, typename base_class::key_comparator() ); + return gp; } /// Extracts the item from the set with comparing functor \p pred @@ -415,20 +417,22 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the set. */ template - bool extract_with( guarded_ptr& ptr, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less() ); + guarded_ptr gp; + base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); + return gp; } /// 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 pointer to the item found as \p guarded_ptr. + If the skip-list is empty the function returns an empty guarded pointer. The item extracted is freed automatically by garbage collector \p GC - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -437,8 +441,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_min( gp )) { + skip_list::guarded_ptr gp( theList.extract_min()); + if ( gp ) { // Deal with gp //... } @@ -446,18 +450,20 @@ namespace cds { namespace container { } \endcode */ - 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 /** - The function searches an item with maximal key, unlinks it, and returns the pointer to 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 the pointer to item found as \p guarded_ptr. + If the skip-list is empty the function returns an empty guarded pointer. The item found is freed by garbage collector \p GC automatically - when returned \ref guarded_ptr object will be destroyed or released. + when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -466,8 +472,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_max( gp )) { + skip_list::guarded_ptr gp( theList.extract_max()); + if ( gp ) { // Deal with gp //... } @@ -475,9 +481,11 @@ namespace cds { namespace container { } \endcode */ - 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; } /// Find the \p key @@ -571,9 +579,8 @@ namespace cds { namespace container { /// Finds \p key and return the item found /** \anchor cds_nonintrusive_SkipListSet_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p result. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p result parameter is left unchanged. + and returns a guarded pointer to the item found. + If \p key is not found the function returns an empty guarded pointer. It is safe when a concurrent thread erases the item returned in \p result guarded pointer. In this case the item will be freed later by garbage collector \p GC automatically @@ -586,8 +593,8 @@ namespace cds { namespace container { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.get( gp, 5 ) ) { + skip_list::guarded_ptr gp( theList.get( 5 )); + if ( theList.get( 5 )) { // Deal with gp //... } @@ -599,14 +606,16 @@ namespace cds { namespace container { should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool get( guarded_ptr& result, Q const& key ) + guarded_ptr get( Q const& key ) { - return base_class::get_with_( result.guard(), key, typename base_class::key_comparator() ); + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() ); + return gp; } /// Finds \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get( guarded_ptr&, Q const&)" + The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get(Q const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q @@ -614,11 +623,13 @@ namespace cds { namespace container { \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 ) { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - return base_class::get_with_( result.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); + guarded_ptr gp; + base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); + return gp; } /// Clears the set (not atomic). diff --git a/cds/intrusive/impl/skip_list.h b/cds/intrusive/impl/skip_list.h index 86c505e2..7a5043d7 100644 --- a/cds/intrusive/impl/skip_list.h +++ b/cds/intrusive/impl/skip_list.h @@ -346,7 +346,7 @@ namespace cds { namespace intrusive { typedef typename traits::stat stat; ///< internal statistics type public: - typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer + typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer /// Max node height. The actual node height should be in range [0 .. c_nMaxHeight) /** @@ -809,9 +809,9 @@ namespace cds { namespace intrusive { } template - bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp ) + bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) { - return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } ); + return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } ); } template @@ -842,18 +842,19 @@ namespace cds { namespace intrusive { } template - bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp ) + bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) { position pos; for (;;) { if ( !find_position( val, pos, cmp, false ) ) { m_Stat.onExtractFailed(); + guard.clear(); return false; } node_type * pDel = pos.pCur; - guard.assign( node_traits::to_value_ptr(pDel)); + guard.set( node_traits::to_value_ptr(pDel)); assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 ); unsigned int nHeight = pDel->height(); @@ -863,12 +864,11 @@ namespace cds { namespace intrusive { m_Stat.onExtractSuccess(); return true; } - m_Stat.onExtractRetry(); } } - bool extract_min_( typename gc::Guard& gDel ) + bool extract_min_( typename guarded_ptr::native_guard& gDel ) { position pos; @@ -876,13 +876,14 @@ namespace cds { namespace intrusive { if ( !find_min_position( pos ) ) { // The list is empty m_Stat.onExtractMinFailed(); + gDel.clear(); return false; } node_type * pDel = pos.pCur; unsigned int nHeight = pDel->height(); - gDel.assign( node_traits::to_value_ptr(pDel) ); + gDel.set( node_traits::to_value_ptr(pDel) ); if ( try_remove_at( pDel, pos, [](value_type const&) {} )) { --m_ItemCounter; @@ -895,7 +896,7 @@ namespace cds { namespace intrusive { } } - bool extract_max_( typename gc::Guard& gDel ) + bool extract_max_( typename guarded_ptr::native_guard& gDel ) { position pos; @@ -903,13 +904,14 @@ namespace cds { namespace intrusive { if ( !find_max_position( pos ) ) { // The list is empty m_Stat.onExtractMaxFailed(); + gDel.clear(); return false; } node_type * pDel = pos.pCur; unsigned int nHeight = pDel->height(); - gDel.assign( node_traits::to_value_ptr(pDel) ); + gDel.set( node_traits::to_value_ptr(pDel) ); if ( try_remove_at( pDel, pos, [](value_type const&) {} )) { --m_ItemCounter; @@ -1186,12 +1188,12 @@ namespace cds { namespace intrusive { /// Extracts the item from the set with specified \p key /** \anchor cds_intrusive_SkipListSet_hp_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 dest 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 it as \p guarded_ptr object. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. - The \ref disposer specified in \p Traits class template parameter is called automatically + The \p disposer specified in \p Traits class template parameter is called automatically by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. @@ -1202,19 +1204,21 @@ namespace cds { namespace intrusive { skip_list theList; // ... { - skip_list::guarded_ptr gp; - theList.extract( gp, 5 ); - // Deal with gp - // ... - + skip_list::guarded_ptr gp(theList.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } // Destructor of gp releases internal HP guard } \endcode */ template - bool extract( guarded_ptr& dest, Q const& key ) + guarded_ptr extract( Q const& key ) { - return extract_( dest.guard(), key, key_comparator() ); + guarded_ptr gp; + extract_( gp.guard(), key, key_comparator() ); + return gp; } /// Extracts the item from the set with comparing functor \p pred @@ -1227,16 +1231,18 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the set. */ template - bool extract_with( guarded_ptr& dest, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less() ); + guarded_ptr gp; + extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); + return gp; } /// 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 dest parameter. - If the skip-list is empty the function returns \p false. + The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object. + If the skip-list is empty the function returns an empty guarded pointer. @note Due the concurrent nature of the list, the function extracts nearly minimum key. It means that the function gets leftmost item and tries to unlink it. @@ -1254,8 +1260,8 @@ namespace cds { namespace intrusive { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_min( gp )) { + skip_list::guarded_ptr gp(theList.extract_min()); + if ( gp ) { // Deal with gp //... } @@ -1263,15 +1269,18 @@ namespace cds { namespace intrusive { } \endcode */ - 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 list /** - The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter. - If the skip-list is empty the function returns empty \p guarded_ptr. + The function searches an item with maximal key, unlinks it, and returns the pointer to item + as \p guarded_ptr object. + If the skip-list is empty the function returns an empty \p guarded_ptr. @note Due the concurrent nature of the list, the function extracts nearly maximal key. It means that the function gets rightmost item and tries to unlink it. @@ -1289,8 +1298,8 @@ namespace cds { namespace intrusive { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.extract_max( gp )) { + skip_list::guarded_ptr gp( theList.extract_max( gp )); + if ( gp ) { // Deal with gp //... } @@ -1298,9 +1307,11 @@ namespace cds { namespace intrusive { } \endcode */ - bool extract_max( guarded_ptr& dest ) + guarded_ptr extract_max() { - return extract_max_( dest.guard() ); + guarded_ptr gp; + extract_max_( gp.guard() ); + return gp; } /// Deletes the item from the set @@ -1463,11 +1474,10 @@ namespace cds { namespace intrusive { /// Finds \p key and return the item found /** \anchor cds_intrusive_SkipListSet_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns the pointer to the item found as \p guarded_ptr. + If \p key is not found the function returns an empt guarded pointer. - The \ref disposer specified in \p Traits class template parameter is called + The \p disposer specified in \p Traits class template parameter is called by garbage collector \p GC asynchronously when returned \ref guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -1478,8 +1488,8 @@ namespace cds { namespace intrusive { skip_list theList; // ... { - skip_list::guarded_ptr gp; - if ( theList.get( gp, 5 )) { + skip_list::guarded_ptr gp(theList.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -1491,14 +1501,16 @@ namespace cds { namespace intrusive { should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool get( guarded_ptr& ptr, Q const& key ) + guarded_ptr get( Q const& key ) { - return get_with_( ptr.guard(), key, key_comparator() ); + guarded_ptr gp; + get_with_( gp.guard(), key, key_comparator() ); + return gp; } /// Finds \p key and return the item found /** - The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)" + The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q @@ -1506,10 +1518,12 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the set. */ template - bool get_with( guarded_ptr& ptr, Q const& key, Less pred ) + guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less() ); + guarded_ptr gp; + get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); + return gp; } /// Returns item count in the set @@ -1546,7 +1560,7 @@ namespace cds { namespace intrusive { void clear() { guarded_ptr gp; - while ( extract_min( gp )); + while ( extract_min_( gp.guard() )); } /// 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.h b/tests/test-hdr/map/hdr_skiplist_map.h index 9122af35..16145294 100644 --- a/tests/test-hdr/map/hdr_skiplist_map.h +++ b/tests/test-hdr/map/hdr_skiplist_map.h @@ -147,18 +147,21 @@ namespace map { // extract/get for ( int i = 0; i < nLimit; ++i ) { int nKey = arrItem[i]; - CPPUNIT_ASSERT( m.get( gp, nKey )); + gp = m.get( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); CPPUNIT_CHECK( gp->second.m_val == nKey * 2 ); - gp.release(); - CPPUNIT_ASSERT( m.extract(gp, nKey)); + + gp = m.extract( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); CPPUNIT_CHECK( gp->second.m_val == nKey * 2 ); - gp.release(); - CPPUNIT_CHECK( !m.get( gp, nKey )); - CPPUNIT_CHECK( !m.extract(gp, nKey)); + + gp = m.get( nKey ); + CPPUNIT_CHECK( !gp ); + CPPUNIT_CHECK( !m.extract(nKey)); CPPUNIT_CHECK( gp.empty()); } CPPUNIT_ASSERT( m.empty()); @@ -169,18 +172,21 @@ namespace map { // extract_with/get_with for ( int i = 0; i < nLimit; ++i ) { int nKey = arrItem[i]; - CPPUNIT_ASSERT( m.get_with( gp, wrapped_item(nKey), wrapped_less() )); + gp = m.get_with( wrapped_item( nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); CPPUNIT_CHECK( gp->second.m_val == nKey * 2 ); - gp.release(); - CPPUNIT_ASSERT( m.extract_with(gp, wrapped_item(nKey), wrapped_less())); + + gp = m.extract_with( wrapped_item( nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == nKey ); CPPUNIT_CHECK( gp->second.m_val == nKey * 2 ); - gp.release(); - CPPUNIT_CHECK( !m.get_with( gp, wrapped_item(nKey), wrapped_less())); - CPPUNIT_CHECK( !m.extract_with( gp, wrapped_item(nKey), wrapped_less())); + + gp = m.get_with( wrapped_item( nKey ), wrapped_less() ); + CPPUNIT_CHECK( !gp ); + CPPUNIT_CHECK( !m.extract_with( wrapped_item(nKey), wrapped_less())); CPPUNIT_CHECK( gp.empty()); } CPPUNIT_ASSERT( m.empty()); @@ -190,30 +196,30 @@ namespace map { CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) ); for ( int i = 0; i < nLimit; ++i ) { - CPPUNIT_ASSERT( m.extract_min(gp)); + gp = m.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == i ); CPPUNIT_CHECK( gp->second.m_val == i * 2 ); gp.release(); CPPUNIT_CHECK( gp.empty()); } - CPPUNIT_CHECK( !m.extract_min(gp)); - CPPUNIT_CHECK( gp.empty()); - CPPUNIT_ASSERT( m.empty()); + CPPUNIT_CHECK( !m.extract_min()); // 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(gp)); + gp = m.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->first == i ); CPPUNIT_CHECK( gp->second.m_val == i * 2 ); gp.release(); CPPUNIT_CHECK( gp.empty()); } - CPPUNIT_CHECK( !m.extract_max(gp)); + CPPUNIT_CHECK( m.extract_max()); CPPUNIT_CHECK( gp.empty()); CPPUNIT_ASSERT( m.empty()); } diff --git a/tests/test-hdr/set/hdr_intrusive_skiplist_set.h b/tests/test-hdr/set/hdr_intrusive_skiplist_set.h index 342b456d..349b2a25 100644 --- a/tests/test-hdr/set/hdr_intrusive_skiplist_set.h +++ b/tests/test-hdr/set/hdr_intrusive_skiplist_set.h @@ -230,38 +230,40 @@ namespace set { // extract fill_skiplist( s, v ); for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) { - CPPUNIT_CHECK( s.get(gp, i)); + gp = s.get( i ); + CPPUNIT_CHECK( gp ); CPPUNIT_CHECK( gp->nKey == i ); CPPUNIT_CHECK( gp->nVal == i * 2 ); gp->nVal *= 2; - gp.release(); - CPPUNIT_CHECK( s.extract( gp, i )); + gp = s.extract( i ); + CPPUNIT_CHECK( gp ); CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey); CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal ); - CPPUNIT_CHECK( !s.extract( gp, i )); - CPPUNIT_CHECK( !s.get( gp, i )); + gp = s.extract( i ); + CPPUNIT_CHECK( !gp ); + CPPUNIT_CHECK( !s.get( i )); } - gp.release(); CPPUNIT_CHECK( s.empty() ); Set::gc::force_dispose(); // extract_with fill_skiplist( s, v ); for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) { - CPPUNIT_CHECK( s.get_with( gp, other_key(i), other_key_less() )); + gp = s.get_with( other_key( i ), other_key_less() ); + CPPUNIT_CHECK( gp ); CPPUNIT_CHECK( gp->nKey == i ); CPPUNIT_CHECK( (*gp).nVal == i * 2 ); gp->nVal *= 2; - gp.release(); - CPPUNIT_CHECK( s.extract_with( gp, other_key(i), other_key_less() )); + gp = s.extract_with( other_key( i ), other_key_less() ); + CPPUNIT_CHECK( gp ); CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey); CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal ); - CPPUNIT_CHECK( !s.extract_with( gp, other_key(i), other_key_less() )); - CPPUNIT_CHECK( !s.get_with( gp, other_key(i), other_key_less() )); + gp = s.extract_with( other_key( i ), other_key_less() ); + CPPUNIT_CHECK( !gp ); + CPPUNIT_CHECK( !s.get_with( other_key(i), other_key_less() )); } - gp.release(); CPPUNIT_CHECK( s.empty() ); Set::gc::force_dispose(); @@ -269,18 +271,19 @@ namespace set { { fill_skiplist( s, v ); int nPrevKey; - CPPUNIT_ASSERT( s.extract_min( gp )); + gp = s.extract_min(); + CPPUNIT_ASSERT( gp ); nPrevKey = gp->nKey; while ( !s.empty() ) { - CPPUNIT_CHECK( s.extract_min( gp )); + gp = s.extract_min(); + CPPUNIT_CHECK( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nPrevKey + 1 ); CPPUNIT_CHECK( (*gp).nVal == (nPrevKey + 1) * 2 ); nPrevKey = gp->nKey; - gp.release(); } gp.release(); - CPPUNIT_CHECK( !s.extract_min(gp)); + CPPUNIT_CHECK( !s.extract_min()); CPPUNIT_CHECK( gp.empty()); } Set::gc::force_dispose(); @@ -289,23 +292,22 @@ namespace set { { fill_skiplist( s, v ); int nPrevKey; - CPPUNIT_ASSERT( s.extract_max( gp )); + gp = s.extract_max(); + CPPUNIT_ASSERT( gp ); nPrevKey = gp->nKey; while ( !s.empty() ) { - - CPPUNIT_CHECK( s.extract_max( gp )); + gp = s.extract_max(); + CPPUNIT_CHECK( gp ); CPPUNIT_ASSERT( !gp.empty() ); CPPUNIT_CHECK( gp->nKey == nPrevKey - 1 ); CPPUNIT_CHECK( (*gp).nVal == (nPrevKey - 1) * 2 ); nPrevKey = gp->nKey; - gp.release(); } gp.release(); - CPPUNIT_CHECK( !s.extract_min(gp)); + CPPUNIT_CHECK( !s.extract_min()); CPPUNIT_CHECK( gp.empty()); - CPPUNIT_CHECK( !s.extract_max(gp)); - CPPUNIT_CHECK( gp.empty()); + CPPUNIT_CHECK( !s.extract_max()); } Set::gc::force_dispose(); } diff --git a/tests/test-hdr/set/hdr_skiplist_set.h b/tests/test-hdr/set/hdr_skiplist_set.h index 2cd81163..f8805cce 100644 --- a/tests/test-hdr/set/hdr_skiplist_set.h +++ b/tests/test-hdr/set/hdr_skiplist_set.h @@ -36,16 +36,17 @@ namespace set { CPPUNIT_ASSERT( s.empty() ); for ( int i = 0; i < nLimit; ++i ) { - CPPUNIT_CHECK( !s.get(gp, i) ); + gp = s.get( i ); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty() ); CPPUNIT_ASSERT( s.insert(i) ); - CPPUNIT_CHECK( s.get(gp, i)); + gp = s.get( i ); + CPPUNIT_CHECK( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == i ); CPPUNIT_CHECK( gp->nVal == i ); - gp.release(); } CPPUNIT_MSG( PrintStat()(s, "Iterator test, ascending insert order") ); @@ -62,11 +63,11 @@ namespace set { nPrevKey = it->nKey; // get - CPPUNIT_CHECK( s.get( gp, it->nKey )); + gp = s.get( it->nKey ); + CPPUNIT_CHECK( gp ); CPPUNIT_ASSERT( !gp.empty() ); CPPUNIT_CHECK( gp->nKey == it->nKey ); CPPUNIT_CHECK( gp->nVal == it->nKey * 2 ); - gp.release(); } CPPUNIT_ASSERT( nCount == nLimit ); @@ -86,17 +87,18 @@ namespace set { CPPUNIT_ASSERT( s.empty() ); for ( int i = nLimit; i > 0; --i ) { - CPPUNIT_CHECK( !s.get_with(gp, i-1, base_class::less() ) ); + gp = s.get_with( i - 1, base_class::less()); + CPPUNIT_CHECK( !gp ); CPPUNIT_CHECK( gp.empty() ); CPPUNIT_ASSERT( s.insert( std::make_pair(i - 1, (i-1) * 2) )); // get_with - CPPUNIT_CHECK( s.get_with(gp, i-1, base_class::less() )); + gp = s.get_with( i - 1, base_class::less()); + CPPUNIT_CHECK( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == i-1 ); CPPUNIT_CHECK( gp->nVal == (i-1) * 2 ); - gp.release(); } CPPUNIT_MSG( PrintStat()(s, "Iterator test, descending insert order") ); @@ -167,22 +169,22 @@ namespace set { // extract/get for ( int i = 0; i < nLimit; ++i ) { int nKey = arrRandom[i]; - CPPUNIT_ASSERT( s.get(gp, nKey)); + gp = s.get( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); CPPUNIT_CHECK( gp->nVal == nKey * 2); - gp.release(); - CPPUNIT_ASSERT( s.extract(gp, nKey)); + gp = s.extract( nKey ); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); CPPUNIT_CHECK( gp->nVal == nKey * 2); - gp.release(); - CPPUNIT_CHECK( !s.get(gp, nKey)); - CPPUNIT_ASSERT( gp.empty()); - CPPUNIT_ASSERT( !s.extract(gp, nKey)); + gp = s.get( nKey ); + CPPUNIT_CHECK( !gp ); CPPUNIT_ASSERT( gp.empty()); + CPPUNIT_ASSERT( !s.extract(nKey)); } CPPUNIT_ASSERT( s.empty() ); @@ -192,19 +194,20 @@ namespace set { for ( int i = 0; i < nLimit; ++i ) { int nKey = arrRandom[i]; - CPPUNIT_ASSERT( s.get_with(gp, wrapped_item(nKey), wrapped_less() )); + gp = s.get_with( wrapped_item( nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); CPPUNIT_CHECK( gp->nVal == nKey ); - gp.release(); - CPPUNIT_ASSERT( s.extract_with(gp, wrapped_item(nKey), wrapped_less() )); + gp = s.extract_with( wrapped_item( nKey ), wrapped_less()); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == nKey ); CPPUNIT_CHECK( gp->nVal == nKey ); - CPPUNIT_CHECK( !s.get_with(gp, wrapped_item(nKey), wrapped_less() )); - CPPUNIT_ASSERT( !s.extract_with(gp, wrapped_item(nKey), wrapped_less() )); - gp.release(); + gp = s.get_with( wrapped_item( nKey ), wrapped_less()); + CPPUNIT_CHECK( !gp ); + CPPUNIT_ASSERT( !s.extract_with( wrapped_item(nKey), wrapped_less() )); } CPPUNIT_ASSERT( s.empty() ); @@ -213,36 +216,34 @@ namespace set { CPPUNIT_ASSERT( s.insert( arrRandom[i]) ); for ( int i = 0; i < nLimit; ++i ) { - CPPUNIT_ASSERT( s.extract_min(gp)); + gp = s.extract_min(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == i ); CPPUNIT_CHECK( gp->nVal == i ); - CPPUNIT_CHECK( !s.get(gp, i )); - gp.release(); + gp = s.get( i ); + CPPUNIT_CHECK( !gp ); } CPPUNIT_ASSERT( s.empty() ); - CPPUNIT_CHECK( !s.extract_min(gp)); - CPPUNIT_ASSERT( gp.empty() ); - CPPUNIT_CHECK( !s.extract_max(gp)); - CPPUNIT_ASSERT( gp.empty() ); + CPPUNIT_CHECK( !s.extract_min()); + CPPUNIT_CHECK( !s.extract_max()); // extract_max for ( int i = 0; i < nLimit; ++i ) CPPUNIT_ASSERT( s.insert( arrRandom[i]) ); for ( int i = nLimit-1; i >= 0; --i ) { - CPPUNIT_ASSERT( s.extract_max(gp)); + gp = s.extract_max(); + CPPUNIT_ASSERT( gp ); CPPUNIT_ASSERT( !gp.empty()); CPPUNIT_CHECK( gp->nKey == i ); CPPUNIT_CHECK( gp->nVal == i ); - CPPUNIT_CHECK( !s.get(gp, i )); - gp.release(); + gp = s.get( i ); + CPPUNIT_CHECK( !gp ); } CPPUNIT_ASSERT( s.empty() ); - CPPUNIT_CHECK( !s.extract_min(gp)); - CPPUNIT_ASSERT( gp.empty() ); - CPPUNIT_CHECK( !s.extract_max(gp)); - CPPUNIT_ASSERT( gp.empty() ); + CPPUNIT_CHECK( !s.extract_min()); + CPPUNIT_CHECK( !s.extract_max()); } CPPUNIT_MSG( PrintStat()(s, nullptr) ); -- 2.34.1