X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_set_nogc.h;h=5874dd206700a4987162c8f3db6b75514ed31fb5;hb=6924946ceeaae28bc227fe7c9d8e939963bb9d69;hp=aaa7ee5b0351d7349bf30f6e9b9268d1ad7888f5;hpb=977a7c10110c2ce47531719035172ec18c25fe84;p=libcds.git diff --git a/cds/container/michael_set_nogc.h b/cds/container/michael_set_nogc.h index aaa7ee5b..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 @@ -64,7 +64,9 @@ namespace cds { namespace container { 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; @@ -74,10 +76,6 @@ namespace cds { namespace container { // 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: //@cond typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; @@ -92,7 +90,7 @@ namespace cds { namespace container { typedef internal_bucket_type_ base_class; public: using base_class::base_class; - using base_class::node_type; + using typename base_class::node_type; using base_class::alloc_node; using base_class::insert_node; using base_class::node_to_value; @@ -105,13 +103,18 @@ namespace cds { namespace container { typedef typename internal_bucket_type::const_iterator bucket_const_iterator; //@endcond + public: + //@cond + typedef typename bucket_stat::stat stat; + //@endcond + protected: //@cond const size_t m_nHashBitmask; - item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor internal_bucket_type* m_Buckets; ///< bucket table - typename bucket_stat::stat m_Stat; ///< Internal statistics + item_counter m_ItemCounter; ///< Item counter + stat m_Stat; ///< Internal statistics //@endcond public: @@ -165,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 @@ -176,7 +179,7 @@ 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 @@ -218,7 +221,7 @@ 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() ) ) + , m_Buckets( bucket_table_allocator().allocate( bucket_count())) { for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) construct_bucket( it ); @@ -230,7 +233,7 @@ namespace cds { namespace container { clear(); 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() ); + bucket_table_allocator().deallocate( m_Buckets, bucket_count()); } /// Inserts new node @@ -246,9 +249,9 @@ namespace cds { namespace container { 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(); @@ -264,9 +267,9 @@ namespace cds { namespace container { 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() ) { + if ( it != refBucket.end()) { ++m_ItemCounter; - return iterator( it, &refBucket, m_Buckets + bucket_count() ); + return iterator( it, &refBucket, m_Buckets + bucket_count()); } return end(); @@ -293,10 +296,10 @@ namespace cds { namespace container { 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 ); } @@ -323,8 +326,8 @@ namespace cds { namespace container { { 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(); } @@ -348,8 +351,8 @@ namespace cds { namespace container { { 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(); } @@ -372,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 { @@ -381,6 +384,10 @@ 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; @@ -423,24 +430,24 @@ namespace cds { namespace container { private: //@cond template - typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* b ) { - new (bucket) internal_bucket_type; + new (b) internal_bucket_type; } template - typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* b ) { - new (bucket) internal_bucket_type( m_Stat ); + 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() ); + 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() ); + return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count()); } //@endcond };