/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_STRIPED_SET_H
You should provide two different hash function \p h1 and \p h2 - one for \p boost::intrusive::unordered_set
and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. <tt>h1(X) != h2(X)</tt> for any value \p X
- The option \p opt::buffer is used for \p boost::intrusive::bucket_traits.
+ The option \p opt::buffer is used for \p boost::intrusive::bucket_traits.
Default is <tt> cds::opt::v::initialized_static_buffer< cds::any_type, 256 > </tt>.
The resizing policy should correlate with the buffer capacity.
The default resizing policy is <tt>cds::container::striped_set::load_factor_resizing<256> </tt> what gives load factor 1 for
typedef cds::details::Allocator< bucket_type, allocator_type > bucket_allocator; ///< bucket allocator type based on allocator_type
protected:
- bucket_type * m_Buckets ; ///< Bucket table
- size_t m_nBucketMask ; ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
- item_counter m_ItemCounter ; ///< Item counter
- hash m_Hash ; ///< Hash functor
+ bucket_type * m_Buckets; ///< Bucket table
+ atomics::atomic<size_t> m_nBucketMask; ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
+ item_counter m_ItemCounter; ///< Item counter
+ hash m_Hash; ///< Hash functor
mutex_policy m_MutexPolicy ; ///< Mutex policy
resizing_policy m_ResizingPolicy; ///< Resizing policy
void alloc_bucket_table( size_t nSize )
{
assert( cds::beans::is_power2( nSize ));
- m_nBucketMask = nSize - 1;
+ m_nBucketMask.store( nSize - 1, atomics::memory_order_release );
m_Buckets = bucket_allocator().NewArray( nSize );
}
bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
{
- return m_Buckets + (nHash & m_nBucketMask);
+ return m_Buckets + (nHash & m_nBucketMask.load( atomics::memory_order_relaxed ));
}
template <typename Q, typename Func>
for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
itNext = it;
++itNext;
- bucket( m_Hash( *it ) )->move_item( *pCur, it );
+ bucket( m_Hash( *it ))->move_item( *pCur, it );
}
pCur->clear();
}
void resize()
{
- size_t nOldCapacity = bucket_count();
- size_t volatile& refBucketMask = m_nBucketMask;
+ size_t nOldCapacity = bucket_count( atomics::memory_order_acquire );
scoped_resize_lock al( m_MutexPolicy );
- if ( al.success() ) {
- if ( nOldCapacity != refBucketMask + 1 ) {
+ if ( al.success()) {
+ if ( nOldCapacity != bucket_count( atomics::memory_order_acquire )) {
// someone resized already
return;
}
/// Default ctor. The initial capacity is 16.
StripedSet()
: m_Buckets( nullptr )
- , m_nBucketMask( c_nMinimalCapacity - 1 )
- , m_MutexPolicy( c_nMinimalCapacity )
+ , m_nBucketMask( c_nMinimalCapacity - 1 )
+ , m_MutexPolicy( c_nMinimalCapacity )
{
- alloc_bucket_table( m_nBucketMask + 1 );
+ alloc_bucket_table( bucket_count());
}
/// Ctor with initial capacity specified
StripedSet(
size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
)
- : m_Buckets( nullptr )
- , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
- , m_MutexPolicy( m_nBucketMask + 1 )
+ : m_Buckets( nullptr )
+ , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
+ , m_MutexPolicy( bucket_count())
{
- alloc_bucket_table( m_nBucketMask + 1 );
+ alloc_bucket_table( bucket_count());
}
/// Ctor with resizing policy (copy semantics)
)
: m_Buckets( nullptr )
, m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
- , m_MutexPolicy( m_nBucketMask + 1 )
+ , m_MutexPolicy( bucket_count())
, m_ResizingPolicy( resizingPolicy )
{
- alloc_bucket_table( m_nBucketMask + 1 );
+ alloc_bucket_table( bucket_count());
}
/// Ctor with resizing policy (move semantics)
)
: m_Buckets( nullptr )
, m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
- , m_MutexPolicy( m_nBucketMask + 1 )
- , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ) )
+ , m_MutexPolicy( bucket_count())
+ , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ))
{
- alloc_bucket_table( m_nBucketMask + 1 );
+ alloc_bucket_table( bucket_count());
}
/// Destructor destroys internal data
~StripedSet()
{
- free_bucket_table( m_Buckets, m_nBucketMask + 1 );
+ free_bucket_table( m_Buckets, bucket_count());
}
public:
*/
size_t bucket_count() const
{
- return m_nBucketMask + 1;
+ return m_nBucketMask.load( atomics::memory_order_relaxed ) + 1;
}
+ //@cond
+ size_t bucket_count( atomics::memory_order load_mo ) const
+ {
+ return m_nBucketMask.load( load_mo ) + 1;
+ }
+ //@endcond
/// Returns lock array size
size_t lock_count() const
projects / libcds.git / blobdiff