Michael & Scott lock-free queue. More...

#include <cds/container/msqueue.h>

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

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

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

typedef Traits	traits
	Queue traits.

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 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
	MSQueue ()
	Initializes empty queue.

	~MSQueue ()
	Destructor clears the queue.

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

bool	enqueue (value_type &&val)
	Enqueues `val` in the queue, move semantics.

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

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

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

bool	push (value_type &&val)
	Synonym for `enqueue()` 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 `dequeue_with()` function.

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

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

size_t	size () const
	Returns queue's item count (see intrusive::MSQueue::size for explanation) 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::MSQueue< GC, cds::intrusive::msqueue::node< T >, Traits >
typedef GC	gc
	Garbage collector.

typedef cds::intrusive::msqueue::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 single_link::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 counter class.

typedef traits::stat	stat
	Internal statistics.

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

Private Member Functions inherited from cds::intrusive::MSQueue< GC, cds::intrusive::msqueue::node< T >, Traits >
	MSQueue ()
	Initializes empty queue.

	~MSQueue ()
	Destructor clears the queue. More...

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

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

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

value_type *	pop ()
	Synonym for dequeue() 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...

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

Static Private Attributes inherited from cds::intrusive::MSQueue< GC, cds::intrusive::msqueue::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 = cds::container::msqueue::traits>
class cds::container::MSQueue< GC, T, Traits >

Michael & Scott lock-free queue.

It is non-intrusive version of Michael & Scott's queue algorithm based on intrusive implementation cds::intrusive::MSQueue.

Template arguments:

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

Member Function Documentation

◆ clear()

template<typename GC , typename T , typename Traits = cds::container::msqueue::traits>

void cds::container::MSQueue< 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 = cds::container::msqueue::traits>

bool cds::container::MSQueue< 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 = cds::container::msqueue::traits>

template<typename Func >

bool cds::container::MSQueue< 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::MSQueue< 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 = cds::container::msqueue::traits>

bool cds::container::MSQueue< GC, T, Traits >::enqueue ( value_type const & 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::MSQueue::enqueue. Returns true if success, false otherwise.

◆ enqueue_with()

template<typename GC , typename T , typename Traits = cds::container::msqueue::traits>

template<typename Func >

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

inline

Enqueues data to the 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::MSQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );

◆ size()

template<typename GC, typename T, typename Traits = cds::container::msqueue::traits>

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

inline

Returns queue's item count (see intrusive::MSQueue::size for explanation)

The value returned depends on msqueue::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/msqueue.h

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

template<typename GC, typename T, typename Traits = cds::container::msqueue::traits> class cds::container::MSQueue< GC, T, Traits >

Member Function Documentation

◆ clear()

◆ dequeue()

◆ dequeue_with()

◆ enqueue()

◆ enqueue_with()

◆ size()

template<typename GC, typename T, typename Traits = cds::container::msqueue::traits>
class cds::container::MSQueue< GC, T, Traits >