X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fcuckoo_map.h;h=d8dc233ac9c020f7cde6b001d0729c86b3cdfce1;hb=c14ae188467d82f4b9227dcfc1052fcd113ad459;hp=f9ae03c7a8fb5570346444bdfee40dbcb3976dda;hpb=bab1583cb2db30355c138a507943cd5ad068ccf4;p=libcds.git diff --git a/cds/container/cuckoo_map.h b/cds/container/cuckoo_map.h index f9ae03c7..d8dc233a 100644 --- a/cds/container/cuckoo_map.h +++ b/cds/container/cuckoo_map.h @@ -1,9 +1,37 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_CUCKOO_MAP_H -#define __CDS_CONTAINER_CUCKOO_MAP_H - -#include +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H +#define CDSLIB_CONTAINER_CUCKOO_MAP_H + +#include #include namespace cds { namespace container { @@ -13,14 +41,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 +70,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 +77,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; @@ -122,7 +122,7 @@ namespace cds { namespace container { About Cuckoo hashing [From "The Art of Multiprocessor Programming"] - Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item + Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size N = 2k we use a two-entry array of tables, and two independent hash functions, h0, h1: KeyRange -> 0,...,k-1 @@ -160,48 +160,16 @@ namespace cds { namespace container { the average search complexity is O(PROBE_SET/2). However, the overhead of sorting can eliminate a gain of ordered search. - The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet - declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain - opt::equal_to option. + The probe set is ordered if \p compare or \p less is specified in \p Traits + template parameter. Otherwise, the probe set is unordered and \p Traits must contain + \p equal_to predicate. 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 +197,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 +228,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 +252,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 +265,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 +307,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 @@ -374,71 +341,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: @@ -537,11 +439,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 @@ -558,12 +456,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 @@ -581,9 +474,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: @@ -595,16 +485,10 @@ 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; } @@ -626,53 +510,47 @@ namespace cds { namespace container { return false; } - /// Ensures that the \p key exists in the map + /// Updates the node /** The operation performs inserting or changing data with lock-free manner. - If the \p key not found in the map, then the new item created from \p key - is inserted into the map (note that in this case the \ref key_type should be - constructible from type \p K). + If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. - The functor \p Func may be a function with signature: - \code - void func( bool bNew, value_type& item ); - \endcode - or a functor: + The functor \p func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list - - The functor may change any fields of the \p item.second that is \ref value_type. + - \p item - an item of the map for \p key - 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. + Returns std::pair where \p first is \p true if operation is successful, + i.e. the node has been inserted or updated, + \p second is \p true if new item has been added or \p false if the item with \p key + already exists. */ template - std::pair ensure( K const& key, Func func ) + std::pair update( K const& key, Func func, bool bAllowInsert = true ) { 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 ); } + std::pair res = base_class::update( *pNode, + [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }, + bAllowInsert ); -# 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; } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( K const& key, Func func ) + { + return update( key, func, true ); + } + //@endcond /// Delete \p key from the map /** \anchor cds_nonintrusive_CuckooMap_erase_val @@ -701,6 +579,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 ); @@ -721,7 +600,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 @@ -732,7 +610,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; } @@ -750,9 +628,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; } @@ -771,8 +650,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. @@ -780,12 +657,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 @@ -799,40 +671,50 @@ 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 - /** \anchor cds_nonintrusive_CuckooMap_find_val - + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. */ template + bool contains( K const& key ) + { + return base_class::contains( key ); + } + //@cond + template + CDS_DEPRECATED("the function is deprecated, use contains()") bool find( K const& key ) { - return base_class::find( key ); + return contains( key ); } + //@endcond - /// Find the key \p val using \p pred predicate for comparing + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)" - but \p pred is used for key comparison. - If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less. - If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to. - \p pred must imply the same element order as the comparator used for building the map. + The function is similar to contains( key ) but \p pred is used for key comparing. + \p Less functor has the interface like \p std::less. + \p Less must imply the same element order as the comparator used for building the map. */ template + bool contains( K const& key, Predicate pred ) + { + CDS_UNUSED( pred ); + return base_class::contains( key, cds::details::predicate_wrapper() ); + } + //@cond + template + CDS_DEPRECATED("the function is deprecated, use contains()") bool find_with( K const& key, Predicate pred ) { - return base_class::find_with( key, cds::details::predicate_wrapper() ); + return contains( key, pred ); } + //@endcond /// Clears the map void clear() @@ -884,8 +766,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