Optimistic queue. More...

#include <cds/container/optimistic_queue.h>

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

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

Public Types
typedef GC	gc
	Garbage collector.

typedef T	value_type
	Value type to be stored in the queue.

typedef Traits	traits
	Queue traits.

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

typedef maker::allocator_type	allocator_type
	Allocator type used for allocate/deallocate the nodes.

typedef base_class::item_counter	item_counter
	Item counting policy used.

typedef base_class::stat	stat
	Internal statistics policy used.

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

Public Member Functions
	OptimisticQueue ()
	Initializes empty queue.

	~OptimisticQueue ()
	Destructor clears the queue.

bool	enqueue (const value_type &val)
	Enqueues `val` value into the queue. More...

bool	enqueue (value_type &&val)
	Enqueues `val` value into the queue, move semntics.

template<typename Func >
bool	enqueue_with (Func f)
	Enqueues `data` to queue using a functor. More...

template<typename... Args>
bool	emplace (Args &&... args)
	Enqueues data of type value_type constructed with `std::forward<Args>(args)...`

bool	push (const value_type &val)
	Synonym for `enqueue( const value_type& )` function.

bool	push (value_type &&val)
	Synonym for `enqueue( value_type&& )` function.

template<typename Func >
bool	push_with (Func f)
	Synonym for `enqueue_with()` function.

bool	dequeue (value_type &dest)
	Dequeues a value from the queue. More...

template<typename Func >
bool	dequeue_with (Func f)
	Dequeues a value using a functor. More...

bool	pop (value_type &dest)
	Synonym for dequeue() function.

template<typename Func >
bool	pop_with (Func f)
	Synonym for template version of `dequeue_with()` function.

bool	empty () const
	Checks if the queue is empty.

void	clear ()
	Clear the queue. More...

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

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

Static Public Attributes
static constexpr const size_t	c_nHazardPtrCount = base_class::c_nHazardPtrCount
	Count of hazard pointer required for the algorithm.

Additional Inherited Members
Private Types inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
typedef GC	gc
	Garbage collector.

typedef cds::intrusive::optimistic_queue::node< T >	value_type
	type of value to be stored in the queue

typedef Traits	traits
	Queue 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 optimistic_queue::get_link_checker< node_type, traits::link_checker >::type	link_checker
	link checker

typedef traits::back_off	back_off
	back-off strategy

typedef traits::item_counter	item_counter
	Item counting policy used.

typedef traits::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

typedef traits::stat	stat
	Internal statistics policy used.

Private Member Functions inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
	OptimisticQueue ()
	Constructor creates empty queue.

bool	enqueue (value_type &val)

value_type *	dequeue ()
	Dequeues a value from the queue. More...

bool	push (value_type &val)
	Synonym for `enqueue()`

value_type *	pop ()
	Synonym for `dequeue()`

bool	empty () const
	Checks if the queue is empty.

void	clear ()
	Clear the stack. More...

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

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

Private Attributes inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
atomic_node_ptr	m_pTail
	Pointer to tail node.

atomic_node_ptr	m_pHead
	Pointer to head node.

node_type	m_Dummy
	dummy node

item_counter	m_ItemCounter
	Item counter.

stat	m_Stat
	Internal statistics.

Static Private Attributes inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
static constexpr const size_t	c_nHazardPtrCount
	Count of hazard pointer required for the algorithm.

Detailed Description

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
class cds::container::OptimisticQueue< GC, T, Traits >

Optimistic queue.

Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.

[2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"

Template arguments:

GC - garbage collector type: gc::HP, gc::DHP.
T - type of values to be stored in the queue
Traits - queue traits, default is optimistic_queue::traits. You can use optimistic_queue::make_traits metafunction to make your traits or just derive your traits from optimistic_queue::traits:
struct myTraits: public cds::container::optimistic_queue::traits {
typedef cds::intrusive::optimistic_queue::stat<> stat;
typedef cds::atomicity::item_counter item_counter;
};
typedef cds::container::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
// Equivalent make_traits example:
typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
typename cds::container::optimistic_queue::make_traits<
cds::opt::stat< cds::container::optimistic_queue::stat<> >,
cds::opt::item_counter< cds::atomicity::item_counter >
>::type
> myQueue;

Member Function Documentation

◆ clear()

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

void cds::container::OptimisticQueue< GC, T, Traits >::clear ( )

inline

Clear the queue.

The function repeatedly calls dequeue until it returns nullptr.

◆ dequeue()

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

bool cds::container::OptimisticQueue< GC, T, Traits >::dequeue ( value_type & dest )

inline

Dequeues a value from the queue.

If queue is not empty, the function returns true, dest contains copy of dequeued value. The assignment operator for type value_type is invoked.

If queue is empty, the function returns false, dest is unchanged.

◆ dequeue_with()

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

template<typename Func >

bool cds::container::OptimisticQueue< GC, T, Traits >::dequeue_with ( Func f )

inline

Dequeues a value using a functor.

Func is a functor called to copy dequeued value. The functor takes one argument - a reference to removed node:

cds:container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});

The functor is called only if the queue is not empty.

◆ enqueue()

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

bool cds::container::OptimisticQueue< GC, T, Traits >::enqueue ( const value_type & val )

inline

Enqueues val value into the queue.

The function makes queue node in dynamic memory calling copy constructor for val and then it calls intrusive::OptimisticQueue::enqueue. Returns true if success, false otherwise.

◆ enqueue_with()

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

template<typename Func >

bool cds::container::OptimisticQueue< GC, T, Traits >::enqueue_with ( Func f )

inline

Enqueues data to queue using a functor.

Func is a functor called to create node. The functor f takes one argument - a reference to a new node of type value_type :

cds::container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );

◆ size()

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

size_t cds::container::OptimisticQueue< GC, T, Traits >::size ( ) const

inline

Returns queue's item count.

The value returned depends on optimistic_queue::traits::item_counter. For atomicity::empty_item_counter, this function always returns 0.

Note: Even if you use real item counter and it returns 0, this fact is not mean that the queue is empty. To check queue emptyness use empty() method.

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

cds/container/optimistic_queue.h

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

template<typename GC, typename T, typename Traits = optimistic_queue::traits> class cds::container::OptimisticQueue< GC, T, Traits >

Member Function Documentation

◆ clear()

◆ dequeue()

◆ dequeue_with()

◆ enqueue()

◆ enqueue_with()

◆ size()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
class cds::container::OptimisticQueue< GC, T, Traits >