X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fcontainer%2Fcuckoo_set.h;fp=cds%2Fcontainer%2Fcuckoo_set.h;h=b94f6bfb4c23a2d08e7ffa5a9f23cb7829b9adad;hp=12172e4bb1f35cfc218ee7a8883dcd125f661556;hb=21b0278a3b655ee2688ac29122fc318fe9f34114;hpb=4a7a5930e31cc64686bc3b19c4056ca8ef648a3a 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