X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_map_nogc.h;h=610eef33901a96f15683d7c8f86f2db061c543fa;hb=2ffdfa60c10505851c105ef69a05251e0b73b8a5;hp=20a3e98af896130b1cf82baa8466939d53196682;hpb=d6cf6cdfed6e799f12f765765ebe0e9718f9f471;p=libcds.git diff --git a/cds/container/michael_map_nogc.h b/cds/container/michael_map_nogc.h index 20a3e98a..610eef33 100644 --- a/cds/container/michael_map_nogc.h +++ b/cds/container/michael_map_nogc.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_MICHAEL_MAP_NOGC_H -#define __CDS_CONTAINER_MICHAEL_MAP_NOGC_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_NOGC_H +#define CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H #include #include @@ -9,102 +37,90 @@ namespace cds { namespace container { - /// Michael's hash map (template specialization for gc::nogc) + /// Michael's hash map (template specialization for \p cds::gc::nogc) /** @ingroup cds_nonintrusive_map \anchor cds_nonintrusive_MichaelHashMap_nogc - This specialization is intended for so-called persistent usage when no item + This specialization is so-called append-only when no item reclamation may be performed. The class does not support deleting of map item. - See \ref cds_nonintrusive_MichaelHashMap_hp "MichaelHashMap" for description of template parameters. - - The interface of the specialization is a little different. + See @ref cds_nonintrusive_MichaelHashMap_hp "MichaelHashMap" for description of template parameters. */ template < class OrderedList, #ifdef CDS_DOXYGEN_INVOKED - class Traits = michael_map::type_traits + class Traits = michael_map::traits #else class Traits #endif > - class MichaelHashMap + class MichaelHashMap { public: - typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation - typedef Traits options ; ///< Traits template parameters + typedef cds::gc::nogc gc; ///< No garbage collector + 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 ; ///< type of value stored in the list - typedef typename bucket_type::value_type value_type ; ///< Pair used as the some functor's argument + typedef typename ordered_list::key_type key_type; ///< key type + typedef typename ordered_list::mapped_type mapped_type; ///< type of value to be stored in the map + typedef typename ordered_list::value_type value_type; ///< Pair used as the some functor's argument - typedef gc::nogc gc ; ///< No garbage collector - typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor + typedef typename ordered_list::key_comparator key_comparator; ///< key comparing functor /// Hash functor for \ref key_type and all its derivatives that you use - typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash; - typedef typename options::item_counter item_counter ; ///< Item counter type + 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 options::allocator > bucket_table_allocator; +#ifdef CDS_DOXYGEN_INVOKED + typedef typename ordered_list::stat stat; ///< Internal statistics +#endif + + // GC and OrderedList::gc must be the same + static_assert(std::is_same::value, "GC and OrderedList::gc must be the same"); protected: //@cond - typedef typename bucket_type::iterator bucket_iterator; - typedef typename bucket_type::const_iterator bucket_const_iterator; - //@endcond + typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; - protected: - item_counter m_ItemCounter ; ///< Item counter - hash m_HashFunctor ; ///< Hash functor + 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_type * m_Buckets ; ///< bucket table + /// Bucket table allocator + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; - private: + typedef typename internal_bucket_type::iterator bucket_iterator; + typedef typename internal_bucket_type::const_iterator bucket_const_iterator; + //@endcond + + public: //@cond - const size_t m_nHashBitmask; + typedef typename bucket_stat::stat stat; //@endcond protected: - /// Calculates hash value of \p key - size_t hash_value( key_type const & key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } - - /// Returns the bucket (ordered list) for \p key - bucket_type& bucket( key_type const& key ) - { - return m_Buckets[ hash_value( key ) ]; - } + //@cond + const size_t m_nHashBitmask; + hash m_HashFunctor; ///< Hash functor + internal_bucket_type* m_Buckets; ///< bucket table + item_counter m_ItemCounter; ///< Item counter + stat m_Stat; ///< Internal statistics + //@endcond protected: - protected: - /// Forward iterator - /** - \p IsConst - constness boolean flag - - The forward iterator for Michael's map is based on \p OrderedList forward iterator and has some features: - - it has no post-increment operator, only pre-increment - - it iterates items in unordered fashion - */ + //@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; @@ -117,11 +133,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 @@ -170,21 +184,56 @@ namespace cds { namespace container { /// Equality operator template - bool operator ==(iterator_type const& i ) + bool operator ==(iterator_type const& i ) const { return base_class::operator ==( i ); } /// Equality operator template - bool operator !=(iterator_type const& i ) + bool operator !=(iterator_type const& i ) const { return !( *this == i ); } }; - + //@endcond public: + ///@name Forward iterators + //@{ /// 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 + + 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 @@ -196,7 +245,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 set @@ -207,44 +256,33 @@ 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 set - //@{ const_iterator begin() const { return get_const_begin(); } - const_iterator cbegin() + + /// Returns a forward const iterator addressing the first element in a set + const_iterator cbegin() const { return get_const_begin(); } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a set - //@{ const_iterator end() const { return get_const_end(); } - const_iterator cend() - { - return get_const_end(); - } - //@} - private: - //@{ - 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 + /// Returns an const iterator that addresses the location succeeding the last element in a set + const_iterator cend() const { - return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); + return get_const_end(); } - //@} + //@} public: /// Initialize the map @@ -261,21 +299,19 @@ namespace cds { namespace container { size_t nMaxItemCount, ///< estimation of max item count in the hash set 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 ),"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 ); } - /// Clear hash set and destroy it + /// Clears hash set 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 @@ -292,12 +328,12 @@ namespace cds { namespace container { template iterator insert( const K& key ) { - bucket_type& refBucket = bucket( key ); + internal_bucket_type& refBucket = bucket( key ); bucket_iterator it = refBucket.insert( key ); - if ( it != refBucket.end() ) { + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); @@ -317,12 +353,12 @@ namespace cds { namespace container { template iterator insert( K const& key, V const& val ) { - bucket_type& refBucket = bucket( key ); + internal_bucket_type& refBucket = bucket( key ); bucket_iterator it = refBucket.insert( key, val ); - if ( it != refBucket.end() ) { + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); @@ -340,12 +376,9 @@ namespace cds { namespace container { The argument \p item of user-defined functor \p func is the reference to the map's item inserted. item.second is a reference to item's value that may be changed. - User-defined functor \p func should guarantee that during changing item's value no any other changes - could be made on this map's item by concurrent threads. - The user-defined functor can be passed by reference using boost::ref - and it is called only if the inserting is successful. - The key_type should be constructible from value of type \p K. + The user-defined functor it is called only if the inserting is successful. + The \p key_type should be constructible from value of type \p K. The function allows to split creating of new item into two part: - create item from \p key; @@ -356,22 +389,26 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. Returns an iterator pointed to inserted value, or \p end() if inserting is failed + + @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level + synchronization. */ template - iterator insert_key( const K& key, Func func ) + iterator insert_with( const K& key, Func func ) { - bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.insert_key( key, func ); + internal_bucket_type& refBucket = bucket( key ); + bucket_iterator it = refBucket.insert_with( key, func ); - if ( it != refBucket.end() ) { + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); } - /// 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 from \p args /** \p key_type should be constructible from type \p K @@ -380,83 +417,106 @@ namespace cds { namespace container { template iterator emplace( K&& key, Args&&... args ) { - bucket_type& refBucket = bucket( key ); + internal_bucket_type& refBucket = bucket( key ); bucket_iterator it = refBucket.emplace( std::forward(key), std::forward(args)... ); - if ( it != refBucket.end() ) { + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); } - /// Ensures that the key \p key exists in the map + /// Updates the item /** - The operation inserts new item if the key \p key is not found in the map. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the map and \p bAllowInsert is \p true, the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. + + Returns std::pair where \p first is an iterator pointing to + item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()), + + \p second is true if new item has been added or \p false if the item + already is in the map. - Returns std::pair where \p first is an iterator pointing to - item found or inserted, \p second is true if new item has been added or \p false if the item - already is in the list. + @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level + synchronization. */ template - std::pair ensure( const K& key ) + std::pair update( const K& key, bool bAllowInsert = true ) { - bucket_type& refBucket = bucket( key ); - std::pair ret = refBucket.ensure( key ); + internal_bucket_type& refBucket = bucket( key ); + std::pair ret = refBucket.update( key, bAllowInsert ); if ( ret.second ) ++m_ItemCounter; - - return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second ); + else if ( ret.first == refBucket.end()) + return std::make_pair( end(), false ); + return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count()), ret.second ); } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( K const& key ) + { + return update( key, true ); + } + //@endcond - /// Find the key \p key - /** \anchor cds_nonintrusive_MichaelMap_nogc_find - + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key - and returns an iterator pointed to item found if the key is found, - and \ref end() otherwise + and returns an iterator pointed to item found and \ref end() otherwise */ template - iterator find( const K& key ) + iterator contains( K const& key ) { - bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find( key ); + internal_bucket_type& refBucket = bucket( key ); + bucket_iterator it = refBucket.contains( key ); - if ( it != refBucket.end() ) - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + if ( it != refBucket.end()) + return iterator( it, &refBucket, m_Buckets + bucket_count()); return end(); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + iterator find( K const& key ) + { + return 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_nogc_find "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. + \p pred must imply the same element order as the comparator used for building the map. + Hash functor specified in \p Traits should accept parameters of type \p K. */ template - iterator find_with( const K& key, Less pred ) + iterator contains( K const& key, Less pred ) { - bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find_with( key, pred ); + internal_bucket_type& refBucket = bucket( key ); + bucket_iterator it = refBucket.contains( key, pred ); - if ( it != refBucket.end() ) - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + if ( it != refBucket.end()) + return iterator( it, &refBucket, m_Buckets + bucket_count()); return end(); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + iterator find_with( K const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond - /// Clears the map (non-atomic) - /** - The function deletes all items from the map. - The function is not atomic. It cleans up each bucket and then resets the item counter to zero. - If there are a thread that performs insertion while \p clear is working the result is undefined in general case: - empty() may return \p true but the map may contain item(s). - */ + /// Clears the map (not atomic) void clear() { for ( size_t i = 0; i < bucket_count(); ++i ) @@ -464,11 +524,10 @@ namespace cds { namespace container { m_ItemCounter.reset(); } - - /// Checks if the map is empty + /// Checks whether the map is empty /** - Emptiness is checked by item counting: if item count is zero then the map is empty. - Thus, the correct item counting feature is an important part of Michael's map implementation. + @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter, + the function always returns \p true. */ bool empty() const { @@ -476,23 +535,73 @@ namespace cds { namespace container { } /// Returns item count in the map + /** + If you use \p atomicity::empty_item_counter in \p traits::item_counter, + the function always returns 0. + */ size_t size() const { return m_ItemCounter; } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + /// Returns the size of hash table /** - Since MichaelHashMap cannot dynamically extend the hash table size, + Since \p %MichaelHashMap cannot dynamically extend the hash table size, the value returned is an constant depending on object initialization parameters; - see MichaelHashMap::MichaelHashMap for explanation. + see \p MichaelHashMap::MichaelHashMap for explanation. */ size_t bucket_count() const { return m_nHashBitmask + 1; } + protected: + //@cond + /// Calculates hash value of \p key + template + size_t hash_value( K const & key ) const + { + return m_HashFunctor( key ) & m_nHashBitmask; + } + + /// Returns the bucket (ordered list) for \p key + template + internal_bucket_type& bucket( K const& key ) + { + 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* b ) + { + new (b) internal_bucket_type; + } + + template + typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* b ) + { + new (b) internal_bucket_type( m_Stat ); + } + //@endcond }; }} // namespace cds::container -#endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_NOGC_H +#endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H