X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_map.h;h=799407ac63546144d584b7e84856ca9340508569;hb=71da1f106e0d9451556720b8315f7db0f24383b7;hp=1f7291e9f9ea494eb2ea5fa267547846a673abc3;hpb=0594e601c8b1fcf9f8ca595d49ef025be04aa8d1;p=libcds.git diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h index 1f7291e9..799407ac 100644 --- a/cds/container/michael_map.h +++ b/cds/container/michael_map.h @@ -1,9 +1,38 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_MICHAEL_MAP_H -#define __CDS_CONTAINER_MICHAEL_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_MICHAEL_MAP_H +#define CDSLIB_CONTAINER_MICHAEL_MAP_H #include +#include #include namespace cds { namespace container { @@ -24,10 +53,10 @@ namespace cds { namespace container { - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector" from the \p libcds library. Note the \p GC must be the same as the GC used for \p OrderedList - - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, \p MichaelKVList - or \p LazyKVList. The ordered list implementation specifies the \p Key and \p Value types stored in the hash-map, - the reclamation schema \p GC used by hash-map, the comparison functor for the type \p Key and other features - specific for the ordered list. + - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, \p MichaelKVList, + \p LazyKVList, \p IterableKVList. The ordered list implementation specifies the \p Key and \p Value types + stored in the hash-map, the reclamation schema \p GC used by hash-map, the comparison functor for the type \p Key + and other features specific for the ordered list. - \p Traits - map traits, default is \p michael_map::traits. Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction. @@ -35,7 +64,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 There are the specializations: @@ -44,47 +73,6 @@ namespace cds { namespace container { - for \p cds::gc::nogc declared in cds/container/michael_map_nogc.h, see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap". - Iterators - - The class supports a forward iterator (\ref iterator and \ref const_iterator). - The iteration is unordered. - The iterator object is thread-safe: the element pointed by the iterator object is guarded, - so, the element cannot be reclaimed while the iterator object is alive. - However, passing an iterator object between threads is dangerous. - - @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate - all elements in the set: any concurrent deletion can exclude the element - pointed by the iterator from the set, and your iteration can be terminated - before end of the set. Therefore, such iteration is more suitable for debugging purpose only - - Remember, each iterator object requires an additional hazard pointer, that may be - a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of - guards is unlimited). - - The iterator class supports the following minimalistic interface: - \code - struct iterator { - // Default ctor - iterator(); - - // Copy ctor - iterator( iterator const& s); - - value_type * operator ->() const; - value_type& operator *() const; - - // Pre-increment - iterator& operator ++(); - - // Copy assignment - iterator& operator = (const iterator& src); - - bool operator ==(iterator const& i ) const; - bool operator !=(iterator const& i ) const; - }; - \endcode - Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced. - \anchor cds_nonintrusive_MichaelHashMap_how_touse How to use @@ -160,58 +148,64 @@ namespace cds { namespace container { class MichaelHashMap { public: - typedef GC gc; ///< Garbage collector - typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket - typedef Traits traits; ///< Map traits + typedef GC gc; ///< Garbage collector + typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket + 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 map + 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 map + typedef typename traits::allocator allocator; ///< Bucket table allocator - typedef typename bucket_type::key_comparator key_comparator; ///< key compare functor + typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor +#ifdef CDS_DOXYGEN_INVOKED + typedef typename ordered_list::stat stat; ///< Internal statistics + /// Guarded pointer - a result of \p get() and \p extract() functions + typedef typename ordered_list::guarded_ptr guarded_ptr; +#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 - /// Bucket table allocator - typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator; - typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer + // GC and OrderedList::gc must be the same + static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - protected: - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - bucket_type * m_Buckets; ///< bucket table + // atomicity::empty_item_counter is not allowed as a item counter + static_assert( !std::is_same::value, + "atomicity::empty_item_counter is not allowed as a item counter"); + + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required - private: //@cond - const size_t m_nHashBitmask; + typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; + + 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; + + typedef typename internal_bucket_type::guarded_ptr guarded_ptr; + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; + typedef typename bucket_stat::stat stat; //@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 ) ]; - } + const size_t m_nHashBitmask; + internal_bucket_type* m_Buckets; ///< bucket table + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + stat m_Stat; ///< Internal statistics //@endcond protected: //@cond /// Forward iterator 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 > { - 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; protected: @@ -295,7 +289,55 @@ namespace cds { namespace container { //@endcond public: + ///@name Forward iterators (only for debugging purpose) + //@{ /// Forward iterator + /** + The forward iterator for Michael's map has some features: + - it has no post-increment operator + - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator. + For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard" + may be thrown if the limit of guard count per thread is exceeded. + - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard. + + Iterator thread safety depends on type of \p OrderedList: + - for \p MichaelKVList and \p LazyKVList: iterator guarantees safety even if you delete the item that iterator points to + because that item is guarded by hazard pointer. + However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the map. + Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. + Use this iterator on the concurrent container for debugging purpose only. + - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment. + + 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 + + @note The iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced. + */ typedef iterator_type< false > iterator; /// Const forward iterator @@ -307,7 +349,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() ); + return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end()); } /// Returns an iterator that addresses the location succeeding the last element in a map @@ -318,44 +360,31 @@ 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( bucket_end()[-1].end(), bucket_end() - 1, bucket_end()); } /// 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 @@ -371,23 +400,22 @@ namespace cds { namespace container { 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_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, - "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 @@ -402,9 +430,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( const K& key ) + bool insert( K&& key ) { - const bool bRet = bucket( key ).insert( key ); + const bool bRet = bucket( key ).insert( std::forward( key )); if ( bRet ) ++m_ItemCounter; return bRet; @@ -422,9 +450,9 @@ namespace cds { namespace container { Returns \p true if \p val is inserted into the map, \p false otherwise. */ template - bool insert( K const& key, V const& val ) + bool insert( K&& key, V&& val ) { - const bool bRet = bucket( key ).insert( key, val ); + const bool bRet = bucket( key ).insert( std::forward( key ), std::forward( val )); if ( bRet ) ++m_ItemCounter; return bRet; @@ -462,52 +490,104 @@ namespace cds { namespace container { synchronization. */ template - bool insert_key( const K& key, Func func ) + bool insert_with( K&& key, Func func ) { - const bool bRet = bucket( key ).insert_key( key, func ); + const bool bRet = bucket( key ).insert_with( std::forward( 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 \p key_type should be - constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor \p Func may signature is: + 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 depends on \p OrderedList: + + for \p MichaelKVList, \p LazyKVList \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 \p mapped_type. - Returns std::pair where \p first is true if operation is successfull, + for \p IterableKVList + \code + void func( value_type& val, value_type * old ); + \endcode + where + - \p val - a new data constructed from \p key + - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr. + + The functor may change non-key fields of \p val; however, \p func must guarantee + that during changing no any other modifications could be made on this item by concurrent threads. + + @return 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_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList" + as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level synchronization. */ + template + std::pair update( K&& key, Func func, bool bAllowInsert = true ) + { + std::pair bRet = bucket( key ).update( std::forward( key ), func, bAllowInsert ); + if ( bRet.first && bRet.second ) + ++m_ItemCounter; + return bRet; + } + //@cond template + CDS_DEPRECATED("ensure() is deprecated, use update()") std::pair ensure( K const& key, Func func ) { - std::pair bRet = bucket( key ).ensure( key, func ); + std::pair bRet = bucket( key ).update( key, func, true ); if ( bRet.first && bRet.second ) ++m_ItemCounter; return bRet; } + //@endcond + + /// Inserts or updates the node (only for \p IterableKVList) + /** + The operation performs inserting or changing data with lock-free manner. + + If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true. + Otherwise, the current element is changed to \p val, the old element will be retired later. + + Returns std::pair where \p first is \p true if operation is successful, + \p second is \p true if \p val has been added or \p false if the item with that key + already in the map. + */ + template +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value, + std::pair + >::type +#endif + upsert( Q&& key, V&& val, bool bAllowInsert = true ) + { + std::pair bRet = bucket( val ).upsert( std::forward( key ), std::forward( val ), bAllowInsert ); + if ( bRet.second ) + ++m_ItemCounter; + return bRet; + } /// For key \p key inserts data of type \p mapped_type created from \p args /** @@ -597,12 +677,12 @@ namespace cds { namespace container { /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract The function searches an item with key equal to \p key, - unlinks it from the set, and returns it in \p dest parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the map, and returns it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type. - The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released. + The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -611,40 +691,40 @@ namespace cds { namespace container { michael_map theMap; // ... { - michael_map::guarded_ptr gp; - theMap.extract( gp, 5 ); - // Deal with gp - // ... - + michael_map::guarded_ptr gp( theMap.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } // Destructor of gp releases internal HP guard } \endcode */ template - bool extract( guarded_ptr& dest, K const& key ) + guarded_ptr extract( K const& key ) { - const bool bRet = bucket( key ).extract( dest, key ); - if ( bRet ) + guarded_ptr gp( bucket( key ).extract( key )); + if ( gp ) --m_ItemCounter; - return bRet; + return gp; } /// Extracts the item using compare functor \p pred /** - The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(guarded_ptr&, K const&)" + The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)" but \p pred predicate is used for key comparing. - \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K + \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K in any order. \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( guarded_ptr& dest, K const& key, Less pred ) + guarded_ptr extract_with( K const& key, Less pred ) { - const bool bRet = bucket( key ).extract_with( dest, key, pred ); - if ( bRet ) + guarded_ptr gp( bucket( key ).extract_with( key, pred )); + if ( gp ) --m_ItemCounter; - return bRet; + return gp; } /// Finds the key \p key @@ -672,6 +752,28 @@ namespace cds { namespace container { return bucket( key ).find( key, f ); } + /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList) + /** + If \p key is not found the function returns \p end(). + + @note This function is supported only for map based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find( K const& key ) + { + auto& b = bucket( key ); + auto it = b.find( key ); + if ( it == b.end()) + return end(); + return iterator( it, &b, bucket_end()); + } + + /// Finds the key \p val using \p pred predicate for searching /** The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)" @@ -685,36 +787,59 @@ namespace cds { namespace container { return bucket( key ).find_with( key, pred, f ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelMap_find_val + /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList) + /** + The function is an analog of \p find(K&) 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 set. + + If \p key is not found the function returns \p end(). + + @note This function is supported only for map based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find_with( K const& key, Less pred ) + { + auto& b = bucket( key ); + auto it = b.find_with( key, pred ); + if ( it == b.end()) + return end(); + return iterator( it, &b, bucket_end()); + } + + /// 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 find( K const& key ) + bool contains( K const& key ) { - return bucket( key ).find( key ); + return bucket( key ).contains( key ); } - /// 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_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 ) + bool contains( K const& key, Less pred ) { - return bucket( key ).find_with( key, pred ); + return bucket( key ).contains( key, pred ); } /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashMap_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns the guarded pointer to the item found. + If \p key is not found the function returns an empty guarded pointer, @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -724,8 +849,8 @@ namespace cds { namespace container { michael_map theMap; // ... { - michael_map::guarded_ptr gp; - if ( theMap.get( gp, 5 )) { + michael_map::guarded_ptr gp( theMap.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -737,24 +862,24 @@ namespace cds { namespace container { should accept a parameter of type \p K that can be not the same as \p key_type. */ template - bool get( guarded_ptr& ptr, K const& key ) + guarded_ptr get( K const& key ) { - return bucket( key ).get( ptr, key ); + return bucket( key ).get( key ); } /// Finds \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( guarded_ptr& ptr, K const&)" + The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)" but \p pred is used for comparing the keys. - \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K + \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K in any order. \p pred must imply the same element order as the comparator used for building the map. */ template - bool get_with( guarded_ptr& ptr, K const& key, Less pred ) + guarded_ptr get_with( K const& key, Less pred ) { - return bucket( key ).get_with( ptr, key, pred ); + return bucket( key ).get_with( key, pred ); } /// Clears the map (not atomic) @@ -791,7 +916,64 @@ namespace cds { namespace container { { return m_nHashBitmask + 1; } + + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + + 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 )]; + } + //@endcond + + private: + //@cond + internal_bucket_type* bucket_begin() const + { + return m_Buckets; + } + + internal_bucket_type* bucket_end() const + { + return m_Buckets + bucket_count(); + } + + const_iterator get_const_begin() const + { + return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end()); + } + const_iterator get_const_end() const + { + return const_iterator( (bucket_end() - 1)->cend(), bucket_end() - 1, bucket_end()); + } + + 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_H +#endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H