Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang. More...

#include <cds/container/tsigas_cycle_queue.h>

Inheritance diagram for cds::container::TsigasCycleQueue< 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::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 base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

Public Member Functions
	TsigasCycleQueue (size_t nCapacity=0)
	Initialize empty queue of capacity `nCapacity`.

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

size_t	capacity () const
	Returns capacity of cyclic buffer.

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

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

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

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

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

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.

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

typedef options::item_counter	item_counter
	Item counter type.

typedef options::disposer	disposer
	Item disposer.

typedef options::back_off	back_off
	back-off strategy used

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

Private Member Functions inherited from cds::intrusive::TsigasCycleQueue< T, Options... >
	TsigasCycleQueue (size_t nCapacity=0)
	Initialize empty queue of capacity `nCapacity`.

	~TsigasCycleQueue ()
	Clears the queue.

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

size_t	capacity () const noexcept()
	Returns capacity of cyclic buffer.

bool	enqueue (value_type &data)
	Enqueues item from the queue.

value_type *	dequeue ()
	Dequeues item from the queue.

bool	push (value_type &data)
	Synonym of enqueue.

value_type *	pop ()
	Synonym of dequeue.

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

void	clear (Disposer f)
	Clears queue in lock-free manner.

void	clear ()
	Clears the queue.

Detailed Description

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

Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang.

It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on intrusive::TsigasCycleQueue.

Source:

[2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems"

T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.

Available Options:

opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
opt::allocator - allocator (like std::allocator). Default is CDS_DEFAULT_ALLOCATOR
opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter
opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
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).

Examples:: #include <cds/container/tsigas_cycle_queue.h>

struct Foo {

...

};

// Queue of Foo, capacity is 1024, statically allocated buffer:

typedef cds::intrusive::TsigasCycleQueue<

Foo

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

> static_queue ;

static_queue stQueue ;

// Queue of Foo, capacity is 1024, dynamically allocated buffer:

typedef cds::intrusive::TsigasCycleQueue<

Foo

,cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >

> dynamic_queue ;

dynamic_queue dynQueue( 1024 ) ;

Constructor & Destructor Documentation

template<typename T , typename... Options>

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

inline

Initialize empty queue of capacity nCapacity.

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

Note that the real capacity of queue is nCapacity - 2.

Member Function Documentation

template<typename T , typename... Options>

size_t cds::container::TsigasCycleQueue< T, Options >::capacity ( ) const

inline

Returns capacity of cyclic buffer.

Warning: real capacity of queue is two less than returned value of this function.

template<typename T , typename... Options>

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

inline

Clear the queue.

The function repeatedly calls dequeue until it returns NULL.

template<typename T , typename... Options>

template<typename Type , typename Func >

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

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

template<typename... Args>

bool cds::container::TsigasCycleQueue< 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>

bool cds::container::TsigasCycleQueue< T, Options >::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::TsigasCycleQueue::enqueue. Returns true if success, false otherwise.

template<typename T , typename... Options>

template<typename Type , typename Func >

bool cds::container::TsigasCycleQueue< 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/tsigas_cycle_queue.h

Data Structures

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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