cds  2.3.1
cds::container::OptimisticQueue< GC, T, Traits > Class Template Reference

Optimistic queue. More...

#include <cds/container/optimistic_queue.h>

Inheritance diagram for cds::container::OptimisticQueue< GC, T, Traits >:
cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >

Data Structures

struct  rebind
 Rebind template arguments. More...
 

Public Types

typedef GC gc
 Garbage collector.
 
typedef T value_type
 Value type to be stored in the queue.
 
typedef Traits traits
 Queue traits.
 
typedef base_class::back_off back_off
 Back-off strategy used.
 
typedef maker::allocator_type allocator_type
 Allocator type used for allocate/deallocate the nodes.
 
typedef base_class::item_counter item_counter
 Item counting policy used.
 
typedef base_class::stat stat
 Internal statistics policy used.
 
typedef base_class::memory_model memory_model
 Memory ordering. See cds::opt::memory_model option.
 

Public Member Functions

 OptimisticQueue ()
 Initializes empty queue.
 
 ~OptimisticQueue ()
 Destructor clears the queue.
 
bool enqueue (const value_type &val)
 Enqueues val value into the queue. More...
 
bool enqueue (value_type &&val)
 Enqueues val value into the queue, move semntics.
 
template<typename Func >
bool enqueue_with (Func f)
 Enqueues data to queue using a functor. More...
 
template<typename... Args>
bool emplace (Args &&... args)
 Enqueues data of type value_type constructed with std::forward<Args>(args)...
 
bool push (const value_type &val)
 Synonym for enqueue( const value_type& ) function.
 
bool push (value_type &&val)
 Synonym for enqueue( value_type&& ) function.
 
template<typename Func >
bool push_with (Func f)
 Synonym for enqueue_with() function.
 
bool dequeue (value_type &dest)
 Dequeues a value from the queue. More...
 
template<typename Func >
bool dequeue_with (Func f)
 Dequeues a value using a functor. More...
 
bool pop (value_type &dest)
 Synonym for dequeue() function.
 
template<typename Func >
bool pop_with (Func f)
 Synonym for template version of dequeue_with() function.
 
bool empty () const
 Checks if the queue is empty.
 
void clear ()
 Clear the queue. More...
 
size_t size () const
 Returns queue's item count. More...
 
const statstatistics () const
 Returns reference to internal statistics.
 

Static Public Attributes

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

Additional Inherited Members

- Private Types inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
typedef GC gc
 Garbage collector.
 
typedef cds::intrusive::optimistic_queue::node< 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.
 
- Private Member Functions inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
 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.
 
- Private Attributes inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
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.
 
- Static Private Attributes inherited from cds::intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
static constexpr const size_t c_nHazardPtrCount
 Count of hazard pointer required for the algorithm.
 

Detailed Description

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

Optimistic 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:

Member Function Documentation

◆ clear()

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

Clear the queue.

The function repeatedly calls dequeue until it returns nullptr.

◆ dequeue()

template<typename GC , typename T , typename Traits = optimistic_queue::traits>
bool cds::container::OptimisticQueue< GC, T, Traits >::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.

◆ dequeue_with()

template<typename GC , typename T , typename Traits = optimistic_queue::traits>
template<typename Func >
bool cds::container::OptimisticQueue< GC, T, Traits >::dequeue_with ( Func  f)
inline

Dequeues a value using a functor.

Func is a functor called to copy dequeued value. The functor takes one argument - a reference to removed node:

cds:container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});

The functor is called only if the queue is not empty.

◆ enqueue()

template<typename GC , typename T , typename Traits = optimistic_queue::traits>
bool cds::container::OptimisticQueue< GC, T, Traits >::enqueue ( const value_type 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::OptimisticQueue::enqueue. Returns true if success, false otherwise.

◆ enqueue_with()

template<typename GC , typename T , typename Traits = optimistic_queue::traits>
template<typename Func >
bool cds::container::OptimisticQueue< GC, T, Traits >::enqueue_with ( Func  f)
inline

Enqueues data to queue using a functor.

Func is a functor called to create node. The functor f takes one argument - a reference to a new node of type value_type :

Bar bar;
myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );

◆ size()

template<typename GC, typename T, typename Traits = optimistic_queue::traits>
size_t cds::container::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 2.3.1 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Fri Sep 1 2017 08:47:07 by Doxygen 1.8.13