From 21b0278a3b655ee2688ac29122fc318fe9f34114 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 10 Nov 2014 14:34:01 +0300 Subject: [PATCH] CuckooSet/Map refactoring --- cds/container/cuckoo_map.h | 143 ++++--------- cds/container/cuckoo_set.h | 99 +++------ cds/container/details/cuckoo_base.h | 47 ++++- cds/intrusive/cuckoo_set.h | 188 +++++++++--------- cds/opt/hash.h | 6 +- tests/test-hdr/map/hdr_cuckoo_map.cpp | 11 +- tests/test-hdr/set/hdr_cuckoo_set.cpp | 17 +- .../test-hdr/set/hdr_intrusive_cuckoo_set.cpp | 26 +-- 8 files changed, 242 insertions(+), 295 deletions(-) diff --git a/cds/container/cuckoo_map.h b/cds/container/cuckoo_map.h index a6755b88..cf15043f 100644 --- a/cds/container/cuckoo_map.h +++ b/cds/container/cuckoo_map.h @@ -13,14 +13,14 @@ namespace cds { namespace container { template struct make_cuckoo_map { - typedef Key key_type ; ///< key type - typedef T mapped_type ; ///< type of value stored in the map - typedef std::pair value_type ; ///< Pair type + typedef Key key_type; ///< key type + typedef T mapped_type; ///< type of value stored in the map + typedef std::pair value_type; ///< Pair 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 { @@ -42,34 +42,6 @@ namespace cds { namespace container { {} }; - /* - template - struct predicate_wrapper { - typedef Pred native_predicate; - - ReturnValue operator()( node_type const& n1, node_type const& n2) const - { - return native_predicate()(n1.m_val.first, n2.m_val.first ); - } - template - ReturnValue operator()( node_type const& n, Q const& v) const - { - return native_predicate()(n.m_val.first, v); - } - template - ReturnValue operator()( Q const& v, node_type const& n) const - { - return native_predicate()(v, n.m_val.first); - } - - template - ReturnValue operator()( Q1 const& v1, Q2 const& v2) const - { - return native_predicate()(v1, v2); - } - }; - */ - struct key_accessor { key_type const& operator()( node_type const& node ) const { @@ -77,34 +49,34 @@ namespace cds { namespace container { } }; - 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 - , cds::details::predicate_wrapper< node_type, typename original_type_traits::equal_to, key_accessor > + , cds::details::predicate_wrapper< node_type, typename original_traits::equal_to, key_accessor > >::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 - , cds::details::compare_wrapper< node_type, typename original_type_traits::compare, key_accessor > + , cds::details::compare_wrapper< node_type, typename original_traits::compare, key_accessor > >::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 - ,cds::details::predicate_wrapper< node_type, typename original_type_traits::less, key_accessor > + ,cds::details::predicate_wrapper< node_type, typename original_traits::less, key_accessor > >::type less; - typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, key_accessor > hash; + typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, key_accessor > hash; }; typedef intrusive::CuckooSet< node_type, intrusive_traits > type; @@ -167,41 +139,9 @@ namespace cds { namespace container { Template arguments: - \p Key - key type - \p T - the type stored in the map. - - \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: - - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor - should be orthogonal (different): for each i,j: i != j => h[i](x) != h[j](x) . - The hash functors are passed as std::tuple< H1, H2, ... Hn > . 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. - 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 map'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 map 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 maps - 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 cuckoo::vector, - Default is \p cuckoo::list. - - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat. - Default is cuckoo::empty_stat + - \p Traits - map 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. Examples @@ -229,7 +169,7 @@ namespace cds { namespace container { #include // Declare type traits - struct my_traits: public cds::container::cuckoo::type_traits + struct my_traits: public cds::container::cuckoo::traits { typedef std::equal_to< std::string > equal_to; typedef std::tuple< hash1, hash2 > hash; @@ -260,7 +200,7 @@ namespace cds { namespace container { // 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 std::less< std::string > less; typedef std::tuple< hash1, hash2 > hash; @@ -284,7 +224,7 @@ namespace cds { namespace container { \endcode */ - template + template class CuckooMap: #ifdef CDS_DOXYGEN_INVOKED protected intrusive::CuckooSet< std::pair< Key const, T>, Traits> @@ -297,36 +237,35 @@ namespace cds { namespace container { typedef typename maker::type base_class; //@endcond public: - typedef Key key_type ; ///< key type - typedef T mapped_type ; ///< value type stored in the container - typedef std::pair value_type ; ///< Key-value pair type stored in the map - - typedef Traits options ; ///< traits + typedef Key key_type; ///< key type + typedef T mapped_type; ///< value type stored in the container + typedef std::pair value_type; ///< Key-value pair type stored in the map + typedef Traits traits; ///< Map traits - typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use - typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< hash tuple type + typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use + typedef typename base_class::hash_tuple_type hash_tuple_type; ///< hash tuple type - 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 \p 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 opt::compare and opt::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 @@ -340,9 +279,9 @@ namespace cds { namespace container { //@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 diff --git a/cds/container/cuckoo_set.h b/cds/container/cuckoo_set.h index 12172e4b..b94f6bfb 100644 --- a/cds/container/cuckoo_set.h +++ b/cds/container/cuckoo_set.h @@ -14,10 +14,10 @@ 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 { @@ -44,34 +44,34 @@ namespace cds { namespace container { template 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; @@ -133,42 +133,9 @@ namespace cds { namespace container { 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 i,j: i != j => h[i](x) != h[j](x) . - The hash functors are passed as std::tuple< H1, H2, ... Hn > . 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. - 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 cuckoo::vector, - Default is \p cuckoo::list. - - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat. - Default is cuckoo::empty_stat - Examples Cuckoo-set with list-based unordered probe set and storing hash values @@ -228,7 +195,7 @@ namespace cds { namespace container { }; // 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; @@ -311,7 +278,7 @@ namespace cds { namespace container { // 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; @@ -335,7 +302,7 @@ namespace cds { namespace container { \endcode */ - template + template class CuckooSet: #ifdef CDS_DOXYGEN_INVOKED protected intrusive::CuckooSet @@ -350,33 +317,33 @@ namespace cds { namespace container { 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 @@ -385,9 +352,9 @@ namespace cds { namespace container { //@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 diff --git a/cds/container/details/cuckoo_base.h b/cds/container/details/cuckoo_base.h index a68feacb..00d28304 100644 --- a/cds/container/details/cuckoo_base.h +++ b/cds/container/details/cuckoo_base.h @@ -118,7 +118,7 @@ namespace cds { namespace container { using intrusive::cuckoo::vector; /// Type traits for CuckooSet and CuckooMap classes - struct type_traits + struct traits { /// Hash functors tuple /** @@ -129,7 +129,13 @@ namespace cds { namespace container { The hash functors are defined as std::tuple< H1, H2, ... Hn > : \@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::container::cuckoo::traits { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + }; + \endcode */ typedef cds::opt::none hash; @@ -168,7 +174,7 @@ namespace cds { namespace container { Only atomic item counter type is allowed. */ - typedef cds::intrusive::cuckoo::type_traits::item_counter item_counter; + typedef cds::intrusive::cuckoo::traits::item_counter item_counter; /// Allocator type /** @@ -195,13 +201,42 @@ namespace cds { namespace container { /// Metafunction converting option list to CuckooSet/CuckooMap traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \p Options list see CuckooSet and CuckooMap + Template argument list \p Options... are: + - \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 i,j: i != j => h[i](x) != h[j](x) . + The hash functors are passed as std::tuple< H1, H2, ... Hn > . 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. + 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 opt::v::sequential_item_counter. + - \p opt::allocator - the allocator type using for allocating bucket tables. + Default is \ref CDS_DEFAULT_ALLOCATOR + - \p opt::node_allocator - the allocator type using for allocating set's items. If this option + is not specified then the type defined in \p %opt::allocator option is used. + - \p 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 cuckoo::vector, + Default is \p cuckoo::list. + - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat. + Default is \p %cuckoo::empty_stat */ template 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 }; diff --git a/cds/intrusive/cuckoo_set.h b/cds/intrusive/cuckoo_set.h index 7b637e40..7ba7b00c 100644 --- a/cds/intrusive/cuckoo_set.h +++ b/cds/intrusive/cuckoo_set.h @@ -92,8 +92,7 @@ namespace cds { namespace intrusive { or \p cds::intrusive::cuckoo::vector. - \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 struct node @@ -241,11 +240,11 @@ namespace cds { namespace intrusive { 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 node_type; @@ -256,9 +255,9 @@ namespace cds { namespace intrusive { /// 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... > @@ -270,9 +269,9 @@ namespace cds { namespace intrusive { 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... > @@ -288,9 +287,9 @@ namespace cds { namespace intrusive { 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 struct traits_hook: public hook< opt::traits_hook_tag, Options... > @@ -1086,7 +1085,7 @@ namespace cds { namespace intrusive { }; /// Type traits for CuckooSet class - struct type_traits + struct traits { /// Hook used /** @@ -1103,17 +1102,23 @@ namespace cds { namespace intrusive { The hash functors are defined as std::tuple< H1, H2, ... Hn > : \@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; @@ -1123,7 +1128,7 @@ namespace cds { namespace intrusive { */ 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. */ @@ -1138,7 +1143,7 @@ namespace cds { namespace intrusive { /// 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. */ @@ -1152,24 +1157,53 @@ namespace cds { namespace intrusive { /// 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 cds::opt::make_options< type_traits, Options...> - \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, %cuckoo::base_hook<> 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 i,j: i != j => h[i](x) != h[j](x) . + The hash functors are passed as std::tuple< H1, H2, ... Hn > . 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. + 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 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 }; @@ -1618,46 +1652,14 @@ namespace cds { namespace intrusive { - \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, %cuckoo::base_hook<> 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 i,j: i != j => h[i](x) != h[j](x) . - The hash functors are passed as std::tuple< H1, H2, ... Hn > . 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. - 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. How to use - 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 @@ -1718,14 +1720,14 @@ namespace cds { namespace intrusive { }; // 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 @@ -1807,14 +1809,14 @@ namespace cds { namespace intrusive { }; // 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 @@ -1834,29 +1836,29 @@ namespace cds { namespace intrusive { \endcode */ - template + template 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< @@ -1867,24 +1869,24 @@ namespace cds { namespace intrusive { >::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 @@ -1922,9 +1924,9 @@ namespace cds { namespace intrusive { //@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 @@ -2740,7 +2742,7 @@ namespace cds { namespace intrusive { }; \endcode - The \ref disposer specified in \p Traits options is not called. + The \ref disposer specified in \p Traits traits is not called. */ template void clear_and_dispose( Disposer oDisposer ) diff --git a/cds/opt/hash.h b/cds/opt/hash.h index 982cdfd3..2c457f79 100644 --- a/cds/opt/hash.h +++ b/cds/opt/hash.h @@ -4,7 +4,7 @@ #define __CDS_OPT_HASH_H #include -#include +#include #include namespace cds { namespace opt { @@ -104,6 +104,10 @@ namespace cds { namespace opt { } // namespace details //@endcond + /// Declare tuple for hash functors \p Functors + template + using hash_tuple = details::hash_list< std::tuple< Functors... >>; + //@cond // At least, two functors must be provided. Single functor is not supported template struct hash< std::tuple >; diff --git a/tests/test-hdr/map/hdr_cuckoo_map.cpp b/tests/test-hdr/map/hdr_cuckoo_map.cpp index cf88bfc9..ef01159e 100644 --- a/tests/test-hdr/map/hdr_cuckoo_map.cpp +++ b/tests/test-hdr/map/hdr_cuckoo_map.cpp @@ -23,12 +23,11 @@ namespace map { { CPPUNIT_MESSAGE( "equal"); { - typedef cc::CuckooMap< CuckooMapHdrTest::key_type, CuckooMapHdrTest::value_type, - cc::cuckoo::make_traits< - co::equal_to< std::equal_to > - ,co::hash< std::tuple< hash1, hash2 > > - >::type - > map_t; + struct map_traits : public cc::cuckoo::traits { + typedef std::equal_to equal_to; + typedef co::hash_tuple< hash1, hash2 > hash; + }; + typedef cc::CuckooMap< CuckooMapHdrTest::key_type, CuckooMapHdrTest::value_type, map_traits > map_t; test_cuckoo(); } diff --git a/tests/test-hdr/set/hdr_cuckoo_set.cpp b/tests/test-hdr/set/hdr_cuckoo_set.cpp index 673950bb..b88f6449 100644 --- a/tests/test-hdr/set/hdr_cuckoo_set.cpp +++ b/tests/test-hdr/set/hdr_cuckoo_set.cpp @@ -7,12 +7,17 @@ namespace set { void CuckooSetHdrTest::Cuckoo_Striped_list_unord() { - typedef cc::CuckooSet< item, - cc::cuckoo::make_traits< - co::equal_to< equal< item > > - ,co::hash< std::tuple< hash1, hash2 > > - >::type - > set_t; + struct set_traits : public cc::cuckoo::traits { + typedef equal equal_to; + typedef co::hash_tuple< hash1, hash2 > hash; + }; + + typedef cc::CuckooSet< item, set_traits > set_t; + // cc::cuckoo::make_traits< + // co::equal_to< equal< item > > + // ,co::hash< std::tuple< hash1, hash2 > > + // >::type + //> set_t; test_int >(); } diff --git a/tests/test-hdr/set/hdr_intrusive_cuckoo_set.cpp b/tests/test-hdr/set/hdr_intrusive_cuckoo_set.cpp index 86342709..98de7617 100644 --- a/tests/test-hdr/set/hdr_intrusive_cuckoo_set.cpp +++ b/tests/test-hdr/set/hdr_intrusive_cuckoo_set.cpp @@ -11,12 +11,11 @@ namespace set { void IntrusiveCuckooSetHdrTest::Cuckoo_striped_list_basehook_equal() { typedef IntrusiveCuckooSetHdrTest::base_item< ci::cuckoo::node< ci::cuckoo::list, 0 > > item_type; - typedef ci::CuckooSet< item_type - ,ci::cuckoo::make_traits< - co::hash< std::tuple< hash1, hash2 > > - ,co::equal_to< equal_to > - >::type - > set_type; + struct set_traits : public ci::cuckoo::traits { + typedef co::hash_tuple< hash1, hash2 > hash; + typedef set::equal_to equal_to; + }; + typedef ci::CuckooSet< item_type, set_traits > set_type; test_cuckoo(); } @@ -25,15 +24,12 @@ namespace set { { typedef IntrusiveCuckooSetHdrTest::base_item< ci::cuckoo::node< ci::cuckoo::vector<4>, 0 > > item_type; - typedef ci::CuckooSet< item_type - ,ci::cuckoo::make_traits< - ci::opt::hook< ci::cuckoo::base_hook< - ci::cuckoo::probeset_type< item_type::probeset_type > - > > - ,co::hash< std::tuple< hash1, hash2 > > - ,co::equal_to< equal_to > - >::type - > set_type; + struct set_traits : public ci::cuckoo::traits { + typedef ci::cuckoo::base_hook< ci::cuckoo::probeset_type< item_type::probeset_type >> hook; + typedef co::hash_tuple< hash1, hash2 > hash; + typedef set::equal_to equal_to; + }; + typedef ci::CuckooSet< item_type, set_traits > set_type; test_cuckoo(); } -- 2.34.1