From f78b1cf121bf6e06c848c96641ff7366b95aafa4 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 25 Jul 2016 23:21:40 +0300 Subject: [PATCH] Added internal statistics for LazyList --- cds/container/details/lazy_list_base.h | 28 +++- cds/intrusive/details/lazy_list_base.h | 122 +++++++++++++++- cds/intrusive/details/michael_list_base.h | 17 ++- cds/intrusive/impl/lazy_list.h | 109 +++++++++++--- cds/intrusive/lazy_list_nogc.h | 69 +++++++-- cds/intrusive/lazy_list_rcu.h | 138 +++++++++++++----- .../intrusive_michael_lazy_dhp.cpp | 2 +- test/unit/list/intrusive_lazy_dhp.cpp | 77 +++++++++- test/unit/list/intrusive_lazy_hp.cpp | 72 ++++++++- test/unit/list/intrusive_lazy_nogc.cpp | 70 ++++++++- test/unit/list/intrusive_michael_dhp.cpp | 2 +- test/unit/list/kv_lazy_dhp.cpp | 4 +- test/unit/list/kv_michael_dhp.cpp | 2 +- test/unit/list/lazy_dhp.cpp | 4 +- test/unit/list/michael_dhp.cpp | 2 +- test/unit/list/test_intrusive_lazy_rcu.h | 74 +++++++++- 16 files changed, 702 insertions(+), 90 deletions(-) diff --git a/cds/container/details/lazy_list_base.h b/cds/container/details/lazy_list_base.h index 5c1521ae..021fc1de 100644 --- a/cds/container/details/lazy_list_base.h +++ b/cds/container/details/lazy_list_base.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_DETAILS_LAZY_LIST_BASE_H @@ -37,10 +37,23 @@ namespace cds { namespace container { - /// LazyList ordered list related definitions + /// \p LazyList ordered list related definitions /** @ingroup cds_nonintrusive_helper */ namespace lazy_list { + + /// \p LazyList internal statistics, see \p cds::intrusive::lazy_list::stat + template + using stat = cds::intrusive::lazy_list::stat< EventCounter >; + + /// \p LazyList empty internal statistics, see \p cds::intrusive::lazy_list::empty_stat + typedef cds::intrusive::lazy_list::empty_stat empty_stat; + + //@cond + template > + using wrapped_stat = cds::intrusive::lazy_list::wrapped_stat< Stat >; + //@endif + /// LazyList traits /** Either \p compare or \p less or both must be specified. @@ -88,10 +101,17 @@ namespace cds { namespace container { /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting typedef atomicity::empty_item_counter item_counter; + /// Internal statistics + /** + By default, internal statistics is disabled (\p lazy_list::empty_stat). + Use \p lazy_list::stat to enable it. + */ + typedef empty_stat stat; + /// C++ memory ordering model /** Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). + or \p opt::v::sequential_consistent (sequentially consistent memory model). */ typedef opt::v::relaxed_ordering memory_model; @@ -125,6 +145,8 @@ namespace cds { namespace container { - \p opt::back_off - back-off strategy used. If the option is not specified, \p cds::backoff::Default is used. - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter). To enable item counting use \p atomicity::item_counter. + - \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat). + To enable it use \p lazy_list::stat - \p opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro. - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). diff --git a/cds/intrusive/details/lazy_list_base.h b/cds/intrusive/details/lazy_list_base.h index 2a8e79b8..e170bf67 100644 --- a/cds/intrusive/details/lazy_list_base.h +++ b/cds/intrusive/details/lazy_list_base.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_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H @@ -215,6 +215,101 @@ namespace cds { namespace intrusive { //@endcond }; + /// \p LazyList internal statistics + template + struct stat { + typedef EventCounter event_counter; ///< Event counter type + + event_counter m_nInsertSuccess; ///< Number of success \p insert() operations + event_counter m_nInsertFailed; ///< Number of failed \p insert() operations + event_counter m_nInsertRetry; ///< Number of attempts to insert new item + 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 + event_counter m_nUpdateRetry; ///< Number of attempts to \p update() the item + event_counter m_nUpdateMarked; ///< Number of attempts to \p update() logically deleted (marked) items + event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations + event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations + event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item + event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations + event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations + + event_counter m_nValidationSuccess; ///< Number of successful validating of search result + event_counter m_nValidationFailed; ///< Number of failed validating of search result + + //@cond + void onInsertSuccess() { ++m_nInsertSuccess; } + void onInsertFailed() { ++m_nInsertFailed; } + void onInsertRetry() { ++m_nInsertRetry; } + void onUpdateNew() { ++m_nUpdateNew; } + void onUpdateExisting() { ++m_nUpdateExisting; } + void onUpdateFailed() { ++m_nUpdateFailed; } + void onUpdateRetry() { ++m_nUpdateRetry; } + void onUpdateMarked() { ++m_nUpdateMarked; } + void onEraseSuccess() { ++m_nEraseSuccess; } + void onEraseFailed() { ++m_nEraseFailed; } + void onEraseRetry() { ++m_nEraseRetry; } + void onFindSuccess() { ++m_nFindSuccess; } + void onFindFailed() { ++m_nFindFailed; } + + void onValidationSuccess() { ++m_nValidationSuccess; } + void onValidationFailed() { ++m_nValidationFailed; } + //@endcond + }; + + /// \p LazyList empty internal statistics + struct empty_stat { + //@cond + void onInsertSuccess() const {} + void onInsertFailed() const {} + void onInsertRetry() const {} + void onUpdateNew() const {} + void onUpdateExisting() const {} + void onUpdateFailed() const {} + void onUpdateRetry() const {} + void onUpdateMarked() const {} + void onEraseSuccess() const {} + void onEraseFailed() const {} + void onEraseRetry() const {} + void onFindSuccess() const {} + void onFindFailed() const {} + + void onValidationSuccess() const {} + void onValidationFailed() const {} + //@endcond + }; + + //@cond + template > + struct wrapped_stat { + typedef Stat stat_type; + + wrapped_stat( stat_type& st ) + : m_stat( st ) + {} + + void onInsertSuccess() { m_stat.onInsertSuccess(); } + void onInsertFailed() { m_stat.onInsertFailed(); } + void onInsertRetry() { m_stat.onInsertRetry(); } + void onUpdateNew() { m_stat.onUpdateNew(); } + void onUpdateExisting() { m_stat.onUpdateExisting(); } + void onUpdateFailed() { m_stat.onUpdateFailed(); } + void onUpdateRetry() { m_stat.onUpdateRetry(); } + void onUpdateMarked() { m_stat.onUpdateMarked(); } + void onEraseSuccess() { m_stat.onEraseSuccess(); } + void onEraseFailed() { m_stat.onEraseFailed(); } + void onEraseRetry() { m_stat.onEraseRetry(); } + void onFindSuccess() { m_stat.onFindSuccess(); } + void onFindFailed() { m_stat.onFindFailed(); } + + void onValidationSuccess() { m_stat.onValidationSuccess(); } + void onValidationFailed() { m_stat.onValidationFailed(); } + + stat_type& m_stat; + }; + //@endcond + + /// LazyList traits struct traits { @@ -260,6 +355,13 @@ namespace cds { namespace intrusive { /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting typedef atomicity::empty_item_counter item_counter; + /// Internal statistics + /** + By default, internal statistics is disabled (\p lazy_list::empty_stat). + Use \p lazy_list::stat to enable it. + */ + typedef empty_stat stat; + /// Link fields checking feature /** Default is \p opt::debug_check_link @@ -298,6 +400,8 @@ namespace cds { namespace intrusive { - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter). To enable item counting use \p atomicity::item_counter. + - \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat). + To enable it use \p lazy_list::stat - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList" @@ -323,6 +427,22 @@ namespace cds { namespace intrusive { class LazyList; //@endcond + //@cond + template + struct is_lazy_list { + enum { + value = false + }; + }; + + template + struct is_lazy_list< LazyList< GC, T, Traits >> { + enum { + value = true + }; + }; + //@endcond + }} // namespace cds::intrusive #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H diff --git a/cds/intrusive/details/michael_list_base.h b/cds/intrusive/details/michael_list_base.h index b6cc2caf..6b68442d 100644 --- a/cds/intrusive/details/michael_list_base.h +++ b/cds/intrusive/details/michael_list_base.h @@ -390,8 +390,21 @@ namespace cds { namespace intrusive { //@endcond - /// Tag for selecting Michael list - //class michael_list_tag; + //@cond + template + struct is_michael_list { + enum { + value = false + }; + }; + + template + struct is_michael_list< MichaelList< GC, T, Traits >> { + enum { + value = true + }; + }; + //@endcond }} // namespace cds::intrusive diff --git a/cds/intrusive/impl/lazy_list.h b/cds/intrusive/impl/lazy_list.h index 7033bde0..abe6ef4c 100644 --- a/cds/intrusive/impl/lazy_list.h +++ b/cds/intrusive/impl/lazy_list.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_INTRUSIVE_IMPL_LAZY_LIST_H @@ -57,7 +57,7 @@ namespace cds { namespace intrusive { - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook) or it must have a member of type lazy_list::node (for lazy_list::member_hook). - \p Traits - type traits. See lazy_list::traits for explanation. - It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template + It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template argument. For example, the following traits-based declaration of \p gc::HP lazy list \code #include @@ -201,9 +201,12 @@ namespace cds { namespace intrusive { typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker - typedef typename traits::back_off back_off; ///< back-off strategy + typedef typename traits::back_off back_off; ///< back-off strategy typedef typename traits::item_counter item_counter; ///< Item counting policy used - typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) + typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) + typedef typename traits::stat stat; ///< Internal statistics + + static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type"); typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer @@ -231,8 +234,8 @@ namespace cds { namespace intrusive { node_type m_Tail; item_counter m_ItemCounter; + stat m_Stat; ///< Internal statistics - //@cond struct clean_disposer { void operator()( value_type * p ) { @@ -498,10 +501,18 @@ namespace cds { namespace intrusive { /// Default constructor initializes empty list LazyList() { - static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" ); m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed ); } + //@cond + template >::value >> + explicit LazyList( Stat& st ) + : m_Stat( st ) + { + m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed ); + } + //@endcond + /// Destroys the list object ~LazyList() { @@ -910,13 +921,19 @@ namespace cds { namespace intrusive { this function always returns 0. @note Even if you use real item counter and it returns 0, this fact does not mean that the list - is empty. To check list emptyness use \p empty() method. + is empty. To check list emptiness use \p empty() method. */ size_t size() const { return m_ItemCounter.value(); } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + protected: //@cond // split-list support @@ -948,16 +965,22 @@ namespace cds { namespace intrusive { if ( validate( pos.pPred, pos.pCur )) { if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } else { link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return true; + break; } } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; } template @@ -973,17 +996,23 @@ namespace cds { namespace intrusive { if ( validate( pos.pPred, pos.pCur )) { if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } else { link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); f( val ); - ++m_ItemCounter; - return true; + break; } } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; } template @@ -1001,21 +1030,29 @@ namespace cds { namespace intrusive { // key already in the list func( false, *node_traits::to_value_ptr( *pos.pCur ) , val ); + m_Stat.onUpdateExisting(); return std::make_pair( true, false ); } else { // new key - if ( !bAllowInsert ) + if ( !bAllowInsert ) { + m_Stat.onUpdateFailed(); return std::make_pair( false, false ); + } link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); func( true, val, val ); - ++m_ItemCounter; - return std::make_pair( true, true ); + break; } } } + + m_Stat.onUpdateRetry(); } + + ++m_ItemCounter; + m_Stat.onUpdateNew(); + return std::make_pair( true, true ); } bool unlink_at( node_type * pHead, value_type& val ) @@ -1036,21 +1073,27 @@ namespace cds { namespace intrusive { { // item found unlink_node( pos.pPred, pos.pCur, pHead ); - --m_ItemCounter; nResult = 1; } else nResult = -1; } } + if ( nResult ) { if ( nResult > 0 ) { + --m_ItemCounter; retire_node( pos.pCur ); + m_Stat.onEraseSuccess(); return true; } + + m_Stat.onEraseFailed(); return false; } } + + m_Stat.onEraseRetry(); } } @@ -1068,7 +1111,6 @@ namespace cds { namespace intrusive { // key found unlink_node( pos.pPred, pos.pCur, pHead ); f( *node_traits::to_value_ptr( *pos.pCur )); - --m_ItemCounter; nResult = 1; } else { @@ -1078,12 +1120,18 @@ namespace cds { namespace intrusive { } if ( nResult ) { if ( nResult > 0 ) { + --m_ItemCounter; retire_node( pos.pCur ); + m_Stat.onEraseSuccess(); return true; } + + m_Stat.onEraseFailed(); return false; } } + + m_Stat.onEraseRetry(); } } @@ -1124,9 +1172,12 @@ namespace cds { namespace intrusive { && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { f( *node_traits::to_value_ptr( *pos.pCur ), val ); + m_Stat.onFindSuccess(); return true; } } + + m_Stat.onFindFailed(); return false; } @@ -1136,9 +1187,13 @@ namespace cds { namespace intrusive { position pos; search( pHead, val, pos, cmp ); - return pos.pCur != &m_Tail - && !pos.pCur->is_marked() - && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0; + if ( pos.pCur != &m_Tail && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + m_Stat.onFindSuccess(); + return true; + } + + m_Stat.onFindFailed(); + return false; } template @@ -1152,8 +1207,11 @@ namespace cds { namespace intrusive { && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { gp.set( pos.guards.template get( position::guard_current_item )); + m_Stat.onFindSuccess(); return true; } + + m_Stat.onFindFailed(); return false; } @@ -1190,7 +1248,18 @@ namespace cds { namespace intrusive { pos.pPred = pPrev.ptr(); } - static bool validate( node_type * pPred, node_type * pCur ) + bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT + { + if ( validate_link( pPred, pCur )) { + m_Stat.onValidationSuccess(); + return true; + } + + m_Stat.onValidationFailed(); + return true; + } + + static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT { return !pPred->is_marked() && !pCur->is_marked() diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index 38384ee9..17a7deb2 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.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_INTRUSIVE_LAZY_LIST_NOGC_H @@ -119,10 +119,13 @@ namespace cds { namespace intrusive { typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker - typedef typename traits::item_counter item_counter; ///< Item counting policy used - typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see lazy_list::traits::memory_model) + typedef typename traits::item_counter item_counter; ///< Item counting policy used + typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) + typedef typename traits::stat stat; ///< Internal statistics //@cond + static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type"); + // Rebind traits (split-list support) template struct rebind_traits { @@ -141,6 +144,7 @@ namespace cds { namespace intrusive { node_type m_Head; ///< List head (dummy node) node_type m_Tail; ///< List tail (dummy node) item_counter m_ItemCounter; ///< Item counter + mutable stat m_Stat; ///< Internal statistics //@cond @@ -348,10 +352,18 @@ namespace cds { namespace intrusive { /// Default constructor initializes empty list LazyList() { - static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" ); m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed ); } + //@cond + template >::value >> + explicit LazyList( Stat& st ) + : m_Stat( st ) + { + m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed ); + } + //@endcond + /// Destroys the list object ~LazyList() { @@ -592,6 +604,12 @@ namespace cds { namespace intrusive { return m_ItemCounter.value(); } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + protected: //@cond // split-list support @@ -624,16 +642,22 @@ namespace cds { namespace intrusive { if ( validate( pos.pPred, pos.pCur )) { if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } else { link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return true; + break; } } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; } iterator insert_at_( node_type * pHead, value_type& val ) @@ -659,21 +683,29 @@ namespace cds { namespace intrusive { // key already in the list func( false, *node_traits::to_value_ptr( *pos.pCur ) , val ); + m_Stat.onUpdateExisting(); return std::make_pair( iterator( pos.pCur ), false ); } else { // new key - if ( !bAllowInsert ) + if ( !bAllowInsert ) { + m_Stat.onUpdateFailed(); return std::make_pair( end(), false ); + } link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); func( true, val, val ); - ++m_ItemCounter; - return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); + break; } } + + m_Stat.onUpdateRetry(); } } + + ++m_ItemCounter; + m_Stat.onUpdateNew(); + return std::make_pair( iterator( node_traits::to_node_ptr( val ) ), true ); } template @@ -694,9 +726,12 @@ namespace cds { namespace intrusive { if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) { f( *node_traits::to_value_ptr( *pos.pCur ), val ); + m_Stat.onFindSuccess(); return true; } } + + m_Stat.onFindFailed(); return false; } @@ -716,9 +751,13 @@ namespace cds { namespace intrusive { search( pHead, val, pos, pred ); if ( pos.pCur != &m_Tail ) { - if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) + if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { + m_Stat.onFindSuccess(); return iterator( pos.pCur ); + } } + + m_Stat.onFindFailed(); return end(); } @@ -772,9 +811,15 @@ namespace cds { namespace intrusive { return cmp(l, r) == 0; } - static bool validate( node_type * pPred, node_type * pCur ) + bool validate( node_type * pPred, node_type * pCur ) { - return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur; + if ( pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur ) { + m_Stat.onValidationSuccess(); + return true; + } + + m_Stat.onValidationFailed(); + return false; } // for split-list diff --git a/cds/intrusive/lazy_list_rcu.h b/cds/intrusive/lazy_list_rcu.h index d22474a2..d5bec4bf 100644 --- a/cds/intrusive/lazy_list_rcu.h +++ b/cds/intrusive/lazy_list_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_INTRUSIVE_LAZY_LIST_RCU_H @@ -88,20 +88,8 @@ namespace cds { namespace intrusive { - \p RCU - one of \ref cds_urcu_gc "RCU type" - \p T - type to be stored in the list - \p Traits - type traits. See \p lazy_list::traits for explanation. - - It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template - argument. Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are: - - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook. - If the option is not specified, lazy_list::base_hook<> is used. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used. - - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer - - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter - - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) - or opt::v::sequential_consistent (sequentially consisnent memory model). + It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template + argument. \par Usage Before including you should include appropriate RCU header file, @@ -145,14 +133,17 @@ namespace cds { namespace intrusive { typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker - typedef typename traits::back_off back_off; ///< back-off strategy (not used) - typedef typename traits::item_counter item_counter; ///< Item counting policy used - typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) - typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy + typedef typename traits::back_off back_off; ///< back-off strategy (not used) + typedef typename traits::item_counter item_counter; ///< Item counting policy used + typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) + typedef typename traits::stat stat; ///< Internal statistics + typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking + static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type"); + //@cond // Rebind traits (split-list support) template @@ -166,13 +157,16 @@ namespace cds { namespace intrusive { //@endcond protected: - typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer - typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support) + //@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) item_counter m_ItemCounter; ///< Item counter + mutable stat m_Stat; ///< Internal statistics //@cond @@ -430,10 +424,18 @@ namespace cds { namespace intrusive { /// Default constructor initializes empty list LazyList() { - static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" ); m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed ); } + //@cond + template >::value >> + explicit LazyList( Stat& st ) + : m_Stat( st ) + { + m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed ); + } + //@endcond + /// Destroys the list object ~LazyList() { @@ -879,13 +881,19 @@ namespace cds { namespace intrusive { this function always returns 0. Warning: even if you use real item counter and it returns 0, this fact is not mean that the list - is empty. To check list emptyness use \ref empty() method. + is empty. To check list emptiness use \ref empty() method. */ size_t size() const { return m_ItemCounter.value(); } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + protected: //@cond // split-list support @@ -926,16 +934,22 @@ namespace cds { namespace intrusive { if ( validate( pos.pPred, pos.pCur )) { if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } f( val ); link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return true; + break; } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; } iterator insert_at_( node_type * pHead, value_type& val ) @@ -982,7 +996,6 @@ namespace cds { namespace intrusive { { // item found unlink_node( pos.pPred, pos.pCur, pHead ); - --m_ItemCounter; nResult = 1; } else @@ -993,11 +1006,17 @@ namespace cds { namespace intrusive { if ( nResult ) { if ( nResult > 0 ) { + --m_ItemCounter; dispose_node( pos.pCur ); + m_Stat.onEraseSuccess(); return true; } + + m_Stat.onEraseFailed(); return false; } + + m_Stat.onEraseRetry(); } } @@ -1018,7 +1037,6 @@ namespace cds { namespace intrusive { // key found unlink_node( pos.pPred, pos.pCur, pHead ); f( *node_traits::to_value_ptr( *pos.pCur )); - --m_ItemCounter; nResult = 1; } else @@ -1029,11 +1047,17 @@ namespace cds { namespace intrusive { if ( nResult ) { if ( nResult > 0 ) { + --m_ItemCounter; dispose_node( pos.pCur ); + m_Stat.onEraseSuccess(); return true; } + + m_Stat.onEraseFailed(); return false; } + + m_Stat.onEraseRetry(); } } @@ -1066,7 +1090,6 @@ namespace cds { namespace intrusive { if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // key found unlink_node( pos.pPred, pos.pCur, pHead ); - --m_ItemCounter; nResult = 1; } else { @@ -1076,10 +1099,17 @@ namespace cds { namespace intrusive { } if ( nResult ) { - if ( nResult > 0 ) + if ( nResult > 0 ) { + --m_ItemCounter; + m_Stat.onEraseSuccess(); return node_traits::to_value_ptr( pos.pCur ); + } + + m_Stat.onEraseFailed(); return nullptr; } + + m_Stat.onEraseRetry(); } } @@ -1092,12 +1122,14 @@ namespace cds { namespace intrusive { search( pHead, val, pos, cmp ); if ( pos.pCur != &m_Tail ) { std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); - if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) - { + if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { f( *node_traits::to_value_ptr( *pos.pCur ), val ); + m_Stat.onFindSuccess(); return true; } } + + m_Stat.onFindFailed(); return false; } @@ -1117,9 +1149,13 @@ namespace cds { namespace intrusive { search( pHead, val, pos, cmp ); if ( pos.pCur != &m_Tail ) { - if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) + if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + m_Stat.onFindSuccess(); return const_iterator( pos.pCur ); + } } + + m_Stat.onFindFailed(); return end(); } @@ -1163,7 +1199,18 @@ namespace cds { namespace intrusive { pos.pPred = pPrev.ptr(); } - static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT + bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT + { + if ( validate_link( pPred, pCur ) ) { + m_Stat.onValidationSuccess(); + return true; + } + + m_Stat.onValidationFailed(); + return false; + } + + static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT { // RCU lock should be locked assert( gc::is_locked()); @@ -1192,15 +1239,22 @@ namespace cds { namespace intrusive { if ( validate( pos.pPred, pos.pCur )) { if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return true; + break; } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; + } template @@ -1221,21 +1275,29 @@ namespace cds { namespace intrusive { // key already in the list func( false, *node_traits::to_value_ptr( *pos.pCur ), val ); + m_Stat.onUpdateExisting(); return std::make_pair( iterator( pos.pCur ), false ); } else { // new key - if ( !bAllowInsert ) + if ( !bAllowInsert ) { + m_Stat.onUpdateFailed(); return std::make_pair( end(), false ); + } func( true, val, val ); link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); + break; } } } + + m_Stat.onUpdateRetry(); } + + ++m_ItemCounter; + m_Stat.onUpdateNew(); + return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); } //@endcond }; diff --git a/test/unit/intrusive-set/intrusive_michael_lazy_dhp.cpp b/test/unit/intrusive-set/intrusive_michael_lazy_dhp.cpp index 633001a0..4b2a2ce1 100644 --- a/test/unit/intrusive-set/intrusive_michael_lazy_dhp.cpp +++ b/test/unit/intrusive-set/intrusive_michael_lazy_dhp.cpp @@ -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. */ #include "test_intrusive_set_hp.h" diff --git a/test/unit/list/intrusive_lazy_dhp.cpp b/test/unit/list/intrusive_lazy_dhp.cpp index a443b005..73246179 100644 --- a/test/unit/list/intrusive_lazy_dhp.cpp +++ b/test/unit/list/intrusive_lazy_dhp.cpp @@ -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. */ #include "test_intrusive_list_hp.h" @@ -60,7 +60,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; @@ -166,6 +166,42 @@ namespace { test_hp( l ); } + TEST_F( IntrusiveLazyList_DHP, base_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_common::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveLazyList_DHP, base_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef intrusive_list_common::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + TEST_F( IntrusiveLazyList_DHP, member_hook ) { typedef ci::LazyList< gc_type, member_item, @@ -269,4 +305,41 @@ namespace { test_hp( l ); } + TEST_F( IntrusiveLazyList_DHP, member_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_common::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveLazyList_DHP, member_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_common::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/intrusive_lazy_hp.cpp b/test/unit/list/intrusive_lazy_hp.cpp index bddb5d4c..bf3d49b5 100644 --- a/test/unit/list/intrusive_lazy_hp.cpp +++ b/test/unit/list/intrusive_lazy_hp.cpp @@ -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. */ #include "test_intrusive_list_hp.h" @@ -167,6 +167,41 @@ namespace { test_hp( l ); } + TEST_F( IntrusiveLazyList_HP, base_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_common::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveLazyList_HP, base_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + TEST_F( IntrusiveLazyList_HP, member_hook ) { typedef ci::LazyList< gc_type, member_item, @@ -270,4 +305,39 @@ namespace { test_hp( l ); } + TEST_F( IntrusiveLazyList_HP, member_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_common::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveLazyList_HP, member_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/intrusive_lazy_nogc.cpp b/test/unit/list/intrusive_lazy_nogc.cpp index bd97556c..10039d1d 100644 --- a/test/unit/list/intrusive_lazy_nogc.cpp +++ b/test/unit/list/intrusive_lazy_nogc.cpp @@ -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. */ #include "test_intrusive_list_nogc.h" @@ -141,6 +141,40 @@ namespace { test_ordered_iterator( l ); } + TEST_F( IntrusiveLazyList_NOGC, base_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + } + TEST_F( IntrusiveLazyList_NOGC, member_hook ) { typedef ci::LazyList< gc_type, member_item, @@ -238,4 +272,38 @@ namespace { test_ordered_iterator( l ); } + TEST_F( IntrusiveLazyList_NOGC, member_hook_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_wrapped_stat ) + { + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + } + } // namespace diff --git a/test/unit/list/intrusive_michael_dhp.cpp b/test/unit/list/intrusive_michael_dhp.cpp index f828c3b2..cbc0d20e 100644 --- a/test/unit/list/intrusive_michael_dhp.cpp +++ b/test/unit/list/intrusive_michael_dhp.cpp @@ -57,7 +57,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; diff --git a/test/unit/list/kv_lazy_dhp.cpp b/test/unit/list/kv_lazy_dhp.cpp index 9b242974..38f72275 100644 --- a/test/unit/list/kv_lazy_dhp.cpp +++ b/test/unit/list/kv_lazy_dhp.cpp @@ -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. */ #include "test_kv_list_hp.h" @@ -49,7 +49,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; diff --git a/test/unit/list/kv_michael_dhp.cpp b/test/unit/list/kv_michael_dhp.cpp index ee2e490b..7a41833f 100644 --- a/test/unit/list/kv_michael_dhp.cpp +++ b/test/unit/list/kv_michael_dhp.cpp @@ -49,7 +49,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; diff --git a/test/unit/list/lazy_dhp.cpp b/test/unit/list/lazy_dhp.cpp index da84906f..7e381c3a 100644 --- a/test/unit/list/lazy_dhp.cpp +++ b/test/unit/list/lazy_dhp.cpp @@ -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. */ #include "test_list_hp.h" @@ -49,7 +49,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; diff --git a/test/unit/list/michael_dhp.cpp b/test/unit/list/michael_dhp.cpp index 65450e98..e2a16e51 100644 --- a/test/unit/list/michael_dhp.cpp +++ b/test/unit/list/michael_dhp.cpp @@ -49,7 +49,7 @@ namespace { void TearDown() { cds::threading::Manager::detachThread(); - cds::gc::hp::GarbageCollector::Destruct(); + cds::gc::dhp::GarbageCollector::Destruct(); } }; diff --git a/test/unit/list/test_intrusive_lazy_rcu.h b/test/unit/list/test_intrusive_lazy_rcu.h index 6dfe773f..f5ddc504 100644 --- a/test/unit/list/test_intrusive_lazy_rcu.h +++ b/test/unit/list/test_intrusive_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_LIST_TEST_INTRUSIVE_LAZY_LIST_RCU_H #define CDSUNIT_LIST_TEST_INTRUSIVE_LAZY_LIST_RCU_H @@ -144,6 +144,41 @@ TYPED_TEST_P( IntrusiveLazyList, base_hook_seqcst ) this->test_rcu( l ); } +TYPED_TEST_P( IntrusiveLazyList, base_hook_stat ) +{ + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< typename TestFixture::rcu_type >> hook; + typedef typename TestFixture::mock_disposer disposer; + typedef typename TestFixture::template cmp< typename TestFixture::base_item > compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< typename TestFixture::rcu_type, typename TestFixture::base_item, traits > list_type; + + list_type l; + this->test_common( l ); + this->test_ordered_iterator( l ); + this->test_rcu( l ); +} + +TYPED_TEST_P( IntrusiveLazyList, base_hook_wrapped_stat ) +{ + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< typename TestFixture::rcu_type >> hook; + typedef typename TestFixture::mock_disposer disposer; + typedef typename TestFixture::template cmp< typename TestFixture::base_item > compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< typename TestFixture::rcu_type, typename TestFixture::base_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + this->test_common( l ); + this->test_ordered_iterator( l ); + this->test_rcu( l ); +} + TYPED_TEST_P( IntrusiveLazyList, member_hook ) { typedef ci::LazyList< typename TestFixture::rcu_type, typename TestFixture::member_item, @@ -228,11 +263,46 @@ TYPED_TEST_P( IntrusiveLazyList, member_hook_back_off ) this->test_rcu( l ); } +TYPED_TEST_P( IntrusiveLazyList, member_hook_stat ) +{ + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( typename TestFixture::member_item, hMember ), cds::opt::gc< typename TestFixture::rcu_type >> hook; + typedef typename TestFixture::mock_disposer disposer; + typedef typename TestFixture::template cmp< typename TestFixture::member_item > compare; + typedef typename TestFixture::template less< typename TestFixture::member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::stat<> stat; + }; + typedef ci::LazyList< typename TestFixture::rcu_type, typename TestFixture::member_item, traits > list_type; + + list_type l; + this->test_common( l ); + this->test_ordered_iterator( l ); + this->test_rcu( l ); +} + +TYPED_TEST_P( IntrusiveLazyList, member_hook_wrapped_stat ) +{ + struct traits: public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( typename TestFixture::member_item, hMember ), cds::opt::gc< typename TestFixture::rcu_type >> hook; + typedef typename TestFixture::mock_disposer disposer; + typedef typename TestFixture::template cmp< typename TestFixture::member_item > compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::intrusive::lazy_list::wrapped_stat<> stat; + }; + typedef ci::LazyList< typename TestFixture::rcu_type, typename TestFixture::member_item, traits > list_type; + + cds::intrusive::lazy_list::stat<> st; + list_type l( st ); + this->test_common( l ); + this->test_ordered_iterator( l ); + this->test_rcu( l ); +} // 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( IntrusiveLazyList, - base_hook, base_hook_cmp, base_hook_item_counting, base_hook_backoff, base_hook_seqcst, member_hook, member_hook_cmp, member_hook_item_counting, member_hook_seqcst, member_hook_back_off + base_hook, base_hook_cmp, base_hook_item_counting, base_hook_backoff, base_hook_seqcst, base_hook_stat, base_hook_wrapped_stat, member_hook, member_hook_cmp, member_hook_item_counting, member_hook_seqcst, member_hook_back_off, member_hook_stat, member_hook_wrapped_stat ); -- 2.34.1