Optimistic queue. More...

#include <cds/container/optimistic_queue.h>

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

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 options::allocator_type	allocator_type
	Allocator type used for allocate/deallocate the nodes.

typedef options::options::item_counter	item_counter
	Item counting policy used.

typedef options::options::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.

size_t	size () const
	Returns queue's item count (see intrusive::OptimisticQueue::size for explanation)

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

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

template<typename Type , typename Func >
bool	enqueue (const Type &data, Func f)
	Enqueues `data` to queue using copy functor. More...

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

template<typename Type , typename Func >
bool	dequeue (Type &dest, Func f)
	Dequeues a value using copy functor. More...

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

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

template<typename Type , typename Func >
bool	push (const Type &data, Func f)
	Synonym for template version of enqueue function.

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

template<typename Type , typename Func >
bool	pop (Type &dest, Func f)
	Synonym for template version of dequeue function.

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

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

Protected Types
typedef options::node_type	node_type
	queue node type (derived from intrusive::optimistic_queue::node)

Additional Inherited Members
Private Types inherited from cds::intrusive::OptimisticQueue< GC, intrusive::optimistic_queue::node< T >, Options... >
typedef intrusive::optimistic_queue::node < T >	value_type
	type of value stored in the queue

typedef options::hook	hook
	hook type

typedef hook::node_type	node_type
	node type

typedef options::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, options::link_checker >::type	link_checker
	link checker

typedef GC	gc
	Garbage collector.

typedef options::back_off	back_off
	back-off strategy

typedef options::item_counter	item_counter
	Item counting policy used.

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

typedef options::stat	stat
	Internal statistics policy used.

Private Member Functions inherited from cds::intrusive::OptimisticQueue< GC, intrusive::optimistic_queue::node< T >, Options... >
	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 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.

Detailed Description

template<typename GC, typename T, typename... Options>
class cds::container::OptimisticQueue< GC, T, Options >

Optimistic queue.

Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.

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

Template arguments:

GC - garbage collector type: gc::HP, gc::PTB. Note that gc::HRC is not supported
T - type to be stored in the queue
Options - options

Options are:

opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
opt::allocator - allocator (like std::allocator) used for nodes allocation. Default is CDS_DEFAULT_ALLOCATOR
opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter
opt::stat - the type to gather internal statistics for debugging and profiling purposes. Possible option value are: intrusive::optimistic_queue::stat, intrusive::optimistic_queue::dummy_stat (the default), user-provided class that supports intrusive::optimistic_queue::stat interface. Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however, they will be automatically converted to intrusive::optimistic_queue::stat and intrusive::optimistic_queue::dummy_stat respectively.
opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) or opt::v::sequential_consistent (sequentially consisnent memory model).

Warning gc::HRC is not supported for this implementation.

Member Function Documentation

template<typename GC , typename T , typename... Options>

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

inline

Clear the queue.

The function repeatedly calls dequeue until it returns NULL.

template<typename GC , typename T , typename... Options>

template<typename Type , typename Func >

bool cds::container::OptimisticQueue< GC, T, Options >::dequeue	(	Type &	dest,
		Func	f
	)

inline

Dequeues a value using copy functor.

Func is a functor called to copy dequeued value to dest of type Type which may be differ from type T stored in the queue. The functor's interface is:

struct myFunctor {
    void operator()(Type& dest, T const& data)
    {
        // Code to copy \p data to \p dest
        dest = data ;
    }
};

You may use boost:ref construction to pass functor f by reference.

Requirements The functor Func should not throw any exception.

template<typename GC , typename T , typename... Options>

bool cds::container::OptimisticQueue< GC, T, Options >::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.

template<typename GC , typename T , typename... Options>

template<typename... Args>

bool cds::container::OptimisticQueue< GC, T, Options >::emplace ( Args &&... args )

inline

Enqueues data of type value_type constructed with std::forward<Args>(args)...

This function is available only for compiler that supports variadic template and move semantics

template<typename GC , typename T , typename... Options>

bool cds::container::OptimisticQueue< GC, T, Options >::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.

template<typename GC , typename T , typename... Options>

template<typename Type , typename Func >

bool cds::container::OptimisticQueue< GC, T, Options >::enqueue	(	const Type &	data,
		Func	f
	)

inline

Enqueues data to queue using copy functor.

Func is a functor called to copy value data of type Type which may be differ from type T stored in the queue. The functor's interface is:

struct myFunctor {
    void operator()(T& dest, SOURCE const& data)
    {
        // // Code to copy \p data to \p dest
        dest = data ;
    }
};

You may use boost:ref construction to pass functor f by reference.

Requirements The functor Func should not throw any exception.

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

cds/container/optimistic_queue.h

Data Structures

Public Types

Public Member Functions

Protected Types

Additional Inherited Members

Detailed Description

template<typename GC, typename T, typename... Options> class cds::container::OptimisticQueue< GC, T, Options >

Member Function Documentation

template<typename GC, typename T, typename... Options>
class cds::container::OptimisticQueue< GC, T, Options >