X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fstriped_map.h;h=e2e412669d7ba2770df85ba5f8cc7c8bd0dc6a12;hb=b68165e6375e3936f6f23466d827f24e48ebad96;hp=fd77756cc9d17a87948d9f0f252824720d65b69d;hpb=abe9634d97a9fece9abe5b0cfc78dc62f62f08c8;p=libcds.git diff --git a/cds/container/striped_map.h b/cds/container/striped_map.h index fd77756c..e2e41266 100644 --- a/cds/container/striped_map.h +++ b/cds/container/striped_map.h @@ -1,17 +1,41 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_STRIPED_MAP_H -#define __CDS_CONTAINER_STRIPED_MAP_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + 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_STRIPED_MAP_H +#define CDSLIB_CONTAINER_STRIPED_MAP_H #include #include #include #include -#ifndef CDS_CXX11_LAMBDA_SUPPORT -# include -#endif - namespace cds { namespace container { //@cond @@ -72,33 +96,33 @@ namespace cds { namespace container { among \p Options template arguments. The \p Options are: - - opt::mutex_policy - concurrent access policy. - Available policies: intrusive::striped_set::striping, intrusive::striped_set::refinable. - Default is %striped_set::striping. - - opt::hash - hash functor. Default option value see opt::v::hash_selector which selects default hash functor for - your compiler. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed - without locks. Note that item counting is an essential part of the map algorithm, so dummy type like atomicity::empty_item_counter - is not suitable. - - opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR. - - opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map. + - \p cds::opt::mutex_policy - concurrent access policy. + Available policies: \p striped_set::striping, \p striped_set::refinable. + Default is \p %striped_set::striping. + - \p cds::opt::hash - hash functor. Default option value see opt::v::hash_selector + which selects default hash functor for your compiler. + - \p cds::opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p %opt::less is used. + - \p cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed + without locks. Note that item counting is an essential part of the map algorithm, so dummy counter + like as \p atomicity::empty_item_counter is not suitable. + - \p cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p cds::opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map. Default option value depends on bucket container type: - for sequential containers like \p std::list, \p std::vector the resizing policy is hash_set::load_factor_resizing<4>; - for other type of containers like \p std::map, \p std::unordered_map the resizing policy is hash_set::no_resizing. - See \ref intrusive::striped_set namespace for list of all possible types of the option. + for sequential containers like \p std::list, \p std::vector the resizing policy is striped_set::load_factor_resizing<4> ; + for other type of containers like \p std::map, \p std::unordered_map the resizing policy is \p striped_set::no_resizing. + See \ref cds_striped_resizing_policy "available resizing policy". Note that the choose of resizing policy depends of \p Container type: for sequential containers like \p std::list, \p std::vector and so on, right choosing of the policy can significantly improve performance. For other, non-sequential types of \p Container (like a \p std::map) the resizing policy is not so important. - - opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing. + - \p cds::opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing. The policy can be optionally used in adapted bucket container for performance reasons of resizing. The detail of copy algorithm depends on type of bucket container and explains below. - \p opt::compare or \p opt::less options are used only in some \p Container class for searching an item. + \p %opt::compare or \p %opt::less options are used only in some \p Container class for searching an item. \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used. You can pass other option that would be passed to adapt metafunction, see below. @@ -106,14 +130,14 @@ namespace cds { namespace container { Internal details The \p %StripedMap class cannot utilize the \p Container container specified directly, but only its adapted variant which - supports an unified interface. Internally, the adaptation is made via hash_set::adapt metafunction that wraps bucket container + supports an unified interface. Internally, the adaptation is made via \p striped_set::adapt metafunction that wraps bucket container and provides the unified bucket interface suitable for \p %StripedMap. Such adaptation is completely transparent for you - you don't need to call \p adapt metafunction directly, \p %StripedMap class's internal machinery itself invokes appropriate \p adapt metafunction to adjust your \p Container container class to \p %StripedMap bucket's internal interface. All you need is to include a right header before striped_hash_map.h. - By default, intrusive::striped_set::adapt metafunction does not make any wrapping to \p AnyContainer, - so, the result %intrusive::striped_set::adapt::type is the same as \p AnyContainer. + By default, striped_set::adapt metafunction does not make any wrapping to \p AnyContainer, + so, the result striped_set::adapt::type is the same as \p AnyContainer. However, there are a lot of specializations of \p adapt for well-known containers, see table below. Any of this specialization wraps corresponding container making it suitable for the map's bucket. Remember, you should include the proper header file for \p adapt before striped_map.h. @@ -139,7 +163,7 @@ namespace cds { namespace container { The type of values stored in the \p std::list must be std::pair< const Key, V > , where \p Key - key type, and \p V - value type The list is ordered by key \p Key. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p Key stored in the list. + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p Key stored in the list. @@ -176,27 +200,6 @@ namespace cds { namespace container { For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X of type \p Key. - - \p stdext::hash_map (only for MS VC++ 2008) - - \code - #include - #include - typedef cds::container::StripedMap< - stdext::hash_map< Key, T, - stdext::hash_compare< - Key, - std::less - > - > - > striped_map; - \endcode - - - You should provide two different hash function \p h1 and \p h2 - one for stdext::hash_map and other for \p %StripedMap. - For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X of type \p Key. - - \p boost::container::slist @@ -211,7 +214,7 @@ namespace cds { namespace container { The type of values stored in the \p boost::container::slist must be std::pair< const Key, T > , where \p Key - key type, and \p T - value type. The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -228,7 +231,7 @@ namespace cds { namespace container { The type of values stored in the \p boost::container::list must be std::pair< const Key, T > , where \p Key - key type, and \p T - value type. The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -238,7 +241,7 @@ namespace cds { namespace container { #include #include typedef cds::container::StripedMap< - boost::container::map< Key, T, std::pair< const Key, T> > + boost::container::map< Key, T, std::less > > striped_map; \endcode @@ -253,7 +256,7 @@ namespace cds { namespace container { #include typedef cds::container::StripedMap< boost::container::flat_map< Key, T, - std::less< std::pair< const Key, T> > + std::less< std::less > > > striped_map; \endcode @@ -282,26 +285,26 @@ namespace cds { namespace container { Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p %StripedMap as bucket type. There are two possibility: - either your \p MyBestContainer class has native support of bucket's interface; - in this case, you can use default hash_set::adapt metafunction; - - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization - cds::container::hash_set::adapt metafunction providing necessary interface. + in this case, you can use default striped_set::adapt metafunction; + - or your \p MyBestContainer class does not support bucket's interface; it means you should develop a specialization + cds::container::striped_set::adapt metafunction providing necessary interface. - The hash_set::adapt< Container, Options... > metafunction has two template argument: + The striped_set::adapt< Container, Options... > metafunction has two template argument: - \p Container is the class that should be used as the bucket, for example, std::list< std::pair< Key, T > >. - \p Options pack is the options from \p %StripedMap declaration. The \p adapt metafunction can use any option from \p Options for its internal use. For example, a \p compare option can be passed to \p adapt metafunction via \p Options argument of \p %StripedMap declaration. - See hash_set::adapt metafunction for the description of interface that the bucket container must provide + See \p striped_set::adapt metafunction for the description of interface that the bucket container must provide to be \p %StripedMap compatible. Copy policy There are three predefined copy policy: - - \p cds::container::hash_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for + - \p cds::container::striped_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for any compiler that do not support move semantics - - \p cds::container::hash_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for + - \p cds::container::striped_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for any compiler that support move semantics. If compiler does not support move semantics, the move policy is the same as \p copy_item - - \p cds::container::hash_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support + - \p cds::container::striped_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support this copy policy, see details in table below. You can define your own copy policy specifically for your case. @@ -336,7 +339,7 @@ namespace cds { namespace container { std::list >::iterator itInsert, std::list >::iterator itWhat ) { - std::pair newVal( itWhat->first, T() ); + std::pair newVal( itWhat->first, T()); std::swap( list.insert( itInsert, newVal )->second, itWhat->second ); } } \endcode @@ -348,7 +351,7 @@ namespace cds { namespace container { std::list >::iterator itInsert, std::list >::iterator itWhat ) { - list.insert( itInsert, std::move( *itWhat ) ); + list.insert( itInsert, std::move( *itWhat )); } } \endcode @@ -357,7 +360,6 @@ namespace cds { namespace container { - \p std::map - \p std::unordered_map - - \p stdext::hash_map (only for MS VC++ 2008) - \p boost::container::map - \p boost::container::flat_map - \p boost::unordered_map @@ -376,7 +378,7 @@ namespace cds { namespace container { { std::swap( map.insert( - std::map::value_type( itWhat->first, T() ) ).first->second + std::map::value_type( itWhat->first, T())).first->second , itWhat->second )); } @@ -412,7 +414,7 @@ namespace cds { namespace container { bc::slist >::iterator itInsert, bc::slist >::iterator itWhat ) { - std::pair newVal( itWhat->first, T() ); + std::pair newVal( itWhat->first, T()); std::swap( list.insert( itInsert, newVal )->second, itWhat->second ); } } \endcode @@ -424,7 +426,7 @@ namespace cds { namespace container { bc::slist >::iterator itInsert, bc::slist >::iterator itWhat ) { - list.insert_after( itInsert, std::move( *itWhat ) ); + list.insert_after( itInsert, std::move( *itWhat )); } } \endcode @@ -433,7 +435,7 @@ namespace cds { namespace container { Advanced functions - libcds provides some advanced functions like \p erase_with, \p find_with, + The library provides some advanced functions like \p erase_with(), \p find_with(), that cannot be supported by all underlying containers. The table below shows whether underlying container supports those functions (the sign "+" means "container supports the function"): @@ -459,11 +461,6 @@ namespace cds { namespace container { - - - - \p stdext::hash_map (only for MS VC++ 2008) - - - - - \p boost::container::slist + @@ -537,46 +534,6 @@ template return p.first; } }; - -# ifndef CDS_CXX11_LAMBDA_SUPPORT - - template - class find_functor_wrapper: protected cds::details::functor_wrapper - { - typedef cds::details::functor_wrapper base_class; - public: - find_functor_wrapper() {} - find_functor_wrapper( Func f ): base_class(f) {} - - template - void operator()( value_type& pair, Q const& /*val*/ ) - { - base_class::get()( pair ); - } - }; - - 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; - } - }; - - struct dummy_insert_functor - { - void operator()( value_type& item ) - {} - }; -# endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT - //@endcond public: @@ -609,7 +566,7 @@ template StripedMap( size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16. ,resizing_policy&& resizingPolicy ///< Resizing policy - ) : base_class( nCapacity, std::forward(resizingPolicy) ) + ) : base_class( nCapacity, std::forward(resizingPolicy)) {} /// Destructor destroys internal data @@ -622,20 +579,16 @@ template The function creates a node with \p key and default value, and then inserts the node created into the map. Preconditions: - - The \ref key_type should be constructible from a value of type \p K. - In trivial case, \p K is equal to \ref key_type. - - The \ref mapped_type should be default-constructible. + - The \p key_type should be constructible from a value of type \p K. + In trivial case, \p K is equal to \p key_type. + - The \p mapped_type should be default-constructible. Returns \p true if inserting successful, \p false otherwise. */ template bool insert( K const& key ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return insert_key( key, [](value_type&){} ); -# else - return insert_key( key, dummy_insert_functor() ); -# endif + return insert_with( key, [](value_type&){} ); } /// Inserts new node @@ -644,20 +597,15 @@ template and then inserts the node created into the map. Preconditions: - - The \ref key_type should be constructible from \p key of type \p K. - - The \ref mapped_type should be constructible from \p val of type \p V. + - The \p key_type should be constructible from \p key of type \p K. + - The \p mapped_type should be constructible from \p val of type \p V. Returns \p true if \p val is inserted into the set, \p false otherwise. */ 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 @@ -675,9 +623,6 @@ template - 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: @@ -689,12 +634,12 @@ template 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 ) { return base_class::insert( key, func ); } - /// For key \p key inserts data of type \ref mapped_type constructed with std::forward(args)... + /// For key \p key inserts data of type \p mapped_type created in-place from \p args /** Returns \p true if inserting successful, \p false otherwise. */ @@ -719,39 +664,29 @@ template return bOk; } - /// 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 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 mapped_type. + - \p item - item of the map - You may pass \p func argument by reference using boost::ref. - - Returns std::pair where \p first is true if operation is successfull, + Returns std::pair where \p first is true if operation is successful, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already is in the map. */ template - std::pair ensure( K const& key, Func func ) + std::pair update( K const& key, Func func, bool bAllowInsert = true ) { std::pair result; bool bResize; @@ -761,7 +696,7 @@ template scoped_cell_lock sl( base_class::m_MutexPolicy, nHash ); pBucket = base_class::bucket( nHash ); - result = pBucket->ensure( key, func ); + result = pBucket->update( key, func, bAllowInsert ); bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket ); } @@ -769,6 +704,14 @@ template base_class::resize(); return result; } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update() instead") + std::pair ensure( K const& key, Func func ) + { + return update( key, func, true ); + } + //@endcond /// Delete \p key from the map /** \anchor cds_nonintrusive_StripedMap_erase @@ -796,11 +739,7 @@ template ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type > bool erase_with( K const& key, Less pred ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT return erase_with( key, pred, [](value_type const&) {} ); -# else - return erase_with( key, pred, typename base_class::empty_erase_functor() ); -# endif } /// Delete \p key from the map @@ -815,11 +754,8 @@ template 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 - - See also: \ref erase */ template bool erase( K const& key, Func f ) @@ -842,6 +778,7 @@ template ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type > bool erase_with( K const& key, Less pred, Func f ) { + CDS_UNUSED( pred ); return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f ); } @@ -857,8 +794,6 @@ template \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. @@ -866,12 +801,7 @@ template template bool find( K const& key, Func f ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } ); -# else - find_functor_wrapper fw(f); - return base_class::find( key, cds::ref(fw) ); -# endif + return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { f(pair); } ); } /// Find the key \p val using \p pred predicate @@ -889,44 +819,56 @@ template ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type > bool find_with( K const& key, Less pred, Func f ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT + CDS_UNUSED( pred ); return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), - [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } ); -# else - find_functor_wrapper fw(f); - return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), cds::ref(fw) ); -# endif + [&f]( value_type& pair, K const& ) mutable { f(pair); } ); } - /// Find the key \p key - /** \anchor cds_nonintrusive_StripedMap_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("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 + /// Checks whether the set contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)" - but \p pred is used for key comparing - \p Less has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the set. + 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 set. @note This function is enabled if the compiler supports C++11 default template arguments for function template and the underlying container - supports \p %find_with feature. + supports \p %contains() feature. */ template ::type > + bool contains( K const& key, Less pred ) + { + CDS_UNUSED( pred ); + return base_class::contains( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >()); + } + //@cond + template ::type > + CDS_DEPRECATED("use contains()") bool find_with( K const& key, Less pred ) { - return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() ); + return contains( key, pred ); } + //@endcond /// Clears the map void clear() @@ -982,4 +924,4 @@ template }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H +#endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_H