From 9f21c2ef35252fc38304efa31b9cca6cd6a46499 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 5 Aug 2016 17:46:02 +0300 Subject: [PATCH] MichaelSet: added support for internal statistics --- cds/container/lazy_list_rcu.h | 140 +++++++++-------- cds/container/michael_list_rcu.h | 128 +++++++++------- cds/container/michael_set_rcu.h | 183 ++++++++++++++--------- cds/details/allocator.h | 2 +- cds/intrusive/lazy_list_rcu.h | 106 ++++++------- cds/intrusive/michael_list_rcu.h | 160 ++++++++++---------- projects/Win/vc14/gtest-set.vcxproj | 6 + test/unit/set/test_michael_lazy_rcu.h | 51 ++++++- test/unit/set/test_michael_michael_rcu.h | 51 ++++++- 9 files changed, 487 insertions(+), 340 deletions(-) diff --git a/cds/container/lazy_list_rcu.h b/cds/container/lazy_list_rcu.h index 0c5ed541..18453ac4 100644 --- a/cds/container/lazy_list_rcu.h +++ b/cds/container/lazy_list_rcu.h @@ -147,6 +147,22 @@ namespace cds { namespace container { typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef LazyList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -155,41 +171,6 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::node_type head_type; - //@endcond - - public: - using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; ///< pointer to extracted node - /// Type of \p get() member function return value - typedef value_type * raw_ptr; - - protected: - //@cond - static value_type& node_to_value( node_type& n ) - { - return n.m_Value; - } - - static value_type const& node_to_value( node_type const& n ) - { - return n.m_Value; - } - - template - static node_type * alloc_node( Q const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -198,30 +179,15 @@ namespace cds { namespace container { } }; typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - head_type& head() - { - return base_class::m_Head; - } - - head_type& head() const - { - return const_cast( base_class::m_Head ); - } - - head_type& tail() - { - return base_class::m_Tail; - } - - head_type const& tail() const - { - return base_class::m_Tail; - } //@endcond + public: + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; ///< pointer to extracted node + /// Type of \p get() member function return value + typedef value_type * raw_ptr; + protected: - //@cond + //@cond template class iterator_type: protected base_class::template iterator_type { @@ -379,9 +345,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - return insert_at( head(), val ); + return insert_at( head(), std::forward( val )); } /// Inserts new node @@ -408,9 +374,9 @@ namespace cds { namespace container { The function makes RCU lock internally. */ template - bool insert( Q const& key, Func func ) + bool insert( Q&& key, Func func ) { - return insert_at( head(), key, func ); + return insert_at( head(), std::forward( key ), func ); } /// Inserts data of type \p value_type constructed from \p args @@ -803,9 +769,9 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, Q const& val ) + bool insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template @@ -815,9 +781,9 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, Q const& key, Func f ) + bool insert_at( head_type& refHead, Q&& key, Func f ) { - scoped_node_ptr pNode( alloc_node( key )); + scoped_node_ptr pNode( alloc_node( std::forward( key ))); if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node_to_value(node) ); } )) { pNode.release(); @@ -871,6 +837,52 @@ namespace cds { namespace container { return pNode ? &pNode->m_Value : nullptr; } + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + + static value_type const& node_to_value( node_type const& n ) + { + return n.m_Value; + } + + template + static node_type * alloc_node( Q&& v ) + { + return cxx_allocator().New( std::forward( v )); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_Head; + } + + head_type& head() const + { + return const_cast(base_class::m_Head); + } + + head_type& tail() + { + return base_class::m_Tail; + } + + head_type const& tail() const + { + return base_class::m_Tail; + } //@endcond }; diff --git a/cds/container/michael_list_rcu.h b/cds/container/michael_list_rcu.h index 861da797..daf8dd7f 100644 --- a/cds/container/michael_list_rcu.h +++ b/cds/container/michael_list_rcu.h @@ -154,6 +154,22 @@ namespace cds { namespace container { typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef MichaelList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -162,10 +178,15 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::atomic_node_ptr head_type; - //@endcond - public: - using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; ///< pointer to extracted node + struct node_disposer { + void operator()( node_type * pNode ) + { + free_node( pNode ); + } + }; + typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; + //@endcond private: //@cond @@ -189,58 +210,14 @@ namespace cds { namespace container { //@endcond public: + ///< pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; + /// Result of \p get(), \p get_with() functions - pointer to the node found typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr; protected: //@cond - static value_type& node_to_value( node_type& n ) - { - return n.m_Value; - } - static value_type const& node_to_value( node_type const& n ) - { - return n.m_Value; - } - - template - static node_type * alloc_node( Q const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } - - struct node_disposer { - void operator()( node_type * pNode ) - { - free_node( pNode ); - } - }; - typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - head_type& head() - { - return base_class::m_pHead; - } - - head_type& head() const - { - return const_cast( base_class::m_pHead ); - } - //@endcond - - protected: - //@cond template class iterator_type: protected base_class::template iterator_type { @@ -392,9 +369,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - return insert_at( head(), val ); + return insert_at( head(), std::forward( val )); } /// Inserts new node @@ -423,9 +400,9 @@ namespace cds { namespace container { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - bool insert( Q const& key, Func func ) + bool insert( Q&& key, Func func ) { - return insert_at( head(), key, func ); + return insert_at( head(), std::forward( key ), func ); } /// Updates data by \p key @@ -817,15 +794,15 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, Q const& val ) + bool insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template - bool insert_at( head_type& refHead, Q const& key, Func f ) + bool insert_at( head_type& refHead, Q&& key, Func f ) { - scoped_node_ptr pNode( alloc_node( key )); + scoped_node_ptr pNode( alloc_node( std::forward( key ))); if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { f( node_to_value(node) ); } )) { pNode.release(); @@ -884,6 +861,41 @@ namespace cds { namespace container { return raw_ptr( base_class::get_at( refHead, val, cmp )); } + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + static value_type const& node_to_value( node_type const& n ) + { + return n.m_Value; + } + + template + static node_type * alloc_node( Q&& v ) + { + return cxx_allocator().New( std::forward( v )); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_pHead; + } + + head_type& head() const + { + return const_cast(base_class::m_pHead); + } //@endcond }; diff --git a/cds/container/michael_set_rcu.h b/cds/container/michael_set_rcu.h index 45fac82a..c3c1adf8 100644 --- a/cds/container/michael_set_rcu.h +++ b/cds/container/michael_set_rcu.h @@ -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_RCU_H @@ -136,70 +136,69 @@ namespace cds { namespace container { { public: typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector - typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation + 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 to be stored in the list - typedef typename bucket_type::key_comparator key_comparator; ///< key comparing functor + typedef typename ordered_list::value_type value_type; ///< type of value to be stored in the list + typedef typename ordered_list::key_comparator key_comparator; ///< key comparing functor + typedef typename ordered_list::stat stat; ///< Internal statistics /// 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 - typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock - typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node - typedef typename bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives + typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock /// 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; - protected: - //@cond - class internal_bucket_type: public bucket_type + // GC and OrderedList::gc must be the same + static_assert(std::is_same::value, "GC and OrderedList::gc must be the same"); + + static_assert(!std::is_same::value, + "atomicity::empty_item_counter is not allowed as a item counter"); + +#ifdef CDS_DOXYGEN_INVOKED + /// Wrapped internal statistics for \p ordered_list + typedef implementatin_specific bucket_stat; + + /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics + typedef modified_ordered_list internal_bucket_type; +#else + 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_; + + class internal_bucket_type: public internal_bucket_type_ { - typedef bucket_type base_class; + typedef internal_bucket_type_ base_class; public: + using base_class::base_class; using base_class::node_type; using base_class::alloc_node; using base_class::insert_node; using base_class::node_to_value; }; +#endif - /// Bucket table allocator - typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator; - - //@endcond - - protected: - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - internal_bucket_type * m_Buckets; ///< bucket table - - private: - //@cond - const size_t m_nHashBitmask; - //@endcond + typedef typename internal_bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node + typedef typename internal_bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives protected: //@cond - /// Calculates hash value of \p key - template - size_t hash_value( Q const& key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } + /// Bucket table allocator + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; - /// 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 ) ]; - } + 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 //@endcond + public: ///@name Forward iterators (thread-safe under RCU lock) //@{ @@ -240,10 +239,10 @@ namespace cds { namespace container { }; \endcode */ - typedef michael_set::details::iterator< bucket_type, false > iterator; + typedef michael_set::details::iterator< internal_bucket_type, false > iterator; /// Const forward 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 /** @@ -290,18 +289,6 @@ namespace cds { namespace container { } //@} - 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 /** @@ -316,21 +303,21 @@ 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"); - - 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 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 @@ -347,9 +334,9 @@ namespace cds { namespace container { Returns \p true if \p val is inserted into the set, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - const bool bRet = bucket( val ).insert( val ); + const bool bRet = bucket( val ).insert( std::forward( val )); if ( bRet ) ++m_ItemCounter; return bRet; @@ -376,15 +363,14 @@ namespace cds { namespace container { synchronization. */ template - bool insert( Q const& val, Func f ) + bool insert( Q&& val, Func f ) { - const bool bRet = bucket( val ).insert( val, f ); + const bool bRet = bucket( val ).insert( std::forward( val ), f ); if ( bRet ) ++m_ItemCounter; return bRet; } - /// Updates the element /** The operation performs inserting or changing data with lock-free manner. @@ -415,7 +401,7 @@ namespace cds { namespace container { synchronization. */ template - std::pair update( const Q& val, Func func, bool bAllowInsert = true ) + std::pair update( Q const& val, Func func, bool bAllowInsert = true ) { std::pair bRet = bucket( val ).update( val, func, bAllowInsert ); if ( bRet.second ) @@ -537,7 +523,7 @@ namespace cds { namespace container { If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr. The function just excludes the item from the set and returns a pointer to item found. - Depends on \p bucket_type you should or should not lock RCU before calling of this function: + 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. @@ -701,7 +687,7 @@ namespace cds { namespace container { /** \anchor cds_nonintrusive_MichaelHashSet_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 bucket_type. + 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 Q that can be not the same as \p value_type. @@ -772,6 +758,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 %MichaelHashSet cannot dynamically extend the hash table size, @@ -782,6 +774,49 @@ 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 )]; + } + + 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 ); + } + + 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 }; }} // namespace cds::container diff --git a/cds/details/allocator.h b/cds/details/allocator.h index babe8344..46a2394a 100644 --- a/cds/details/allocator.h +++ b/cds/details/allocator.h @@ -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_DETAILS_ALLOCATOR_H diff --git a/cds/intrusive/lazy_list_rcu.h b/cds/intrusive/lazy_list_rcu.h index 935c294c..554ffe07 100644 --- a/cds/intrusive/lazy_list_rcu.h +++ b/cds/intrusive/lazy_list_rcu.h @@ -31,7 +31,7 @@ #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H #define CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H -#include // unique_lock +#include // unique_lock #include #include #include @@ -160,12 +160,6 @@ namespace cds { namespace intrusive { using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >; //@endcond - protected: - //@cond - typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer - typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support) - //@endcond - protected: node_type m_Head; ///< List head (dummy node) node_type m_Tail; ///< List tail (dummy node) @@ -173,6 +167,8 @@ namespace cds { namespace intrusive { mutable stat m_Stat; ///< Internal statistics //@cond + typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer + typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support) /// Position pointer for item search struct position { @@ -197,14 +193,6 @@ namespace cds { namespace intrusive { typedef std::unique_lock< position > scoped_position_lock; typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> deadlock_policy; - //@endcond - - protected: - //@cond - static void clear_links( node_type * pNode ) - { - pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); - } struct clear_and_dispose { void operator()( value_type * p ) @@ -214,34 +202,6 @@ namespace cds { namespace intrusive { disposer()( p ); } }; - - static void dispose_node( node_type * pNode ) - { - assert( pNode ); - assert( !gc::is_locked()); - - gc::template retire_ptr( node_traits::to_value_ptr( *pNode )); - } - - static void link_node( node_type * pNode, node_type * pPred, node_type * pCur ) - { - assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur ); - link_checker::is_empty( pNode ); - - pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed ); - pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release ); - } - - void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead ) - { - assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur ); - assert( pCur != &m_Tail ); - - node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr(); - pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search - pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting - } - //@endcond public: @@ -410,20 +370,6 @@ namespace cds { namespace intrusive { } //@} - private: - //@cond - const_iterator get_const_begin() const - { - const_iterator it( const_cast( &m_Head )); - ++it ; // skip dummy head - return it; - } - const_iterator get_const_end() const - { - return const_iterator( const_cast( &m_Tail )); - } - //@endcond - public: /// Default constructor initializes empty list LazyList() @@ -900,6 +846,38 @@ namespace cds { namespace intrusive { protected: //@cond + static void clear_links( node_type * pNode ) + { + pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); + } + + static void dispose_node( node_type * pNode ) + { + assert( pNode ); + assert( !gc::is_locked() ); + + gc::template retire_ptr( node_traits::to_value_ptr( *pNode ) ); + } + + static void link_node( node_type * pNode, node_type * pPred, node_type * pCur ) + { + assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur ); + link_checker::is_empty( pNode ); + + pNode->m_pNext.store( marked_node_ptr( pCur ), memory_model::memory_order_relaxed ); + pPred->m_pNext.store( marked_node_ptr( pNode ), memory_model::memory_order_release ); + } + + void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead ) + { + assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur ); + assert( pCur != &m_Tail ); + + node_type * pNext = pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr(); + pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search + pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release ); // physically deleting + } + // split-list support bool insert_aux_node( node_type * pNode ) { @@ -1304,6 +1282,20 @@ namespace cds { namespace intrusive { return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); } //@endcond + + private: + //@cond + const_iterator get_const_begin() const + { + const_iterator it( const_cast(&m_Head) ); + ++it; // skip dummy head + return it; + } + const_iterator get_const_end() const + { + return const_iterator( const_cast(&m_Tail) ); + } + //@endcond }; }} // namespace cds::intrusive diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index 230b22c6..1b215c1d 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -163,12 +163,6 @@ namespace cds { namespace intrusive { typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy; - static void clear_links( node_type * pNode ) - { - pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release ); - pNode->m_pDelChain = nullptr; - } - struct clear_and_dispose { void operator()( value_type * p ) { @@ -178,31 +172,6 @@ namespace cds { namespace intrusive { } }; - static void dispose_node( node_type * pNode ) - { - assert( pNode ); - assert( !gc::is_locked() ); - - gc::template retire_ptr( node_traits::to_value_ptr( *pNode ) ); - } - - static void dispose_chain( node_type * pChain ) - { - if ( pChain ) { - assert( !gc::is_locked() ); - - auto f = [&pChain]() -> cds::urcu::retired_ptr { - node_type * p = pChain; - if ( p ) { - pChain = p->m_pDelChain; - return cds::urcu::make_retired_ptr( node_traits::to_value_ptr( p )); - } - return cds::urcu::make_retired_ptr( static_cast(nullptr)); - }; - gc::batch_retire(std::ref(f)); - } - } - /// Position pointer for item search struct position { atomic_node_ptr * pPrev ; ///< Previous node @@ -222,7 +191,6 @@ namespace cds { namespace intrusive { dispose_chain( pDelChain ); } }; - //@endcond public: @@ -243,56 +211,6 @@ namespace cds { namespace intrusive { /// Result of \p get(), \p get_with() functions - pointer to the node found typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr; - protected: - //@cond - - bool link_node( node_type * pNode, position& pos ) - { - assert( pNode != nullptr ); - link_checker::is_empty( pNode ); - - marked_node_ptr p( pos.pCur ); - pNode->m_pNext.store( p, memory_model::memory_order_release ); - if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ))) - return true; - - pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); - return false; - } - - static void link_to_remove_chain( position& pos, node_type * pDel ) - { - assert( pDel->m_pDelChain == nullptr ); - - pDel->m_pDelChain = pos.pDelChain; - pos.pDelChain = pDel; - } - - bool unlink_node( position& pos, erase_node_mask nMask ) - { - assert(gc::is_locked() ); - - // Mark the node (logical deletion) - marked_node_ptr next(pos.pNext, 0); - - if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ))) { - - // Try physical removal - fast path - marked_node_ptr cur(pos.pCur); - if ( cds_likely( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) { - if ( nMask == erase_mask ) - link_to_remove_chain( pos, pos.pCur ); - } - else { - // Slow path - search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() ); - } - return true; - } - return false; - } - //@endcond - protected: //@cond template @@ -916,8 +834,86 @@ namespace cds { namespace intrusive { { return m_Stat; } + protected: //@cond + static void clear_links( node_type * pNode ) + { + pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release ); + pNode->m_pDelChain = nullptr; + } + + static void dispose_node( node_type * pNode ) + { + assert( pNode ); + assert( !gc::is_locked() ); + + gc::template retire_ptr( node_traits::to_value_ptr( *pNode ) ); + } + + static void dispose_chain( node_type * pChain ) + { + if ( pChain ) { + assert( !gc::is_locked() ); + + auto f = [&pChain]() -> cds::urcu::retired_ptr { + node_type * p = pChain; + if ( p ) { + pChain = p->m_pDelChain; + return cds::urcu::make_retired_ptr( node_traits::to_value_ptr( p ) ); + } + return cds::urcu::make_retired_ptr( static_cast(nullptr) ); + }; + gc::batch_retire( std::ref( f ) ); + } + } + + bool link_node( node_type * pNode, position& pos ) + { + assert( pNode != nullptr ); + link_checker::is_empty( pNode ); + + marked_node_ptr p( pos.pCur ); + pNode->m_pNext.store( p, memory_model::memory_order_release ); + if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) ) + return true; + + pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); + return false; + } + + static void link_to_remove_chain( position& pos, node_type * pDel ) + { + assert( pDel->m_pDelChain == nullptr ); + + pDel->m_pDelChain = pos.pDelChain; + pos.pDelChain = pDel; + } + + bool unlink_node( position& pos, erase_node_mask nMask ) + { + assert( gc::is_locked() ); + + // Mark the node (logical deletion) + marked_node_ptr next( pos.pNext, 0 ); + + if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) ) { + + // Try physical removal - fast path + marked_node_ptr cur( pos.pCur ); + if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) ) { + if ( nMask == erase_mask ) + link_to_remove_chain( pos, pos.pCur ); + } + else { + // Slow path + search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() ); + } + return true; + } + return false; + } + // split-list support bool insert_aux_node( node_type * pNode ) { diff --git a/projects/Win/vc14/gtest-set.vcxproj b/projects/Win/vc14/gtest-set.vcxproj index d67504e4..fb7d4479 100644 --- a/projects/Win/vc14/gtest-set.vcxproj +++ b/projects/Win/vc14/gtest-set.vcxproj @@ -333,6 +333,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console @@ -349,6 +350,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console @@ -365,6 +367,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console @@ -381,6 +384,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console @@ -399,6 +403,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console @@ -419,6 +424,7 @@ _ENABLE_ATOMIC_ALIGNMENT_FIX;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) + 4503 Console diff --git a/test/unit/set/test_michael_lazy_rcu.h b/test/unit/set/test_michael_lazy_rcu.h index 832fcaf3..ffe1e100 100644 --- a/test/unit/set/test_michael_lazy_rcu.h +++ b/test/unit/set/test_michael_lazy_rcu.h @@ -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 CDSUNIT_SET_TEST_MICHAEL_LAZY_RCU_H #define CDSUNIT_SET_TEST_MICHAEL_LAZY_RCU_H @@ -216,11 +216,58 @@ TYPED_TEST_P( MichaelLazySet, mutex ) this->test( s ); } +TYPED_TEST_P( MichaelLazySet, stat ) +{ + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct list_traits: public cc::lazy_list::traits + { + typedef typename TestFixture::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::stat<> stat; + }; + typedef cc::LazyList< rcu_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef typename TestFixture::hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< rcu_type, list_type, set_traits >set_type; + + set_type s( TestFixture::kSize, 4 ); + this->test( s ); +} + +TYPED_TEST_P( MichaelLazySet, wrapped_stat ) +{ + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct list_traits: public cc::lazy_list::traits + { + typedef typename TestFixture::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::wrapped_stat<> stat; + }; + typedef cc::LazyList< rcu_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef typename TestFixture::hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< rcu_type, list_type, set_traits >set_type; + + set_type s( TestFixture::kSize, 4 ); + this->test( s ); +} // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as // "No test named can be found in this test case" REGISTER_TYPED_TEST_CASE_P( MichaelLazySet, - compare, less, cmpmix, item_counting, backoff, seq_cst, mutex + compare, less, cmpmix, item_counting, backoff, seq_cst, mutex, stat, wrapped_stat ); diff --git a/test/unit/set/test_michael_michael_rcu.h b/test/unit/set/test_michael_michael_rcu.h index 99f75ee6..c6b9ea0d 100644 --- a/test/unit/set/test_michael_michael_rcu.h +++ b/test/unit/set/test_michael_michael_rcu.h @@ -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 CDSUNIT_SET_TEST_MICHAEL_MICHAEL_RCU_H #define CDSUNIT_SET_TEST_MICHAEL_MICHAEL_RCU_H @@ -192,11 +192,58 @@ TYPED_TEST_P( MichaelSet, seq_cst ) this->test( s ); } +TYPED_TEST_P( MichaelSet, stat ) +{ + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct list_traits: public cc::michael_list::traits + { + typedef typename TestFixture::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::stat<> stat; + }; + typedef cc::MichaelList< rcu_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef typename TestFixture::hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< rcu_type, list_type, set_traits >set_type; + + set_type s( TestFixture::kSize, 4 ); + this->test( s ); +} + +TYPED_TEST_P( MichaelSet, wrapped_stat ) +{ + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct list_traits: public cc::michael_list::traits + { + typedef typename TestFixture::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::wrapped_stat<> stat; + }; + typedef cc::MichaelList< rcu_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef typename TestFixture::hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< rcu_type, list_type, set_traits >set_type; + + set_type s( TestFixture::kSize, 4 ); + this->test( s ); +} // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as // "No test named can be found in this test case" REGISTER_TYPED_TEST_CASE_P( MichaelSet, - compare, less, cmpmix, item_counting, backoff, seq_cst + compare, less, cmpmix, item_counting, backoff, seq_cst, stat, wrapped_stat ); -- 2.34.1