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:
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_SPLIT_LIST_RCU_H
#include <cds/intrusive/details/split_list_base.h>
#include <cds/details/binary_functor_wrapper.h>
+#include <cds/details/type_padding.h>
namespace cds { namespace intrusive {
The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
the comparing functor for the type \p T and other features specific for the ordered list.
- \p Traits - set traits, default isd \p split_list::traits.
- Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
+ Instead of defining \p Traits struct you can use option-based syntax provided by \p split_list::make_traits metafunction.
@note About required features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
protected:
//@cond
- typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
+ typedef split_list::details::rebind_list_traits<OrderedList, traits> ordered_list_adapter;
//@endcond
public:
# ifdef CDS_DOXYGEN_INVOKED
typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
# else
- typedef typename wrapped_ordered_list::result ordered_list;
+ typedef typename ordered_list_adapter::result ordered_list;
# endif
typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
typedef typename traits::stat stat; ///< Internal statistics
+ // GC and OrderedList::gc must be the same
+ static_assert( std::is_same<gc, typename ordered_list::gc>::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<item_counter, cds::atomicity::empty_item_counter>::value,
+ "cds::atomicity::empty_item_counter is not allowed as a item counter");
+
protected:
+ //@cond
typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
typedef split_list::node<list_node_type> node_type; ///< split-list node type
- typedef node_type dummy_node_type; ///< dummy node type
/// Split-list node traits
/**
This traits is intended for converting between underlying ordered list node type \ref list_node_type
and split-list node type \ref node_type
*/
- typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
+ typedef typename ordered_list_adapter::node_traits node_traits;
- //@cond
/// Bucket table implementation
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , dummy_node_type
+ , typename ordered_list_adapter::aux_node
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
+ , opt::free_list< typename traits::free_list >
>::type bucket_table;
+ typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
+
//@endcond
protected:
typedef typename base_class::auxiliary_head bucket_head_type;
public:
- bool insert_at( dummy_node_type * pHead, value_type& val )
+ bool insert_at( aux_node_type * pHead, value_type& val )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Func>
- bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
+ bool insert_at( aux_node_type * pHead, value_type& val, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Func>
- std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
+ std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
return base_class::update_at( h, val, func, bAllowInsert );
}
- bool unlink_at( dummy_node_type * pHead, value_type& val )
+ bool unlink_at( aux_node_type * pHead, value_type& val )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare, typename Func>
- bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
+ bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
+ bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+ value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare, typename Func>
- bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
+ bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
+ bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+ raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
return base_class::get_at( h, val, cmp );
}
- bool insert_aux_node( dummy_node_type * pNode )
+ bool insert_aux_node( aux_node_type * pNode )
{
return base_class::insert_aux_node( pNode );
}
- bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
+ bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
{
bucket_head_type h(pHead);
return base_class::insert_aux_node( h, pNode );
};
//@endcond
- protected:
- ordered_list_wrapper m_List; ///< Ordered list containing split-list items
- bucket_table m_Buckets; ///< bucket table
- atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
- atomics::atomic<size_t> 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 accumulator
-
- 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 <typename Q>
- 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<dummy_node_type *>( 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<gc, typename ordered_list::gc>::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<item_counter, cds::atomicity::empty_item_counter>::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<size_t>(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<size_t>::max(), memory_model::memory_order_relaxed );
- }
-
- template <typename Q, typename Compare, typename Func>
- bool find_( Q& val, Compare cmp, Func f )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q> 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<Q>& val){ f(item, val.val ); }));
- }
-
- template <typename Q, typename Compare>
- bool find_value( Q const& val, Compare cmp )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> 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 <typename Q, typename Compare>
- raw_ptr get_( Q const& val, Compare cmp )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
- dummy_node_type * pHead = get_bucket( nHash );
- assert( pHead != nullptr );
-
- raw_ptr p = m_List.get_at( pHead, sv, cmp );
- m_Stat.onFind( !!p );
- return p;
- }
-
- template <typename Q, typename Compare>
- value_type * extract_( Q const& val, Compare cmp )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
- dummy_node_type * pHead = get_bucket( nHash );
- assert( pHead != nullptr );
-
- value_type * pNode = m_List.extract_at( pHead, sv, cmp );
- if ( pNode ) {
- --m_ItemCounter;
- m_Stat.onExtractSuccess();
- }
- else
- m_Stat.onExtractFailed();
- return pNode;
- }
-
- template <typename Q, typename Less>
- value_type * extract_with_( Q const& val, Less pred )
- {
- CDS_UNUSED( pred );
- return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
- }
-
- template <typename Q, typename Compare>
- bool erase_( const Q& val, Compare cmp )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> 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 <typename Q, typename Compare, typename Func>
- bool erase_( Q const& val, Compare cmp, Func f )
- {
- size_t nHash = hash_value( val );
- split_list::details::search_value_type<Q const> 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;
- }
-
- //@endcond
-
public:
/// Initialize split-ordered list of default capacity
/**
*/
SplitListSet()
: m_nBucketCountLog2(1)
- , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
{
init();
}
)
: m_Buckets( nItemCount, nLoadFactor )
, m_nBucketCountLog2(1)
- , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
{
init();
}
+ /// Destroys split-list
+ ~SplitListSet()
+ {
+ m_List.clear();
+ gc::force_dispose();
+ }
+
public:
/// Inserts new node
/**
bool insert( value_type& val )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
bool insert( value_type& val, Func f )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
bool unlink( value_type& val )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- if ( m_List.unlink_at( pHead, val ) ) {
+ if ( m_List.unlink_at( pHead, val )) {
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
template <typename Q>
bool erase( Q const& key )
{
- return erase_( key, key_comparator() );
+ return erase_( key, key_comparator());
}
/// Deletes the item from the set using \p pred for searching
bool erase_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
+ return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
}
/// Deletes the item from the set
bool erase_with( Q const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
+ return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
}
/// Extracts an item from the set
template <typename Q>
exempt_ptr extract( Q const& key )
{
- return exempt_ptr(extract_( key, key_comparator() ));
+ return exempt_ptr(extract_( key, key_comparator()));
}
/// Extracts an item from the set using \p pred for searching
bool find_with( Q& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
+ return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
}
//@cond
template <typename Q, typename Less, typename Func>
bool find_with( Q const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
+ return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
}
//@endcond
template <typename Q>
bool contains( Q const& key )
{
- return find_value( key, key_comparator() );
+ return find_value( key, key_comparator());
}
//@cond
template <typename Q>
bool contains( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
+ return find_value( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
}
//@cond
template <typename Q, typename Less>
template <typename Q>
raw_ptr get( Q const& key )
{
- return get_( key, key_comparator() );
+ return get_( key, key_comparator());
}
/// Finds the key \p key and return the item found
raw_ptr get_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
+ return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
}
void clear()
{
iterator it = begin();
- while ( it != end() ) {
+ while ( it != end()) {
iterator i(it);
++i;
unlink( *it );
*/
iterator begin()
{
- return iterator( m_List.begin(), m_List.end() );
+ return iterator( m_List.begin(), m_List.end());
}
/// Returns an iterator that addresses the location succeeding the last element in a split-list
*/
iterator end()
{
- return iterator( m_List.end(), m_List.end() );
+ return iterator( m_List.end(), m_List.end());
}
/// Returns a forward const iterator addressing the first element in a split-list
/// Returns a forward const iterator addressing the first element in a split-list
const_iterator cbegin() const
{
- return const_iterator( m_List.cbegin(), m_List.cend() );
+ return const_iterator( m_List.cbegin(), m_List.cend());
}
/// Returns an const iterator that addresses the location succeeding the last element in a split-list
/// Returns an const iterator that addresses the location succeeding the last element in a split-list
const_iterator cend() const
{
- return const_iterator( m_List.cend(), m_List.cend() );
+ return const_iterator( m_List.cend(), m_List.cend());
}
//@}
+
+ protected:
+ //@cond
+ aux_node_type * alloc_aux_node( size_t nHash )
+ {
+ m_Stat.onHeadNodeAllocated();
+ aux_node_type* p = m_Buckets.alloc_aux_node();
+ if ( p )
+ p->m_nHash = nHash;
+ return p;
+ }
+
+ void free_aux_node( aux_node_type * p )
+ {
+ m_Buckets.free_aux_node( p );
+ m_Stat.onHeadNodeFreed();
+ }
+
+ /// Calculates hash value of \p key
+ template <typename Q>
+ 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 ));
+ }
+
+ aux_node_type * init_bucket( size_t const nBucket )
+ {
+ assert( nBucket > 0 );
+ size_t nParent = parent_bucket( nBucket );
+
+ aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
+ if ( pParentBucket == nullptr ) {
+ pParentBucket = init_bucket( nParent );
+ m_Stat.onRecursiveInitBucket();
+ }
+
+ assert( pParentBucket != nullptr );
+
+ // Allocate an aux node for new bucket
+ aux_node_type * pBucket = m_Buckets.bucket( nBucket );
+
+ back_off bkoff;
+ for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
+ if ( pBucket )
+ return pBucket;
+
+ pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
+ if ( pBucket ) {
+ if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
+ m_Buckets.bucket( nBucket, pBucket );
+ m_Stat.onNewBucket();
+ return pBucket;
+ }
+
+ // Another thread set the bucket. Wait while it done
+ free_aux_node( pBucket );
+ m_Stat.onBucketInitContenton();
+ break;
+ }
+
+ // There are no free buckets. It means that the bucket table is full
+ // Wait while another thread set the bucket or a free bucket will be available
+ m_Stat.onBucketsExhausted();
+ bkoff();
+ }
+
+ // Another thread set the bucket. Wait while it done
+ for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
+ bkoff();
+ m_Stat.onBusyWaitBucketInit();
+ }
+
+ return pBucket;
+ }
+
+ aux_node_type * get_bucket( size_t nHash )
+ {
+ size_t nBucket = bucket_no( nHash );
+
+ aux_node_type * pHead = m_Buckets.bucket( nBucket );
+ if ( pHead == nullptr )
+ pHead = init_bucket( nBucket );
+
+ assert( pHead->is_dummy());
+
+ return pHead;
+ }
+
+ void init()
+ {
+ // Initialize bucket 0
+ aux_node_type * pNode = alloc_aux_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<size_t>(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<size_t>::max(), memory_model::memory_order_relaxed );
+ }
+
+ template <typename Q, typename Compare, typename Func>
+ bool find_( Q& val, Compare cmp, Func f )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
+ aux_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<Q>& val){ f(item, val.val ); }));
+ }
+
+ template <typename Q, typename Compare>
+ bool find_value( Q const& val, Compare cmp )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ aux_node_type * pHead = get_bucket( nHash );
+ assert( pHead != nullptr );
+
+ return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
+ }
+
+ template <typename Q, typename Compare>
+ raw_ptr get_( Q const& val, Compare cmp )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ aux_node_type * pHead = get_bucket( nHash );
+ assert( pHead != nullptr );
+
+ raw_ptr p = m_List.get_at( pHead, sv, cmp );
+ m_Stat.onFind( !!p );
+ return p;
+ }
+
+ template <typename Q, typename Compare>
+ value_type * extract_( Q const& val, Compare cmp )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ aux_node_type * pHead = get_bucket( nHash );
+ assert( pHead != nullptr );
+
+ value_type * pNode = m_List.extract_at( pHead, sv, cmp );
+ if ( pNode ) {
+ --m_ItemCounter;
+ m_Stat.onExtractSuccess();
+ }
+ else
+ m_Stat.onExtractFailed();
+ return pNode;
+ }
+
+ template <typename Q, typename Less>
+ value_type * extract_with_( Q const& val, Less pred )
+ {
+ CDS_UNUSED( pred );
+ return extract_( val, typename ordered_list_adapter::template make_compare_from_less<Less>());
+ }
+
+ template <typename Q, typename Compare>
+ bool erase_( const Q& val, Compare cmp )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ aux_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 <typename Q, typename Compare, typename Func>
+ bool erase_( Q const& val, Compare cmp, Func f )
+ {
+ size_t nHash = hash_value( val );
+ split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
+ aux_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;
+ }
+ //@endcond
+
+ protected:
+ //@cond
+ static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
+
+ typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
+ padded_bucket_table m_Buckets; ///< bucket table
+
+ typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
+ padded_ordered_list m_List; ///< Ordered list containing split-list items
+
+ atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
+ atomics::atomic<size_t> 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 accumulator
+ //@endcond
};
}} // namespace cds::intrusive