#define CDSLIB_INTRUSIVE_SPLIT_LIST_H
#include <cds/intrusive/details/split_list_base.h>
+#include <limits>
namespace cds { namespace intrusive {
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
// 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 ) {
m_Buckets.bucket( 0, pNode );
}
- void inc_item_count()
+ 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;
+
+ const size_t nLoadFactor = m_Buckets.load_factor();
size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
- if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
- {
- m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
- }
+ const size_t nBucketCount = static_cast<size_t>(1) << sz;
+ if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
+ return; // someone already have updated m_nBucketCountLog2, so stop here
+
+ const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
+ : std::numeric_limits<size_t>::max();
+ m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
+ memory_model::memory_order_relaxed );
+ m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_seq_cst, memory_model::memory_order_relaxed );
}
template <typename Q, typename Compare, typename Func>
/// Initialize split-ordered list of default capacity
/**
The default capacity is defined in bucket table constructor.
- See \p split_list::expandable_bucket_table, \p split_list::static_ducket_table
+ See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
which selects by \p split_list::dynamic_bucket_table option.
*/
SplitListSet()
: m_nBucketCountLog2(1)
+ , 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()) )
{
init();
}