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_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 the 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.

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:

• GC - garbage collector type: gc::HP, gc::DHP
• T - type of value to be stored in the queue. A value of type T must be derived from optimistic_queue::node for optimistic_queue::base_hook, or it should have a member of type optimistic_queue::node for optimistic_queue::member_hook, or it should be convertible to optimistic_queue::node for optimistic_queue::traits_hook.
• Traits - queue traits, default is optimistic_queue::traits. You can use optimistic_queue::make_traits metafunction to make your traits or just derive your traits from optimistic_queue::traits:

  struct myTraits: public cds::intrusive::optimistic_queue::traits {
      typedef cds::intrusive::optimistic_queue::stat<> stat;
      typedef cds::atomicity::item_counter    item_counter;
  };
  typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
  
  // Equivalent make_traits example:
  typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
      typename cds::intrusive::optimistic_queue::make_traits<
          cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
          cds::opt::item_counter< cds::atomicity::item_counter >
      >::type
  > myQueue;

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/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,
    Foo,
    typename ci::optimistic_queue::make_traits<
        ci::opt::hook<
            ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
        >
        ,cds::opt::item_counter< cds::atomicity::item_counter >
    >::type
> 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,
    typename ci::optimistic_queue::make_traits<
        ci::opt::hook<
            ci::optimistic_queue::member_hook<
                offsetof(Bar, hMember)
                ,ci::opt::gc< hp_gc >
            >
        >
    >::type
> BarQueue;

Member Function Documentation

clear()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>

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

inline

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 ( )

inline

Dequeues a value from the queue.

If the queue is empty the function returns nullptr

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 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 )

inline

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

inline

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.

Note

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