-//$$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 <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>
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>
template < typename HookType, typename... Options>
struct hook
{
- typedef typename opt::make_options< default_hook, Options...>::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 < typename... Options >
struct base_hook: public hook< opt::base_hook_tag, Options... >
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, typename... Options >
struct member_hook: public hook< opt::member_hook_tag, Options... >
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, typename... Options >
struct traits_hook: public hook< opt::traits_hook_tag, Options... >
};
//@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.
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
>
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:
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::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( 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_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 ) {
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, 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 {}
};
/// 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 <typename... Options>
struct make_traits {
typedef typename cds::opt::make_options<
- typename cds::opt::find_type_traits< cuckoo::type_traits, Options... >::type
+ 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 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
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 ))
/// 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 )
{
\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;
template <typename Q, typename Predicate>
value_type * erase_with( Q const& val, Predicate pred )
{
+ CDS_UNUSED( pred );
return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
}
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 nullptr.
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( 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( 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 find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
+ 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 )
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
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
+#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
projects / libcds.git / blobdiff