#ifndef __CDS_CONTAINER_CUCKOO_SET_H
#define __CDS_CONTAINER_CUCKOO_SET_H
-#include <cds/container/cuckoo_base.h>
+#include <cds/container/details/cuckoo_base.h>
#include <cds/details/binary_functor_wrapper.h>
namespace cds { namespace container {
struct make_cuckoo_set
{
typedef T value_type;
- typedef Traits original_type_traits;
- typedef typename original_type_traits::probeset_type probeset_type;
- static bool const store_hash = original_type_traits::store_hash;
- static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_type_traits::hash::hash_tuple_type >::value) : 0;
+ typedef Traits original_traits;
+ typedef typename original_traits::probeset_type probeset_type;
+ static bool const store_hash = original_traits::store_hash;
+ static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_traits::hash::hash_tuple_type >::value) : 0;
struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
{
: m_val(v)
{}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
node_type( Args&&... args )
: m_val( std::forward<Args>(args)...)
{}
-# else
- node_type()
- {}
-# endif
};
struct value_accessor {
template <typename Pred, typename ReturnValue>
using predicate_wrapper = cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >;
- struct intrusive_traits: public original_type_traits
+ struct intrusive_traits: public original_traits
{
typedef intrusive::cuckoo::base_hook<
cds::intrusive::cuckoo::probeset_type< probeset_type >
,cds::intrusive::cuckoo::store_hash< store_hash_count >
> hook;
- typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
+ typedef cds::intrusive::cuckoo::traits::disposer disposer;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::equal_to, opt::none >::value
+ std::is_same< typename original_traits::equal_to, opt::none >::value
, opt::none
- , predicate_wrapper< typename original_type_traits::equal_to, bool >
+ , predicate_wrapper< typename original_traits::equal_to, bool >
>::type equal_to;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::compare, opt::none >::value
+ std::is_same< typename original_traits::compare, opt::none >::value
, opt::none
- , predicate_wrapper< typename original_type_traits::compare, int >
+ , predicate_wrapper< typename original_traits::compare, int >
>::type compare;
typedef typename std::conditional<
- std::is_same< typename original_type_traits::less, opt::none >::value
+ std::is_same< typename original_traits::less, opt::none >::value
,opt::none
- ,predicate_wrapper< typename original_type_traits::less, bool >
+ ,predicate_wrapper< typename original_traits::less, bool >
>::type less;
- typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, value_accessor > hash;
+ typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, value_accessor > hash;
};
typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
Template arguments:
- \p T - the type stored in the set.
- - \p Traits - type traits. See cuckoo::type_traits for explanation.
+ - \p Traits - type traits. See cuckoo::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:
- - 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 opt::v::sequential_item_counter.
- - opt::allocator - the allocator type using for allocating bucket tables.
- Default is \p CDS_DEFAULT_ALLOCATOR
- - opt::node_allocator - the allocator type using for allocating set's items. If this option
- is not specified then the type defined in opt::allocator option is used.
- - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
- of the object once it's introduced in the container. When this option is used,
- the unordered container will store the calculated hash value in the node and rehashing operations won't need
- to recalculate the hash of the value. This option will improve the performance of unordered containers
- when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
- - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
- Default is \p cuckoo::list.
- - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
- Default is cuckoo::empty_stat
-
<b>Examples</b>
Cuckoo-set with list-based unordered probe set and storing hash values
};
// Declare type traits
- struct my_traits: public cds::container::cuckoo::type_traits
+ struct my_traits: public cds::container::cuckoo::traits
{
typedef my_data_equa_to equal_to;
typedef std::tuple< hash1, hash2 > hash;
// Declare type traits
// We use a vector of capacity 4 as probe-set container and store hash values in the node
- struct my_traits: public cds::container::cuckoo::type_traits
+ struct my_traits: public cds::container::cuckoo::traits
{
typedef my_data_compare compare;
typedef std::tuple< hash1, hash2 > hash;
\endcode
*/
- template <typename T, typename Traits = cuckoo::type_traits>
+ template <typename T, typename Traits = cuckoo::traits>
class CuckooSet:
#ifdef CDS_DOXYGEN_INVOKED
protected intrusive::CuckooSet<T, Traits>
public:
typedef T value_type ; ///< value type stored in the container
- typedef Traits options ; ///< traits
+ typedef Traits traits ; ///< traits
- typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
- typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple
+ typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
+ typedef typename base_class::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
- typedef typename base_class::mutex_policy mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
- typedef typename base_class::stat stat ; ///< internal statistics type
+ typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see cuckoo::traits::mutex_policy
+ typedef typename base_class::stat stat; ///< internal statistics type
- static bool const c_isSorted = base_class::c_isSorted ; ///< whether the probe set should be ordered
- static size_t const c_nArity = base_class::c_nArity ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
+ static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
+ static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
- typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
+ typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
- typedef typename base_class::key_comparator key_comparator ; ///< key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
+ typedef typename base_class::key_comparator key_comparator; ///< key comparing functor based on \p Traits::compare and \p Traits::less option setter. Used only for ordered probe set
- typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
+ typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
/// Node allocator type
typedef typename std::conditional<
- std::is_same< typename options::node_allocator, opt::none >::value,
+ std::is_same< typename traits::node_allocator, opt::none >::value,
allocator,
- typename options::node_allocator
+ typename traits::node_allocator
>::type node_allocator;
/// item counter type
- typedef typename options::item_counter item_counter;
+ typedef typename traits::item_counter item_counter;
protected:
//@cond
//@endcond
public:
- static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ; ///< default probeset size
- static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize ; ///< default initial size
- static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit ; ///< Count of attempts to relocate before giving up
+ static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
+ static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
+ static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
protected:
//@cond
{
return cxx_node_allocator().New( v );
}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
static node_type * alloc_node( Args&&... args )
{
return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
}
-# endif
static void free_node( node_type * pNode )
{
typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor {
- void operator()( value_type& ) const
- {}
- };
-
- struct empty_find_functor {
- template <typename Q>
- void operator()( node_type& item, Q& val ) const
- {}
- };
-
- template <typename Func>
- class insert_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- insert_wrapper( Func f ): base_class(f) {}
-
- void operator()( node_type& node )
- {
- base_class::get()( node.m_val );
- }
- };
-
- template <typename Q, typename Func>
- class ensure_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- Q const& val;
-
- ensure_wrapper( Q const& v, Func f) : base_class(f), val(v) {}
-
- void operator()( bool bNew, node_type& item, node_type const& )
- {
- base_class::get()( bNew, item.m_val, val );
- }
- };
-
- template <typename Func>
- class find_wrapper: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- find_wrapper( Func f )
- : base_class(f)
- {}
-
- template <typename Q>
- void operator()( node_type& item, Q& val )
- {
- base_class::get()( item.m_val, val );
- }
- };
-# endif
//@endcond
public:
: base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
{}
-# 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()
)
: base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
{}
-# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
/// Destructor clears the set
~CuckooSet()
template <typename Q>
bool insert( Q const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return insert( val, []( value_type& ) {} );
-# else
- return insert( val, empty_insert_functor() );
-# endif
}
/// Inserts new node
The type \p Q can differ from \ref value_type of items storing in the set.
Therefore, the \p value_type should be constructible from type \p Q.
- The user-defined functor is called only if the inserting is success. It can be passed by reference
- using <tt>boost::ref</tt>
+ The user-defined functor is called only if the inserting is success.
*/
template <typename Q, typename Func>
bool insert( Q const& val, Func f )
{
scoped_node_ptr pNode( alloc_node( val ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- if ( base_class::insert( *pNode, [&f]( node_type& node ) { cds::unref(f)( node.m_val ); } ))
-# else
- insert_wrapper<Func> wrapper( f );
- if ( base_class::insert( *pNode, cds::ref(wrapper) ))
-# endif
- {
+ if ( base_class::insert( *pNode, [&f]( node_type& node ) { f( node.m_val ); } )) {
pNode.release();
return true;
}
return false;
}
-# ifdef CDS_EMPLACE_SUPPORT
/// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
/**
Returns \p true if inserting successful, \p false otherwise.
-
- This function is available only for compiler that supports
- variadic template and move semantics
*/
template <typename... Args>
bool emplace( Args&&... args )
}
return false;
}
-# endif
/// Ensures that the \p val exists in the set
/**
The functor can change non-key fields of the \p item.
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
-
Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
\p second is true if new item has been added or \p false if the item with \p val key
already exists.
std::pair<bool, bool> ensure( Q const& val, Func func )
{
scoped_node_ptr pNode( alloc_node( val ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
std::pair<bool, bool> res = base_class::ensure( *pNode,
- [&val,&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val, val ); }
+ [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); }
);
-# else
- ensure_wrapper<Q, Func> wrapper( val, func );
- std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
-# endif
if ( res.first && res.second )
pNode.release();
return res;
template <typename Q, typename Predicate>
bool erase_with( Q const& key, Predicate pred )
{
+ CDS_UNUSED( pred );
node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
if ( pNode ) {
free_node( pNode );
void operator()(value_type const& val);
};
\endcode
- The functor can be passed by value or by reference using <tt>boost:ref</tt>
Return \p true if key is found and deleted, \p false otherwise
*/
{
node_type * pNode = base_class::erase( key );
if ( pNode ) {
- cds::unref(f)( pNode->m_val );
+ f( pNode->m_val );
free_node( pNode );
return true;
}
template <typename Q, typename Predicate, typename Func>
bool erase_with( Q const& key, Predicate pred, Func f )
{
+ CDS_UNUSED( pred );
node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
if ( pNode ) {
- cds::unref(f)( pNode->m_val );
+ f( pNode->m_val );
free_node( pNode );
return true;
}
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
The functor can 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
can modify both arguments.
template <typename Q, typename Func>
bool find( Q& val, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find( val, [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find( val, cds::ref(wrapper) );
-# endif
+ return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
}
/// 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 )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
- [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
-# endif
+ [&f](node_type& item, Q& v) { f( item.m_val, v );});
}
/// Find the key \p 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 value or by reference using <tt>boost::ref</tt> or cds::ref.
-
The functor can change non-key fields of \p item.
The type \p Q can differ from \ref value_type of items storing in the container.
template <typename Q, typename Func>
bool find( Q const& val, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find( val, [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find( val, cds::ref(wrapper) );
-# endif
+ return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
}
/// Find the key \p val using \p pred predicate for comparing
template <typename Q, typename Predicate, typename Func>
bool find_with( Q const& val, Predicate pred, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
- [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
-# else
- find_wrapper<Func> wrapper(f);
- return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
-# endif
+ [&f](node_type& item, Q const& v) { f( item.m_val, v );});
}
/// Find the key \p val
template <typename Q>
bool find( Q const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return base_class::find( val, [](node_type&, Q const&) {});
-# else
- return base_class::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 base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
-# else
- return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), empty_find_functor());
-# endif
}
/// Clears the set
projects / libcds.git / blobdiff