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

Basket lock-free queue (non-intrusive variant) More...

#include <cds/container/basket_queue.h>

Inheritance diagram for cds::container::BasketQueue< GC, T, Traits >:

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's 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
	BasketQueue ()
	Initializes empty queue.
	~BasketQueue ()
	Destructor clears the queue.
bool	enqueue (value_type const &val)
	Enqueues val value into the queue. More...
bool	enqueue (value_type &&val)
	Enqueues val value into the queue, move semantics.
template<typename Func >
bool	enqueue_with (Func f)
	Enqueues data to queue using a functor. More...
bool	push (value_type const &val)
	Synonym for enqueue() function.
bool	push (value_type &&val)
	Synonym for enqueue() function, move semantics.
template<typename Func >
bool	push_with (Func f)
	Synonym for enqueue_with() function.
template<typename... Args>
bool	emplace (Args &&... args)
	Enqueues data of type value_type constructed with std::forward<Args>(args)...
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 dequeue_with() function.
bool	empty ()
	Checks if the queue is empty. More...
void	clear ()
	Clear the queue. More...
size_t	size () const
	Returns queue's item count. More...
const stat &	statistics () 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.

Protected Types
typedef maker::node_type	node_type
	queue node type (derived from intrusive::basket_queue::node)

Additional Inherited Members
Private Types inherited from cds::intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
typedef GC	gc
	Garbage collector.
typedef intrusive::basket_queue::node< T >	value_type
	type of value 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 single_link::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::stat	stat
	Internal statistics policy used.
typedef traits::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.
Private Member Functions inherited from cds::intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
	BasketQueue ()
	Initializes empty queue.
	~BasketQueue ()
	Destructor clears the queue. More...
bool	enqueue (value_type &val)
	Enqueues val value into the queue. More...
bool	push (value_type &val)
	Synonym for enqueue() function.
value_type *	dequeue ()
	Dequeues a value from the queue. More...
value_type *	pop ()
	Synonym for dequeue() function.
bool	empty ()
	Checks if the queue is empty. More...
void	clear ()
	Clear the queue. More...
size_t	size () const
	Returns queue's item count. More...
const stat &	statistics () const
	Returns reference to internal statistics.
Private Attributes inherited from cds::intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
atomic_marked_ptr	m_pHead
	Queue's head pointer (aligned)
atomic_marked_ptr	m_pTail
	Queue's tail pointer (aligned)
node_type	m_Dummy
	dummy node
item_counter	m_ItemCounter
	Item counter.
stat	m_Stat
	Internal statistics.
Static Private Attributes inherited from cds::intrusive::BasketQueue< GC, intrusive::basket_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 = basket_queue::traits>
class cds::container::BasketQueue< GC, T, Traits >

Basket lock-free queue (non-intrusive variant)

It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.

Source:

[2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"

Key idea

In the 'basket' approach, instead of the traditional ordered list of nodes, the queue consists of an ordered list of groups of nodes (logical baskets). The order of nodes in each basket need not be specified, and in fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic rules:

• Each basket has a time interval in which all its nodes' enqueue operations overlap.
• The baskets are ordered by the order of their respective time intervals.
• For each basket, its nodes' dequeue operations occur after its time interval.
• The dequeue operations are performed according to the order of baskets.

Two properties define the FIFO order of nodes:

• The order of nodes in a basket is not specified.
• The order of nodes in different baskets is the FIFO-order of their respective baskets.

In algorithms such as the MS-queue or optimistic queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the queue's tail pointer, and all the threads that fail on a particular CAS operation (and also the winner of that CAS) overlap in time. In particular, they share the time interval of the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of the queue may be inserted into the same basket. By integrating the basket-mechanism as the back-off mechanism, the time usually spent on backing-off before trying to link onto the new tail, can now be utilized to insert the failed operations into the basket, allowing enqueues to complete sooner. In the meantime, the next successful CAS operations by enqueues allow new baskets to be formed down the list, and these can be filled concurrently. Moreover, the failed operations don't retry their link attempt on the new tail, lowering the overall contention on it. This leads to a queue algorithm that unlike all former concurrent queue algorithms requires virtually no tuning of the backoff mechanisms to reduce contention, making the algorithm an attractive out-of-the-box queue.

In order to enqueue, just as in MSQueue, a thread first tries to link the new node to the last node. If it failed to do so, then another thread has already succeeded. Thus it tries to insert the new node into the new basket that was created by the winner thread. To dequeue a node, a thread first reads the head of the queue to obtain the oldest basket. It may then dequeue any node in the oldest basket.

Template arguments:

• GC - garbage collector type: gc::HP, gc::DHP
• T - type of value to be stored in the queue
• Traits - queue traits, default is basket_queue::traits. You can use basket_queue::make_traits metafunction to make your traits or just derive your traits from basket_queue::traits:

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

Member Function Documentation

clear()

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

void cds::container::BasketQueue< 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 = basket_queue::traits>

bool cds::container::BasketQueue< 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 value_type is invoked. If queue is empty, the function returns false, dest is unchanged.

dequeue_with()

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

template<typename Func >

bool cds::container::BasketQueue< 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::BasketQueue< 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.

empty()

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

bool cds::container::BasketQueue< GC, T, Traits >::empty ( )

inline

Checks if the queue is empty.

Note that this function is not const. The function is based on dequeue() algorithm.

enqueue()

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

bool cds::container::BasketQueue< GC, T, Traits >::enqueue ( value_type const &  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::BasketQueue::enqueue(). Returns true if success, false otherwise.

enqueue_with()

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

template<typename Func >

bool cds::container::BasketQueue< 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 :

cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );

size()

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

size_t cds::container::BasketQueue< GC, T, Traits >::size ( ) const

inline

Returns queue's item count.

The value returned depends on Traits (see basket_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/container/basket_queue.h