X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Ftreiber_stack.h;h=0678d9a19ad48e0b0183c77c2f20c79fa60d1b7e;hb=6d68de6d1598f3abac6b562816af12cb2d2bf1ad;hp=dfb549d53cfe8811dc5a045eddc91dd3078d81ce;hpb=2e8a58841ca3d7cc736cc9483b691cf70c3ecdb3;p=libcds.git diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index dfb549d5..0678d9a1 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -1,15 +1,42 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_INTRUSIVE_TREIBER_STACK_H -#define __CDS_INTRUSIVE_TREIBER_STACK_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + 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_TREIBER_STACK_H +#define CDSLIB_INTRUSIVE_TREIBER_STACK_H #include -#include -#include +#include // unique_lock +#include #include #include -#include -#include +#include #include namespace cds { namespace intrusive { @@ -19,6 +46,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 { @@ -32,11 +101,11 @@ namespace cds { namespace intrusive { { operation_id idOp; ///< Op id T * pVal; ///< for push: pointer to argument; for pop: accepts a return value - CDS_ATOMIC::atomic nStatus; ///< Internal elimination status + atomics::atomic nStatus; ///< Internal elimination status operation() : pVal( nullptr ) - , nStatus(0) + , nStatus( 0 /*op_free*/ ) {} }; //@endcond @@ -82,7 +151,10 @@ namespace cds { namespace intrusive { else ++m_PassivePopCollision; } - void onEliminationFailed() { ++m_EliminationFailed;} + void onEliminationFailed() + { + ++m_EliminationFailed; + } //@endcond }; @@ -100,6 +172,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 \p cds::backoff::delay<> + typedef cds::backoff::delay<> elimination_backoff; + + /// Buffer type for elimination array + /** + Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_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::initialized_static_buffer< any_type, 4 > . + */ + typedef opt::v::initialized_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::sync::spin + typedef cds::sync::spin lock_type; + + ///@} + }; + + /// Metafunction converting option list to \p treiber_stack::traits + /** + Supported \p Options are: + - \p 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. + - \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 dispose removed items. Default is \p opt::v::empty_disposer. This option is used only + in \p TreiberStack::clear function. + - \p opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link. + - \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::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. + - \p 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. + - \p 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: + - \p opt::buffer - a buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_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::initialized_static_buffer< any_type, 4 > . + - \p opt::random_engine - a random engine to generate a random position in elimination array. + Default is \p opt::v::c_rand. + - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<> + - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::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 { @@ -111,7 +295,23 @@ namespace cds { namespace intrusive { { typedef typename Traits::back_off back_off; - back_off m_bkoff; + struct wrapper + { + back_off m_bkoff; + + void reset() + { + m_bkoff.reset(); + } + + template + bool backoff( treiber_stack::operation< T >&, Stat& ) + { + m_bkoff(); + return false; + } + }; + public: elimination_backoff() {} @@ -119,16 +319,10 @@ namespace cds { namespace intrusive { elimination_backoff( size_t ) {} - void reset() - { - m_bkoff.reset(); - } - - template - bool backoff(treiber_stack::operation< T >&, Stat& ) + typedef wrapper type; + type init() { - m_bkoff(); - return false; + return wrapper(); } }; @@ -161,18 +355,10 @@ 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( CDS_ATOMIC::memory_order_acquire ) != op_busy; } - }; -# endif - /// Elimination back-off data struct elimination_data { - elimination_random_engine randEngine; ///< random engine - collision_array collisions; ///< collision array + mutable elimination_random_engine randEngine; ///< random engine + collision_array collisions; ///< collision array elimination_data() { @@ -187,11 +373,23 @@ namespace cds { namespace intrusive { enum operation_status { op_free = 0, - op_busy = 1, + op_waiting = 1, op_collided = 2 }; - typedef cds::lock::scoped_lock< elimination_lock_type > slot_scoped_lock; + typedef std::unique_lock< elimination_lock_type > slot_scoped_lock; + + template + typename std::enable_if< Exp2, size_t >::type slot_index() const + { + return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1); + } + + template + typename std::enable_if< !Exp2, size_t >::type slot_index() const + { + return m_Elimination.randEngine() % m_Elimination.collisions.capacity(); + } public: elimination_backoff() @@ -205,6 +403,13 @@ namespace cds { namespace intrusive { m_Elimination.collisions.zeroize(); } + typedef elimination_backoff& type; + + type init() + { + return *this; + } + void reset() {} @@ -212,11 +417,11 @@ namespace cds { namespace intrusive { bool backoff( operation_desc& op, Stat& stat ) { elimination_backoff_type bkoff; - op.nStatus.store( op_busy, CDS_ATOMIC::memory_order_relaxed ); + op.nStatus.store( op_waiting, atomics::memory_order_relaxed ); elimination_rec * myRec = cds::algo::elimination::init_record( op ); - collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()]; + collision_array_record& slot = m_Elimination.collisions[ slot_index() ]; { slot.lock.lock(); elimination_rec * himRec = slot.pRec; @@ -224,37 +429,28 @@ namespace cds { namespace intrusive { operation_desc * himOp = static_cast( himRec->pOp ); assert( himOp ); if ( himOp->idOp != op.idOp ) { + if ( op.idOp == treiber_stack::op_push ) himOp->pVal = op.pVal; else op.pVal = himOp->pVal; + slot.pRec = nullptr; + himOp->nStatus.store( op_collided, atomics::memory_order_release ); slot.lock.unlock(); - himOp->nStatus.store( op_collided, CDS_ATOMIC::memory_order_release ); cds::algo::elimination::clear_record(); stat.onActiveCollision( op.idOp ); return true; } - himOp->nStatus.store( op_free, CDS_ATOMIC::memory_order_release ); + //himOp->nStatus.store( op_free, atomics::memory_order_release ); } slot.pRec = myRec; slot.lock.unlock(); } // 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( CDS_ATOMIC::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( CDS_ATOMIC::memory_order_acquire ) != op_busy; } - //}; - bkoff( bkoff_predicate(&op) ); -# endif + bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_waiting; } ); { slot_scoped_lock l( slot.lock ); @@ -262,7 +458,7 @@ namespace cds { namespace intrusive { slot.pRec = nullptr; } - bool bCollided = op.nStatus.load( CDS_ATOMIC::memory_order_acquire ) == op_collided; + bool bCollided = op.nStatus.load( atomics::memory_order_relaxed ) == op_collided; if ( !bCollided ) stat.onEliminationFailed(); @@ -278,7 +474,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. @@ -293,59 +489,48 @@ namespace cds { namespace intrusive { @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex. The main difficulty is the managing life-time of elimination record. - Our implementation uses simplified lock-based (spin-based) approach which allows + This implementation uses simplified lock-based (spin-based) approach which allows the elimination record allocation on thread's stack. 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 +538,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 +566,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; + + 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 in the objects of type stack1_t and stack2_t independently + // You may add myData objects into stack1_t and stack2_t independently void foo() { stack1_t s1; stack2_t s2; @@ -406,12 +606,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 +619,77 @@ 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, CDS_OPTIONS13 >::type - ,CDS_OPTIONS13 - >::type options; - //@endcond - public: /// Rebind template arguments - template + template struct rebind { - typedef TreiberStack< GC2, T2, CDS_OTHER_OPTIONS13> 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 GC gc; ///< Garbage collector + typedef T value_type; ///< type of value stored in the stack + typedef Traits traits; ///< Stack traits + + 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, 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 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 - typedef GC gc ; ///< Garbage collector - typedef typename options::back_off back_off ; ///< back-off strategy + /// How many Hazard pointers is required for Treiber's stack implementation + static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1; 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; + typedef treiber_stack::details::elimination_backoff elimination_backoff; + 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,47 +701,27 @@ 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 /** This form should be used if you use elimination back-off with dynamically allocated collision array, i.e - \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >. + \p Traits contains typedef cds::opt::v::initialized_dynamic_buffer buffer. \p nCollisionCapacity parameter specifies the capacity of collision array. */ 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() @@ -573,7 +738,7 @@ namespace cds { namespace intrusive { node_type * pNew = node_traits::to_node_ptr( val ); link_checker::is_empty( pNew ); - m_Backoff.reset(); + typename elimination_backoff::type bkoff = m_Backoff.init(); operation_desc op; if ( enable_elimination ) { @@ -581,17 +746,17 @@ namespace cds { namespace intrusive { op.pVal = &val; } - node_type * t = m_Top.load(memory_model::memory_order_relaxed); + node_type * t = m_Top.load( memory_model::memory_order_relaxed ); while ( true ) { pNew->m_pNext.store( t, memory_model::memory_order_relaxed ); - if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) { // #1 sync-with #2 + if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_acquire )) { ++m_ItemCounter; m_stat.onPush(); return true; } m_stat.onPushRace(); - if ( m_Backoff.backoff( op, m_stat )) + if ( bkoff.backoff( op, m_stat )) return true; } } @@ -604,7 +769,7 @@ namespace cds { namespace intrusive { */ value_type * pop() { - m_Backoff.reset(); + typename elimination_backoff::type bkoff = m_Backoff.init(); typename gc::Guard guard; operation_desc op; @@ -613,12 +778,15 @@ namespace cds { namespace intrusive { } while ( true ) { - node_type * t = guard.protect( m_Top, node_to_value() ); + node_type * t = guard.protect( m_Top, + []( node_type * p ) -> value_type * { + return node_traits::to_value_ptr( p ); + }); if ( t == nullptr ) return nullptr; // stack is empty node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed); - if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed )) { // #2 + if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { clear_links( t ); --m_ItemCounter; m_stat.onPop(); @@ -626,7 +794,7 @@ namespace cds { namespace intrusive { } m_stat.onPopRace(); - if ( m_Backoff.backoff( op, m_stat )) { + if ( bkoff.backoff( op, m_stat )) { // may return nullptr if stack is empty return op.pVal; } @@ -636,7 +804,6 @@ namespace cds { namespace intrusive { /// Check if stack is empty bool empty() const { - // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0 return m_Top.load( memory_model::memory_order_relaxed ) == nullptr; } @@ -644,8 +811,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() @@ -656,7 +822,7 @@ namespace cds { namespace intrusive { pTop = m_Top.load( memory_model::memory_order_relaxed ); if ( pTop == nullptr ) return; - if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed ) ) { // sync-with #1 and #2 + if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { m_ItemCounter.reset(); break; } @@ -667,7 +833,7 @@ namespace cds { namespace intrusive { node_type * p = pTop; pTop = p->m_pNext.load(memory_model::memory_order_relaxed); clear_links( p ); - gc::template retire( node_traits::to_value_ptr( *p ) ); + gc::template retire( node_traits::to_value_ptr( *p )); } } @@ -676,7 +842,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 @@ -693,4 +859,4 @@ namespace cds { namespace intrusive { }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H +#endif // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H