X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_set_nogc.h;h=5874dd206700a4987162c8f3db6b75514ed31fb5;hp=1dd1c10377893060c115a126c7b61c0785dd4988;hb=1132246d5685f87a5b240e077b7e88d56e38b1ff;hpb=cd515d6402be81b84e2eb0c9d4cf0a1ca9e4d95a diff --git a/cds/container/michael_set_nogc.h b/cds/container/michael_set_nogc.h index 1dd1c103..5874dd20 100644 --- a/cds/container/michael_set_nogc.h +++ b/cds/container/michael_set_nogc.h @@ -1,11 +1,11 @@ /* This file is a part of libcds - Concurrent Data Structures library - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + (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: @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_MICHAEL_SET_NOGC_H @@ -33,7 +33,6 @@ #include #include -#include namespace cds { namespace container { @@ -59,67 +58,109 @@ namespace cds { namespace container { class MichaelHashSet< cds::gc::nogc, OrderedList, Traits > { public: - typedef cds::gc::nogc gc; ///< Garbage collector - typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation - typedef Traits traits; ///< Set traits + typedef cds::gc::nogc gc; ///< Garbage collector + typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket implementation + typedef Traits traits; ///< Set traits - typedef typename bucket_type::value_type value_type; ///< type of value stored in the list - typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor + typedef typename ordered_list::value_type value_type; ///< type of value 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 +#endif /// Hash functor for \ref value_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::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; + // 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 - bucket_type * m_Buckets; ///< bucket table + 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_; - private: + class internal_bucket_type: public internal_bucket_type_ + { + typedef internal_bucket_type_ base_class; + public: + using base_class::base_class; + using typename base_class::node_type; + using base_class::alloc_node; + using base_class::insert_node; + using base_class::node_to_value; + }; + + /// Bucket table allocator + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; + + 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: //@cond - /// Calculates hash value of \p key - template - size_t hash_value( const Q& key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } - - /// Returns the bucket (ordered list) for \p key - template - bucket_type& bucket( const Q& key ) - { - return m_Buckets[ hash_value( key ) ]; - } + 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 public: + ///@name Forward iterators + //@{ /// Forward iterator /** The forward iterator for Michael's set 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 michael_set::details::iterator< bucket_type, false > iterator; + typedef michael_set::details::iterator< internal_bucket_type, false > iterator; /// Const forward iterator /** For iterator's features and requirements see \ref iterator */ - typedef michael_set::details::iterator< bucket_type, true > const_iterator; + typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator; /// Returns a forward iterator addressing the first element in a set /** @@ -127,7 +168,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 @@ -138,44 +179,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(); } + + /// 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(); } + + /// Returns an const iterator that addresses the location succeeding the last element in a set 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: /// Initialize hash set @@ -191,22 +221,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_set::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 set and destroys it ~MichaelHashSet() { 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 @@ -219,12 +246,12 @@ namespace cds { namespace container { template iterator insert( const Q& val ) { - bucket_type& refBucket = bucket( val ); + internal_bucket_type& refBucket = bucket( val ); bucket_iterator it = refBucket.insert( 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(); @@ -237,12 +264,12 @@ namespace cds { namespace container { template iterator emplace( Args&&... args ) { - bucket_type& refBucket = bucket( value_type(std::forward(args)...)); - bucket_iterator it = refBucket.emplace( std::forward(args)... ); - - if ( it != refBucket.end() ) { + typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward( args )... ); + internal_bucket_type& refBucket = bucket( internal_bucket_type::node_to_value( *pNode )); + bucket_iterator it = refBucket.insert_node( pNode ); + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); @@ -266,13 +293,13 @@ namespace cds { namespace container { template std::pair update( Q const& val, bool bAllowInsert = true ) { - bucket_type& refBucket = bucket( val ); + internal_bucket_type& refBucket = bucket( val ); std::pair ret = refBucket.update( val, bAllowInsert ); - if ( ret.first != refBucket.end() ) { + if ( ret.first != refBucket.end()) { if ( ret.second ) ++m_ItemCounter; - return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second ); + return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count()), ret.second ); } return std::make_pair( end(), ret.second ); } @@ -297,10 +324,10 @@ namespace cds { namespace container { template iterator contains( Q const& key ) { - bucket_type& refBucket = bucket( 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(); } @@ -322,10 +349,10 @@ namespace cds { namespace container { template iterator contains( Q const& key, Less pred ) { - bucket_type& refBucket = bucket( key ); + 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(); } @@ -348,8 +375,8 @@ namespace cds { namespace container { /// Checks if the set is empty /** - The emptiness is checked by the item counting: if item count is zero then the set is empty. - Thus, the correct item counting feature is an important part of Michael's set implementation. + @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter, + the function always returns \p true. */ bool empty() const { @@ -357,11 +384,21 @@ namespace cds { namespace container { } /// Returns item count in the set + /** + @warning 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 \p %MichaelHashSet cannot dynamically extend the hash table size, @@ -372,6 +409,47 @@ namespace cds { namespace container { { return m_nHashBitmask + 1; } + + protected: + //@cond + /// Calculates hash value of \p key + template + size_t hash_value( const Q& key ) const + { + return m_HashFunctor( key ) & m_nHashBitmask; + } + + /// Returns the bucket (ordered list) for \p key + template + internal_bucket_type& bucket( const Q& key ) + { + return m_Buckets[hash_value( key )]; + } + //@endcond + + private: + //@cond + 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 ); + } + + 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 }; }} // cds::container