Vyukov's MPMC bounded queue. More...

#include <cds/container/vyukov_mpmc_cycle_queue.h>

Inheritance diagram for cds::container::VyukovMPMCCycleQueue< T, Options >:

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

Public Types
typedef T	value_type

typedef options::item_counter	item_counter
	Item counter type.

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

Public Member Functions
	VyukovMPMCCycleQueue (size_t nCapacity=0)
	Constructs the queue of capacity `nCapacity`. More...

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

bool	enqueue (value_type const &data)

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

template<typename Dest , typename Func >
bool	dequeue (Dest &data, Func func)
	Dequeues an item from queue. More...

bool	dequeue (value_type &data)
	Dequeues an item from queue to `data`. More...

bool	push (value_type const &data)
	Synonym of enqueue.

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

bool	pop (value_type &data)
	Synonym of dequeue.

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 ()
	Clears the queue.

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

size_t	capacity () const
	Returns capacity of cyclic buffer.

Detailed Description

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

Vyukov's MPMC bounded queue.

This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net) It's multi-producer multi-consumer (MPMC), array-based, fails on overflow, does not require GC, w/o priorities, causal FIFO, blocking producers and consumers queue. The algorithm is pretty simple and fast. It's not lock-free in the official meaning, just implemented by means of atomic RMW operations w/o mutexes.

The cost of enqueue/dequeue is 1 CAS per operation. No dynamic memory allocation/management during operation. Producers and consumers are separated from each other (as in the two-lock queue), i.e. do not touch the same data while queue is not empty.

Source:: http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

Template parameters

T - type stored in queue.
Options - queue's options

Options Options are:

opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter
opt::value_cleaner - a functor to clean item dequeued. Default value is opt::v::destruct_cleaner that calls the destructor of type T. After an item is dequeued, value_cleaner cleans the cell that the item has been occupied. If T is a complex type, value_cleaner may be the useful feature.
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).

License: Simplified BSD license by Dmitry Vyukov (http://www.1024cores.net/site/1024cores/home/code-license)

Example: #include <cds/container/vyukov_mpmc_cycle_queue.h>

// // Queue with 1024 item static buffer

cds::container::vyukov_mpmc_bounded<

int

,cds::opt::buffer< cds::opt::v::static_buffer<int, 1024> >

> myQueue ;

Member Typedef Documentation

template<typename T, typename... Options>

typedef T cds::container::VyukovMPMCCycleQueue< T, Options >::value_type

type of value stored in the queue

Constructor & Destructor Documentation

template<typename T, typename... Options>

cds::container::VyukovMPMCCycleQueue< T, Options >::VyukovMPMCCycleQueue ( size_t nCapacity = 0 )

inline

Constructs the queue of capacity nCapacity.

For cds::opt::v::static_buffer the nCapacity parameter is ignored.

Member Function Documentation

template<typename T, typename... Options>

template<typename Dest , typename Func >

bool cds::container::VyukovMPMCCycleQueue< T, Options >::dequeue	(	Dest &	data,
		Func	func
	)

inline

Dequeues an item from queue.

Func is a functor called to copy dequeued value of type T to dest of type Dest. The functor's interface is:

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

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

Requirements The functor Func should not throw any exception.

template<typename T, typename... Options>

bool cds::container::VyukovMPMCCycleQueue< T, Options >::dequeue ( value_type & data )

inline

Dequeues an item from queue to data.

If queue is empty, returns false, data is unchanged.

template<typename T, typename... Options>

template<typename... Args>

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

template<typename Source , typename Func >

bool cds::container::VyukovMPMCCycleQueue< T, Options >::enqueue	(	Source const &	data,
		Func	func
	)

inline

Enqueues data to queue using copy functor.

Func is a functor called to copy value data of type Source 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.

template<typename T, typename... Options>

bool cds::container::VyukovMPMCCycleQueue< T, Options >::enqueue ( value_type const & data )

inline

Enqueues data to queue

template<typename T, typename... Options>

size_t cds::container::VyukovMPMCCycleQueue< T, Options >::size ( ) const

inline

Returns queue's item count.

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

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

cds/container/vyukov_mpmc_cycle_queue.h

Data Structures

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

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