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_type *	pop ()
	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. 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:

• GC - garbage collector type: gc::HP, gc::DHP. Garbage collecting schema must be the same as treiber_stack::node GC.
• T - a type the stack contains. A value of type T must be derived from treiber_stack::node for treiber_stack::base_hook, or it should have a member of type treiber_stack::node for treiber_stack::member_hook, or it should be convertible to treiber_stack::node for treiber_stack::traits_hook.
• Traits - stack traits, default is treiber_stack::traits. You can use treiber_stack::make_traits metafunction to make your traits or just derive your traits from treiber_stack::traits:

  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;

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,
    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<
        ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
        cds::opt::enable_elimination< true >
    >::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/intrusive/treiber_stack.h