/*
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/
{
public:
// placeholder ctor
- lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
+ lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2)) {}
// real ctor
- lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
+ lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity)) {}
};
class scoped_lock: public std::unique_lock< lock_array_type >
if ( m_bLocked ) {
m_guard[0] = &(policy.m_Locks[0].at(nCell));
for ( unsigned int i = 1; i < c_nArity; ++i ) {
- m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
+ m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
}
}
else {
/// Refinable concurrent access policy
/**
- This is one of available opt::mutex_policy option type for CuckooSet
+ This is one of available \p opt::mutex_policy option type for \p CuckooSet
- Refining is like a striping technique (see cuckoo::striping)
+ Refining is like a striping technique (see \p cuckoo::striping)
but it allows growing the size of lock array when resizing the hash table.
So, the sizes of hash table and lock array are equal.
The default is \p std::recursive_mutex. The mutex type should be default-constructible.
- \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
count of lock arrays. Default value is 2.
- - \p BackOff - back-off strategy. Default is cds::backoff::yield
+ - \p BackOff - back-off strategy. Default is \p cds::backoff::Default
- \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
- \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
class according to its \p opt::stat option.
template <
class RecursiveLock = std::recursive_mutex,
unsigned int Arity = 2,
- typename BackOff = cds::backoff::yield,
+ typename BackOff = cds::backoff::Default,
class Alloc = CDS_DEFAULT_ALLOCATOR,
class Stat = empty_refinable_stat
>
atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
- lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
- spinlock_type m_access ; ///< access to m_arrLocks
- statistics_type m_Stat ; ///< internal statistics
+ lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
+ spinlock_type m_access ; ///< access to m_arrLocks
+ statistics_type m_Stat ; ///< internal statistics
//@endcond
protected:
struct lock_array_disposer {
void operator()( lock_array_type * pArr )
{
+ // Seems, there is a false positive in std::shared_ptr deallocation in uninstrumented libc++
+ // see, for example, https://groups.google.com/forum/#!topic/thread-sanitizer/eHu4dE_z7Cc
+ // https://reviews.llvm.org/D21609
+ CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
lock_array_allocator().Delete( pArr );
+ CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
}
};
lock_array_ptr create_lock_array( size_t nCapacity )
{
- return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
+ return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer());
}
void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
{
owner_t me = (owner_t) cds::OS::get_current_thread_id();
owner_t who;
+ size_t cur_capacity;
back_off bkoff;
while ( true ) {
scoped_spinlock sl(m_access);
for ( unsigned int i = 0; i < c_nArity; ++i )
pLockArr[i] = m_arrLocks[i];
+ cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
}
// wait while resizing
while ( true ) {
who = m_Owner.load( atomics::memory_order_acquire );
- if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
+ if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask))
break;
bkoff();
m_Stat.onCellWaitResizing();
}
- if ( pLockArr[0] != m_arrLocks[0] ) {
- m_Stat.onCellArrayChanged();
- }
- else {
+ if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
size_t const nMask = pLockArr[0]->size() - 1;
assert( cds::beans::is_power2( nMask + 1 ));
}
who = m_Owner.load( atomics::memory_order_acquire );
- if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
+ if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask)) && cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
m_Stat.onCellLock();
return;
}
- for ( unsigned int i = 0; i < c_nArity; ++i ) {
+ for ( unsigned int i = 0; i < c_nArity; ++i )
parrLock[i]->unlock();
- }
m_Stat.onCellLockFailed();
}
+ else
+ m_Stat.onCellArrayChanged();
// clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
// (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
// It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
- // Destructing a lot of mutexes under spin-lock is a bad solution
+ // However, destructing a lot of mutexes under spin-lock is a bad solution
for ( unsigned int i = 0; i < c_nArity; ++i )
pLockArr[i].reset();
}
parrLock[0] = &(m_arrLocks[0]->at(nCell));
for ( unsigned int i = 1; i < c_nArity; ++i ) {
- parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
+ parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)));
}
m_Stat.onSecondCellLock();
void acquire_resize( lock_array_ptr * pOldLocks )
{
owner_t me = (owner_t) cds::OS::get_current_thread_id();
+ size_t cur_capacity;
while ( true ) {
{
scoped_spinlock sl(m_access);
for ( unsigned int i = 0; i < c_nArity; ++i )
pOldLocks[i] = m_arrLocks[i];
+ cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
}
// global lock
owner_t ownNull = 0;
if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
- if ( pOldLocks[0] != m_arrLocks[0] ) {
- m_Owner.store( 0, atomics::memory_order_release );
- m_Stat.onResizeLockArrayChanged();
- }
- else {
+ if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
pOldLocks[0]->lock_all();
m_Stat.onResizeLock();
return;
}
+
+ m_Owner.store( 0, atomics::memory_order_release );
+ m_Stat.onResizeLockArrayChanged();
}
else
m_Stat.onResizeLockIter();
// clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
// (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
// It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
- // Destructing a lot of mutexes under spin-lock is a bad solution
+ // However, destructing a lot of mutexes under spin-lock is a bad solution
for ( unsigned int i = 0; i < c_nArity; ++i )
pOldLocks[i].reset();
}
{
scoped_spinlock sl(m_access);
+ m_nCapacity.store( nCapacity, atomics::memory_order_release );
for ( unsigned int i = 0; i < c_nArity; ++i )
m_arrLocks[i] = pNew[i];
}
- m_nCapacity.store( nCapacity, atomics::memory_order_release );
m_Stat.onResize();
}
{
node_type * pPrev = itPrev.pNode;
node_type * pWhat = itWhat.pNode;
- assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
+ assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat));
if ( pPrev )
pPrev->m_pNext = pWhat->m_pNext;
[From <i>"The Art of Multiprocessor Programming"</i>]
<a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
- occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
+ occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set of size
N = 2k we use a two-entry array of tables, and two independent hash functions,
<tt> h0, h1: KeyRange -> 0,...,k-1</tt>
mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
protected:
bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
- size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
- unsigned int const m_nProbesetSize ; ///< Probe set size
- unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
+ atomics::atomic<size_t> m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
+ unsigned int const m_nProbesetSize ; ///< Probe set size
+ unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
hash m_Hash ; ///< Hash functor tuple
mutex_policy m_MutexPolicy ; ///< concurrent access policy
bucket_entry& bucket( unsigned int nTable, size_t nHash )
{
assert( nTable < c_nArity );
- return m_BucketTable[nTable][nHash & m_nBucketMask];
+ return m_BucketTable[nTable][nHash & m_nBucketMask.load( atomics::memory_order_relaxed ) ];
}
static void store_hash( node_type * pNode, size_t * pHashes )
void allocate_bucket_tables( size_t nSize )
{
- assert( cds::beans::is_power2( nSize ) );
+ assert( cds::beans::is_power2( nSize ));
- m_nBucketMask = nSize - 1;
+ m_nBucketMask.store( nSize - 1, atomics::memory_order_release );
bucket_table_allocator alloc;
for ( unsigned int i = 0; i < c_nArity; ++i )
m_BucketTable[i] = alloc.NewArray( nSize );
}
void free_bucket_tables()
{
- free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
+ free_bucket_tables( m_BucketTable, m_nBucketMask.load( atomics::memory_order_relaxed ) + 1 );
}
static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
unsigned int nTable = contains( arrPos, arrHash, val, pred );
if ( nTable != c_nUndefTable ) {
node_type& node = *arrPos[nTable].itFound;
- f( *node_traits::to_value_ptr(node) );
+ f( *node_traits::to_value_ptr(node));
bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
}
- pVal = node_traits::to_value_ptr( *refBucket.begin() );
+ pVal = node_traits::to_value_ptr( *refBucket.begin());
copy_hash( arrHash, *pVal );
scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
- if ( !guard2.locked() )
+ if ( !guard2.locked())
continue ; // try one more time
- refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
+ refBucket.remove( typename bucket_entry::iterator(), refBucket.begin());
unsigned int i = (nTable + 1) % c_nArity;
bucket_entry& bkt = bucket( i, arrHash[i] );
if ( bkt.size() < m_nProbesetThreshold ) {
position pos;
- contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
+ contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
m_Stat.onSuccessRelocateRound();
return true;
bucket_entry& bkt = bucket( i, arrHash[i] );
if ( bkt.size() < m_nProbesetSize ) {
position pos;
- contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
+ contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
nTable = i;
memcpy( arrGoalHash, arrHash, sizeof(arrHash));
{
m_Stat.onResizeCall();
- size_t nOldCapacity = bucket_count();
+ size_t nOldCapacity = bucket_count( atomics::memory_order_acquire );
bucket_entry * pOldTable[ c_nArity ];
{
scoped_resize_lock guard( m_MutexPolicy );
- if ( nOldCapacity != bucket_count() ) {
+ if ( nOldCapacity != bucket_count()) {
m_Stat.onFalseResizeCall();
return;
}
memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
allocate_bucket_tables( nCapacity );
- typedef typename bucket_entry::iterator bucket_iterator;
hash_array arrHash;
position arrPos[ c_nArity ];
value_type& val = *node_traits::to_value_ptr( *it );
copy_hash( arrHash, val );
- contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
+ CDS_VERIFY_EQ( contains( arrPos, arrHash, val, key_predicate()), c_nUndefTable );
for ( unsigned int i = 0; i < c_nArity; ++i ) {
bucket_entry& refBucket = bucket( i, arrHash[i] );
if ( refBucket.size() < m_nProbesetSize ) {
refBucket.insert_after( arrPos[i].itPrev, &*it );
assert( refBucket.size() > 1 );
- copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
+ copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
m_Stat.onResizeRelocateCall();
relocate( i, arrHash );
break;
Probe set threshold = probe set size - 1
*/
CuckooSet()
- : m_nProbesetSize( calc_probeset_size(0) )
+ : m_nProbesetSize( calc_probeset_size(0))
, m_nProbesetThreshold( m_nProbesetSize - 1 )
, m_MutexPolicy( c_nDefaultInitialSize )
{
, unsigned int nProbesetSize ///< probe set size
, unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
)
- : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
+ : m_nProbesetSize( calc_probeset_size(nProbesetSize))
, m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
, m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
{
CuckooSet(
hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : m_nProbesetSize( calc_probeset_size(0) )
+ : m_nProbesetSize( calc_probeset_size(0))
, m_nProbesetThreshold( m_nProbesetSize -1 )
, m_Hash( h )
, m_MutexPolicy( c_nDefaultInitialSize )
, unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
, hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
+ : m_nProbesetSize( calc_probeset_size(nProbesetSize))
, m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
, m_Hash( h )
, m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
CuckooSet(
hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : m_nProbesetSize( calc_probeset_size(0) )
+ : m_nProbesetSize( calc_probeset_size(0))
, m_nProbesetThreshold( m_nProbesetSize / 2 )
- , m_Hash( std::forward<hash_tuple_type>(h) )
+ , m_Hash( std::forward<hash_tuple_type>(h))
, m_MutexPolicy( c_nDefaultInitialSize )
{
check_common_constraints();
, unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
, hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
+ : m_nProbesetSize( calc_probeset_size(nProbesetSize))
, m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
- , m_Hash( std::forward<hash_tuple_type>(h) )
+ , m_Hash( std::forward<hash_tuple_type>(h))
, m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
{
check_common_constraints();
{
scoped_cell_lock guard( m_MutexPolicy, arrHash );
- if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
+ if ( contains( arrPos, arrHash, val, key_predicate()) != c_nUndefTable ) {
m_Stat.onInsertFailed();
return false;
}
++m_ItemCounter;
nGoalTable = i;
assert( refBucket.size() > 1 );
- copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
+ copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
goto do_relocate;
}
}
{
scoped_cell_lock guard( m_MutexPolicy, arrHash );
- unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
+ unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
if ( nTable != c_nUndefTable ) {
func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
m_Stat.onUpdateExist();
++m_ItemCounter;
nGoalTable = i;
assert( refBucket.size() > 1 );
- copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
+ copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
goto do_relocate;
}
}
{
scoped_cell_lock guard( m_MutexPolicy, arrHash );
- unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
+ unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
--m_ItemCounter;
/// Clears the set
/**
The function unlinks all items from the set.
- For any item <tt> @ref disposer</tt> is called
+ For any item \p Traits::disposer is called
*/
void clear()
{
- clear_and_dispose( disposer() );
+ clear_and_dispose( disposer());
}
/// Clears the set and calls \p disposer for each item
};
\endcode
- The <tt> @ref disposer</tt> specified in \p Traits is not called.
+ The \p Traits::disposer is not called.
*/
template <typename Disposer>
void clear_and_dispose( Disposer oDisposer )
for ( unsigned int i = 0; i < c_nArity; ++i ) {
bucket_entry * pEntry = m_BucketTable[i];
- bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
+ bucket_entry * pEnd = pEntry + m_nBucketMask.load( atomics::memory_order_relaxed ) + 1;
for ( ; pEntry != pEnd ; ++pEntry ) {
pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
}
*/
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