From b971d5a61eb52476792fcd748e9151ce53e0e57c Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 10 Oct 2016 18:37:43 +0300 Subject: [PATCH] Refactored IterableList to prevent violation of the order of elements --- cds/container/impl/iterable_list.h | 77 ++--- cds/intrusive/details/iterable_list_base.h | 20 +- cds/intrusive/impl/iterable_list.h | 309 ++++++++++-------- .../include/cds_test/stat_iterable_list_out.h | 5 +- .../intrusive-list/intrusive_iterable_dhp.cpp | 4 +- .../test_intrusive_iterable_list.h | 6 +- test/unit/list/iterable_dhp.cpp | 3 +- test/unit/list/iterable_hp.cpp | 2 +- test/unit/list/kv_iterable_dhp.cpp | 2 +- test/unit/list/kv_iterable_hp.cpp | 2 +- test/unit/list/test_iterable_list.h | 2 +- 11 files changed, 228 insertions(+), 204 deletions(-) diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h index ae058609..1c34960c 100644 --- a/cds/container/impl/iterable_list.h +++ b/cds/container/impl/iterable_list.h @@ -157,9 +157,9 @@ namespace cds { namespace container { protected: //@cond - typedef typename maker::cxx_data_allocator cxx_data_allocator; - typedef typename maker::data_disposer data_disposer; - typedef typename base_class::atomic_node_ptr head_type; + typedef typename maker::cxx_data_allocator cxx_data_allocator; + typedef typename maker::data_disposer data_disposer; + typedef typename base_class::node_type head_type; //@endcond public: @@ -174,10 +174,6 @@ namespace cds { namespace container { typedef typename base_class::template iterator_type iterator_base; friend class IterableList; - iterator_type( head_type const& pNode ) - : iterator_base( pNode ) - {} - iterator_type( iterator_base it ) : iterator_base( it ) {} @@ -289,7 +285,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( head() ); + return iterator( base_class::begin() ); } /// Returns an iterator that addresses the location succeeding the last element in a list @@ -302,31 +298,31 @@ namespace cds { namespace container { */ iterator end() { - return iterator(); + return iterator( base_class::end()); } /// Returns a forward const iterator addressing the first element in a list const_iterator begin() const { - return const_iterator( head() ); + return const_iterator( base_class::cbegin() ); } /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { - return const_iterator( head() ); + return const_iterator( base_class::cbegin() ); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator end() const { - return const_iterator(); + return const_iterator( base_class::cend()); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator cend() const { - return const_iterator(); + return const_iterator( base_class::cend()); } //@} @@ -771,15 +767,7 @@ namespace cds { namespace container { typedef std::unique_ptr< value_type, data_disposer > scoped_data_ptr; - head_type& head() - { - return base_class::m_pHead; - } - - head_type const& head() const - { - return base_class::m_pHead; - } + using base_class::head; //@endcond protected: @@ -789,11 +777,11 @@ namespace cds { namespace container { return insert_node_at( head(), pData ); } - bool insert_node_at( head_type& refHead, value_type* pData ) + bool insert_node_at( head_type* pHead, value_type* pData ) { assert( pData ); scoped_data_ptr p( pData ); - if ( base_class::insert_at( refHead, *pData )) { + if ( base_class::insert_at( pHead, *pData )) { p.release(); return true; } @@ -802,17 +790,17 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, Q&& val ) + bool insert_at( head_type* pHead, Q&& val ) { - return insert_node_at( refHead, alloc_data( std::forward( val ))); + return insert_node_at( pHead, alloc_data( std::forward( val ))); } template - bool insert_at( head_type& refHead, Q&& key, Func f ) + bool insert_at( head_type* pHead, Q&& key, Func f ) { scoped_data_ptr pNode( alloc_data( std::forward( key ))); - if ( base_class::insert_at( refHead, *pNode, f )) { + if ( base_class::insert_at( pHead, *pNode, f )) { pNode.release(); return true; } @@ -820,17 +808,17 @@ namespace cds { namespace container { } template - bool emplace_at( head_type& refHead, Args&&... args ) + bool emplace_at( head_type* pHead, Args&&... args ) { - return insert_node_at( refHead, alloc_data( std::forward(args)... )); + return insert_node_at( pHead, alloc_data( std::forward(args)... )); } template - std::pair update_at( head_type& refHead, Q&& key, Func f, bool bAllowInsert ) + std::pair update_at( head_type* pHead, Q&& key, Func f, bool bAllowInsert ) { scoped_data_ptr pData( alloc_data( std::forward( key ))); - std::pair ret = base_class::update_at( refHead, *pData, f, bAllowInsert ); + std::pair ret = base_class::update_at( pHead, *pData, f, bAllowInsert ); if ( ret.first ) pData.release(); @@ -838,41 +826,40 @@ namespace cds { namespace container { } template - bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f ) + bool erase_at( head_type* pHead, Q const& key, Compare cmp, Func f ) { - return base_class::erase_at( refHead, key, cmp, f ); + return base_class::erase_at( pHead, key, cmp, f ); } template - guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp ) + guarded_ptr extract_at( head_type* pHead, Q const& key, Compare cmp ) { - return base_class::extract_at( refHead, key, cmp ); + return base_class::extract_at( pHead, key, cmp ); } template - bool find_at( head_type const& refHead, Q const& key, Compare cmp ) const + bool find_at( head_type const* pHead, Q const& key, Compare cmp ) const { - return base_class::find_at( refHead, key, cmp ); + return base_class::find_at( pHead, key, cmp ); } template - bool find_at( head_type const& refHead, Q& val, Compare cmp, Func f ) const + bool find_at( head_type const* pHead, Q& val, Compare cmp, Func f ) const { - return base_class::find_at( refHead, val, cmp, f ); + return base_class::find_at( pHead, val, cmp, f ); } template - iterator find_iterator_at( head_type const& refHead, Q const& key, Compare cmp ) const + iterator find_iterator_at( head_type const* pHead, Q const& key, Compare cmp ) const { - return iterator( base_class::find_iterator_at( refHead, key, cmp )); + return iterator( base_class::find_iterator_at( pHead, key, cmp )); } template - guarded_ptr get_at( head_type const& refHead, Q const& key, Compare cmp ) const + guarded_ptr get_at( head_type const* pHead, Q const& key, Compare cmp ) const { - return base_class::get_at( refHead, key, cmp ); + return base_class::get_at( pHead, key, cmp ); } - //@endcond }; diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 4bb37e48..07e6efde 100644 --- a/cds/intrusive/details/iterable_list_base.h +++ b/cds/intrusive/details/iterable_list_base.h @@ -77,8 +77,9 @@ namespace cds { namespace intrusive { event_counter m_nInsertFailed; ///< Number of failed \p insert() operations event_counter m_nInsertRetry; ///< Number of attempts to insert new item event_counter m_nReuseNode; ///< Number of reusing empty node when inserting/updating - event_counter m_nReuseNodeMarkFailed; ///< Number of unsuccessful marking attempts when we try to reuse node - event_counter m_nReuseNodeSeqBreak; ///< Number of breaking sequence of \p prev -> \p next node when we try to reuse \p prev node + event_counter m_nNodeMarkFailed; ///< Number of unsuccessful marking attempts when we try to insert new data + event_counter m_nNodeSeqBreak; ///< Number of breaking sequence events of \p prev -> \p next node when we try to insert new data + event_counter m_nNewNodeCreated; ///< Number of new node created when we try to insert new data event_counter m_nUpdateNew; ///< Number of new item inserted for \p update() event_counter m_nUpdateExisting; ///< Number of existing item updates event_counter m_nUpdateFailed; ///< Number of failed \p update() call @@ -97,8 +98,9 @@ namespace cds { namespace intrusive { void onInsertFailed() { ++m_nInsertFailed; } void onInsertRetry() { ++m_nInsertRetry; } void onReuseNode() { ++m_nReuseNode; } - void onReuseNodeMarkFailed(){ ++m_nReuseNodeMarkFailed; } - void onReuseNodeSeqBreak() { ++m_nReuseNodeSeqBreak; } + void onNodeMarkFailed() { ++m_nNodeMarkFailed; } + void onNodeSeqBreak() { ++m_nNodeSeqBreak; } + void onNewNodeCreated() { ++m_nNewNodeCreated; } void onUpdateNew() { ++m_nUpdateNew; } void onUpdateExisting() { ++m_nUpdateExisting; } void onUpdateFailed() { ++m_nUpdateFailed; } @@ -121,8 +123,9 @@ namespace cds { namespace intrusive { void onInsertFailed() const {} void onInsertRetry() const {} void onReuseNode() const {} - void onReuseNodeMarkFailed() const {} - void onReuseNodeSeqBreak() const {} + void onNodeMarkFailed() const {} + void onNodeSeqBreak() const {} + void onNewNodeCreated() const {} void onUpdateNew() const {} void onUpdateExisting() const {} void onUpdateFailed() const {} @@ -151,8 +154,9 @@ namespace cds { namespace intrusive { void onInsertFailed() { m_stat.onInsertFailed(); } void onInsertRetry() { m_stat.onInsertRetry(); } void onReuseNode() { m_stat.onReuseNode(); } - void onReuseNodeMarkFailed() { m_stat.onReuseNodeMarkFailed(); } - void onReuseNodeSeqBreak() { m_stat.onReuseNodeSeqBreak(); } + void onNodeMarkFailed() { m_stat.onNodeMarkFailed();} + void onNodeSeqBreak() { m_stat.onNodeSeqBreak(); } + void onNewNodeCreated() { m_stat.onNewNodeCreated();} void onUpdateNew() { m_stat.onUpdateNew(); } void onUpdateExisting() { m_stat.onUpdateExisting();} void onUpdateFailed() { m_stat.onUpdateFailed(); } diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index eb87e3e8..bf01a327 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -141,7 +141,7 @@ namespace cds { namespace intrusive { typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer - static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 3; ///< Count of hazard pointer required for the algorithm //@cond // Rebind traits (split-list support) @@ -165,7 +165,9 @@ namespace cds { namespace intrusive { typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support) typedef typename node_type::marked_data_ptr marked_data_ptr; - atomic_node_ptr m_pHead; ///< Head pointer + node_type m_Head; + node_type m_Tail; + item_counter m_ItemCounter; ///< Item counter mutable stat m_Stat; ///< Internal statistics @@ -173,12 +175,15 @@ namespace cds { namespace intrusive { /// Position pointer for item search struct position { - atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead) + node_type const* pHead; node_type * pPrev; ///< Previous node node_type * pCur; ///< Current node - value_type * pFound; ///< Value of \p pCur->data, valid only if data found - typename gc::Guard guard; ///< guard for \p pFound + value_type * pFound; ///< Value of \p pCur->data, valid only if data found + value_type * pPrevVal; ///< Value of \p pPrev->data, can be \p nullptr + + typename gc::Guard guard; ///< guard for \p pFound + typename gc::Guard prevGuard; ///< guard for \p pPrevVal }; //@endcond @@ -190,32 +195,28 @@ namespace cds { namespace intrusive { friend class IterableList; protected: - node_type* m_pNode; + node_type const* m_pNode; typename gc::Guard m_Guard; // data guard void next() { - while ( m_pNode ) { - m_pNode = m_pNode->next.load( memory_model::memory_order_acquire ); - if ( !m_pNode ) { - m_Guard.clear(); - break; - } - if ( m_Guard.protect( m_pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) - break; + for ( node_type* p = m_pNode->next.load( memory_model::memory_order_relaxed ); p != m_pNode; p = p->next.load( memory_model::memory_order_relaxed )) + { + m_pNode = p; + if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) + return; } + m_Guard.clear(); } - explicit iterator_type( atomic_node_ptr const& pNode ) - : m_pNode( pNode.load( memory_model::memory_order_acquire )) + explicit iterator_type( node_type const* pNode ) + : m_pNode( pNode ) { - if ( m_pNode ) { - if ( !m_Guard.protect( m_pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) - next(); - } + if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) + next(); } - iterator_type( node_type* pNode, value_type* pVal ) + iterator_type( node_type const* pNode, value_type* pVal ) : m_pNode( pNode ) { if ( m_pNode ) { @@ -341,7 +342,7 @@ namespace cds { namespace intrusive { */ iterator begin() { - return iterator( m_pHead ); + return iterator( &m_Head ); } /// Returns an iterator that addresses the location succeeding the last element in a list @@ -354,46 +355,48 @@ namespace cds { namespace intrusive { */ iterator end() { - return iterator(); + return iterator( &m_Tail ); } /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { - return const_iterator( m_pHead ); + return const_iterator( &m_Head ); } /// Returns a forward const iterator addressing the first element in a list const_iterator begin() const { - return const_iterator( m_pHead ); + return const_iterator( &m_Head ); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator end() const { - return const_iterator(); + return const_iterator( &m_Tail ); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator cend() const { - return const_iterator(); + return const_iterator( &m_Tail ); } //@} public: /// Default constructor initializes empty list IterableList() - : m_pHead( nullptr ) - {} + { + init_list(); + } //@cond template >::value >> explicit IterableList( Stat& st ) - : m_pHead( nullptr ) - , m_Stat( st ) - {} + : m_Stat( st ) + { + init_list(); + } //@endcond /// Destroys the list object @@ -411,7 +414,7 @@ namespace cds { namespace intrusive { */ bool insert( value_type& val ) { - return insert_at( m_pHead, val ); + return insert_at( &m_Head, val ); } /// Inserts new node @@ -436,7 +439,7 @@ namespace cds { namespace intrusive { template bool insert( value_type& val, Func f ) { - return insert_at( m_pHead, val, f ); + return insert_at( &m_Head, val, f ); } /// Updates the node @@ -462,7 +465,7 @@ namespace cds { namespace intrusive { template std::pair update( value_type& val, Func func, bool bInsert = true ) { - return update_at( m_pHead, val, func, bInsert ); + return update_at( &m_Head, val, func, bInsert ); } /// Insert or update @@ -480,7 +483,7 @@ namespace cds { namespace intrusive { */ std::pair upsert( value_type& val, bool bInsert = true ) { - return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert ); + return update_at( &m_Head, val, []( value_type&, value_type* ) {}, bInsert ); } /// Unlinks the item \p val from the list @@ -499,7 +502,7 @@ namespace cds { namespace intrusive { */ bool unlink( value_type& val ) { - return unlink_at( m_pHead, val ); + return unlink_at( &m_Head, val ); } /// Deletes the item from the list @@ -513,7 +516,7 @@ namespace cds { namespace intrusive { template bool erase( Q const& key ) { - return erase_at( m_pHead, key, key_comparator()); + return erase_at( &m_Head, key, key_comparator()); } /// Deletes the item from the list using \p pred predicate for searching @@ -529,7 +532,7 @@ namespace cds { namespace intrusive { bool erase_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Deletes the item from the list @@ -549,7 +552,7 @@ namespace cds { namespace intrusive { template bool erase( Q const& key, Func func ) { - return erase_at( m_pHead, key, key_comparator(), func ); + return erase_at( &m_Head, key, key_comparator(), func ); } /// Deletes the item from the list using \p pred predicate for searching @@ -565,7 +568,7 @@ namespace cds { namespace intrusive { bool erase_with( Q const& key, Less pred, Func f ) { CDS_UNUSED( pred ); - return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } /// Extracts the item from the list with specified \p key @@ -598,7 +601,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - return extract_at( m_pHead, key, key_comparator()); + return extract_at( &m_Head, key, key_comparator()); } /// Extracts the item using compare functor \p pred @@ -614,7 +617,7 @@ namespace cds { namespace intrusive { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Finds \p key in the list @@ -638,13 +641,13 @@ namespace cds { namespace intrusive { template bool find( Q& key, Func f ) const { - return find_at( m_pHead, key, key_comparator(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } //@cond template bool find( Q const& key, Func f ) const { - return find_at( m_pHead, key, key_comparator(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } //@endcond @@ -655,7 +658,7 @@ namespace cds { namespace intrusive { template iterator find( Q const& key ) const { - return find_iterator_at( m_pHead, key, key_comparator()); + return find_iterator_at( &m_Head, key, key_comparator()); } /// Finds the \p key using \p pred predicate for searching @@ -669,14 +672,14 @@ namespace cds { namespace intrusive { bool find_with( Q& key, Less pred, Func f ) const { CDS_UNUSED( pred ); - return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } //@cond template bool find_with( Q const& key, Less pred, Func f ) const { CDS_UNUSED( pred ); - return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } //@endcond @@ -692,7 +695,7 @@ namespace cds { namespace intrusive { iterator find_with( Q const& key, Less pred ) const { CDS_UNUSED( pred ); - return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Checks whether the list contains \p key @@ -703,7 +706,7 @@ namespace cds { namespace intrusive { template bool contains( Q const& key ) const { - return find_at( m_pHead, key, key_comparator()); + return find_at( &m_Head, key, key_comparator()); } /// Checks whether the list contains \p key using \p pred predicate for searching @@ -716,7 +719,7 @@ namespace cds { namespace intrusive { bool contains( Q const& key, Less pred ) const { CDS_UNUSED( pred ); - return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Finds the \p key and return the item found @@ -751,7 +754,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) const { - return get_at( m_pHead, key, key_comparator()); + return get_at( &m_Head, key, key_comparator()); } /// Finds the \p key and return the item found @@ -767,14 +770,15 @@ namespace cds { namespace intrusive { guarded_ptr get_with( Q const& key, Less pred ) const { CDS_UNUSED( pred ); - return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Clears the list (thread safe, not atomic) void clear() { position pos; - for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) { + pos.pPrev = nullptr; + for ( pos.pCur = m_Head.next.load( memory_model::memory_order_relaxed ); pos.pCur != pos.pPrev; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) { while ( true ) { pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr(); if ( !pos.pFound ) @@ -784,6 +788,7 @@ namespace cds { namespace intrusive { break; } } + pos.pPrev = pos.pCur; } } @@ -820,27 +825,27 @@ namespace cds { namespace intrusive { // split-list support bool insert_aux_node( node_type * pNode ) { - return insert_aux_node( m_pHead, pNode ); + return insert_aux_node( &m_Head, pNode ); } // split-list support - bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode ) + bool insert_aux_node( node_type* pHead, node_type * pNode ) { assert( pNode != nullptr ); // Hack: convert node_type to value_type. // In principle, auxiliary node can be non-reducible to value_type // We assume that comparator can correctly distinguish aux and regular node. - return insert_at( refHead, *node_traits::to_value_ptr( pNode ) ); + return insert_at( pHead, *node_traits::to_value_ptr( pNode ) ); } #endif - bool insert_at( atomic_node_ptr& refHead, value_type& val ) + bool insert_at( node_type* pHead, value_type& val ) { position pos; while ( true ) { - if ( search( refHead, val, pos, key_comparator() )) { + if ( search( pHead, val, pos, key_comparator() )) { m_Stat.onInsertFailed(); return false; } @@ -856,7 +861,7 @@ namespace cds { namespace intrusive { } template - bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f ) + bool insert_at( node_type* pHead, value_type& val, Func f ) { position pos; @@ -864,7 +869,7 @@ namespace cds { namespace intrusive { guard.assign( &val ); while ( true ) { - if ( search( refHead, val, pos, key_comparator() ) ) { + if ( search( pHead, val, pos, key_comparator() ) ) { m_Stat.onInsertFailed(); return false; } @@ -881,7 +886,7 @@ namespace cds { namespace intrusive { } template - std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) + std::pair update_at( node_type* pHead, value_type& val, Func func, bool bInsert ) { position pos; @@ -889,13 +894,13 @@ namespace cds { namespace intrusive { guard.assign( &val ); while ( true ) { - if ( search( refHead, val, pos, key_comparator() ) ) { + if ( search( pHead, val, pos, key_comparator() ) ) { // try to replace pCur->data with val assert( pos.pFound != nullptr ); assert( key_comparator()(*pos.pFound, val) == 0 ); marked_data_ptr pFound( pos.pFound ); - if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ), + if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))) { if ( pos.pFound != &val ) { @@ -924,12 +929,12 @@ namespace cds { namespace intrusive { } } - bool unlink_at( atomic_node_ptr& refHead, value_type& val ) + bool unlink_at( node_type* pHead, value_type& val ) { position pos; back_off bkoff; - while ( search( refHead, val, pos, key_comparator())) { + while ( search( pHead, val, pos, key_comparator())) { if ( pos.pFound == &val ) { if ( unlink_data( pos )) { --m_ItemCounter; @@ -950,10 +955,10 @@ namespace cds { namespace intrusive { } template - bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos ) + bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos ) { back_off bkoff; - while ( search( refHead, val, pos, cmp )) { + while ( search( pHead, val, pos, cmp )) { if ( unlink_data( pos )) { f( *pos.pFound ); --m_ItemCounter; @@ -971,25 +976,25 @@ namespace cds { namespace intrusive { } template - bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f ) + bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f ) { position pos; - return erase_at( refHead, val, cmp, f, pos ); + return erase_at( pHead, val, cmp, f, pos ); } template - bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) + bool erase_at( node_type* pHead, Q const& val, Compare cmp ) { position pos; - return erase_at( refHead, val, cmp, [](value_type const&){}, pos ); + return erase_at( pHead, val, cmp, [](value_type const&){}, pos ); } template - guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) + guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp ) { position pos; back_off bkoff; - while ( search( refHead, val, pos, cmp )) { + while ( search( pHead, val, pos, cmp )) { if ( unlink_data( pos )) { --m_ItemCounter; m_Stat.onEraseSuccess(); @@ -1007,10 +1012,10 @@ namespace cds { namespace intrusive { } template - bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const + bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const { position pos; - if ( search( refHead, val, pos, cmp ) ) { + if ( search( pHead, val, pos, cmp ) ) { m_Stat.onFindSuccess(); return true; } @@ -1020,10 +1025,10 @@ namespace cds { namespace intrusive { } template - bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const + bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const { position pos; - if ( search( refHead, val, pos, cmp )) { + if ( search( pHead, val, pos, cmp )) { assert( pos.pFound != nullptr ); f( *pos.pFound, val ); m_Stat.onFindSuccess(); @@ -1035,10 +1040,10 @@ namespace cds { namespace intrusive { } template - iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const + iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const { position pos; - if ( search( refHead, val, pos, cmp )) { + if ( search( pHead, val, pos, cmp )) { assert( pos.pCur != nullptr ); assert( pos.pFound != nullptr ); m_Stat.onFindSuccess(); @@ -1046,14 +1051,14 @@ namespace cds { namespace intrusive { } m_Stat.onFindFailed(); - return iterator{}; + return iterator( &m_Tail ); } template - guarded_ptr get_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const + guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const { position pos; - if ( search( refHead, val, pos, cmp )) { + if ( search( pHead, val, pos, cmp )) { m_Stat.onFindSuccess(); return guarded_ptr( std::move( pos.guard )); } @@ -1061,26 +1066,36 @@ namespace cds { namespace intrusive { m_Stat.onFindFailed(); return guarded_ptr(); } + + node_type* head() + { + return &m_Head; + } + + node_type const* head() const + { + return &m_Head; + } //@endcond protected: - //@cond template - bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const + bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const { - atomic_node_ptr* pHead = const_cast( &refHead ); - node_type * pPrev = nullptr; + pos.pHead = pHead; + node_type* pPrev = const_cast( pHead ); + value_type* pPrevVal = nullptr; while ( true ) { - node_type * pCur = pHead->load( memory_model::memory_order_relaxed ); + node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed ); - if ( pCur == nullptr ) { + if ( pCur == pCur->next.load( memory_model::memory_order_relaxed )) { // end-of-list - pos.pHead = pHead; pos.pPrev = pPrev; - pos.pCur = nullptr; + pos.pCur = pCur; pos.pFound = nullptr; + pos.pPrevVal = pPrevVal; return false; } @@ -1091,24 +1106,32 @@ namespace cds { namespace intrusive { }).ptr(); if ( pVal ) { - int nCmp = cmp( *pVal, val ); + int const nCmp = cmp( *pVal, val ); if ( nCmp >= 0 ) { - pos.pHead = pHead; pos.pPrev = pPrev; pos.pCur = pCur; pos.pFound = pVal; + pos.pPrevVal = pPrevVal; return nCmp == 0; } } pPrev = pCur; - pHead = &( pCur->next ); + pPrevVal = pVal; + pos.prevGuard.copy( pos.guard ); } } //@endcond private: //@cond + void init_list() + { + m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed ); + // end-of-list mark: node.next == node + m_Tail.next.store( &m_Tail, memory_model::memory_order_release ); + } + node_type * alloc_node( value_type * pVal ) { m_Stat.onNodeCreated(); @@ -1129,8 +1152,8 @@ namespace cds { namespace intrusive { void destroy() { - node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed ); - while ( pNode ) { + node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed ); + while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) { value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr(); if ( pVal ) retire_data( pVal ); @@ -1142,61 +1165,72 @@ namespace cds { namespace intrusive { bool link_data( value_type * pVal, position& pos ) { - if ( pos.pPrev ) { - if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == marked_data_ptr() ) { - // reuse pPrev - - // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible - // if current thread will be preempted and another thread deletes pos.pCur data - // and then set it to another. - // To prevent this we mark pos.pCur data as undeletable by setting LSB - marked_data_ptr val( pos.pFound ); - if ( pos.pCur && !pos.pCur->data.compare_exchange_strong( val, val | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { - // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data - m_Stat.onReuseNodeMarkFailed(); - return false; - } + assert( pos.pPrev != nullptr ); + assert( pos.pCur != nullptr ); - if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) { - // sequence pPrev - pCur is broken - if ( pos.pCur ) - pos.pCur->data.store( val, memory_model::memory_order_relaxed ); - m_Stat.onReuseNodeSeqBreak(); - return false; - } + // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible + // if current thread will be preempted and another thread will delete pos.pCur data + // and then set it to another. + // To prevent this we mark pos.pCur data as undeletable by setting LSB + marked_data_ptr valCur( pos.pFound ); + if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data + m_Stat.onNodeMarkFailed(); + return false; + } - // Set pos.pPrev data if it is null - marked_data_ptr p; - bool result = pos.pPrev->data.compare_exchange_strong( p, marked_data_ptr( pVal ), - memory_model::memory_order_release, atomics::memory_order_relaxed ); + marked_data_ptr valPrev( pos.pPrevVal ); + if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + pos.pCur->data.store( valCur, memory_model::memory_order_relaxed ); + m_Stat.onNodeMarkFailed(); + return false; + } - // Clear pos.pCur data mark - if ( pos.pCur ) - pos.pCur->data.store( val, memory_model::memory_order_relaxed ); + // checks if link pPrev -> pCur is broken + if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) { + // sequence pPrev - pCur is broken + pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed ); + pos.pCur->data.store( valCur, memory_model::memory_order_relaxed ); + m_Stat.onNodeSeqBreak(); + return false; + } - if ( result ) - m_Stat.onReuseNode(); - return result; - } - else { - // insert new node between pos.pPrev and pos.pCur - node_type * pNode = alloc_node( pVal ); - pNode->next.store( pos.pCur, memory_model::memory_order_relaxed ); + if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr ) + { + // reuse pPrev - if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ))) - return true; + // Set pos.pPrev data if it is null + valPrev |= 1; + bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ), + memory_model::memory_order_release, atomics::memory_order_relaxed ); + + // Clears data marks + pos.pCur->data.store( valCur, memory_model::memory_order_relaxed ); - delete_node( pNode ); + if ( result ) { + m_Stat.onReuseNode(); + return result; } } else { + // insert new node between pos.pPrev and pos.pCur node_type * pNode = alloc_node( pVal ); pNode->next.store( pos.pCur, memory_model::memory_order_relaxed ); - if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) ) - return true; + + bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ); + + // Clears data marks + pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed ); + pos.pCur->data.store( valCur, memory_model::memory_order_relaxed ); + + if ( result ) { + m_Stat.onNewNodeCreated(); + return result; + } delete_node( pNode ); } + return false; } @@ -1212,7 +1246,6 @@ namespace cds { namespace intrusive { } return false; } - //@endcond }; }} // namespace cds::intrusive diff --git a/test/include/cds_test/stat_iterable_list_out.h b/test/include/cds_test/stat_iterable_list_out.h index c2aceeef..04b1193a 100644 --- a/test/include/cds_test/stat_iterable_list_out.h +++ b/test/include/cds_test/stat_iterable_list_out.h @@ -47,8 +47,9 @@ namespace cds_test { << CDSSTRESS_STAT_OUT( s, m_nInsertFailed ) << CDSSTRESS_STAT_OUT( s, m_nInsertRetry ) << CDSSTRESS_STAT_OUT( s, m_nReuseNode ) - << CDSSTRESS_STAT_OUT( s, m_nReuseNodeMarkFailed ) - << CDSSTRESS_STAT_OUT( s, m_nReuseNodeSeqBreak ) + << CDSSTRESS_STAT_OUT( s, m_nNodeMarkFailed ) + << CDSSTRESS_STAT_OUT( s, m_nNodeSeqBreak ) + << CDSSTRESS_STAT_OUT( s, m_nNewNodeCreated ) << CDSSTRESS_STAT_OUT( s, m_nUpdateNew ) << CDSSTRESS_STAT_OUT( s, m_nUpdateExisting ) << CDSSTRESS_STAT_OUT( s, m_nUpdateFailed ) diff --git a/test/unit/intrusive-list/intrusive_iterable_dhp.cpp b/test/unit/intrusive-list/intrusive_iterable_dhp.cpp index 38d8c527..e604978f 100644 --- a/test/unit/intrusive-list/intrusive_iterable_dhp.cpp +++ b/test/unit/intrusive-list/intrusive_iterable_dhp.cpp @@ -5,7 +5,7 @@ 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: @@ -42,8 +42,6 @@ namespace { { typedef ci::IterableList< gc_type, item_type > list_type; - // +1 - for guarded_ptr - // +3 - for iterator test cds::gc::dhp::GarbageCollector::Construct( 16, list_type::c_nHazardPtrCount ); cds::threading::Manager::attachThread(); } diff --git a/test/unit/intrusive-list/test_intrusive_iterable_list.h b/test/unit/intrusive-list/test_intrusive_iterable_list.h index 1db06f9c..763826e2 100644 --- a/test/unit/intrusive-list/test_intrusive_iterable_list.h +++ b/test/unit/intrusive-list/test_intrusive_iterable_list.h @@ -5,7 +5,7 @@ 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 CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H #define CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H @@ -242,6 +242,7 @@ namespace cds_test { EXPECT_FALSE( l.contains( i.nKey )); EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less())); EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_TRUE( l.find( i.nKey ) == l.end()); EXPECT_EQ( i.s.nFindCall, 0 ); EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); EXPECT_EQ( i.s.nFindCall, 0 ); @@ -292,6 +293,7 @@ namespace cds_test { EXPECT_TRUE( l.contains( i.nKey )); EXPECT_TRUE( l.contains( i )); EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_FALSE( l.find( i.nKey ) == l.end() ); EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); EXPECT_EQ( i.s.nFindCall, 1 ); EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } )); diff --git a/test/unit/list/iterable_dhp.cpp b/test/unit/list/iterable_dhp.cpp index b008e92c..b1da7f23 100644 --- a/test/unit/list/iterable_dhp.cpp +++ b/test/unit/list/iterable_dhp.cpp @@ -5,7 +5,7 @@ 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: @@ -42,7 +42,6 @@ namespace { { typedef cc::IterableList< gc_type, item > list_type; - // +3 - for guarded_ptr, iterators cds::gc::dhp::GarbageCollector::Construct( 16, list_type::c_nHazardPtrCount ); cds::threading::Manager::attachThread(); } diff --git a/test/unit/list/iterable_hp.cpp b/test/unit/list/iterable_hp.cpp index b590344c..f96b60cd 100644 --- a/test/unit/list/iterable_hp.cpp +++ b/test/unit/list/iterable_hp.cpp @@ -5,7 +5,7 @@ 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: diff --git a/test/unit/list/kv_iterable_dhp.cpp b/test/unit/list/kv_iterable_dhp.cpp index 9cb97e1e..94903d5d 100644 --- a/test/unit/list/kv_iterable_dhp.cpp +++ b/test/unit/list/kv_iterable_dhp.cpp @@ -5,7 +5,7 @@ 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: diff --git a/test/unit/list/kv_iterable_hp.cpp b/test/unit/list/kv_iterable_hp.cpp index 84cf2c54..6553792a 100644 --- a/test/unit/list/kv_iterable_hp.cpp +++ b/test/unit/list/kv_iterable_hp.cpp @@ -5,7 +5,7 @@ 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: diff --git a/test/unit/list/test_iterable_list.h b/test/unit/list/test_iterable_list.h index 40dbfe99..693731d7 100644 --- a/test/unit/list/test_iterable_list.h +++ b/test/unit/list/test_iterable_list.h @@ -5,7 +5,7 @@ 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: -- 2.34.1