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>
{
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
projects / libcds.git / blobdiff