-//$$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
/// CuckooSet-related definitions
namespace cuckoo {
- //@cond
- struct implementation_tag;
- //@endcond
-
/// Option to define probeset type
/**
The option specifies probeset type for the CuckooSet.
//@endcond
//@cond
- // Probeset type declarations.
+ /// List probeset type
struct list;
+ //@endcond
+
+ /// Vector probeset type
template <unsigned int Capacity>
struct vector
{
+ /// Vector capacity
static unsigned int const c_nCapacity = Capacity;
};
- //@endcond
/// CuckooSet node
/**
{
m_pNext = nullptr;
}
-
};
template <unsigned int VectorSize, typename Tag>
{
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_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
- counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
- counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
- counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
- counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
+ counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
+ 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; }
void onInsertRelocate() { ++m_nInsertRelocateCount; }
void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
- void onEnsureExist() { ++m_nEnsureExistCount; }
- void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
- void onEnsureResize() { ++m_nEnsureResizeCount; }
- void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
- void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
+ void onUpdateExist() { ++m_nUpdateExistCount; }
+ void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
+ void onUpdateResize() { ++m_nUpdateResizeCount; }
+ void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
+ void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
void onUnlinkFailed() { ++m_nUnlinkFailed; }
void onInsertRelocate() const {}
void onInsertRelocateFault() const {}
- void onEnsureExist() const {}
- void onEnsureSuccess() const {}
- void onEnsureResize() const {}
- void onEnsureRelocate() const {}
- void onEnsureRelocateFault() const {}
+ void onUpdateExist() const {}
+ void onUpdateSuccess() const {}
+ void onUpdateResize() const {}
+ void onUpdateRelocate() const {}
+ void onUpdateRelocateFault() const {}
void onUnlinkSuccess() const {}
void onUnlinkFailed() const {}
{
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
/// node disposer
typedef typename traits::disposer disposer;
- //@cond
- typedef cds::intrusive::cuckoo::implementation_tag implementation_tag;
- //@endcond
protected:
//@cond
typedef typename node_type::probeset_class probeset_class;
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 )
{
cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
- //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
}
static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
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 unsigned int const c_nUndefTable = (unsigned int) -1;
+ static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
template <typename Q, typename Predicate >
unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
{
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;
}
}
return true;
}
- /// Ensures that the \p val exists in the set
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val not found in the set, then \p val is inserted into the set.
+ If the item \p val is not found in the set, then \p val is inserted into the set
+ iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor signature is:
+ The functor \p func signature is:
\code
void func( bool bNew, value_type& item, value_type& val );
\endcode
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- \p item - item of the set
- - \p val - argument \p val passed into the \p ensure function
+ - \p val - argument \p val passed into the \p %update() function
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
- refers to the same thing.
+ refer to the same thing.
The functor may change non-key fields of the \p item.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
+ 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 is in the set.
+ already exists.
*/
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
{
hash_array arrHash;
position arrPos[ c_nArity ];
{
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.onEnsureExist();
+ m_Stat.onUpdateExist();
return std::make_pair( true, false );
}
- node_type * pNode = node_traits::to_node_ptr( val );
- store_hash( pNode, arrHash );
+ if ( !bAllowInsert )
+ return std::make_pair( false, false );
+
+ //node_type * pNode = node_traits::to_node_ptr( val );
+ //store_hash( pNode, arrHash );
for ( unsigned int i = 0; i < c_nArity; ++i ) {
bucket_entry& refBucket = bucket( i, arrHash[i] );
refBucket.insert_after( arrPos[i].itPrev, pNode );
func( true, val, val );
++m_ItemCounter;
- m_Stat.onEnsureSuccess();
+ m_Stat.onUpdateSuccess();
return std::make_pair( true, true );
}
}
++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;
}
}
}
- m_Stat.onEnsureResize();
+ m_Stat.onUpdateResize();
resize();
}
do_relocate:
- m_Stat.onEnsureRelocate();
+ m_Stat.onUpdateRelocate();
if ( !relocate( nGoalTable, arrHash )) {
- m_Stat.onEnsureRelocateFault();
- m_Stat.onEnsureResize();
+ m_Stat.onUpdateRelocateFault();
+ m_Stat.onUpdateResize();
resize();
}
- m_Stat.onEnsureSuccess();
+ m_Stat.onUpdateSuccess();
return std::make_pair( true, true );
}
+ //@cond
+ 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 );
+ }
+ //@endcond
/// Unlink the item \p val from the set
/**
{
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_( val, key_predicate(), f );
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& val, Func f )
+ {
+ return find_( val, key_predicate(), f );
+ }
+ //@endcond
/// Find the key \p val using \p pred predicate for comparing
/**
CDS_UNUSED( pred );
return find_( val, typename predicate_wrapper<Predicate>::type(), f );
}
-
- /// Find the key \p val
- /** \anchor cds_intrusive_CuckooSet_find_cfunc
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- The functor may change non-key fields of \p item.
-
- The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
- may modify both arguments.
-
- The function returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f )
- {
- return find_( val, key_predicate(), f );
- }
-
- /// Find the key \p val using \p pred predicate for comparing
- /**
- The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the set.
- */
+ //@cond
template <typename Q, typename Predicate, typename Func>
bool find_with( Q const& val, Predicate pred, Func f )
{
CDS_UNUSED( pred );
return find_( val, typename predicate_wrapper<Predicate>::type(), f );
}
+ //@endcond
- /// Find the key \p val
- /** \anchor cds_intrusive_CuckooSet_find_val
- The function searches the item with key equal to \p val
+ /// Checks whether the set contains \p key
+ /**
+ The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
- bool find( Q const& val )
+ bool contains( Q const& key )
{
- return find( val, [](value_type&, Q const& ) {} );
+ return find( key, [](value_type&, Q const& ) {} );
}
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key )
+ {
+ return contains( key );
+ }
+ //@endcond
- /// Find the key \p val using \p pred predicate for comparing
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the set.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ 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 find_with( Q const& val, Predicate pred )
+ bool contains( Q const& key, Predicate pred )
{
CDS_UNUSED( pred );
- return find_with(
val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
+ return find_with(
key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
}
+ //@cond
+ template <typename Q, typename Predicate>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Predicate pred )
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// 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