#ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
#define __CDS_INTRUSIVE_CUCKOO_SET_H
-#include <cds/intrusive/base.h>
+#include <memory>
+#include <type_traits>
+#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/details/std/type_traits.h>
-#include <cds/ref.h>
#include <cds/os/thread.h>
-#include <cds/details/std/memory.h>
-#include <cds/details/functor_wrapper.h>
#include <cds/lock/spinlock.h>
-#include <cds/details/std/mutex.h>
-//#include <boost/thread/recursive_mutex.hpp>
namespace cds { namespace intrusive {
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 options;
typedef typename options::probeset_type probeset_type;
typedef typename options::tag tag;
- 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
*/
- 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
- 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
*/
- 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;
- 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
*/
- 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
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 ) {}
};
};
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] )
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
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,
class Alloc = CDS_DEFAULT_ALLOCATOR,
typedef cds::OS::ThreadId threadId_t;
typedef cds::lock::Spin spinlock_type;
- typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
+ 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
+ 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
// wait while resizing
while ( true ) {
- who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
+ who = m_Owner.load( atomics::memory_order_acquire );
if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
break;
bkoff();
parrLock[i]->lock();
}
- who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
+ who = m_Owner.load( atomics::memory_order_acquire );
if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
m_Stat.onCellLock();
return;
// 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();
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 )
// 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 ( 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, CDS_ATOMIC::memory_order_release );
+ m_Owner.store( 0, atomics::memory_order_release );
m_Stat.onResizeLockArrayChanged();
}
else {
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 )
m_arrLocks[i] = pNew[i];
}
- m_nCapacity.store( nCapacity, CDS_ATOMIC::memory_order_release );
+ m_nCapacity.store( nCapacity, atomics::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
This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
\p Options list see \ref CuckooSet.
*/
- 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::type_traits, Options... >::type
+ ,Options...
>::type type ; ///< Result of metafunction
};
for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
pNext = pNode->m_pNext;
pNode->clear();
- cds::unref(disp)( pNode );
+ disp( pNode );
}
nSize = 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;
}
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,
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;
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;
}
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()
allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
}
-# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// Destructor
~CuckooSet()
*/
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
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>
+ using \p std::ref
*/
template <typename Func>
bool insert( value_type& val, Func f )
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 );
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.
+ You may pass \p func argument by reference using \p std::ref.
Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
\p second is \p true if new item has been added or \p false if the item with \p key
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 );
+ func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
m_Stat.onEnsureExist();
return std::make_pair( true, false );
}
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();
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 );
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
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
\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.
*/
\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.
+ You can pass \p f argument by reference using \p std::ref.
The functor may change non-key fields of \p item.
\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.
+ You can pass \p f argument by reference using \p std::ref.
The functor may change non-key fields of \p item.
template <typename Q>
bool find( Q const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return find( val, [](value_type&, Q const& ) {} );
-# else
- return find( val, empty_find_functor() );
-# endif
}
/// Find the key \p val using \p pred predicate for comparing
template <typename Q, typename Predicate>
bool find_with( Q const& val, 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
}
/// Clears the set
// 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;
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();
projects / libcds.git / blobdiff