Basket lock-free queue (intrusive variant) More...
|Rebind template arguments. More...|
|Garbage collector. |
|type of value stored in the queue |
|Queue traits. |
|hook type |
|node type |
|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 |
|back-off strategy |
|Item counting policy used. |
|Internal statistics policy used. |
|Memory ordering. See cds::opt::memory_model option. |
|Initializes empty queue. |
|Destructor clears the queue. More...|
|bool||enqueue (value_type &val)|
|bool||push (value_type &val)|
|Synonym for |
|value_type *||dequeue ()|
|Dequeues a value from the queue. More...|
|value_type *||pop ()|
|Synonym for |
|Checks if the queue is empty. More...|
|Clear the queue. More...|
|size_t||size () const|
|Returns queue's item count. More...|
|const stat &||statistics () const|
|Returns reference to internal statistics. |
|static constexpr const size_t||c_nHazardPtrCount = 6|
|Count of hazard pointer required for the algorithm. |
|Queue's head pointer (aligned) |
|Queue's tail pointer (aligned) |
|dummy node |
|Item counter. |
|Internal statistics. |
Basket lock-free queue (intrusive variant)
Implementation of basket queue algorithm.
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:
Two properties define the FIFO order of nodes:
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.
GC- garbage collector type:
T- type of value to be stored in the queue
Traits- queue traits, default is
basket_queue::traits. You can use
basket_queue::make_traitsmetafunction to make your traits or just derive your traits from
Garbage collecting schema
GC must be consistent with the
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.
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.
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.
Dequeues a value from the queue.
MSQueue::dequeue()note about item disposing
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.
Returns queue's item count.