cds::intrusive::OptimisticQueue< GC, T, Options > Class Template Reference

Optimistic queue. More...

#include <cds/intrusive/optimistic_queue.h>

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

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

Public Member Functions
	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.

Protected Attributes
aligned_node_ptr	m_pTail
	Pointer to tail node.
aligned_node_ptr	m_pHead
	Pointer to head node.
node_type	m_Dummy
	dummy node
item_counter	m_ItemCounter
	Item counter.
stat	m_Stat
	Internal statistics.

Static Protected Attributes
static const size_t	m_nHazardPtrCount = 5
	Count of hazard pointer required for the algorithm.

Detailed Description

template<typename GC, typename T, typename... Options>
class cds::intrusive::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

Type of node: optimistic_queue::node.

Options are:

• opt::hook - hook used. Possible values are: optimistic_queue::base_hook, optimistic_queue::member_hook, optimistic_queue::traits_hook. If the option is not specified, optimistic_queue::base_hook<> is used.
• opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
• opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used in dequeue function.
• opt::link_checker - the type of node's link fields checking. Default is opt::debug_check_link
• opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter
• opt::stat - the type to gather internal statistics. Possible option value are: optimistic_queue::stat, optimistic_queue::dummy_stat, user-provided class that supports optimistic_queue::stat interface. Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however, they will be automatically converted to optimistic_queue::stat and optimistic_queue::dummy_stat respectively. Default is optimistic_queue::dummy_stat.
• 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).

Garbage collecting schema GC must be consistent with the optimistic_queue::node GC.

About item disposing

The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from the standpoint of the algo. See dequeue function for explanation.

Examples

#include <cds/intrusive/optimistic_queue.h>
#include <cds/gc/hp.h>

namespace ci = cds::inrtusive ;
typedef cds::gc::HP hp_gc;

// Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
struct Foo: public ci::optimistic_queue::node< hp_gc >
{
    // Your data
    ...
};

typedef ci::OptimisticQueue< hp_gc,
    Foo
    ,ci::opt::hook<
        ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
    >
    ,cds::opt::item_counter< cds::atomicity::item_counter >
> FooQueue   ;

// Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
struct Bar
{
    // Your data
    ...
    ci::optimistic_queue::node< hp_gc > hMember ;
};

typedef ci::OptimisticQueue< hp_gc,
    Bar
    ,ci::opt::hook<
        ci::optimistic_queue::member_hook<
            offsetof(Bar, hMember)
            ,ci::opt::gc< hp_gc >
        >
    >
> BarQueue   ;

Member Function Documentation

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

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

inline

Clear the stack.

The function repeatedly calls dequeue until it returns NULL. The disposer defined in template Options is called for each item that can be safely disposed.

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

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

inline

Dequeues a value from the queue.

If the queue is empty the function returns NULL

Warning

The queue algorithm has following feature: when dequeue is called, the item returning is still queue's top, and previous top is disposed:

      before dequeuing         Dequeue               after dequeuing
      +------------------+                           +------------------+
Top ->|      Item 1      |  -> Dispose Item 1        |      Item 2      | <- Top
      +------------------+                           +------------------+
      |      Item 2      |  -> Return Item 2         |       ...        |
      +------------------+
      |       ...        |

dequeue function returns Item 2, that becomes new top of queue, and calls the disposer for Item 1, that was queue's top on function entry. Thus, you cannot manually delete item returned because it is still included in item sequence and it has valuable link field that must not be zeroed. The item may be deleted only in disposer call.

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

bool cds::intrusive::OptimisticQueue< GC, T, Options >::enqueue ( value_type &  val )

inline

Enqueues data in lock-free manner. Always return true

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

size_t cds::intrusive::OptimisticQueue< GC, 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.

Warning: 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/intrusive/optimistic_queue.h