#define __CDS_INTRUSIVE_TREIBER_STACK_H
#include <type_traits>
+#include <mutex> // unique_lock
#include <cds/intrusive/details/single_link_struct.h>
-#include <cds/ref.h>
#include <cds/algo/elimination.h>
#include <cds/opt/buffer.h>
#include <cds/lock/spinlock.h>
-#include <cds/lock/scoped_lock.h>
#include <cds/details/type_padding.h>
namespace cds { namespace intrusive {
*/
namespace treiber_stack {
+ /// Stack node
+ /**
+ Template parameters:
+ - GC - garbage collector used
+ - Tag - a \ref cds_intrusive_hook_tag "tag"
+ */
+ template <class GC, typename Tag = opt::none >
+ 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 <typename NodeTraits, typename... Options >
+ 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 {
else
++m_PassivePopCollision;
}
- void onEliminationFailed() { ++m_EliminationFailed;}
+ void onEliminationFailed()
+ {
+ ++m_EliminationFailed;
+ }
//@endcond
};
//@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 <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
+ */
+ 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 <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
+ - 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 <typename... Options>
+ 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 {
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()
}
// Wait for colliding operation
- bkoff( [&op]() -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
+ 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 )
//@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.
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, <tt>single_link::base_hook<></tt> 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 <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
- - 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 <cds/intrusive/stack/treiber_stack.h>
+ #include <cds/intrusive/treiber_stack.h>
#include <cds/gc/hp.h>
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 >
{
// ...
};
// 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<true>
+ 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 <cds/intrusive/stack/treiber_stack.h>
+ #include <cds/intrusive/treiber_stack.h>
#include <cds/gc/hp.h>
namespace ci = cds::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;
}
\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 <cds/intrusive/stack/treiber_stack.h>
- #include <cds/gc/hp.h>
#include <stddef.h> // offsetof macro
+ #include <cds/intrusive/treiber_stack.h>
+ #include <cds/gc/hp.h>
namespace ci = cds::intrusive;
typedef cds::gc::HP gc;
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 <typename GC, typename T, typename... Options>
+ 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 <typename GC2, typename T2, typename... Options2>
+ template <typename GC2, typename T2, typename Traits2>
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<enable_elimination, value_type, options> m_Backoff;
+ treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
typedef intrusive::node_to_value<TreiberStack> 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<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
+
+ static_assert( !enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value,
+ "Random engine result type must be unsigned int");
//@endcond
protected:
template <bool EnableElimination>
struct elimination_backoff_impl;
-
- void init()
- {
- // GC and node_type::gc must be the same
- static_assert(( std::is_same<gc, typename node_type::gc>::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<gc, cds::gc::HRC>::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<typename elimination_random_engine::result_type, unsigned int>::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
/**
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()
/** @anchor cds_intrusive_TreiberStack_clear
For each removed item the disposer is called.
- <b>Caution</b>
- It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
+ @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
if some other thread pushes an item into the stack during \p clear works
*/
void clear()
The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
this function always returns 0.
- <b>Warning</b>: 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
projects / libcds.git / blobdiff