-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
#ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
#define CDSLIB_INTRUSIVE_CUCKOO_SET_H
{
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 >
protected:
//@cond
- lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
+ lock_array m_Locks[c_nArity] ; ///< array of \p lock_array_type
statistics_type m_Stat ; ///< internal statistics
//@endcond
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();
}
for ( unsigned int i = 0; i < c_nArity; ++i )
pNew[i] = create_lock_array( nCapacity );
- /*
- // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
- // that is unacceptable under spin-lock
- // So, we store copy of m_arrLocks in pOld
- lock_array_ptr pOld[ c_nArity ];
- for ( unsigned int i = 0; i < c_nArity; ++i )
- pOld[i] = m_arrLocks[i];
-
- // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
- // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
- */
-
{
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();
}
}
};
- /// CuckooSet internal statistics
+ /// \p CuckooSet internal statistics
struct stat {
typedef cds::atomicity::event_counter counter_type ; ///< Counter type
- counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
+ counter_type m_nRelocateCallCount ; ///< Count of \p relocate() function call
counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
- counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
+ counter_type m_nSuccessRelocateCount ; ///< Count of successful item relocating
counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
- counter_type m_nResizeCallCount ; ///< Count of \p resize function call
- counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
- counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
- counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
+ counter_type m_nResizeCallCount ; ///< Count of \p resize() function call
+ counter_type m_nFalseResizeCount ; ///< Count of false \p resize() function call (when other thread has been resized the set)
+ counter_type m_nResizeSuccessNodeMove; ///< Count of successful node moving when resizing
+ counter_type m_nResizeRelocateCall ; ///< Count of \p relocate() function call from \p resize function
- counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
- counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
- counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
- counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
- counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
+ counter_type m_nInsertSuccess ; ///< Count of successful \p insert() function call
+ counter_type m_nInsertFailed ; ///< Count of failed \p insert() function call
+ counter_type m_nInsertResizeCount ; ///< Count of \p resize() function call from \p insert()
+ counter_type m_nInsertRelocateCount ; ///< Count of \p relocate() function call from \p insert()
+ counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate() function call from \p insert()
counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
- counter_type m_nUpdateSuccessCount ; ///< Count of successfull \p insert function call for new node
- counter_type m_nUpdateResizeCount ; ///< Count of \p resize function call from \p update()
- counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate function call from \p update()
- counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate function call from \p update()
+ counter_type m_nUpdateSuccessCount ; ///< Count of successful \p insert() function call for new node
+ counter_type m_nUpdateResizeCount ; ///< Count of \p resize() function call from \p update()
+ counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate() function call from \p update()
+ counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate() function call from \p update()
- counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
- counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
+ counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink() function call
+ counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink() function call
- counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
- counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
+ counter_type m_nEraseSuccess ; ///< Count of success \p erase() function call
+ counter_type m_nEraseFailed ; ///< Count of failed \p erase() function call
- counter_type m_nFindSuccess ; ///< Count of success \p find function call
- counter_type m_nFindFailed ; ///< Count of failed \p find function call
+ counter_type m_nFindSuccess ; ///< Count of success \p find() function call
+ counter_type m_nFindFailed ; ///< Count of failed \p find() function call
- counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
- counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
+ counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal() function call
+ counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal() function call
- counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
- counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
+ counter_type m_nFindWithSuccess ; ///< Count of success \p find_with() function call
+ counter_type m_nFindWithFailed ; ///< Count of failed \p find_with() function call
//@cond
void onRelocateCall() { ++m_nRelocateCallCount; }
{
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;
};
template <typename Node, unsigned int Capacity>
- class bucket_entry<Node, cuckoo::vector<Capacity> >
+ class bucket_entry<Node, cuckoo::vector<Capacity>>
{
public:
typedef Node node_type;
{
assert( m_nSize < c_nCapacity );
- // std alorithm
if ( nFrom < m_nSize )
std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
-
- // alternative: low-level byte copying
- //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
}
void shift_down( node_type ** pFrom )
{
assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
- // std algo
- std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
-
- // alternative: low-level byte copying
- //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
+ std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
}
public:
class iterator
assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
if ( it.pArr ) {
- shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
- *(it.pArr + 1) = p;
+ shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
+ it.pArr[1] = p;
}
else {
shift_up(0);
struct hash_ops {
static void store( Node * pNode, size_t * pHashes )
{
- memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
+ memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
}
static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
{
<b>About Cuckoo hashing</b>
[From <i>"The Art of Multiprocessor Programming"</i>]
- Cuckoo hashing 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
+ <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 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,
the average search complexity is <tt>O(PROBE_SET/2)</tt>.
However, the overhead of sorting can eliminate a gain of ordered search.
- The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
- parameter. Otherwise, the probe set is unordered and \p Traits must contain
- opt::equal_to option.
+ The probe set is ordered if \p compare or \p less is specified in \p Traits template
+ parameter. Otherwise, the probe set is unordered and \p Traits should provide
+ \p equal_to predicate.
- The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
+ The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
Template arguments:
- - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
- or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
- or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
- - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
+ - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
+ or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
+ or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
+ - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
<b>How to use</b>
typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
- /// Actual mutex policy
- /**
- Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
- but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
- - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
- - otherwise real mutex policy statistics is used
- */
+ //@cond
typedef typename original_mutex_policy::template rebind_statistics<
typename std::conditional<
std::is_same< stat, cuckoo::empty_stat >::value
,typename original_mutex_policy::real_stat
>::type
>::other mutex_policy;
+ //@endcond
+ /// Probe set should be ordered or not
+ /**
+ If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
+ Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
+ */
static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
- && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
+ && std::is_same< typename traits::less, opt::none >::value );
static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
/// Key equality functor; used only for unordered probe-set
typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
- /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
+ /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
/// allocator type
bucket_iterator itFound;
};
- typedef typename std::conditional< c_isSorted
- , cuckoo::details::contains< node_traits, true >
- , cuckoo::details::contains< node_traits, false >
- >::type contains_action;
+ typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
template <typename Predicate>
struct predicate_wrapper {
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
+ contains( arrPos, arrHash, val, key_predicate()) ; // must return 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;
CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
{
- return nProbesetSize
- ? nProbesetSize
- : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
-;
+ return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
+ ? node_type::probeset_size
+ : (nProbesetSize
+ ? nProbesetSize
+ : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
}
//@endcond
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 )
{
/// Constructs the set object with given probe set size and threshold
/**
If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
- then \p nProbesetSize should be equal to vector's \p Capacity.
+ then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size
- , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , 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 ))
{
/// Constructs the set object with given hash functor tuple
/**
- The probe set size and threshold are set as default, see CuckooSet()
+ The probe set size and threshold are set as default, see \p CuckooSet()
*/
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 )
then \p nProbesetSize should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size, positive integer
- , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , 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 ))
/// Constructs the set object with given hash functor tuple (move semantics)
/**
- The probe set size and threshold are set as default, see CuckooSet()
+ The probe set size and threshold are set as default, see \p CuckooSet()
*/
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();
then \p nProbesetSize should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size, positive integer
- , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , 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();
public:
/// Inserts new node
/**
- The function inserts \p val in the set if it does not contain
- an item with key equal to \p val.
+ The function inserts \p val in the set if it does not contain an item with key equal to \p val.
- Returns \p true if \p val is placed into the set, \p false otherwise.
+ Returns \p true if \p val is inserted into the set, \p false otherwise.
*/
bool insert( value_type& val )
{
{
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;
}
}
The functor may change non-key fields of the \p item.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
i.e. the node has been inserted or updated,
\p second is \p true if new item has been added or \p false if the item with \p key
already exists.
{
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;
}
}
return std::make_pair( true, true );
}
//@cond
- // Deprecated, use update()
template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
std::pair<bool, bool> ensure( value_type& val, Func func )
{
return update( val, func, true );
{
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;
return find( key, [](value_type&, Q const& ) {} );
}
//@cond
- // Deprecated, use contains()
template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( Q const& key )
{
return contains( key );
/// Checks whether the set contains \p key using \p pred predicate for searching
/**
The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
- \p Less functor has the interface like \p std::less.
- \p Less must imply the same element order as the comparator used for building the set.
+ If the set is unordered, \p Predicate has semantics like \p std::equal_to.
+ For ordered set \p Predicate has \p std::less semantics. In that case \p pred
+ must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Predicate>
bool contains( Q const& key, Predicate pred )
return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
}
//@cond
- // Deprecated,use contains()
template <typename Q, typename Predicate>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find_with( Q const& key, Predicate pred )
{
return contains( key, pred );
/// Clears the set
/**
The function unlinks all items from the set.
- For any item \ref disposer 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
/**
- The function unlinks all items from the set calling \p disposer for each item.
+ The function unlinks all items from the set calling \p oDisposer for each item.
\p Disposer functor interface is:
\code
struct Disposer{
};
\endcode
- The \ref disposer specified in \p Traits 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