cds  2.3.1
cds::intrusive::SegmentedQueue< GC, T, Traits > Class Template Reference

Segmented queue. More...

#include <cds/intrusive/segmented_queue.h>

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

Public Types

typedef GC gc
 Garbage collector.
 
typedef T value_type
 type of the value stored in the queue
 
typedef Traits traits
 Queue traits.
 
typedef traits::disposer disposer
 value disposer, called only in clear() when the element to be dequeued
 
typedef traits::allocator allocator
 Allocator maintaining the segments.
 
typedef traits::memory_model memory_model
 Memory ordering. See cds::opt::memory_model option.
 
typedef traits::item_counter item_counter
 Item counting policy, see cds::opt::item_counter option setter.
 
typedef traits::stat stat
 Internal statistics policy.
 
typedef traits::lock_type lock_type
 Type of mutex for maintaining an internal list of allocated segments.
 
typedef traits::permutation_generator permutation_generator
 Random permutation generator for sequence [0, quasi-factor)
 

Public Member Functions

 SegmentedQueue (size_t nQuasiFactor)
 Initializes the empty queue. More...
 
 ~SegmentedQueue ()
 Clears the queue and deletes all internal data.
 
bool enqueue (value_type &val)
 Inserts a new element at last segment of the queue.
 
value_typedequeue ()
 Removes an element from first segment of the queue and returns it. More...
 
bool push (value_type &val)
 Synonym for enqueue(value_type&) member function.
 
value_typepop ()
 Synonym for dequeue() member function.
 
bool empty () const
 Checks if the queue is empty. More...
 
void clear ()
 Clear the queue. More...
 
template<class Disposer >
void clear_with (Disposer)
 Clear the queue. More...
 
size_t size () const
 Returns queue's item count.
 
const statstatistics () const
 Returns reference to internal statistics. More...
 
size_t quasi_factor () const
 Returns quasi factor, a power-of-two number.
 

Static Public Attributes

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

Protected Attributes

segment_list m_SegmentList
 List of segments.
 
item_counter m_ItemCounter
 Item counter.
 
stat m_Stat
 Internal statistics.
 

Detailed Description

template<class GC, typename T, typename Traits = segmented_queue::traits>
class cds::intrusive::SegmentedQueue< GC, T, Traits >

Segmented queue.

The queue is based on work

  • [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"

In this paper the authors offer a relaxed version of linearizability, so-called quasi-linearizability, that preserves some of the intuition, provides a flexible way to control the level of relaxation and supports th implementation of more concurrent and scalable data structure. Intuitively, the linearizability requires each run to be equivalent in some sense to a serial run of the algorithm. This equivalence to some serial run imposes strong synchronization requirements that in many cases results in limited scalability and synchronization bottleneck.

The general idea is that the queue maintains a linked list of segments, each segment is an array of nodes in the size of the quasi factor, and each node has a deleted boolean marker, which states if it has been dequeued. Each producer iterates over last segment in the linked list in some random permutation order. Whet it finds an empty cell it performs a CAS operation attempting to enqueue its new element. In case the entire segment has been scanned and no available cell is found (implying that the segment is full), then it attempts to add a new segment to the list.

The dequeue operation is similar: the consumer iterates over the first segment in the linked list in some random permutation order. When it finds an item which has not yet been dequeued, it performs CAS on its deleted marker in order to "delete" it, if succeeded this item is considered dequeued. In case the entire segment was scanned and all the nodes have already been dequeued (implying that the segment is empty), then it attempts to remove this segment from the linked list and starts the same process on the next segment. If there is no next segment, the queue is considered empty.

Based on the fact that most of the time threads do not add or remove segments, most of the work is done in parallel on different cells in the segments. This ensures a controlled contention depending on the segment size, which is quasi factor.

The segmented queue is an unfair queue since it violates the strong FIFO order but no more than quasi factor. This means that the consumer dequeues any item from the current first segment.

Template parameters:

The queue stores the pointers to enqueued items so no special node hooks are needed.

Constructor & Destructor Documentation

◆ SegmentedQueue()

template<class GC , typename T , typename Traits = segmented_queue::traits>
cds::intrusive::SegmentedQueue< GC, T, Traits >::SegmentedQueue ( size_t  nQuasiFactor)
inline

Initializes the empty queue.

Parameters
nQuasiFactorQuasi factor. If it is not a power of 2 it is rounded up to nearest power of 2. Minimum is 2.

Member Function Documentation

◆ clear()

template<class GC , typename T , typename Traits = segmented_queue::traits>
void cds::intrusive::SegmentedQueue< GC, T, Traits >::clear ( )
inline

Clear the queue.

The function repeatedly calls dequeue() until it returns nullptr. The disposer specified in Traits template argument is called for each removed item.

◆ clear_with()

template<class GC , typename T , typename Traits = segmented_queue::traits>
template<class Disposer >
void cds::intrusive::SegmentedQueue< GC, T, Traits >::clear_with ( Disposer  )
inline

Clear the queue.

The function repeatedly calls dequeue() until it returns nullptr. Disposer is called for each removed item.

◆ dequeue()

template<class GC , typename T , typename Traits = segmented_queue::traits>
value_type* cds::intrusive::SegmentedQueue< GC, T, Traits >::dequeue ( )
inline

Removes an element from first segment of the queue and returns it.

If the queue is empty the function returns nullptr.

The disposer specified in Traits template argument is not called for returned item. You should manually dispose the item:

struct my_disposer {
void operator()( foo * p )
{
delete p;
}
};
// ...
// Dequeue an item
foo * pItem = theQueue.dequeue();
// deal with pItem
//...
// pItem is not longer needed and can be deleted
// Do it via gc::HP::retire
cds::gc::HP::template retire< my_disposer >( pItem );

◆ empty()

template<class GC, typename T, typename Traits = segmented_queue::traits>
bool cds::intrusive::SegmentedQueue< GC, T, Traits >::empty ( ) const
inline

Checks if the queue is empty.

The original segmented queue algorithm does not allow to check emptiness accurately because empty() is unlinearizable. This function tests queue's emptiness checking size() == 0, so, the item counting feature is an essential part of queue's algorithm.

◆ statistics()

template<class GC, typename T, typename Traits = segmented_queue::traits>
const stat& cds::intrusive::SegmentedQueue< GC, T, Traits >::statistics ( ) const
inline

Returns reference to internal statistics.

The type of internal statistics is specified by Traits template argument.


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:23 by Doxygen 1.8.13