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

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

#include <cds/intrusive/basket_queue.h>

Data Structures

struct  rebind
 Rebind template arguments. More...
 

Public Types

typedef GC gc
 Garbage collector.
 
typedef 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.
 

Public Member Functions

 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_typedequeue ()
 Dequeues a value from the queue. More...
 
value_typepop ()
 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 statstatistics () const
 Returns reference to internal statistics.
 

Static Public Attributes

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

Protected Attributes

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.
 

Detailed Description

template<typename GC, typename T, typename Traits = basket_queue::traits>
class cds::intrusive::BasketQueue< GC, T, Traits >

Basket lock-free queue (intrusive variant)

Implementation of basket queue algorithm.

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

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

About item disposing
Like MSQueue, the Baskets 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 doc for explanation.
Examples
#include <cds/intrusive/basket_queue.h>
#include <cds/gc/hp.h>
namespace ci = cds::inrtusive;
typedef cds::gc::HP hp_gc;
// Basket queue with Hazard Pointer garbage collector, base hook + item disposer:
struct Foo: public ci::basket_queue::node< hp_gc >
{
// Your data
...
};
// Disposer for Foo struct just deletes the object passed in
struct fooDisposer {
void operator()( Foo * p )
{
delete p;
}
};
struct fooTraits: public ci::basket_queue::traits {
typedef ci::basket_queue::base_hook< ci::opt::gc<hp_gc> > hook;
typedef fooDisposer disposer;
};
typedef ci::BasketQueue< hp_gc, Foo, fooTraits > fooQueue;
// BasketQueue with Hazard Pointer garbage collector,
// member hook + item disposer + item counter,
// without padding of internal queue data:
struct Bar
{
// Your data
...
ci::basket_queue::node< hp_gc > hMember;
};
struct barTraits: public
ci::basket_queue::make_traits<
ci::opt::hook<
ci::basket_queue::member_hook<
offsetof(Bar, hMember)
,ci::opt::gc<hp_gc>
>
>
,ci::opt::disposer< fooDisposer >
,cds::opt::item_counter< cds::atomicity::item_counter >
,cds::opt::padding< cds::opt::no_special_padding >
>::type
{};
typedef ci::BasketQueue< hp_gc, Bar, barTraits > barQueue;

Constructor & Destructor Documentation

§ ~BasketQueue()

template<typename GC, typename T, typename Traits = basket_queue::traits>
cds::intrusive::BasketQueue< GC, T, Traits >::~BasketQueue ( )
inline

Destructor clears the queue.

Since the baskets queue contains at least one item even if the queue is empty, the destructor may call item disposer.

Member Function Documentation

§ clear()

template<typename GC, typename T, typename Traits = basket_queue::traits>
void cds::intrusive::BasketQueue< GC, T, Traits >::clear ( )
inline

Clear the queue.

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 = basket_queue::traits>
value_type* cds::intrusive::BasketQueue< GC, T, Traits >::dequeue ( )
inline

Dequeues a value from the queue.

If the queue is empty the function returns nullptr.

Note
See MSQueue::dequeue() note about item disposing

§ empty()

template<typename GC, typename T, typename Traits = basket_queue::traits>
bool cds::intrusive::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 but really it does not dequeue any item.

§ enqueue()

template<typename GC, typename T, typename Traits = basket_queue::traits>
bool cds::intrusive::BasketQueue< GC, T, Traits >::enqueue ( value_type val)
inline

Enqueues val value into the queue.

The function always returns true.

§ size()

template<typename GC, typename T, typename Traits = basket_queue::traits>
size_t cds::intrusive::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 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:49 by Doxygen 1.8.12