cds::intrusive::TsigasCycleQueue< T, Options > Class Template Reference

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

#include <cds/intrusive/tsigas_cycle_queue.h>

Inheritance diagram for cds::intrusive::TsigasCycleQueue< T, Options >:

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

Public Types
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.

Public Member Functions
	TsigasCycleQueue (size_t nCapacity=0)
	Initialize empty queue of capacity nCapacity. More...
	~TsigasCycleQueue ()
	Clears the queue.
size_t	size () const noexcept()
	Returns queue's item count. More...
size_t	capacity () const noexcept()
	Returns capacity of cyclic buffer.
bool	enqueue (value_type &data)
	Enqueues item from the queue. More...
value_type *	dequeue ()
	Dequeues item from the queue. More...
bool	push (value_type &data)
	Synonym of enqueue.
value_type *	pop ()
	Synonym of dequeue.
bool	empty () const
	Checks if the queue is empty.
template<typename Disposer >
void	clear (Disposer f)
	Clears queue in lock-free manner. More...
void	clear ()
	Clears the queue. More...

Detailed Description

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

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

Source:

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

Template arguments:

• T - data stored in queue. The queue stores pointers to passed data of type T. Restriction: the queue can manage at least two-byte aligned data: the least significant bit (LSB) of any pointer stored in the queue must be zero since the algorithm may use LSB as a flag that marks the free cell.
• Options - options

Options are:

• opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
• opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used only in clear function.
• 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).

This queue algorithm does not require any garbage collector.

Examples:

#include <cds/intrusive/tsigas_cycle_queue.h>

struct Foo {
    ...
};

// Queue of Foo pointers, 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 pointers, 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::intrusive::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>

template<typename Disposer >

void cds::intrusive::TsigasCycleQueue< T, Options >::clear ( Disposer  f )

inline

Clears queue in lock-free manner.

f parameter is a functor to dispose removed items. The interface of DISPOSER is:

struct myDisposer {
    void operator ()( T * val ) ;
};

You can pass disposer by reference using boost::ref. The disposer will be called immediately for each item.

template<typename T, typename... Options>

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

inline

Clears the queue.

This function uses the disposer that is specified in Options.

template<typename T, typename... Options>

value_type* cds::intrusive::TsigasCycleQueue< T, Options >::dequeue ( )

inline

Dequeues item from the queue.

If the queue is empty the function returns NULL

Dequeue does not call value disposer. You can manually dispose returned value if it is needed.

template<typename T, typename... Options>

bool cds::intrusive::TsigasCycleQueue< T, Options >::enqueue ( value_type &  data )

inline

Enqueues item from the queue.

Returns true if success, false otherwise (for example, if queue is full)

template<typename T, typename... Options>

size_t cds::intrusive::TsigasCycleQueue< T, Options >::size ( ) const

inlinenoexcept

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/intrusive/tsigas_cycle_queue.h