From c14ae188467d82f4b9227dcfc1052fcd113ad459 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 7 Sep 2016 23:15:56 +0300 Subject: [PATCH] Docfix, minor changes --- cds/container/details/base.h | 10 +- cds/container/details/iterable_list_base.h | 9 +- cds/container/details/michael_list_base.h | 4 +- cds/container/details/split_list_base.h | 4 +- cds/intrusive/details/base.h | 11 +- cds/intrusive/details/iterable_list_base.h | 7 - cds/intrusive/impl/iterable_list.h | 2 +- cds/intrusive/split_list.h | 522 +++++++++++---------- 8 files changed, 287 insertions(+), 282 deletions(-) diff --git a/cds/container/details/base.h b/cds/container/details/base.h index 1edbbe65..17acad69 100644 --- a/cds/container/details/base.h +++ b/cds/container/details/base.h @@ -5,7 +5,7 @@ Source code repo: http://github.com/khizmax/libcds/ Download: http://sourceforge.net/projects/libcds/files/ - + Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_DETAILS_BASE_H @@ -81,6 +81,12 @@ namespace container { @ingroup cds_nonintrusive_containers */ + //@cond + template + struct is_iterable_list: public cds::intrusive::is_iterable_list< List > + {}; + //@endcond + } // namespace container } // namespace cds diff --git a/cds/container/details/iterable_list_base.h b/cds/container/details/iterable_list_base.h index 4dab48eb..621e0923 100644 --- a/cds/container/details/iterable_list_base.h +++ b/cds/container/details/iterable_list_base.h @@ -153,19 +153,12 @@ namespace cds { namespace container { This struct is empty and it is used only as a tag for selecting \p IterableList as ordered list implementation in declaration of some classes. - See split_list::traits::ordered_list as an example. + See \p split_list::traits::ordered_list as an example. */ struct iterable_list_tag {}; //@cond - template - struct is_iterable_list { - enum { - value = false - }; - }; - template struct is_iterable_list< IterableList> { diff --git a/cds/container/details/michael_list_base.h b/cds/container/details/michael_list_base.h index df2e9e36..5b3cb3fa 100644 --- a/cds/container/details/michael_list_base.h +++ b/cds/container/details/michael_list_base.h @@ -145,10 +145,10 @@ namespace cds { namespace container { // Tag for selecting Michael's list implementation /** - This struct is empty and it is used only as a tag for selecting MichaelList + This struct is empty and it is used only as a tag for selecting \p MichaelList as ordered list implementation in declaration of some classes. - See split_list::traits::ordered_list as an example. + See \p split_list::traits::ordered_list as an example. */ struct michael_list_tag {}; diff --git a/cds/container/details/split_list_base.h b/cds/container/details/split_list_base.h index 608db8c5..841d34aa 100644 --- a/cds/container/details/split_list_base.h +++ b/cds/container/details/split_list_base.h @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_DETAILS_SPLIT_LIST_BASE_H @@ -129,7 +129,7 @@ namespace cds { namespace container { - for \p lazy_list_tag: \p container::lazy_list::traits. If this type is \p opt::none, the ordered list traits is combined with default - ordered list traits above and split-list traits. + ordered list traits and split-list traits. */ typedef opt::none ordered_list_traits; diff --git a/cds/intrusive/details/base.h b/cds/intrusive/details/base.h index f81c3c45..03673dc1 100644 --- a/cds/intrusive/details/base.h +++ b/cds/intrusive/details/base.h @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H @@ -321,6 +321,15 @@ namespace intrusive { @ingroup cds_intrusive_containers */ + //@cond + template + struct is_iterable_list { + enum { + value = false + }; + }; + //@endcond + }} // namespace cds::intrusuve #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 3ddaa07a..381a28a2 100644 --- a/cds/intrusive/details/iterable_list_base.h +++ b/cds/intrusive/details/iterable_list_base.h @@ -273,13 +273,6 @@ namespace cds { namespace intrusive { //@endcond //@cond - template - struct is_iterable_list { - enum { - value = false - }; - }; - template struct is_iterable_list< IterableList< GC, T, Traits >> { enum { diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index ea051c88..cbb76352 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -160,6 +160,7 @@ namespace cds { namespace intrusive { //@endcond protected: + //@cond typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support) @@ -167,7 +168,6 @@ namespace cds { namespace intrusive { item_counter m_ItemCounter; ///< Item counter mutable stat m_Stat; ///< Internal statistics - //@cond typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator; /// Position pointer for item search diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index f4fce634..8adce76a 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -91,12 +91,14 @@ namespace cds { namespace intrusive { Template parameters are: - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList. - The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation - schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for - the ordered list. + The intrusive ordered list implementation specifies the type \p T stored in the split-list set, the reclamation + schema \p GC used by split-list set, the comparison functor for the type \p T and other features specific for + the ordered list. - \p Traits - split-list traits, default is \p split_list::traits. Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction. + @warning \p IterableList is not supported as \p OrderedList template parameter. + There are several specialization of the split-list class for different \p GC: - for \ref cds_urcu_gc "RCU type" include - see \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list" @@ -252,6 +254,7 @@ namespace cds { namespace intrusive { static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators protected: + //@cond typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list typedef split_list::node node_type; ///< split-list node type typedef node_type dummy_node_type; ///< dummy node type @@ -263,7 +266,6 @@ namespace cds { namespace intrusive { */ typedef split_list::node_traits node_traits; - //@cond /// Bucket table implementation typedef typename split_list::details::bucket_table_selector< traits::dynamic_bucket_table @@ -272,6 +274,8 @@ namespace cds { namespace intrusive { , opt::allocator< typename traits::allocator > , opt::memory_model< memory_model > >::type bucket_table; + + typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator; //@endcond protected: @@ -373,261 +377,6 @@ namespace cds { namespace intrusive { }; //@endcond - protected: - ordered_list_wrapper m_List; ///< Ordered list containing split-list items - bucket_table m_Buckets; ///< bucket table - atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) - atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - stat m_Stat; ///< Internal statistics - - protected: - //@cond - typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator; - - dummy_node_type * alloc_dummy_node( size_t nHash ) - { - m_Stat.onHeadNodeAllocated(); - return dummy_node_allocator().New( nHash ); - } - void free_dummy_node( dummy_node_type * p ) - { - dummy_node_allocator().Delete( p ); - m_Stat.onHeadNodeFreed(); - } - - /// Calculates hash value of \p key - template - size_t hash_value( Q const& key ) const - { - return m_HashFunctor( key ); - } - - size_t bucket_no( size_t nHash ) const - { - return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 ); - } - - static size_t parent_bucket( size_t nBucket ) - { - assert( nBucket > 0 ); - return nBucket & ~( 1 << bitop::MSBnz( nBucket )); - } - - dummy_node_type * init_bucket( size_t nBucket ) - { - assert( nBucket > 0 ); - size_t nParent = parent_bucket( nBucket ); - - dummy_node_type * pParentBucket = m_Buckets.bucket( nParent ); - if ( pParentBucket == nullptr ) { - pParentBucket = init_bucket( nParent ); - m_Stat.onRecursiveInitBucket(); - } - - assert( pParentBucket != nullptr ); - - // Allocate a dummy node for new bucket - { - dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket )); - if ( m_List.insert_aux_node( pParentBucket, pBucket )) { - m_Buckets.bucket( nBucket, pBucket ); - m_Stat.onNewBucket(); - return pBucket; - } - free_dummy_node( pBucket ); - } - - // Another thread set the bucket. Wait while it done - - // In this point, we must wait while nBucket is empty. - // The compiler can decide that waiting loop can be "optimized" (stripped) - // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer. - m_Stat.onBucketInitContenton(); - back_off bkoff; - while ( true ) { - dummy_node_type volatile * p = m_Buckets.bucket( nBucket ); - if ( p != nullptr ) - return const_cast( p ); - bkoff(); - m_Stat.onBusyWaitBucketInit(); - } - } - - dummy_node_type * get_bucket( size_t nHash ) - { - size_t nBucket = bucket_no( nHash ); - - dummy_node_type * pHead = m_Buckets.bucket( nBucket ); - if ( pHead == nullptr ) - pHead = init_bucket( nBucket ); - - assert( pHead->is_dummy()); - - return pHead; - } - - void init() - { - // GC and OrderedList::gc must be the same - static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - - // atomicity::empty_item_counter is not allowed as a item counter - static_assert( !std::is_same::value, - "cds::atomicity::empty_item_counter is not allowed as a item counter"); - - // Initialize bucket 0 - dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ ); - - // insert_aux_node cannot return false for empty list - CDS_VERIFY( m_List.insert_aux_node( pNode )); - - m_Buckets.bucket( 0, pNode ); - } - - static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor ) - { - return nBucketCount * nLoadFactor; - } - - void inc_item_count() - { - size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed); - if ( ++m_ItemCounter <= nMaxCount ) - return; - - size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed); - const size_t nBucketCount = static_cast(1) << sz; - if ( nBucketCount < m_Buckets.capacity()) { - // we may grow the bucket table - const size_t nLoadFactor = m_Buckets.load_factor(); - if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) - return; // someone already have updated m_nBucketCountLog2, so stop here - - m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), - memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); - m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); - } - else - m_nMaxItemCount.store( std::numeric_limits::max(), memory_model::memory_order_relaxed ); - } - - template - bool find_( Q& val, Compare cmp, Func f ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - return m_Stat.onFind( - m_List.find_at( pHead, sv, cmp, - [&f](value_type& item, split_list::details::search_value_type& val){ f(item, val.val ); }) - ); - } - - template - bool find_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - return m_Stat.onFind( m_List.find_at( pHead, sv, cmp )); - } - - template - guarded_ptr get_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - guarded_ptr gp = m_List.get_at( pHead, sv, cmp ); - m_Stat.onFind( !gp.empty() ); - return gp; - } - - template - guarded_ptr get_( Q const& key ) - { - return get_( key, key_comparator()); - } - - template - guarded_ptr get_with_( Q const& key, Less ) - { - return get_( key, typename wrapped_ordered_list::template make_compare_from_less()); - } - - template - bool erase_( Q const& val, Compare cmp, Func f ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - if ( m_List.erase_at( pHead, sv, cmp, f )) { - --m_ItemCounter; - m_Stat.onEraseSuccess(); - return true; - } - m_Stat.onEraseFailed(); - return false; - } - - template - bool erase_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - if ( m_List.erase_at( pHead, sv, cmp )) { - --m_ItemCounter; - m_Stat.onEraseSuccess(); - return true; - } - m_Stat.onEraseFailed(); - return false; - } - - template - guarded_ptr extract_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); - dummy_node_type * pHead = get_bucket( nHash ); - assert( pHead != nullptr ); - - guarded_ptr gp = m_List.extract_at( pHead, sv, cmp ); - if ( gp ) { - --m_ItemCounter; - m_Stat.onExtractSuccess(); - } - else - m_Stat.onExtractFailed(); - return gp; - } - - template - guarded_ptr extract_( Q const& key ) - { - return extract_( key, key_comparator()); - } - - template - guarded_ptr extract_with_( Q const& key, Less ) - { - return extract_( key, typename wrapped_ordered_list::template make_compare_from_less()); - } - //@endcond - public: /// Initialize split-ordered list of default capacity /** @@ -1198,6 +947,261 @@ namespace cds { namespace intrusive { return const_iterator( m_List.cend(), m_List.cend()); } //@} + + protected: + //@cond + dummy_node_type * alloc_dummy_node( size_t nHash ) + { + m_Stat.onHeadNodeAllocated(); + return dummy_node_allocator().New( nHash ); + } + void free_dummy_node( dummy_node_type * p ) + { + dummy_node_allocator().Delete( p ); + m_Stat.onHeadNodeFreed(); + } + + /// Calculates hash value of \p key + template + size_t hash_value( Q const& key ) const + { + return m_HashFunctor( key ); + } + + size_t bucket_no( size_t nHash ) const + { + return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1); + } + + static size_t parent_bucket( size_t nBucket ) + { + assert( nBucket > 0 ); + return nBucket & ~(1 << bitop::MSBnz( nBucket )); + } + + dummy_node_type * init_bucket( size_t nBucket ) + { + assert( nBucket > 0 ); + size_t nParent = parent_bucket( nBucket ); + + dummy_node_type * pParentBucket = m_Buckets.bucket( nParent ); + if ( pParentBucket == nullptr ) { + pParentBucket = init_bucket( nParent ); + m_Stat.onRecursiveInitBucket(); + } + + assert( pParentBucket != nullptr ); + + // Allocate a dummy node for new bucket + { + dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) ); + if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { + m_Buckets.bucket( nBucket, pBucket ); + m_Stat.onNewBucket(); + return pBucket; + } + free_dummy_node( pBucket ); + } + + // Another thread set the bucket. Wait while it done + + // In this point, we must wait while nBucket is empty. + // The compiler can decide that waiting loop can be "optimized" (stripped) + // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer. + m_Stat.onBucketInitContenton(); + back_off bkoff; + while ( true ) { + dummy_node_type volatile * p = m_Buckets.bucket( nBucket ); + if ( p != nullptr ) + return const_cast(p); + bkoff(); + m_Stat.onBusyWaitBucketInit(); + } + } + + dummy_node_type * get_bucket( size_t nHash ) + { + size_t nBucket = bucket_no( nHash ); + + dummy_node_type * pHead = m_Buckets.bucket( nBucket ); + if ( pHead == nullptr ) + pHead = init_bucket( nBucket ); + + assert( pHead->is_dummy() ); + + return pHead; + } + + void init() + { + // GC and OrderedList::gc must be the same + static_assert(std::is_same::value, "GC and OrderedList::gc must be the same"); + + // atomicity::empty_item_counter is not allowed as a item counter + static_assert(!std::is_same::value, + "cds::atomicity::empty_item_counter is not allowed as a item counter"); + + // Initialize bucket 0 + dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ ); + + // insert_aux_node cannot return false for empty list + CDS_VERIFY( m_List.insert_aux_node( pNode ) ); + + m_Buckets.bucket( 0, pNode ); + } + + static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor ) + { + return nBucketCount * nLoadFactor; + } + + void inc_item_count() + { + size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed ); + if ( ++m_ItemCounter <= nMaxCount ) + return; + + size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed ); + const size_t nBucketCount = static_cast(1) << sz; + if ( nBucketCount < m_Buckets.capacity() ) { + // we may grow the bucket table + const size_t nLoadFactor = m_Buckets.load_factor(); + if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) ) + return; // someone already have updated m_nBucketCountLog2, so stop here + + m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), + memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); + m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); + } + else + m_nMaxItemCount.store( std::numeric_limits::max(), memory_model::memory_order_relaxed ); + } + + template + bool find_( Q& val, Compare cmp, Func f ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + return m_Stat.onFind( + m_List.find_at( pHead, sv, cmp, + [&f]( value_type& item, split_list::details::search_value_type& val ) { f( item, val.val ); } ) + ); + } + + template + bool find_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ) ); + } + + template + guarded_ptr get_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + guarded_ptr gp = m_List.get_at( pHead, sv, cmp ); + m_Stat.onFind( !gp.empty() ); + return gp; + } + + template + guarded_ptr get_( Q const& key ) + { + return get_( key, key_comparator() ); + } + + template + guarded_ptr get_with_( Q const& key, Less ) + { + return get_( key, typename wrapped_ordered_list::template make_compare_from_less() ); + } + + template + bool erase_( Q const& val, Compare cmp, Func f ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + if ( m_List.erase_at( pHead, sv, cmp, f ) ) { + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return true; + } + m_Stat.onEraseFailed(); + return false; + } + + template + bool erase_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + if ( m_List.erase_at( pHead, sv, cmp ) ) { + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return true; + } + m_Stat.onEraseFailed(); + return false; + } + + template + guarded_ptr extract_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash ) ); + dummy_node_type * pHead = get_bucket( nHash ); + assert( pHead != nullptr ); + + guarded_ptr gp = m_List.extract_at( pHead, sv, cmp ); + if ( gp ) { + --m_ItemCounter; + m_Stat.onExtractSuccess(); + } + else + m_Stat.onExtractFailed(); + return gp; + } + + template + guarded_ptr extract_( Q const& key ) + { + return extract_( key, key_comparator() ); + } + + template + guarded_ptr extract_with_( Q const& key, Less ) + { + return extract_( key, typename wrapped_ordered_list::template make_compare_from_less() ); + } + //@endcond + + protected: + //@cond + ordered_list_wrapper m_List; ///< Ordered list containing split-list items + bucket_table m_Buckets; ///< bucket table + atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + stat m_Stat; ///< Internal statistics + //@endcond }; }} // namespace cds::intrusive -- 2.34.1