From 4c89a9724eef392097b48cf125d47a88e32ffd0b Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 3 Oct 2014 16:24:49 +0400 Subject: [PATCH] cds::container::TreiberStack refactoring --- cds/container/treiber_stack.h | 231 +++++++++++++++++++++------------- cds/intrusive/details/base.h | 17 ++- cds/intrusive/treiber_stack.h | 22 ++-- 3 files changed, 169 insertions(+), 101 deletions(-) diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h index 61afd976..37348aad 100644 --- a/cds/container/treiber_stack.h +++ b/cds/container/treiber_stack.h @@ -3,59 +3,136 @@ #ifndef __CDS_CONTAINER_TREIBER_STACK_H #define __CDS_CONTAINER_TREIBER_STACK_H -#include +#include // unique_ptr #include #include namespace cds { namespace container { - //@cond namespace treiber_stack { - using cds::intrusive::treiber_stack::stat; - using cds::intrusive::treiber_stack::empty_stat; + /// Internal statistics + template + using stat = cds::intrusive::treiber_stack::stat < Counter >; - template - struct make_treiber_stack + /// Dummy internal statistics + typedef cds::intrusive::treiber_stack::empty_stat empty_stat; + + /// TreiberStack default type traits + struct traits { - typedef T value_type; - - struct default_options { - typedef cds::backoff::Default back_off; - typedef CDS_DEFAULT_ALLOCATOR allocator; - typedef cds::opt::v::relaxed_ordering memory_model; - typedef cds::atomicity::empty_item_counter item_counter; - typedef empty_stat stat; - - // Elimination back-off options - static CDS_CONSTEXPR_CONST bool enable_elimination = false; - typedef cds::backoff::delay<> elimination_backoff; - typedef opt::v::static_buffer< int, 4 > buffer; - typedef opt::v::c_rand random_engine; - typedef cds::lock::Spin lock_type; - }; + /// Back-off strategy + typedef cds::backoff::Default back_off; + + /// Node allocator + typedef CDS_DEFAULT_ALLOCATOR allocator; + + /// C++ memory ordering model + /** + Can be opt::v::relaxed_ordering (relaxed memory model, the default) + or opt::v::sequential_consistent (sequentially consisnent memory model). + */ + typedef opt::v::relaxed_ordering memory_model; + + /// Item counting feature; by default, disabled + typedef cds::atomicity::empty_item_counter item_counter; + + /// Internal statistics (by default, no internal statistics) + /** + Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default), + user-provided class that supports treiber_stack::stat interface. + */ + typedef empty_stat stat; + + /** @name Elimination back-off traits + The following traits is used only if elimination enabled + */ + ///@{ + + /// Enable elimination back-off; by default, it is disabled + static CDS_CONSTEXPR_CONST bool enable_elimination = false; + + /// Back-off strategy to wait for elimination, default is cds::backoff::delay<> + typedef cds::backoff::delay<> elimination_backoff; + + /// Buffer type for elimination array + /** + Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. + The size should be selected empirically for your application and hardware, there are no common rules for that. + Default is %opt::v::static_buffer< any_type, 4 > . + */ + typedef opt::v::static_buffer< int, 4 > buffer; + + /// Random engine to generate a random position in elimination array + typedef opt::v::c_rand random_engine; + + /// Lock type used in elimination, default is cds::lock::Spin + typedef cds::lock::Spin lock_type; + + ///@} + }; + /// Metafunction converting option list to \p TreiberStack traits + /** + This is a wrapper for cds::opt::make_options< type_traits, Options...> + Supported \p Options are: + - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR + - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - 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). + - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter + - opt::stat - the type to gather internal statistics. + Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default), + user-provided class that supports \p treiber_stack::stat interface. + - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false. + + If elimination back-off is enabled, additional options can be specified: + - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. + The size should be selected empirically for your application and hardware, there are no common rules for that. + Default is %opt::v::static_buffer< any_type, 4 > . + - opt::random_engine - a random engine to generate a random position in elimination array. + Default is \p opt::v::c_rand. + - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> + - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin. + */ + template + struct make_traits { +# ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined type; ///< Metafunction result +# else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< default_options, Options... >::type - ,Options... - >::type options; + typename cds::opt::find_type_traits< traits, Options... >::type + , Options... + >::type type; +# endif + }; + } // namespace treiber_stack + //@cond + namespace details { + template + struct make_treiber_stack + { typedef GC gc; - typedef typename options::memory_model memory_model; + typedef T value_type; + typedef Traits traits; - struct node_type: public cds::intrusive::single_link::node< gc > + struct node_type: public cds::intrusive::treiber_stack::node< gc > { value_type m_value; node_type( const value_type& val ) : m_value( val ) {} + template node_type( Args&&... args ) - : m_value( std::forward(args)...) + : m_value( std::forward( args )... ) {} }; - typedef typename options::allocator::template rebind::other allocator_type; + typedef typename traits::allocator::template rebind::other allocator_type; typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator; struct node_deallocator @@ -66,26 +143,18 @@ namespace cds { namespace container { } }; - typedef intrusive::TreiberStack< - gc - ,node_type - ,intrusive::opt::hook< - intrusive::single_link::base_hook< cds::opt::gc > - > - ,cds::opt::back_off< typename options::back_off > - ,cds::intrusive::opt::disposer< node_deallocator > - ,cds::opt::memory_model< memory_model > - ,cds::opt::item_counter< typename options::item_counter > - ,cds::opt::stat< typename options::stat > - ,cds::opt::enable_elimination< options::enable_elimination > - ,cds::opt::buffer< typename options::buffer > - ,cds::opt::random_engine< typename options::random_engine > - ,cds::opt::elimination_backoff< typename options::elimination_backoff > - ,cds::opt::lock_type< typename options::lock_type > - > type; + struct intrusive_traits: public traits + { + typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc > hook; + typedef node_deallocator disposer; + static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker; + }; + + // Result of metafunction + typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type; }; - } // namespace treiber_stack - //@endcond + } // namespace details + //@endecond /// Treiber's stack algorithm /** @ingroup cds_nonintrusive_stack @@ -95,65 +164,54 @@ namespace cds { namespace container { Template arguments: - \p GC - garbage collector type: gc::HP, gc::PTB - \p T - type stored in the stack. It should be default-constructible, copy-constructible, assignable type. - - \p Options - options - - Available \p Options: - - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR - - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used - - 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). - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter - - opt::stat - the type to gather internal statistics. - Possible option value are: \ref cds::intrusive::treiber_stack::stat "treiber_stack::stat", - \ref cds::intrusive::treiber_stack::empty_stat "treiber_stack::empty_stat" (the default), - user-provided class that supports treiber_stack::stat interface. - - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p valse. - - If elimination back-off is enabled (\p %cds::opt::enable_elimination< true >) additional options can be specified: - - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer. - The buffer can be any size: \p Exp2 template parameter of those classes can be \p false. - The size should be selected empirically for your application and hardware, there are no common rules for that. - Default is %opt::v::static_buffer< any_type, 4 > . - - opt::random_engine - a random engine to generate a random position in elimination array. - Default is opt::v::c_rand. - - opt::elimination_backoff - back-off strategy to wait for elimination, default is cds::backoff::delay<> - - opt::lock_type - a lock type used in elimination back-off, default is cds::lock::Spin. + - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits + metafunction to make your traits or just derive your traits from \p %treiber_stack::traits: + \code + struct myTraits: public cds::container::treiber_stack::traits { + typedef cds::container::treiber_stack::stat<> stat; + }; + typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack; + \endcode */ - template < typename GC, typename T, typename... Options > + template < + typename GC, + typename T, + typename Traits = treiber_stack::traits + > class TreiberStack : public #ifdef CDS_DOXYGEN_INVOKED - intrusive::TreiberStack< GC, cds::intrusive::single_link::node< T >, Options... > + intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits > #else - treiber_stack::make_treiber_stack< GC, T, Options... >::type + details::make_treiber_stack< GC, T, Traits >::type #endif { //@cond - typedef treiber_stack::make_treiber_stack< GC, T, Options... > options; - typedef typename options::type base_class; + typedef details::make_treiber_stack< GC, T, Traits > maker; + typedef typename maker::type base_class; //@endcond public: /// Rebind template arguments - template + template struct rebind { - typedef TreiberStack< GC2, T2, Options2...> other ; ///< Rebinding result + typedef TreiberStack< GC2, T2, Traits2> other ; ///< Rebinding result }; public: typedef T value_type ; ///< Value type stored in the stack - typedef typename base_class::gc gc ; ///< Garbage collector used - typedef typename base_class::back_off back_off ; ///< Back-off strategy used - typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes - typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_order option - typedef typename base_class::stat stat ; ///< Internal statistics policy used + typedef typename base_class::gc gc ; ///< Garbage collector used + typedef typename base_class::back_off back_off ; ///< Back-off strategy used + typedef typename maker::allocator_type allocator_type ; ///< Allocator type used for allocating/deallocating the nodes + typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_order option + typedef typename base_class::stat stat ; ///< Internal statistics policy used protected: - typedef typename options::node_type node_type ; ///< stack node type (derived from intrusive::single_link::node) + typedef typename maker::node_type node_type ; ///< stack node type (derived from intrusive::treiber_stack::node) //@cond - typedef typename options::cxx_allocator cxx_allocator; - typedef typename options::node_deallocator node_deallocator; // deallocate node + typedef typename maker::cxx_allocator cxx_allocator; + typedef typename maker::node_deallocator node_deallocator; //@endcond protected: @@ -201,6 +259,7 @@ namespace cds { namespace container { : base_class( nCollisionCapacity ) {} + /// \p %TreiberStack is not copy-constructible TreiberStack( TreiberStack const& ) = delete; /// Clears the stack on destruction diff --git a/cds/intrusive/details/base.h b/cds/intrusive/details/base.h index 68c1449c..73c653de 100644 --- a/cds/intrusive/details/base.h +++ b/cds/intrusive/details/base.h @@ -14,16 +14,24 @@ namespace cds { @ingroup cds_intrusive_containers The namespace cds::intrusive contains intrusive lock-free containers. The idea comes from \p boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach. - The intrusive containers of libcds library is developed as close to boost::intrusive + The intrusive containers of libcds library is developed as close to \p boost::intrusive In terms of lock-free approach, the main advantage of intrusive containers is that no memory allocation is performed to maintain container items. However, additional requirements is imposed for types and values that can be stored in intrusive container. See the container documentation for details. - Restriction for Gidenstam's garbage collector cds::gc::HRC: - the Gidenstam's garbage collector makes additional requirements to type of item in intrusive container. - Therefore, for this GC only \p base_hook is allowed as the value of opt::hook option. + \anchor cds_intrusive_hook_tag + \par Tags + Many hooks and nodes for intrusive containers contain template argument \p Tag. + This argument serves as a tag, so you can derive from more than one container's node and hence put an object in multiple intrusive containers + at the same time. An incomplete type can serve as a tag. If you specify two hooks, you must specify a different tag for each one. + Example: + \code + struct tag1; + cds::intrusive::treiber_stack::node< cds::gc::HP, tag > + \endcode + If no tag is specified åðó default \p cds::opt::none will be used. \anchor cds_intrusive_item_destroying \par Destroying items @@ -125,7 +133,6 @@ namespace cds { for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node you should convert it to the pointer to the item and then protect resulting item pointer. Otherwise an unpredictable result may occur. - */ namespace intrusive { diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index de04aae1..d82c9576 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -23,7 +23,7 @@ namespace cds { namespace intrusive { /** Template parameters: - GC - garbage collector used - - Tag - a tag used to distinguish between different type + - Tag - this argument serves as \ref cds_intrusive_hook_tag "a tag" */ template using node = cds::intrusive::single_link::node< GC, Tag > ; @@ -32,7 +32,7 @@ namespace cds { namespace intrusive { /** \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - \ref cds_intrusive_hook_tag "a tag" */ template < typename... Options > using base_hook = cds::intrusive::single_link::base_hook< Options...>; @@ -44,7 +44,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - \ref cds_intrusive_hook_tag "a tag" */ template < size_t MemberOffset, typename... Options > using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >; @@ -56,7 +56,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - \ref cds_intrusive_hook_tag "a tag" */ template using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >; @@ -146,7 +146,7 @@ namespace cds { namespace intrusive { struct traits { /// Back-off strategy - typedef cds::backoff::Default back_off; + typedef cds::backoff::Default back_off; /// Hook, possible types are treiber_stack::base_hook, treiber_stack::member_hook, treiber_stack::traits_hook typedef treiber_stack::base_hook<> hook; @@ -548,7 +548,11 @@ namespace cds { namespace intrusive { > stack_t; \endcode */ - template + template < + typename GC, + typename T, + typename Traits = treiber_stack::traits + > class TreiberStack { public: @@ -559,7 +563,7 @@ namespace cds { namespace intrusive { }; public: - typedef GC gc; ///< Garbage collector + typedef GC gc; ///< Garbage collector typedef T value_type; ///< type of value stored in the stack typedef Traits traits; ///< Stack traits @@ -584,7 +588,6 @@ namespace cds { namespace intrusive { /// Random engine used in elimination back-off typedef typename traits::random_engine elimination_random_engine; - protected: typename node_type::atomic_node_ptr m_Top; ///< Top of the stack item_counter m_ItemCounter; ///< Item counter @@ -615,7 +618,6 @@ namespace cds { namespace intrusive { static_assert( (!enable_elimination || std::is_same::value), "Random engine result type must be unsigned int" ); } - //@endcond public: @@ -639,7 +641,7 @@ namespace cds { namespace intrusive { init(); } - /// %TreiberStack is not copy-constructible + /// \p %TreiberStack is not copy-constructible TreiberStack( TreiberStack const& ) = delete; /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function -- 2.34.1