-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
-#define __CDS_INTRUSIVE_CUCKOO_SET_H
+ (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
#include <memory>
#include <type_traits>
-#include <cds/intrusive/base.h>
+#include <mutex>
+#include <functional> // ref
+#include <cds/intrusive/details/base.h>
#include <cds/opt/compare.h>
#include <cds/opt/hash.h>
-#include <cds/lock/array.h>
-#include <cds/ref.h>
+#include <cds/sync/lock_array.h>
#include <cds/os/thread.h>
-#include <cds/details/functor_wrapper.h>
-#include <cds/lock/spinlock.h>
+#include <cds/sync/spinlock.h>
-#include <cds/details/std/mutex.h>
-//#include <boost/thread/recursive_mutex.hpp>
namespace cds { namespace intrusive {
/// CuckooSet-related definitions
namespace cuckoo {
-
/// 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
/**
or \p cds::intrusive::cuckoo::vector<Capacity>.
- \p StoreHashCount - constant that defines whether to store node hash values.
See cuckoo::store_hash option for explanation
- - Tag - a tag used to distinguish between different implementation when two or more
- \p node is needed in single struct.
+ - \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
struct node
{
m_pNext = nullptr;
}
-
};
template <unsigned int VectorSize, typename Tag>
typedef opt::none tag;
};
- template < typename HookType, CDS_DECL_OPTIONS3>
+ template < typename HookType, typename... Options>
struct hook
{
- typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options;
+ typedef typename opt::make_options< default_hook, Options...>::type traits;
- typedef typename options::probeset_type probeset_type;
- typedef typename options::tag tag;
- static unsigned int const store_hash = options::store_hash;
+ typedef typename traits::probeset_type probeset_type;
+ typedef typename traits::tag tag;
+ static unsigned int const store_hash = traits::store_hash;
typedef node<probeset_type, store_hash, tag> node_type;
/// Base hook
/**
\p Options are:
- - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
- - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
- - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+ - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+ - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < CDS_DECL_OPTIONS3 >
- struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
+ template < typename... Options >
+ struct base_hook: public hook< opt::base_hook_tag, Options... >
{};
/// Member hook
Use \p offsetof macro to define \p MemberOffset
\p Options are:
- - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
- - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
- - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+ - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+ - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
- struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
+ template < size_t MemberOffset, typename... Options >
+ struct member_hook: public hook< opt::member_hook_tag, Options... >
{
//@cond
static const size_t c_nMemberOffset = MemberOffset;
See \ref node_traits for \p NodeTraits interface description
\p Options are:
- - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
- - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
- - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+ - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+ - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template <typename NodeTraits, CDS_DECL_OPTIONS3 >
- struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
+ template <typename NodeTraits, typename... Options >
+ struct traits_hook: public hook< opt::traits_hook_tag, Options... >
{
//@cond
typedef NodeTraits node_traits;
The policy contains an internal array of \p RecursiveLock locks.
Template arguments:
- - \p RecursiveLock - the type of recursive mutex. The default is \p cds_std::recursive_mutex. The mutex type should be default-constructible.
+ - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
Note that a recursive spin-lock is not suitable for lock striping for performance reason.
- \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.
class according to its \p opt::stat option.
*/
template <
- class RecursiveLock = cds_std::recursive_mutex,
+ class RecursiveLock = std::recursive_mutex,
unsigned int Arity = 2,
class Alloc = CDS_DEFAULT_ALLOCATOR,
class Stat = empty_striping_stat
};
//@endcond
- typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
+ typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
protected:
//@cond
{
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 cds::lock::scoped_lock< lock_array_type >
+ class scoped_lock: public std::unique_lock< lock_array_type >
{
- typedef cds::lock::scoped_lock< lock_array_type > base_class;
+ typedef std::unique_lock< lock_array_type > base_class;
public:
scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
};
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 {
};
class scoped_full_lock {
- cds::lock::scoped_lock< lock_array_type > m_guard;
+ std::unique_lock< lock_array_type > m_guard;
public:
scoped_full_lock( striping& policy )
: m_guard( policy.m_Locks[0] )
/// 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.
Template arguments:
- \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
- The default is \p cds_std::recursive_mutex. The mutex type should be default-constructible.
+ 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 = cds_std::recursive_mutex,
+ 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
>
protected:
//@cond
- typedef cds::lock::trivial_select_policy lock_selection_policy;
+ typedef cds::sync::trivial_select_policy lock_selection_policy;
class lock_array_type
- : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
+ : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
, public std::enable_shared_from_this< lock_array_type >
{
- typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
+ typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
public:
lock_array_type( size_t nCapacity )
: lock_array_base( nCapacity )
typedef unsigned long long owner_t;
typedef cds::OS::ThreadId threadId_t;
- typedef cds::lock::Spin spinlock_type;
- typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
+ typedef cds::sync::spin spinlock_type;
+ typedef std::unique_lock< spinlock_type > scoped_spinlock;
//@endcond
protected:
//@cond
static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
- CDS_ATOMIC::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
- CDS_ATOMIC::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
+ 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
//@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::getCurrentThreadId();
+ 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( CDS_ATOMIC::memory_order_acquire );
- if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
+ who = m_Owner.load( atomics::memory_order_acquire );
+ 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 ));
parrLock[i]->lock();
}
- who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
- if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
+ who = m_Owner.load( atomics::memory_order_acquire );
+ 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();
}
// It is assumed that the current thread already has a lock
// and requires a second lock for other hash
- size_t const nMask = m_nCapacity.load(CDS_ATOMIC::memory_order_acquire) - 1;
+ size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
m_Stat.onSecondCellLockFailed();
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_all()
{
- owner_t me = (owner_t) cds::OS::getCurrentThreadId();
+ owner_t me = (owner_t) cds::OS::get_current_thread_id();
back_off bkoff;
while ( true ) {
owner_t ownNull = 0;
- if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
+ if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
m_arrLocks[0]->lock_all();
m_Stat.onFullLock();
void release_all()
{
m_arrLocks[0]->unlock_all();
- m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
+ m_Owner.store( 0, atomics::memory_order_release );
}
void acquire_resize( lock_array_ptr * pOldLocks )
{
- owner_t me = (owner_t) cds::OS::getCurrentThreadId();
+ 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, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
- if ( pOldLocks[0] != m_arrLocks[0] ) {
- m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
- m_Stat.onResizeLockArrayChanged();
- }
- else {
+ if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
+ 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();
}
void release_resize( lock_array_ptr * pOldLocks )
{
- m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
+ m_Owner.store( 0, atomics::memory_order_release );
pOldLocks[0]->unlock_all();
}
//@endcond
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, CDS_ATOMIC::memory_order_release );
m_Stat.onResize();
}
*/
size_t lock_count() const
{
- return m_nCapacity.load(CDS_ATOMIC::memory_order_relaxed);
+ return m_nCapacity.load(atomics::memory_order_relaxed);
}
/// Returns the arity of \p refinable mutex policy
}
};
- /// 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 {}
};
/// Type traits for CuckooSet class
- struct type_traits
+ struct traits
{
/// Hook used
/**
The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
\@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
- Up to 10 different hash functors are supported.
+
+ To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
+ \code
+ struct my_traits: public cds::intrusive::cuckoo::traits {
+ typedef cds::opt::hash_tuple< hash1, hash2 > hash;
+ };
+ \endcode
*/
typedef cds::opt::none hash;
/// Concurrent access policy
/**
Available opt::mutex_policy types:
- - cuckoo::striping - simple, but the lock array is not resizable
- - cuckoo::refinable - resizable lock array, but more complex access to set data.
+ - \p cuckoo::striping - simple, but the lock array is not resizable
+ - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
- Default is cuckoo::striping.
+ Default is \p cuckoo::striping.
*/
typedef cuckoo::striping<> mutex_policy;
*/
typedef opt::none equal_to;
- /// Key comparison functor
+ /// Key comparing functor
/**
No default functor is provided. If the option is not specified, the \p less is used.
*/
/// Item counter
/**
The type for item counting feature.
- Default is cds::atomicity::item_counter
+ Default is \p cds::atomicity::item_counter
Only atomic item counter type is allowed.
*/
/// Disposer
/**
- The disposer functor is used in CuckooSet::clear member function
+ The disposer functor is used in \p CuckooSet::clear() member function
to free set's node.
*/
typedef intrusive::opt::v::empty_disposer disposer;
- /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat
+ /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
typedef empty_stat stat;
};
- /// Metafunction converting option list to CuckooSet traits
+ /// Metafunction converting option list to \p CuckooSet traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
- \p Options list see \ref CuckooSet.
+ Template argument list \p Options... are:
+ - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
+ \p cuckoo::traits_hook.
+ If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
+ - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
+ should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
+ The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
+ the number \p k - the count of hash tables in cuckoo hashing.
+ - \p opt::mutex_policy - concurrent access policy.
+ Available policies: \p cuckoo::striping, \p cuckoo::refinable.
+ Default is \p %cuckoo::striping.
+ - \p opt::equal_to - key equality functor like \p std::equal_to.
+ If this functor is defined then the probe-set will be unordered.
+ If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
+ and \p %opt::equal_to will be ignored.
+ - \p opt::compare - key comparison functor. No default functor is provided.
+ If the option is not specified, the \p %opt::less is used.
+ If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
+ - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
+ If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
+ - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
+ The item counter should be atomic.
+ - \p opt::allocator - the allocator type using for allocating bucket tables.
+ Default is \ref CDS_DEFAULT_ALLOCATOR
+ - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
+ freeing nodes. Default is \p intrusive::opt::v::empty_disposer
+ - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
+ Default is \p %cuckoo::empty_stat
+
+ The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
+ specified by \p opt::hook option.
*/
- template <CDS_DECL_OPTIONS11>
+ template <typename... Options>
struct make_traits {
typedef typename cds::opt::make_options<
- typename cds::opt::find_type_traits< cuckoo::type_traits, CDS_OPTIONS10 >::type
- ,CDS_OPTIONS11
+ typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
+ ,Options...
>::type type ; ///< Result of metafunction
};
{
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;
for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
pNext = pNode->m_pNext;
pNode->clear();
- cds::unref(disp)( pNode );
+ disp( pNode );
}
nSize = 0;
};
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);
void clear( Disposer disp )
{
for ( unsigned int i = 0; i < m_nSize; ++i ) {
- cds::unref(disp)( m_arrNode[i] );
+ disp( m_arrNode[i] );
}
m_nSize = 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 )
{
struct contains<NodeTraits, true>
{
template <typename BucketEntry, typename Position, typename Q, typename Compare>
- static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp )
+ static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
{
// Ordered version
typedef typename BucketEntry::iterator bucket_iterator;
<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 <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
- If the prior value was \p NULL, it is done. Otherwise, it swaps the newly nest-less value \p y
+ If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
- was \p NULL, it is done. Otherwise, the method continues swapping entries (alternating tables)
+ was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
until it finds an empty slot. We might not find an empty slot, either because the table is full,
or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
number of successive displacements we are willing to undertake. When this limit is exceeded,
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. See cuckoo::type_traits for explanation. It is possible to declare option-based
- set with cuckoo::make_traits metafunction result as \p Traits template argument.
-
- Template argument list \p Options... of cuckoo::make_traits metafunction are:
- - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
- If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
- - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
- should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
- The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
- the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
- then k is unlimited, otherwise up to 10 different hash functors are supported.
- - opt::mutex_policy - concurrent access policy.
- Available policies: cuckoo::striping, cuckoo::refinable.
- Default is cuckoo::striping.
- - opt::equal_to - key equality functor like \p std::equal_to.
- If this functor is defined then the probe-set will be unordered.
- If opt::compare or opt::less option is specified too, then the probe-set will be ordered
- and opt::equal_to will be ignored.
- - opt::compare - key comparison functor. No default functor is provided.
- If the option is not specified, the opt::less is used.
- If opt::compare or opt::less option is specified, then the probe-set will be ordered.
- - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
- If opt::compare or opt::less option is specified, then the probe-set will be ordered.
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter
- The item counter should be atomic.
- - opt::allocator - the allocator type using for allocating bucket tables.
- Default is \p CDS_DEFAULT_ALLOCATOR
- - intrusive::opt::disposer - the disposer type used in \ref clear() member function for
- freeing nodes. Default is intrusive::opt::v::empty_disposer
- - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
- Default is cuckoo::empty_stat
-
- The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type
- specified by \p opt::hook option.
+ - \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>
- You should incorporate cuckoo::node into your struct \p T and provide
- appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
- define a struct based on cuckoo::type_traits.
+ You should incorporate \p cuckoo::node into your struct \p T and provide
+ appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
+ Usually, for \p Traits you define a struct based on \p cuckoo::traits.
Example for base hook and list-based probe-set:
\code
};
// Declare type traits
- struct my_traits: public cds::intrusive::cuckoo::type_traits
+ struct my_traits: public cds::intrusive::cuckoo::traits
{
typedef cds::intrusive::cuckoo::base_hook<
cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
> hook;
typedef my_data_equa_to equal_to;
- typedef std::tuple< hash1, hash2 > hash;
+ typedef cds::opt::hash_tuple< hash1, hash2 > hash;
};
// Declare CuckooSet type
};
// Declare type traits
- struct my_traits: public cds::intrusive::cuckoo::type_traits
+ struct my_traits: public cds::intrusive::cuckoo::traits
{
typedef cds::intrusive::cuckoo::base_hook<
cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
> hook;
typedef my_data_compare compare;
- typedef std::tuple< hash1, hash2 > hash;
+ typedef cds::opt::hash_tuple< hash1, hash2 > hash;
};
// Declare CuckooSet type
\endcode
*/
- template <typename T, typename Traits = cuckoo::type_traits>
+ template <typename T, typename Traits = cuckoo::traits>
class CuckooSet
{
public:
- typedef T value_type ; ///< The value type stored in the set
- typedef Traits options ; ///< Set traits
+ typedef T value_type; ///< The value type stored in the set
+ typedef Traits traits; ///< Set traits
- typedef typename options::hook hook ; ///< hook type
- typedef typename hook::node_type node_type ; ///< node type
- typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
+ typedef typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
- typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
- typedef typename hash::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple
+ typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
+ typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
- typedef typename options::stat stat ; ///< internal statistics type
+ typedef typename traits::stat stat; ///< internal statistics type
- typedef typename options::mutex_policy original_mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
+ 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 cuckoo::type_traits::mutex_policy)
- but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits:
- - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one
- - 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
- static bool const c_isSorted = !( std::is_same< typename options::compare, opt::none >::value
- && std::is_same< typename options::less, opt::none >::value ) ; ///< whether the probe set should be ordered
+ /// 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 );
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, options, !c_isSorted>::type key_equal_to;
+ 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
- typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
+ /// 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
- typedef typename options::allocator allocator;
+ typedef typename traits::allocator allocator;
/// item counter type
- typedef typename options::item_counter item_counter;
+ typedef typename traits::item_counter item_counter;
/// node disposer
- typedef typename options::disposer disposer;
+ typedef typename traits::disposer disposer;
protected:
//@cond
typedef size_t hash_array[c_nArity] ; ///< hash array
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor {
- void operator()( value_type& )
- {}
- };
-
- struct empty_erase_functor {
- void operator()( value_type const& )
- {}
- };
-
- struct empty_find_functor {
- template <typename Q>
- void operator()( value_type& item, Q& val )
- {}
- };
-# endif
-
-# if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
- template <typename Disposer>
- class disposer_wrapper: protected cds::details::functor_wrapper<Disposer>
- {
- typedef cds::details::functor_wrapper<Disposer> base_class;
- public:
- disposer_wrapper( Disposer d): base_class(d) {}
-
- void operator()( node_type * pNode )
- {
- base_class::get()( node_traits::to_value_ptr( pNode ));
- }
- };
-# endif
-
struct position {
bucket_iterator itPrev;
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 {
//@endcond
public:
- static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size
- static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size
- static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up
+ static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
+ static size_t const c_nDefaultInitialSize = 16; ///< default initial size
+ static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
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;
- cds::unref(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();
unsigned int nTable = contains( arrPos, arrHash, val, pred );
if ( nTable != c_nUndefTable ) {
- cds::unref(f)( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
+ f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
m_Stat.onFindSuccess();
return true;
}
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 ))
allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
}
-# ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// 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();
allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
}
-# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// Destructor
~CuckooSet()
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 )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return insert( val, []( value_type& ) {} );
-# else
- return insert( val, empty_insert_functor() );
-# endif
}
/// Inserts new node
\endcode
where \p val is the item inserted.
- The user-defined functor is called only if the inserting is success and can be passed by reference
- using <tt>boost::ref</tt>
+ The user-defined functor is called only if the inserting is success.
*/
template <typename Func>
bool insert( value_type& val, Func f )
{
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;
}
bucket_entry& refBucket = bucket( i, arrHash[i] );
if ( refBucket.size() < m_nProbesetThreshold ) {
refBucket.insert_after( arrPos[i].itPrev, pNode );
- cds::unref(f)( val );
+ f( val );
++m_ItemCounter;
m_Stat.onInsertSuccess();
return true;
bucket_entry& refBucket = bucket( i, arrHash[i] );
if ( refBucket.size() < m_nProbesetSize ) {
refBucket.insert_after( arrPos[i].itPrev, pNode );
- cds::unref(f)( val );
+ f( val );
++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.
- You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
-
- 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 ) {
- cds::unref(func)( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
- m_Stat.onEnsureExist();
+ func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
+ 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] );
if ( refBucket.size() < m_nProbesetThreshold ) {
refBucket.insert_after( arrPos[i].itPrev, pNode );
- cds::unref(func)( true, val, val );
+ func( true, val, val );
++m_ItemCounter;
- m_Stat.onEnsureSuccess();
+ m_Stat.onUpdateSuccess();
return std::make_pair( true, true );
}
}
bucket_entry& refBucket = bucket( i, arrHash[i] );
if ( refBucket.size() < m_nProbesetSize ) {
refBucket.insert_after( arrPos[i].itPrev, pNode );
- cds::unref(func)( true, val, val );
+ func( true, val, val );
++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;
The function searches an item with key equal to \p val in the set,
unlinks it from the set, and returns a pointer to unlinked item.
- If the item with key equal to \p val is not found the function return \p NULL.
+ If the item with key equal to \p val is not found the function return \p nullptr.
Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
value_type * erase( Q const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return erase( val, [](value_type const&) {} );
-# else
- return erase( val, empty_erase_functor() );
-# endif
}
/// Deletes the item from the set using \p pred predicate for searching
template <typename Q, typename Predicate>
value_type * erase_with( Q const& val, Predicate pred )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
-# else
- return erase_( val, typename predicate_wrapper<Predicate>::type(), empty_erase_functor() );
-# endif
}
/// Delete the item from the set
void operator()( value_type const& item );
};
\endcode
- The functor may be passed by reference with <tt>boost:ref</tt>
- If the item with key equal to \p val is not found the function return \p NULL.
+ If the item with key equal to \p val is not found the function return \p nullptr.
Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q, typename Predicate, typename Func>
value_type * erase_with( Q const& val, Predicate pred, Func f )
{
+ CDS_UNUSED( pred );
return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
}
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
-
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
{
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
/**
template <typename Q, typename Predicate, typename Func>
bool find_with( Q& val, Predicate pred, Func f )
{
+ 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.
-
- You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
-
- 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( key, [](value_type&, Q const& ) {} );
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return find( val, [](value_type&, Q const& ) {} );
-# else
- return find( val, empty_find_functor() );
-# endif
+ 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( 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 )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
-# else
- return find_with( val, typename predicate_wrapper<Predicate>::type(), empty_find_functor() );
-# endif
+ 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 options is not called.
+ The \p Traits::disposer is not called.
*/
template <typename Disposer>
void clear_and_dispose( Disposer oDisposer )
// locks entire array
scoped_full_lock sl( m_MutexPolicy );
-# if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
- disposer_wrapper<Disposer> disp( oDisposer );
-# endif
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 ) {
-# if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1600)
- // MSVC 10: error to call nested typedefs node_traits from lambda
pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
-# else
- pEntry->clear( cds::ref(disp) );
-# endif
}
}
m_ItemCounter.reset();
*/
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
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
+#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
projects / libcds.git / blobdiff