Treiber's stack algorithm. More...

#include <cds/container/treiber_stack.h>

Inheritance diagram for cds::container::TreiberStack< GC, T, Traits >:

Data Structures
struct	rebind
	Rebind template arguments. More...

Public Types
typedef T	value_type
	Value type stored in the stack.

typedef base_class::gc	gc
	Garbage collector used.

typedef base_class::back_off	back_off
	Back-off strategy used.

typedef maker::allocator_type	allocator_type
	Allocator type used for allocating/deallocating the nodes.

typedef base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_order option.

typedef base_class::stat	stat
	Internal statistics policy used.

Public Types inherited from cds::intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
typedef GC	gc
	Garbage collector.

typedef cds::intrusive::treiber_stack::node< 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 ()
	Clears the stack on destruction.

bool	push (value_type const &val)
	Pushes copy of `val` on the stack.

template<typename... Args>
bool	emplace (Args &&... args)
	Pushes data of type value_type created from `std::forward<Args>(args)...`

bool	pop (value_type &val)
	Pops an item from the stack. More...

template<typename Func >
bool	pop_with (Func f)
	Pops an item from the stack with functor. More...

bool	empty () const
	Check if stack is empty.

void	clear ()
	Clear the stack.

size_t	size () const
	Returns stack's item count. More...

stat const &	statistics () const
	Returns reference to internal statistics.

Public Member Functions inherited from cds::intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
	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.

Protected Types
typedef maker::node_type	node_type
	stack node type (derived from `intrusive::treiber_stack::node`)

Additional Inherited Members
Static Public Attributes inherited from cds::intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
static constexpr size_t const	c_nHazardPtrCount
	How many Hazard pointers is required for Treiber's stack implementation.

static constexpr const bool	enable_elimination
	Elimination back-off is enabled or not.

Protected Attributes inherited from cds::intrusive::TreiberStack< GC, cds::intrusive::treiber_stack::node< T >, Traits >
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::container::TreiberStack< GC, T, Traits >

Treiber's stack algorithm.

It is non-intrusive version of Treiber's stack algorithm based on intrusive implementation intrusive::TreiberStack.

Template arguments:

GC - garbage collector type: gc::HP, gc::DHP
T - type stored in the stack.
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::container::treiber_stack::traits {
typedef cds::intrusive::treiber_stack::stat<> stat;
typedef cds::atomicity::item_counter item_counter;
};
typedef cds::container::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::item_counter< cds::atomicity::item_counter >,
cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
>::type
> myStack;

Constructor & Destructor Documentation

◆ TreiberStack()

template<typename GC , typename T , typename Traits = treiber_stack::traits>

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

Member Function Documentation

◆ pop()

template<typename GC , typename T , typename Traits = treiber_stack::traits>

bool cds::container::TreiberStack< GC, T, Traits >::pop ( value_type & val )

inline

Pops an item from the stack.

The value of popped item is stored in val using assignment operator. On success functions returns true, val contains value popped from the stack. If stack is empty the function returns false, val is unchanged.

◆ pop_with()

template<typename GC , typename T , typename Traits = treiber_stack::traits>

template<typename Func >

bool cds::container::TreiberStack< GC, T, Traits >::pop_with ( Func f )

inline

Pops an item from the stack with functor.

Func can be used to copy/move popped item from the stack. Func interface is:

void func( value_type& src );

where src - item popped.

◆ size()

template<typename GC , typename T , typename Traits = treiber_stack::traits>

size_t cds::container::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/container/treiber_stack.h

Data Structures

Public Types

Public Member Functions

Protected Types

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

◆ TreiberStack()

Member Function Documentation

◆ pop()

◆ pop_with()

◆ size()

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