X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fcuckoo_map.h;h=b5204ffdb6f9dc8652739f4e10b965ac2a55b561;hb=4ca7a52111a504c05818a718a21081fb04fea00e;hp=d9282266b552d050498d375a9f183fb550a8081e;hpb=7d15399a4d18ae2061ddb01656d85dbc940ff915;p=libcds.git diff --git a/cds/container/cuckoo_map.h b/cds/container/cuckoo_map.h index d9282266..b5204ffd 100644 --- a/cds/container/cuckoo_map.h +++ b/cds/container/cuckoo_map.h @@ -1,9 +1,9 @@ //$$CDS-header$$ -#ifndef __CDS_CONTAINER_CUCKOO_MAP_H -#define __CDS_CONTAINER_CUCKOO_MAP_H +#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H +#define CDSLIB_CONTAINER_CUCKOO_MAP_H -#include +#include #include namespace cds { namespace container { @@ -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 { @@ -36,44 +36,11 @@ namespace cds { namespace container { : m_val( std::make_pair( key_type(key), mapped_type(v) )) {} -# ifdef CDS_EMPLACE_SUPPORT template node_type( K&& key, Args&&... args ) : m_val( std::forward(key), std::move( mapped_type(std::forward(args)...)) ) {} -# else - node_type() - {} -# endif - }; - - /* - 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 @@ -82,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; @@ -138,9 +105,9 @@ namespace cds { namespace container { The insert(x) successively "kicks out" conflicting items until every key has a slot. To add \p x, the method swaps \p x with \p y, the current occupant of table[0][h0(x)]. - If the prior value was \p NULL, it is done. Otherwise, it swaps the newly nest-less value \p y + If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y for the current occupant of table[1][h1(y)] in the same way. As before, if the prior value - was \p NULL, it is done. Otherwise, the method continues swapping entries (alternating tables) + was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables) until it finds an empty slot. We might not find an empty slot, either because the table is full, or because the sequence of displacement forms a cycle. We therefore need an upper limit on the number of successive displacements we are willing to undertake. When this limit is exceeded, @@ -172,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 @@ -234,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; @@ -265,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; @@ -289,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> @@ -302,36 +237,39 @@ 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 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 Traits options ; ///< traits + 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 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 base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see \p cuckoo::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::type_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; + + //@cond + typedef cds::container::cuckoo::implementation_tag implementation_tag; + //@endcond protected: //@cond @@ -345,9 +283,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 @@ -356,13 +294,11 @@ namespace cds { namespace container { { return cxx_node_allocator().New( key ); } -# ifdef CDS_EMPLACE_SUPPORT template static node_type * alloc_node( K&& key, Args&&... args ) { return cxx_node_allocator().MoveNew( std::forward( key ), std::forward(args)... ); } -# endif static void free_node( node_type * pNode ) { @@ -381,71 +317,6 @@ namespace cds { namespace container { 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 - {} - }; - - template - class insert_value_functor - { - Q const& m_val; - public: - insert_value_functor( Q const & v) - : m_val(v) - {} - - void operator()( value_type& item ) - { - item.second = m_val; - } - }; - - template - class insert_key_wrapper: protected cds::details::functor_wrapper - { - typedef cds::details::functor_wrapper base_class; - public: - insert_key_wrapper( Func f ): base_class(f) {} - - void operator()( node_type& item ) - { - base_class::get()( item.m_val ); - } - }; - - template - class ensure_wrapper: protected cds::details::functor_wrapper - { - typedef cds::details::functor_wrapper base_class; - public: - ensure_wrapper( Func f) : base_class(f) {} - - void operator()( bool bNew, node_type& item, node_type const& ) - { - base_class::get()( bNew, item.m_val ); - } - }; - - template - class find_wrapper: protected cds::details::functor_wrapper - { - typedef cds::details::functor_wrapper base_class; - public: - find_wrapper( Func f ) - : base_class(f) - {} - - template - void operator()( node_type& item, Q& val ) - { - base_class::get()( item.m_val, val ); - } - }; -#endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT - //@endcond public: @@ -499,7 +370,6 @@ namespace cds { namespace container { : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h ) {} -# ifdef CDS_MOVE_SEMANTICS_SUPPORT /// Constructs a map with given hash functor tuple (move semantics) /** The probe set size and threshold are set as default, see CuckooSet() @@ -523,7 +393,6 @@ namespace cds { namespace container { ) : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward(h) ) {} -# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT /// Destructor clears the map ~CuckooMap() @@ -546,11 +415,7 @@ namespace cds { namespace container { template bool insert( K const& key ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return insert_key( key, [](value_type&){} ); -# else - return insert_key( key, empty_insert_functor() ); -# endif + return insert_with( key, [](value_type&){} ); } /// Inserts new node @@ -567,12 +432,7 @@ namespace cds { namespace container { template bool insert( K const& key, V const& val ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return insert_key( key, [&val](value_type& item) { item.second = val ; } ); -# else - insert_value_functor f(val); - return insert_key( key, cds::ref(f) ); -# endif + return insert_with( key, [&val](value_type& item) { item.second = val ; } ); } /// Inserts new node and initialize it by a functor @@ -590,9 +450,6 @@ namespace cds { namespace container { - item.first is a const reference to item's key that cannot be changed. - item.second is a reference to item's value that may be changed. - The user-defined functor can be passed by reference using boost::ref - and it is called only if inserting is successful. - The key_type should be constructible from value of type \p K. The function allows to split creating of new item into two part: @@ -604,29 +461,19 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. */ template - bool insert_key( const K& key, Func func ) + bool insert_with( const K& key, Func func ) { scoped_node_ptr pNode( alloc_node( key )); -# ifdef CDS_CXX11_LAMBDA_SUPPORT - if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_val ); } )) -# else - insert_key_wrapper wrapper(func); - if ( base_class::insert( *pNode, cds::ref(wrapper) )) -#endif - { + if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) { pNode.release(); return true; } return false; } -# ifdef CDS_EMPLACE_SUPPORT /// For key \p key inserts data of type \ref value_type constructed with std::forward(args)... /** Returns \p true if inserting successful, \p false otherwise. - - This function is available only for compiler that supports - variadic template and move semantics */ template bool emplace( K&& key, Args&&... args ) @@ -638,8 +485,6 @@ namespace cds { namespace container { } return false; } -# endif - /// Ensures that the \p key exists in the map /** @@ -666,8 +511,6 @@ namespace cds { namespace container { The functor may change any fields of the \p item.second that is \ref value_type. - You may pass \p func argument by reference using boost::ref. - Returns std::pair 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 key already is in the list. @@ -676,14 +519,9 @@ namespace cds { namespace container { std::pair ensure( K const& key, Func func ) { scoped_node_ptr pNode( alloc_node( key )); -# ifdef CDS_CXX11_LAMBDA_SUPPORT std::pair res = base_class::ensure( *pNode, - [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val ); } + [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); } ); -# else - ensure_wrapper wrapper( func ); - std::pair res = base_class::ensure( *pNode, cds::ref(wrapper) ); -# endif if ( res.first && res.second ) pNode.release(); return res; @@ -716,6 +554,7 @@ namespace cds { namespace container { template bool erase_with( K const& key, Predicate pred ) { + CDS_UNUSED( pred ); node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper()); if ( pNode ) { free_node( pNode ); @@ -736,7 +575,6 @@ namespace cds { namespace container { void operator()(value_type& item) { ... } }; \endcode - The functor may be passed by reference using boost:ref Return \p true if key is found and deleted, \p false otherwise @@ -747,7 +585,7 @@ namespace cds { namespace container { { node_type * pNode = base_class::erase( key ); if ( pNode ) { - cds::unref(f)( pNode->m_val ); + f( pNode->m_val ); free_node( pNode ); return true; } @@ -765,9 +603,10 @@ namespace cds { namespace container { template bool erase_with( K const& key, Predicate pred, Func f ) { + CDS_UNUSED( pred ); node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper() ); if ( pNode ) { - cds::unref(f)( pNode->m_val ); + f( pNode->m_val ); free_node( pNode ); return true; } @@ -786,8 +625,6 @@ namespace cds { namespace container { \endcode where \p item is the item found. - You can pass \p f argument by reference using boost::ref or cds::ref. - The functor may change \p item.second. The function returns \p true if \p key is found, \p false otherwise. @@ -795,12 +632,7 @@ namespace cds { namespace container { template bool find( K const& key, Func f ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );}); -# else - find_wrapper wrapper(f); - return base_class::find( key, cds::ref(wrapper) ); -# endif + return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );}); } /// Find the key \p val using \p pred predicate for comparing @@ -814,13 +646,9 @@ namespace cds { namespace container { template bool find_with( K const& key, Predicate pred, Func f ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT + CDS_UNUSED( pred ); return base_class::find_with( key, cds::details::predicate_wrapper(), - [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );}); -# else - find_wrapper wrapper(f); - return base_class::find_with( key, cds::details::predicate_wrapper(), cds::ref(wrapper) ); -# endif + [&f](node_type& item, K const& ) { f( item.m_val );}); } /// Find the key \p key @@ -846,6 +674,7 @@ namespace cds { namespace container { template bool find_with( K const& key, Predicate pred ) { + CDS_UNUSED( pred ); return base_class::find_with( key, cds::details::predicate_wrapper() ); } @@ -899,8 +728,7 @@ namespace cds { namespace container { { return base_class::mutex_policy_statistics(); } - }; }} // namespace cds::container -#endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H +#endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H