X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fdetails%2Fmichael_list_base.h;h=6b68442db1993fb45b596618e1321ecbac19d40f;hp=bd556f3a2f22f2cc6cae291608905b5cf62b901f;hb=f78b1cf121bf6e06c848c96641ff7366b95aafa4;hpb=1503681e52c392bee2329cf66c910be0f8640105 diff --git a/cds/intrusive/details/michael_list_base.h b/cds/intrusive/details/michael_list_base.h index bd556f3a..6b68442d 100644 --- a/cds/intrusive/details/michael_list_base.h +++ b/cds/intrusive/details/michael_list_base.h @@ -1,15 +1,41 @@ -//$$CDS-header$$ - -#ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H -#define __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + 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: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + 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. +*/ + +#ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H +#define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H #include -#include // ref #include #include -#include +#include #include -#include #include namespace cds { namespace intrusive { @@ -21,8 +47,8 @@ namespace cds { namespace intrusive { /// Michael's list node /** Template parameters: - - GC - garbage collector - - Tag - a tag used to distinguish between different implementation + - \p GC - garbage collector + - \p Tag - a \ref cds_intrusive_hook_tag "tag" */ template struct node @@ -30,8 +56,8 @@ namespace cds { namespace intrusive { typedef GC gc ; ///< Garbage collector typedef Tag tag ; ///< tag - typedef cds::details::marked_ptr marked_ptr ; ///< marked pointer - typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC + typedef cds::details::marked_ptr marked_ptr; ///< marked pointer + typedef typename gc::template atomic_marked_ptr atomic_marked_ptr; ///< atomic marked pointer specific for GC atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container @@ -75,7 +101,7 @@ namespace cds { namespace intrusive { /** \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < typename... Options > struct base_hook: public hook< opt::base_hook_tag, Options... > @@ -88,7 +114,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < size_t MemberOffset, typename... Options > struct member_hook: public hook< opt::member_hook_tag, Options... > @@ -105,7 +131,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template struct traits_hook: public hook< opt::traits_hook_tag, Options... > @@ -115,7 +141,7 @@ namespace cds { namespace intrusive { //@endcond }; - /// Check link + /// Checks link template struct link_checker { @@ -130,6 +156,7 @@ namespace cds { namespace intrusive { static void is_empty( const node_type * pNode ) { assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr ); + CDS_UNUSED( pNode ); } }; @@ -169,12 +196,107 @@ namespace cds { namespace intrusive { //@endcond }; - /// Type traits for MichaelList class - struct type_traits + + /// \p MichaelList 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_nHelpingSuccess; ///< Number of successful help attempts to remove marked item during searching + event_counter m_nHelpingFailed; ///< Number if failed help attempts to remove marked item during searching + + //@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 onHelpingSuccess() { ++m_nHelpingSuccess; } + void onHelpingFailed() { ++m_nHelpingFailed; } + //@endcond + }; + + /// \p MichaelList 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 onHelpingSuccess() const {} + void onHelpingFailed() 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 onHelpingSuccess() { m_stat.onHelpingSuccess(); } + void onHelpingFailed() { m_stat.onHelpingFailed(); } + + stat_type& m_stat; + }; + //@endcond + + /// MichaelList traits + struct traits { /// Hook used /** - Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook. + Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook. */ typedef base_hook<> hook; @@ -184,54 +306,68 @@ namespace cds { namespace intrusive { */ typedef opt::none compare; - /// specifies binary predicate used for key compare. + /// Specifies binary predicate used for key compare. /** Default is \p std::less. */ typedef opt::none less; - /// back-off strategy used - /** - If the option is not specified, the cds::backoff::Default is used. - */ + /// Back-off strategy typedef cds::backoff::Default back_off; - /// Disposer - /** - the functor used for dispose removed items. Default is opt::v::empty_disposer. - */ + /// Disposer for removing items typedef opt::v::empty_disposer disposer; - /// Item counter + /// 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 /** - The type for item counting feature. - Default is no item counter (\ref atomicity::empty_item_counter) + By default, internal statistics is disabled (\p michael_list::empty_stat). + Use \p michael_list::stat to enable it. */ - typedef atomicity::empty_item_counter item_counter; + typedef empty_stat stat; /// Link fields checking feature /** - Default is \ref opt::debug_check_link + Default is \p opt::debug_check_link */ static const opt::link_check_type link_checker = opt::debug_check_link; /// C++ memory ordering model /** - List of available memory ordering see opt::memory_model + Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + or \p opt::v::sequential_consistent (sequentially consisnent memory model). */ typedef opt::v::relaxed_ordering memory_model; /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList") /** - List of available options see opt::rcu_check_deadlock + List of available policy see \p opt::rcu_check_deadlock */ typedef opt::v::rcu_throw_deadlock rcu_check_deadlock; }; - /// Metafunction converting option list to traits + /// Metafunction converting option list to \p michael_list::traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \p Options list see \ref MichaelList. + Supported \p Options are: + - \p opt::hook - hook used. Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook. + If the option is not specified, \p %michael_list::base_hook<> and \p gc::HP is used. + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature + of GC schema the disposer may be called asynchronously. + - \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 michael_list::empty_stat). + To enable it use \p michael_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 consistent memory model). + - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList" + Default is \p opt::v::rcu_throw_deadlock */ template struct make_traits { @@ -239,10 +375,9 @@ namespace cds { namespace intrusive { typedef implementation_defined type ; ///< Metafunction result # else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< type_traits, Options... >::type + typename cds::opt::find_type_traits< traits, Options... >::type ,Options... >::type type; - //typedef typename cds::opt::make_options< type_traits, Options...>::type type ; ///< Result of metafunction # endif }; @@ -250,14 +385,27 @@ namespace cds { namespace intrusive { //@cond // Forward declaration - template < class GC, typename T, class Traits = michael_list::type_traits > + template < class GC, typename T, class Traits = michael_list::traits > class MichaelList; //@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 -#endif // #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H +#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H