//$$CDS-header$$
-#ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
-#define __CDS_INTRUSIVE_CUCKOO_SET_H
+#ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
+#define CDSLIB_INTRUSIVE_CUCKOO_SET_H
#include <memory>
#include <type_traits>
#include <mutex>
-#include <cds/intrusive/base.h>
+#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 {
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
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;
};
//@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
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] )
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
+ 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
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;
back_off bkoff;
// 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();
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();
while ( true ) {
{
// 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
};
/// 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
};
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;
}
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;
- \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 Traits - type traits, default is 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
+ Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
+ but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
+ - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
- otherwise real mutex policy statistics is used
*/
typedef typename original_mutex_policy::template rebind_statistics<
>::type
>::other mutex_policy;
- 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
+ static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
+ && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
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;
+ 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;
//@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
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
\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 )
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.
-
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
already is in the set.
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 );
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 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
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 );
}
\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
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 );
}
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
+ CDS_UNUSED( pred );
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
};
\endcode
- The \ref disposer specified in \p Traits options is not called.
+ The \ref disposer specified in \p Traits traits 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;
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();
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
+#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
projects / libcds.git / blobdiff