#include <limits>
#include <cds/intrusive/details/split_list_base.h>
+#include <cds/details/type_padding.h>
namespace cds { namespace intrusive {
//@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
+ typedef node_type aux_node_type; ///< dummy node type
/// Split-list node traits
/**
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , dummy_node_type
+ , aux_node_type
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
+ , opt::free_list< typename traits::free_list >
>::type bucket_table;
-
- typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
//@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>
- guarded_ptr extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
+ guarded_ptr extract_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, 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>
- guarded_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
+ guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& 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 );
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 )) {
protected:
//@cond
- dummy_node_type * alloc_dummy_node( size_t nHash )
+ aux_node_type * alloc_aux_node( size_t nHash )
{
m_Stat.onHeadNodeAllocated();
- return dummy_node_allocator().New( nHash );
+ aux_node_type* p = m_Buckets.alloc_aux_node();
+ if ( p )
+ p->m_nHash = nHash;
+ return p;
}
- void free_dummy_node( dummy_node_type * p )
+
+ void free_aux_node( aux_node_type * p )
{
- dummy_node_allocator().Delete( p );
+ m_Buckets.free_aux_node( p );
m_Stat.onHeadNodeFreed();
}
return nBucket & ~(1 << bitop::MSBnz( nBucket ));
}
- dummy_node_type * init_bucket( size_t nBucket )
+ aux_node_type * init_bucket( size_t nBucket )
{
assert( nBucket > 0 );
size_t nParent = parent_bucket( nBucket );
- dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
+ aux_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;
+ aux_node_type * pBucket;
+ if ( ( pBucket = m_Buckets.bucket( nBucket )) == nullptr ) {
+ 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;
+ }
+ else {
+ // Another thread set the bucket. Wait while it done
+ free_aux_node( pBucket );
+ }
+ }
+ else {
+ // There are no free buckets. It means that the bucket table is full
+ // Wait while another thread set th bucket
+ m_Stat.onBucketsExhausted();
}
- free_dummy_node( pBucket );
}
+ else
+ return 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 );
+ aux_node_type volatile * p = m_Buckets.bucket( nBucket );
if ( p != nullptr )
- return const_cast<dummy_node_type *>(p);
+ return const_cast<aux_node_type *>(p);
bkoff();
m_Stat.onBusyWaitBucketInit();
}
}
- dummy_node_type * get_bucket( size_t nHash )
+ aux_node_type * get_bucket( size_t nHash )
{
size_t nBucket = bucket_no( nHash );
- dummy_node_type * pHead = m_Buckets.bucket( nBucket );
+ aux_node_type * pHead = m_Buckets.bucket( nBucket );
if ( pHead == nullptr )
pHead = init_bucket( nBucket );
"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)*/ );
+ aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+ assert( pNode != nullptr );
// insert_aux_node cannot return false for empty list
CDS_VERIFY( m_List.insert_aux_node( pNode ) );
{
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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
return m_Stat.onFind(
{
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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
return m_Stat.onFind( m_List.find_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
guarded_ptr gp = m_List.get_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
if ( m_List.erase_at( pHead, sv, cmp, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
if ( m_List.erase_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
protected:
//@cond
- ordered_list_wrapper m_List; ///< Ordered list containing split-list items
- bucket_table m_Buckets; ///< bucket table
+ typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+ padded_bucket_table m_Buckets; ///< bucket table
+
+ typedef typename cds::details::type_padding< ordered_list_wrapper, traits::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
projects / libcds.git / blobdiff