cds  2.2.0
cds::intrusive::TreiberStack< GC, T, Traits > Class Template Reference

Treiber intrusive stack. More...

#include <cds/intrusive/treiber_stack.h>

Data Structures

struct  rebind
 Rebind template arguments. More...
 

Public Types

typedef GC gc
 Garbage collector.
 
typedef T value_type
 type of value stored in the stack
 
typedef Traits traits
 Stack traits.
 
typedef traits::hook hook
 hook type
 
typedef hook::node_type node_type
 node type
 
typedef traits::disposer disposer
 disposer used
 
typedef get_node_traits< value_type, node_type, hook >::type node_traits
 node traits
 
typedef single_link::get_link_checker< node_type, traits::link_checker >::type link_checker
 link checker
 
typedef traits::memory_model memory_model
 Memory ordering. See cds::opt::memory_model option.
 
typedef traits::item_counter item_counter
 Item counter class.
 
typedef traits::stat stat
 Internal statistics.
 
typedef traits::back_off back_off
 back-off strategy
 
typedef traits::elimination_backoff elimination_backoff_type
 back-off strategy used to wait for elimination
 
typedef traits::lock_type elimination_lock_type
 Lock type used in elimination back-off.
 
typedef traits::random_engine elimination_random_engine
 Random engine used in elimination back-off.
 

Public Member Functions

 TreiberStack ()
 Constructs empty stack.
 
 TreiberStack (size_t nCollisionCapacity)
 Constructs empty stack and initializes elimination back-off data. More...
 
 TreiberStack (TreiberStack const &)=delete
 TreiberStack is not copy-constructible
 
 ~TreiberStack ()
 Destructor calls clear member function.
 
bool push (value_type &val)
 Push the item val on the stack. More...
 
value_typepop ()
 Pop an item from the stack. More...
 
bool empty () const
 Check if stack is empty.
 
void clear ()
 Clear the stack. More...
 
size_t size () const
 Returns stack's item count. More...
 
stat const & statistics () const
 Returns reference to internal statistics.
 

Static Public Attributes

static constexpr size_t const c_nHazardPtrCount = 1
 How many Hazard pointers is required for Treiber's stack implementation.
 
static constexpr const bool enable_elimination = traits::enable_elimination
 Elimination back-off is enabled or not.
 

Protected Attributes

node_type::atomic_node_ptr m_Top
 Top of the stack.
 
item_counter m_ItemCounter
 Item counter.
 
stat m_stat
 Internal statistics.
 

Detailed Description

template<typename GC, typename T, typename Traits = treiber_stack::traits>
class cds::intrusive::TreiberStack< GC, T, Traits >

Treiber 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.

Elimination back-off technique can be used optionally. The idea of elimination algorithm is taken from:

  • [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"

The elimination algorithm uses a single elimination array as a back-off schema on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate on the array, and if they fail in eliminating, they attempt to access the stack again and so on.

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 the elimination record allocation on thread's stack. This approach demonstrates sufficient performance under high load.

Template arguments:

Note
Be careful when you want destroy an item popped, see Destroying items of intrusive containers.

Examples

Example of how to use treiber_stack::base_hook. Your class that objects will be pushed on TreiberStack should be based on treiber_stack::node class

#include <cds/intrusive/treiber_stack.h>
#include <cds/gc/hp.h>
namespace ci = cds::intrusive;
typedef cds::gc::HP gc;
struct myData: public ci::treiber_stack::node< gc >
{
// ...
};
// Stack type
typedef ci::TreiberStack< gc,
myData,
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<
ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
>::type
> elimination_stack_t;

Example of how to use treiber_stack::base_hook with different tags.

#include <cds/intrusive/treiber_stack.h>
#include <cds/gc/hp.h>
namespace ci = cds::intrusive;
typedef cds::gc::HP gc;
// It is not necessary to declare complete type for tags
struct tag1;
struct tag2;
struct myData
: public ci::treiber_stack::node< gc, tag1 >
, public ci::treiber_stack::node< gc, tag2 >
{
// ...
};
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 into stack1_t and stack2_t independently
void foo() {
stack1_t s1;
stack2_t s2;
myData i1, i2;
s1.push( i1 );
s2.push( i2 );
s2.push( i1 ) ; // i1 is now contained in s1 and s2.
myData * p;
p = s1.pop() ; // pop i1 from s1
p = s1.pop() ; // p == nullptr, s1 is empty
p = s2.pop() ; // pop i1 from s2
p = s2.pop() ; // pop i2 from s2
p = s2.pop() ; // p == nullptr, s2 is empty
}

Example of how to use treiber_stack::member_hook. Your class should have a member of type treiber_stack::node

#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::treiber_stack::node< gc > member_hook_;
// ...
};
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;

Constructor & Destructor Documentation

§ TreiberStack()

template<typename GC, typename T, typename Traits = treiber_stack::traits>
cds::intrusive::TreiberStack< GC, T, Traits >::TreiberStack ( size_t  nCollisionCapacity)
inline

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 Traits contains typedef cds::opt::v::initialized_dynamic_buffer buffer. nCollisionCapacity parameter specifies the capacity of collision array.

Member Function Documentation

§ clear()

template<typename GC, typename T, typename Traits = treiber_stack::traits>
void cds::intrusive::TreiberStack< GC, T, Traits >::clear ( )
inline

Clear the stack.

For each removed item the disposer is called.

Note
It is possible that after clear() the empty() returns false if some other thread pushes an item into the stack during clear works

§ pop()

template<typename GC, typename T, typename Traits = treiber_stack::traits>
value_type* cds::intrusive::TreiberStack< GC, T, Traits >::pop ( )
inline

Pop an item from the stack.

If stack is empty, returns nullptr. The disposer is not called for popped item. See Destroying items of intrusive containers.

§ push()

template<typename GC, typename T, typename Traits = treiber_stack::traits>
bool cds::intrusive::TreiberStack< GC, T, Traits >::push ( value_type val)
inline

Push the item val on the stack.

No copying is made since it is intrusive stack.

§ size()

template<typename GC, typename T, typename Traits = treiber_stack::traits>
size_t cds::intrusive::TreiberStack< GC, T, Traits >::size ( ) const
inline

Returns stack's item count.

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 is empty. To check emptyness use empty() method.

The documentation for this class was generated from the following file:

cds 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:53 by Doxygen 1.8.12