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

Optimistic intruive lock-free queue. More...

#include <cds/intrusive/optimistic_queue.h>

Data Structures

struct  rebind
 Rebind template arguments. More...

Public Types

typedef GC gc
 Garbage collector.
typedef 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 optimistic_queue::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 counting policy used.
typedef traits::memory_model memory_model
 Memory ordering. See cds::opt::memory_model option.
typedef traits::stat stat
 Internal statistics policy used.

Public Member Functions

 OptimisticQueue ()
 Constructor creates empty queue.
bool enqueue (value_type &val)
value_typedequeue ()
 Dequeues a value from the queue. More...
bool push (value_type &val)
 Synonym for enqueue()
value_typepop ()
 Synonym for dequeue()
bool empty () const
 Checks if the queue is empty.
void clear ()
 Clear the stack. More...
size_t size () const
 Returns queue's item count. More...
const statstatistics () const
 Returns refernce to internal statistics.

Static Public Attributes

static constexpr const size_t c_nHazardPtrCount = 5
 Count of hazard pointer required for the algorithm.

Protected Attributes

atomic_node_ptr m_pTail
 Pointer to tail node.
atomic_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.

Detailed Description

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
class cds::intrusive::OptimisticQueue< GC, T, Traits >

Optimistic intruive lock-free queue.

Implementation of Ladan-Mozes & Shavit optimistic queue algorithm. [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"

Template arguments:

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.
#include <cds/gc/hp.h>
#include <cds/intrusive/optimistic_queue.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,
typename ci::optimistic_queue::make_traits<
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,
typename ci::optimistic_queue::make_traits<
offsetof(Bar, hMember)
,ci::opt::gc< hp_gc >
> BarQueue;

Member Function Documentation

§ clear()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
void cds::intrusive::OptimisticQueue< GC, T, Traits >::clear ( )

Clear the stack.

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

§ dequeue()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
value_type* cds::intrusive::OptimisticQueue< GC, T, Traits >::dequeue ( )

Dequeues a value from the queue.

If the queue is empty the function returns nullptr

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 the queue and it has valuable link field that must not be zeroed. The item may be deleted only in disposer call.

§ enqueue()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
bool cds::intrusive::OptimisticQueue< GC, T, Traits >::enqueue ( value_type val)

Enqueues data in lock-free manner. Always return true

§ size()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
size_t cds::intrusive::OptimisticQueue< GC, T, Traits >::size ( ) const

Returns queue's item count.

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

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 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:52 by Doxygen 1.8.12