X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Ftreiber_stack.h;h=9ccaa87e6b02fd4f7ba9046f0d761cb6d5318289;hp=35c8a9bcc521737f296429bef946b4c45df7d624;hb=25f6df95be1521466e78b4db7a1bf34da590f41f;hpb=abe9634d97a9fece9abe5b0cfc78dc62f62f08c8 diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index 35c8a9bc..9ccaa87e 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -4,12 +4,11 @@ #define __CDS_INTRUSIVE_TREIBER_STACK_H #include -#include -#include +#include // unique_lock +#include #include #include #include -#include #include namespace cds { namespace intrusive { @@ -19,6 +18,48 @@ namespace cds { namespace intrusive { */ namespace treiber_stack { + /// Stack node + /** + Template parameters: + - GC - garbage collector used + - Tag - a \ref cds_intrusive_hook_tag "tag" + */ + template + using node = cds::intrusive::single_link::node< GC, Tag >; + + /// Base hook + /** + \p Options are: + - opt::gc - garbage collector used. + - opt::tag - a \ref cds_intrusive_hook_tag "tag" + */ + template < typename... Options > + using base_hook = cds::intrusive::single_link::base_hook< Options...>; + + /// Member hook + /** + \p MemberOffset specifies offset in bytes of \ref node member into your structure. + Use \p offsetof macro to define \p MemberOffset + + \p Options are: + - opt::gc - garbage collector used. + - opt::tag - a \ref cds_intrusive_hook_tag "tag" + */ + template < size_t MemberOffset, typename... Options > + using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >; + + /// Traits hook + /** + \p NodeTraits defines type traits for node. + See \ref node_traits for \p NodeTraits interface description + + \p Options are: + - opt::gc - garbage collector used. + - opt::tag - a \ref cds_intrusive_hook_tag "tag" + */ + template + using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >; + //@cond /// Operation id for the \ref cds_elimination_description "elimination back-off" enum operation_id { @@ -82,7 +123,10 @@ namespace cds { namespace intrusive { else ++m_PassivePopCollision; } - void onEliminationFailed() { ++m_EliminationFailed;} + void onEliminationFailed() + { + ++m_EliminationFailed; + } //@endcond }; @@ -100,6 +144,118 @@ namespace cds { namespace intrusive { //@endcond }; + /// TreiberStack default type traits + struct traits + { + /// Back-off strategy + typedef cds::backoff::Default back_off; + + /// Hook, possible types are \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook + typedef treiber_stack::base_hook<> hook; + + /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear() function + typedef opt::v::empty_disposer disposer; + + /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting + typedef cds::atomicity::empty_item_counter item_counter; + + /// 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). + */ + typedef opt::v::relaxed_ordering memory_model; + + /// Internal statistics (by default, disabled) + /** + 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. + */ + typedef treiber_stack::empty_stat stat; + + /// Link checking, see \p cds::opt::link_checker + static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link; + + /** @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 treiber_stack::traits + /** + Supported \p Options are: + - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook. + If the option is not specified, \p %treiber_stack::base_hook<> is used. + - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only + in \p TreiberStack::clear function. + - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link. + - 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, i.e. + no item counting. Use \p cds::atomicity::item_counter to enable item counting. + - 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. + + Example: declare \p %TreiberStack with elimination enabled and internal statistics + \code + typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, + typename cds::intrusive::treiber_stack::make_traits< + cds::opt::enable_elimination< true >, + cds::opt::stat< cds::intrusive::treiber_stack::stat<> > + >::type + > myStack; + \endcode + */ + 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< traits, Options... >::type + , Options... + >::type type; +# endif + }; + + //@cond namespace details { @@ -161,14 +317,6 @@ namespace cds { namespace intrusive { /// Operation descriptor used in elimination back-off typedef treiber_stack::operation< T > operation_desc; -# if !(defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)) - struct bkoff_predicate { - operation_desc * pOp; - bkoff_predicate( operation_desc * p ): pOp(p) {} - bool operator()() { return pOp->nStatus.load( atomics::memory_order_acquire ) != op_busy; } - }; -# endif - /// Elimination back-off data struct elimination_data { elimination_random_engine randEngine; ///< random engine @@ -191,7 +339,7 @@ namespace cds { namespace intrusive { op_collided = 2 }; - typedef cds::lock::scoped_lock< elimination_lock_type > slot_scoped_lock; + typedef std::unique_lock< elimination_lock_type > slot_scoped_lock; public: elimination_backoff() @@ -243,19 +391,7 @@ namespace cds { namespace intrusive { } // Wait for colliding operation -# if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10) - // MSVC++ 2010 compiler error C2065: 'op_busy' : undeclared identifier - bkoff( [&op]() -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } ); -# else - // Local structs is not supported by old compilers (for example, GCC 4.3) - //struct bkoff_predicate { - // operation_desc * pOp; - // bkoff_predicate( operation_desc * p ): pOp(p) {} - // bool operator()() { return pOp->nStatus.load( atomics::memory_order_acquire ) != op_busy; } - //}; - bkoff( bkoff_predicate(&op) ); -# endif - + bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } ); { slot_scoped_lock l( slot.lock ); if ( slot.pRec == myRec ) @@ -278,7 +414,7 @@ namespace cds { namespace intrusive { //@endcond } // namespace treiber_stack - /// Treiber stack + /// Treiber intrusive stack /** @ingroup cds_intrusive_stack Intrusive implementation of well-known Treiber's stack algorithm: - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986. @@ -298,54 +434,43 @@ namespace cds { namespace intrusive { This approach demonstrates sufficient performance under high load. Template arguments: - - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB - - \p T - type to be inserted into the stack - - \p Options - options - - \p Options are: - - opt::hook - hook used. Possible values are: single_link::base_hook, single_link::member_hook, single_link::traits_hook. - If the option is not specified, single_link::base_hook<> is used. - For Gidenstam's gc::HRC, only single_link::base_hook is supported. - - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used. - - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used only - in \ref clear function. - - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link. - Note: for gc::HRC garbage collector, link checking policy is always selected as \ref opt::always_check_link. - - 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 treiber_stack::stat, \ref 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. - - Garbage collecting schema \p GC must be consistent with the single_link::node GC. - - Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers". + - \p GC - garbage collector type: \p gc::HP, \p gc::DHP. + Garbage collecting schema must be the same as \p treiber_stack::node GC. + - \p T - a type the stack contains. A value of type \p T must be derived + from \p treiber_stack::node for \p treiber_stack::base_hook, + or it should have a member of type \p %treiber_stack::node for \p treiber_stack::member_hook, + or it should be convertible to \p %treiber_stack::node for \p treiber_stack::traits_hook. + - \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::intrusive::treiber_stack::traits { + typedef cds::intrusive::treiber_stack::stat<> stat; + }; + typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack; + + // Equivalent make_traits example: + typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, + typename cds::intrusive::treiber_stack::make_traits< + cds::opt::stat< cds::intrusive::treiber_stack::stat<> > + >::type + > myStack; + \endcode + + @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers". @anchor cds_intrusive_TreiberStack_examples \par Examples - Example of how to use \p single_link::base_hook. - Your class that objects will be pushed on \p %TreiberStack should be based on \p single_link::node class + Example of how to use \p treiber_stack::base_hook. + Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class \code - #include + #include #include namespace ci = cds::intrusive; typedef cds::gc::HP gc; - struct myData: public ci::single_link::node< gc > + struct myData: public ci::treiber_stack::node< gc > { // ... }; @@ -353,20 +478,24 @@ namespace cds { namespace intrusive { // Stack type typedef ci::TreiberStack< gc, myData, - ci::opt::hook< ci::single_link::base_hook< gc > > + typename cds::intrusive::treiber_stack::make_traits< + ci::opt::hook< ci::treiber_stack::base_hook< gc > > + >::type > stack_t; // Stack with elimination back-off enabled typedef ci::TreiberStack< gc, myData, - ci::opt::hook< ci::single_link::base_hook< gc > >, - cds::opt::enable_elimination + typename ci::treiber_stack::make_traits< + ci::opt::hook< ci::treiber_stack::base_hook< gc > >, + cds::opt::enable_elimination< true > + >::type > elimination_stack_t; \endcode - Example of how to use \p base_hook with different tags. + Example of how to use \p treiber_stack::base_hook with different tags. \code - #include + #include #include namespace ci = cds::intrusive; @@ -377,16 +506,27 @@ namespace cds { namespace intrusive { struct tag2; struct myData - : public ci::single_link::node< gc, tag1 > - , public ci::single_link::node< gc, tag2 > + : public ci::treiber_stack::node< gc, tag1 > + , public ci::treiber_stack::node< gc, tag2 > { // ... }; - typedef ci::TreiberStack< gc, myData, ci::opt::hook< ci::single_link::base_hook< gc, tag1 > > stack1_t; - typedef ci::TreiberStack< gc, myData, ci::opt::hook< ci::single_link::base_hook< gc, tag2 > > stack2_t; + typedef ci::TreiberStack< gc, + myData, + typename ci::treiber_stack::make_traits< + ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > > + >::type + > stack1_t; - // You may add myData objects in the objects of type stack1_t and stack2_t independently + typedef ci::TreiberStack< gc, + myData, + typename ci::treiber_stack::make_traits< + ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > > + >::type + > stack2_t; + + // You may add myData objects into stack1_t and stack2_t independently void foo() { stack1_t s1; stack2_t s2; @@ -406,12 +546,12 @@ namespace cds { namespace intrusive { } \endcode - Example of how to use \p member_hook. - Your class that will be pushed on \p %TreiberStack should have a member of type \p single_link::node + Example of how to use \p treiber_stack::member_hook. + Your class should have a member of type \p treiber_stack::node \code - #include - #include #include // offsetof macro + #include + #include namespace ci = cds::intrusive; typedef cds::gc::HP gc; @@ -419,92 +559,74 @@ namespace cds { namespace intrusive { struct myData { // ... - ci::single_link::node< gc > member_hook_; + ci::treiber_stack::node< gc > member_hook_; // ... }; - typedef ci::TreiberStack< gc, myData, - ci::opt::hook< - ci::single_link::member_hook< offsetof(myData, member_hook_), - gc - > + typedef ci::TreiberStack< gc, + myData, + typename ci::treiber_stack::make_traits< + ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >> + >::type > stack_t; \endcode */ - template + template < + typename GC, + typename T, + typename Traits = treiber_stack::traits + > class TreiberStack { - //@cond - struct default_options - { - typedef cds::backoff::Default back_off; - typedef single_link::base_hook<> hook; - typedef opt::v::empty_disposer disposer; - typedef atomicity::empty_item_counter item_counter; - typedef opt::v::relaxed_ordering memory_model; - typedef treiber_stack::empty_stat stat; - static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = opt::debug_check_link; - - // 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; - }; - //@endcond - - public: - //@cond - typedef typename opt::make_options< - typename cds::opt::find_type_traits< default_options, Options... >::type - ,Options... - >::type options; - //@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 ; ///< type of value stored in the stack - typedef typename options::hook hook ; ///< hook type - typedef typename hook::node_type node_type ; ///< node type - typedef typename options::disposer disposer ; ///< disposer used - typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits - typedef typename single_link::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker - typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option - typedef typename options::item_counter item_counter ; ///< Item counting policy used - typedef typename options::stat stat ; ///< Internal statistics policy used + typedef GC gc; ///< Garbage collector + typedef T value_type; ///< type of value stored in the stack + typedef Traits traits; ///< Stack traits - typedef GC gc ; ///< Garbage collector - typedef typename options::back_off back_off ; ///< back-off strategy + typedef typename traits::hook hook; ///< hook type + typedef typename hook::node_type node_type; ///< node type + typedef typename traits::disposer disposer; ///< disposer used + typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits + typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker ; ///< link checker + typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option + typedef typename traits::item_counter item_counter; ///< Item counter class + typedef typename traits::stat stat; ///< Internal statistics + typedef typename traits::back_off back_off; ///< back-off strategy public: // related to elimination back-off /// Elimination back-off is enabled or not - static CDS_CONSTEXPR_CONST bool enable_elimination = options::enable_elimination; + static CDS_CONSTEXPR const bool enable_elimination = traits::enable_elimination; /// back-off strategy used to wait for elimination - typedef typename options::elimination_backoff elimination_backoff_type; + typedef typename traits::elimination_backoff elimination_backoff_type; /// Lock type used in elimination back-off - typedef typename options::lock_type elimination_lock_type; + typedef typename traits::lock_type elimination_lock_type; /// Random engine used in elimination back-off - typedef typename options::random_engine elimination_random_engine; - + 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 - stat m_stat ; ///< Internal statistics + typename node_type::atomic_node_ptr m_Top; ///< Top of the stack + item_counter m_ItemCounter; ///< Item counter + stat m_stat; ///< Internal statistics //@cond - treiber_stack::details::elimination_backoff m_Backoff; + treiber_stack::details::elimination_backoff m_Backoff; typedef intrusive::node_to_value node_to_value; typedef treiber_stack::operation< value_type > operation_desc; + + // GC and node_type::gc must be the same + static_assert( std::is_same::value, "GC and node_type::gc must be the same"); + + static_assert( !enable_elimination || std::is_same::value, + "Random engine result type must be unsigned int"); //@endcond protected: @@ -516,34 +638,13 @@ namespace cds { namespace intrusive { template struct elimination_backoff_impl; - - void init() - { - // GC and node_type::gc must be the same - static_assert(( std::is_same::value ), "GC and node_type::gc must be the same"); - - // For cds::gc::HRC, only base_hook is allowed - static_assert(( - std::conditional< - std::is_same::value, - std::is_same< typename hook::hook_type, opt::base_hook_tag >, - boost::true_type - >::type::value - ), "For cds::gc::HRC, only base_hook is allowed"); - - static_assert( (!enable_elimination || std::is_same::value), - "Random engine result type must be unsigned int" ); - } - //@endcond public: /// Constructs empty stack TreiberStack() : m_Top( nullptr ) - { - init(); - } + {} /// Constructs empty stack and initializes elimination back-off data /** @@ -554,9 +655,10 @@ namespace cds { namespace intrusive { TreiberStack( size_t nCollisionCapacity ) : m_Top( nullptr ) , m_Backoff( nCollisionCapacity ) - { - init(); - } + {} + + /// \p %TreiberStack is not copy-constructible + TreiberStack( TreiberStack const& ) = delete; /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function ~TreiberStack() @@ -644,8 +746,7 @@ namespace cds { namespace intrusive { /** @anchor cds_intrusive_TreiberStack_clear For each removed item the disposer is called. - Caution - It is possible that after clear() the empty() returns \p false + @note It is possible that after clear() the empty() returns \p false if some other thread pushes an item into the stack during \p clear works */ void clear() @@ -676,7 +777,7 @@ namespace cds { namespace intrusive { The value returned depends on opt::item_counter option. For atomicity::empty_item_counter, this function always returns 0. - Warning: even if you use real item counter and it returns 0, this fact is not mean that the stack + @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack is empty. To check emptyness use \ref empty() method. */ size_t size() const