X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_map_rcu.h;h=cc0fba5eb8ee687488cd75a32c9b7e52f77f6165;hb=2402fb1beb25ec532cea91c8dfbb9425eb5bdf48;hp=54cd1b5710e9cd82e978c92a82e4fbd36c0f3ab1;hpb=ba8f90c18cb0f1087573692b6e7aacc183233233;p=libcds.git diff --git a/cds/container/michael_map_rcu.h b/cds/container/michael_map_rcu.h index 54cd1b57..cc0fba5e 100644 --- a/cds/container/michael_map_rcu.h +++ b/cds/container/michael_map_rcu.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H -#define __CDS_CONTAINER_MICHAEL_MAP_RCU_H + (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_MICHAEL_MAP_RCU_H +#define CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H #include #include @@ -33,7 +61,7 @@ namespace cds { namespace container { \p key_type and an argument of template type \p K must meet the following requirements: - \p key_type should be constructible from value of type \p K; - the hash functor should be able to calculate correct hash value from argument \p key of type \p K: - hash( key_type(key) ) == hash( key ) + hash( key_type(key)) == hash( key ) - values of type \p key_type and \p K should be comparable How to use @@ -55,89 +83,78 @@ namespace cds { namespace container { { public: typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector - typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation + typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation typedef Traits traits; ///< Map traits - typedef typename bucket_type::key_type key_type ; ///< key type - typedef typename bucket_type::mapped_type mapped_type ; ///< value type - typedef typename bucket_type::value_type value_type ; ///< key/value pair stored in the list - typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor + typedef typename ordered_list::key_type key_type; ///< key type + typedef typename ordered_list::mapped_type mapped_type; ///< value type + typedef typename ordered_list::value_type value_type; ///< key/value pair stored in the list + typedef typename ordered_list::key_comparator key_comparator;///< key comparison functor +#ifdef CDS_DOXYGEN_INVOKED + typedef typename ordered_list::stat stat; ///< Internal statistics + typedef typename ordered_list::exempt_ptr exempt_ptr; ///< pointer to extracted node + /// Type of \p get() member function return value + typedef typename ordered_list::raw_ptr raw_ptr; + typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock +#endif /// Hash functor for \ref key_type and all its derivatives that you use typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash; typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::allocator allocator; ///< Bucket table allocator - /// Bucket table allocator - typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator; - - typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock - typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that - static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal; + static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal; + + // GC and OrderedList::gc must be the same + static_assert(std::is_same::value, "GC and OrderedList::gc must be the same"); + + // atomicity::empty_item_counter is not allowed as a item counter + static_assert(!std::is_same::value, + "cds::atomicity::empty_item_counter is not allowed as a item counter"); protected: - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - bucket_type * m_Buckets; ///< bucket table + //@cond + typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; - private: + typedef typename ordered_list::template rebind_traits< + cds::opt::item_counter< cds::atomicity::empty_item_counter > + , cds::opt::stat< typename bucket_stat::wrapped_stat > + >::type internal_bucket_type; + + /// Bucket table allocator + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; + //@endcond + + public: //@cond - const size_t m_nHashBitmask; + typedef typename bucket_stat::stat stat; + typedef typename internal_bucket_type::exempt_ptr exempt_ptr; + typedef typename internal_bucket_type::raw_ptr raw_ptr; + typedef typename internal_bucket_type::rcu_lock rcu_lock; //@endcond protected: //@cond - /// Calculates hash value of \p key - template - size_t hash_value( Q const& key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } - - /// Returns the bucket (ordered list) for \p key - template - bucket_type& bucket( Q const& key ) - { - return m_Buckets[ hash_value( key ) ]; - } - template - bucket_type const& bucket( Q const& key ) const - { - return m_Buckets[ hash_value( key ) ]; - } + const size_t m_nHashBitmask; + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + internal_bucket_type * m_Buckets; ///< bucket table + stat m_Stat; ///< Internal statistics //@endcond - protected: - /// Forward iterator - /** - \p IsConst - constness boolean flag - - The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features: - - it has no post-increment operator, only pre-increment - - it iterates items in unordered fashion - - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data. - - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent - deleting operations it is no guarantee that you iterate all item in the map. - Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container - for debug purpose only. - */ + protected: + //@cond template - class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > + class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > { - //@cond - typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class; + typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class; friend class MichaelHashMap; - //@endcond protected: - //@cond - //typedef typename base_class::bucket_type bucket_type; typedef typename base_class::bucket_ptr bucket_ptr; typedef typename base_class::list_iterator list_iterator; - //typedef typename bucket_type::key_type key_type; - //@endcond - public: /// Value pointer type (const for const_iterator) typedef typename cds::details::make_const_type::pointer value_ptr; @@ -150,11 +167,9 @@ namespace cds { namespace container { typedef typename cds::details::make_const_type::reference pair_ref; protected: - //@cond iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast ) : base_class( it, pFirst, pLast ) {} - //@endcond public: /// Default ctor @@ -214,9 +229,49 @@ namespace cds { namespace container { return !( *this == i ); } }; + //@endcond public: + ///@name Forward iterators (thread-safe under RCU lock) + //@{ + /// Forward iterator + /** + The forward iterator for Michael's map is based on \p OrderedList forward iterator and has some features: + - it has no post-increment operator + - it iterates items in unordered fashion + + You may safely use iterators in multi-threaded environment only under RCU lock. + Otherwise, a crash is possible if another thread deletes the element the iterator points to. + + The iterator interface: + \code + class iterator { + public: + // Default constructor + iterator(); + + // Copy construtor + iterator( iterator const& src ); + + // Dereference operator + value_type * operator ->() const; + + // Dereference operator + value_type& operator *() const; + + // Preincrement operator + iterator& operator ++(); + + // Assignment operator + iterator& operator = (iterator const& src); + + // Equality operators + bool operator ==(iterator const& i ) const; + bool operator !=(iterator const& i ) const; + }; + \endcode + */ typedef iterator_type< false > iterator; /// Const forward iterator @@ -228,7 +283,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() ); + return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count()); } /// Returns an iterator that addresses the location succeeding the last element in a map @@ -239,69 +294,62 @@ namespace cds { namespace container { */ iterator end() { - return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); + return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count()); } /// Returns a forward const iterator addressing the first element in a map - //@{ const_iterator begin() const { return get_const_begin(); } + + /// Returns a forward const iterator addressing the first element in a map const_iterator cbegin() const { return get_const_begin(); } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a map - //@{ const_iterator end() const { return get_const_end(); } + + /// Returns an const iterator that addresses the location succeeding the last element in a map const_iterator cend() const { return get_const_end(); } - //@} - - private: - //@cond - const_iterator get_const_begin() const - { - return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); - } - const_iterator get_const_end() const - { - return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); - } - //@endcond + //@} public: /// Initializes the map - /** @copydetails cds_nonintrusive_MichaelHashMap_hp_ctor + /** + The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount + when you create an object. + \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10. + Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [O(nLoadFactor)]. + Note, that many popular STL hash map implementation uses load factor 1. + + The ctor defines hash table size as rounding nMacItemCount / nLoadFactor up to nearest power of two. */ MichaelHashMap( size_t nMaxItemCount, ///< estimation of max item count in the hash map size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor )) + , m_Buckets( bucket_table_allocator().allocate( bucket_count())) { - // GC and OrderedList::gc must be the same - static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - - // atomicity::empty_item_counter is not allowed as a item counter - static_assert( !std::is_same::value, - "cds::atomicity::empty_item_counter is not allowed as a item counter"); - - m_Buckets = bucket_table_allocator().NewArray( bucket_count() ); + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + construct_bucket( it ); } /// Clears hash map and destroys it ~MichaelHashMap() { clear(); - bucket_table_allocator().Delete( m_Buckets, bucket_count() ); + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + it->~internal_bucket_type(); + bucket_table_allocator().deallocate( m_Buckets, bucket_count()); } /// Inserts new node with key and default value @@ -382,58 +430,61 @@ namespace cds { namespace container { synchronization. */ template - bool insert_key( const K& key, Func func ) + bool insert_with( const K& key, Func func ) { - const bool bRet = bucket( key ).insert_key( key, func ); + const bool bRet = bucket( key ).insert_with( key, func ); if ( bRet ) ++m_ItemCounter; return bRet; } - - /// Ensures that the \p key exists in the map + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element 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). - 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: + will be inserted into the map iff \p bAllowInsert is \p true. + (note that in this case the \ref key_type should be constructible from type \p K). + Otherwise, if \p key is found, the functor \p func is called with item found. + + 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 + - \p item - the item found or inserted - The functor may change any fields of the \p item.second that is \ref mapped_type. + The functor may change any fields of the \p item.second that is \p mapped_type. The function applies RCU lock internally. - 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 exists. @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level synchronization. */ template - std::pair ensure( K const& key, Func func ) + std::pair update( K const& key, Func func, bool bAllowInsert = true ) { - std::pair bRet = bucket( key ).ensure( key, func ); - if ( bRet.first && bRet.second ) + std::pair bRet = bucket( key ).update( key, func, bAllowInsert ); + if ( bRet.second ) ++m_ItemCounter; return bRet; } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( K const& key, Func func ) + { + return update( key, func, true ); + } + //@endcond /// For key \p key inserts data of type \p mapped_type created from \p args /** @@ -527,14 +578,14 @@ namespace cds { namespace container { /// Extracts an item from the map /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract The function searches an item with key equal to \p key, - unlinks it from the map, places item pointer into \p dest argument, and returns \p true. - If the item is not found the function return \p false. + unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item is not found the function return an empty \p exempt_ptr. - @note The function does NOT call RCU read-side lock or synchronization, - and does NOT dispose the item found. It just excludes the item from the map - and returns a pointer to item found. - You should lock RCU before calling of the function, and you should synchronize RCU - outside the RCU lock to free extracted item + The function just excludes the key from the map and returns a pointer to item found. + Depends on \p ordered_list you should or should not lock RCU before calling of this function: + - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked + - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked + See ordered list implementation for details. \code #include @@ -549,16 +600,14 @@ namespace cds { namespace container { // ... rcu_michael_map::exempt_ptr p; - { - // first, we should lock RCU - rcu_michael_map::rcu_lock lock; - - // Now, you can apply extract function - // Note that you must not delete the item found inside the RCU lock - if ( theMap.extract( p, 10 )) { - // do something with p - ... - } + + // For MichaelList we should not lock RCU + + // Note that you must not delete the item found inside the RCU lock + p = theMap.extract( 10 ); + if ( p ) { + // do something with p + ... } // We may safely release p here @@ -567,30 +616,27 @@ namespace cds { namespace container { \endcode */ template - bool extract( exempt_ptr& dest, K const& key ) + exempt_ptr extract( K const& key ) { - if ( bucket( key ).extract( dest, key )) { + exempt_ptr p = bucket( key ).extract( key ); + if ( p ) --m_ItemCounter; - return true; - } - return false; + return p; } /// Extracts an item from the map using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_extract "extract(exempt_ptr&, K const&)" - but \p pred is used for key comparing. + The function is an analog of \p extract(K const&) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( exempt_ptr& dest, K const& key, Less pred ) + exempt_ptr extract_with( K const& key, Less pred ) { - if ( bucket( key ).extract_with( dest, key, pred )) { + exempt_ptr p = bucket( key ).extract_with( key, pred ); + if ( p ) --m_ItemCounter; - return true; - } - return false; + return p; } /// Finds the key \p key @@ -615,7 +661,7 @@ namespace cds { namespace container { The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( K const& key, Func f ) const + bool find( K const& key, Func f ) { return bucket( key ).find( key, f ); } @@ -628,42 +674,58 @@ namespace cds { namespace container { \p Less must imply the same element order as the comparator used for building the map. */ template - bool find_with( K const& key, Less pred, Func f ) const + bool find_with( K const& key, Less pred, Func f ) { return bucket( key ).find_with( key, pred, f ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelMap_rcu_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. The function applies RCU lock internally. */ template - bool find( K const& key ) const + bool contains( K const& key ) { - return bucket( key ).find( key ); + return bucket( key ).contains( key ); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find( K const& key ) + { + return bucket( key ).contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)" - but \p pred is used for key comparing. + The function is an analog of 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 find_with( K const& key, Less pred ) const + bool contains( K const& key, Less pred ) + { + return bucket( key ).contains( key, pred ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( K const& key, Less pred ) { - return bucket( key ).find_with( key, pred ); + return bucket( key ).contains( key, pred ); } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get The function searches the item with key equal to \p key and returns the pointer to item found. If \p key is not found it returns \p nullptr. + Note the type of returned value depends on underlying \p ordered_list. + For details, see documentation of ordered list you use. Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type. @@ -673,22 +735,23 @@ namespace cds { namespace container { typedef cds::container::MichaelHashMap< your_template_parameters > hash_map; hash_map theMap; // ... + typename hash_map::raw_ptr gp; { // Lock RCU hash_map::rcu_lock lock; - hash_map::value_type * = theMap.get( 5 ); - if ( pVal ) { - // Deal with pVal + gp = theMap.get( 5 ); + if ( gp ) { + // Deal with gp //... } // Unlock RCU by rcu_lock destructor - // pVal can be freed at any time after RCU has been unlocked + // gp can be reclaimed at any time after RCU has been unlocked } \endcode */ template - value_type * get( K const& key ) const + raw_ptr get( K const& key ) { return bucket( key ).get( key ); } @@ -703,7 +766,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - value_type * get_with( K const& key, Less pred ) const + raw_ptr get_with( K const& key, Less pred ) { return bucket( key ).get_with( key, pred ); } @@ -742,6 +805,12 @@ namespace cds { namespace container { return m_ItemCounter; } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + /// Returns the size of hash table /** Since \p %MichaelHashMap cannot dynamically extend the hash table size, @@ -752,7 +821,52 @@ namespace cds { namespace container { { return m_nHashBitmask + 1; } + + protected: + //@cond + /// Calculates hash value of \p key + template + size_t hash_value( Q const& key ) const + { + return m_HashFunctor( key ) & m_nHashBitmask; + } + + /// Returns the bucket (ordered list) for \p key + template + internal_bucket_type& bucket( Q const& key ) + { + return m_Buckets[hash_value( key )]; + } + template + internal_bucket_type const& bucket( Q const& key ) const + { + return m_Buckets[hash_value( key )]; + } + //@endcond + private: + //@cond + const_iterator get_const_begin() const + { + return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count()); + } + const_iterator get_const_end() const + { + return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count()); + } + + template + typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type; + } + + template + typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type( m_Stat ); + } + //@endcond }; }} // namespace cds::container -#endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H +#endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H