//$$CDS-header$$
-#ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
-#define __CDS_INTRUSIVE_TREIBER_STACK_H
+#ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
+#define CDSLIB_INTRUSIVE_TREIBER_STACK_H
#include <type_traits>
-#include <functional> // ref
#include <mutex> // unique_lock
#include <cds/intrusive/details/single_link_struct.h>
#include <cds/algo/elimination.h>
#include <cds/opt/buffer.h>
-#include <cds/lock/spinlock.h>
+#include <cds/sync/spinlock.h>
#include <cds/details/type_padding.h>
namespace cds { namespace intrusive {
/**
Template parameters:
- GC - garbage collector used
- - Tag - a tag used to distinguish between different type
+ - Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <class GC, typename Tag = opt::none >
- using node = cds::intrusive::single_link::node< GC, Tag > ;
+ using node = cds::intrusive::single_link::node< GC, Tag >;
/// Base hook
/**
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
template < typename... Options >
using base_hook = cds::intrusive::single_link::base_hook< Options...>;
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
template < size_t MemberOffset, typename... Options >
using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - 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... >;
operation()
: pVal( nullptr )
- , nStatus(0)
- {}
+ {
+ nStatus.store( 0 /*op_free*/, atomics::memory_order_release );
+ }
};
//@endcond
else
++m_PassivePopCollision;
}
- void onEliminationFailed() { ++m_EliminationFailed;}
+ void onEliminationFailed()
+ {
+ ++m_EliminationFailed;
+ }
//@endcond
};
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
+ /// 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 opt::v::empty_disposer. This option is used only in \ref TreiberStack::clear function
+ /// 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
- typedef cds::atomicity::empty_item_counter item_counter;
+ /// 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 opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
+ /**
+ Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
*/
typedef opt::v::relaxed_ordering memory_model;
- /// Internal statistics (by default, no internal statistics)
+ /// Internal statistics (by default, disabled)
/**
- Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
- user-provided class that supports treiber_stack::stat interface.
+ 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 cds::opt::link_checker
- static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = opt::debug_check_link;
+ /// 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;
+ 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;
/// 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;
+ /// Lock type used in elimination, default is cds::sync::spin
+ typedef cds::sync::spin lock_type;
///@}
};
- /// Metafunction converting option list to \p TreiberStack traits
+ /// Metafunction converting option list to \p treiber_stack::traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
Supported \p Options are:
-
- - opt::hook - hook used. Possible values are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
+ - 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
- 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
+ - 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::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.
+ - 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 <typename... Options>
struct make_traits {
{
typedef typename Traits::back_off back_off;
- back_off m_bkoff;
+ struct wrapper
+ {
+ back_off m_bkoff;
+
+ void reset()
+ {
+ m_bkoff.reset();
+ }
+
+ template <typename Stat>
+ bool backoff( treiber_stack::operation< T >&, Stat& )
+ {
+ m_bkoff();
+ return false;
+ }
+ };
+
public:
elimination_backoff()
{}
elimination_backoff( size_t )
{}
- void reset()
+ typedef wrapper type;
+ type init()
{
- m_bkoff.reset();
- }
-
- template <typename Stat>
- bool backoff(treiber_stack::operation< T >&, Stat& )
- {
- m_bkoff();
- return false;
+ return wrapper();
}
};
/// 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()
{
typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
+ }
+
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< !Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
+ }
+
public:
elimination_backoff()
{
m_Elimination.collisions.zeroize();
}
+ typedef elimination_backoff& type;
+
+ type init()
+ {
+ return *this;
+ }
+
void reset()
{}
bool backoff( operation_desc& op, Stat& stat )
{
elimination_backoff_type bkoff;
- op.nStatus.store( op_busy, atomics::memory_order_relaxed );
+ op.nStatus.store( op_busy, atomics::memory_order_release );
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;
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, atomics::memory_order_release );
cds::algo::elimination::clear_record();
stat.onActiveCollision( op.idOp );
return true;
}
// 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::PTB.
- Garbage collecting schema must be consistent with the treiber_stack::node GC.
- - \p T - type to be inserted into the stack
+ - \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
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".
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;
// Stack type
typedef ci::TreiberStack< gc,
myData,
- ci::opt::hook< ci::treiber_stack::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,
- typename ci::treiber_stack::make_traits<
+ typename ci::treiber_stack::make_traits<
ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
cds::opt::enable_elimination< true >
>::type
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;
// ...
};
- typedef ci::TreiberStack< gc,
- myData,
- typename ci::treiber_stack::make_traits<
+ typedef ci::TreiberStack< gc,
+ myData,
+ typename ci::treiber_stack::make_traits<
ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
- >::type
+ >::type
> stack1_t;
- typedef ci::TreiberStack< gc,
- myData,
+ typedef ci::TreiberStack< gc,
+ myData,
typename ci::treiber_stack::make_traits<
- ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 >
+ 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;
\endcode
Example of how to use \p treiber_stack::member_hook.
- Your class that will be pushed on \p %TreiberStack should have a member of type \p treiber_stack::node
+ Your class should have a member of type \p treiber_stack::node
\code
#include <stddef.h> // offsetof macro
- #include <cds/intrusive/stack/treiber_stack.h>
+ #include <cds/intrusive/treiber_stack.h>
#include <cds/gc/hp.h>
namespace ci = cds::intrusive;
// ...
};
- typedef ci::TreiberStack< 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 >
+ ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
>::type
> stack_t;
\endcode
*/
- template <typename GC, typename T, typename Traits = treiber_stack::traits >
+ template <
+ typename GC,
+ typename T,
+ typename Traits = treiber_stack::traits
+ >
class TreiberStack
{
public:
};
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
typedef typename traits::hook hook; ///< hook type
- typedef typename traits::node_type node_type; ///< node 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 cds::opt::memory_model option
- typedef typename traits::item_counter item_counter; ///< Item counting policy used
- typedef typename traits::stat stat; ///< Internal statistics policy used
+ 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 = traits::enable_elimination;
+ static CDS_CONSTEXPR const bool enable_elimination = traits::enable_elimination;
/// back-off strategy used to wait for elimination
typedef typename traits::elimination_backoff elimination_backoff_type;
/// Lock type used in elimination back-off
/// 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
stat m_stat; ///< Internal statistics
//@cond
- treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
+ typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
+ elimination_backoff 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");
-
- 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();
- }
+ {}
- /// %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
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 ) {
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, atomics::memory_order_relaxed )) { // #1 sync-with #2
+ if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
++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;
}
}
*/
value_type * pop()
{
- m_Backoff.reset();
+ typename elimination_backoff::type bkoff = m_Backoff.init();
typename gc::Guard guard;
operation_desc op;
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, atomics::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();
}
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;
}
/// 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;
}
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, atomics::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;
}
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
+#endif // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
projects / libcds.git / blobdiff