Segmented queue. More...

#include <cds/container/segmented_queue.h>

Inheritance diagram for 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::node_allocator	node_allocator
	Node allocator.

typedef base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

typedef base_class::item_counter	item_counter
	Item counting policy, see cds::opt::item_counter option setter.

typedef base_class::stat	stat
	Internal statistics policy.

typedef base_class::lock_type	lock_type
	Type of mutex for maintaining an internal list of allocated segments.

typedef base_class::permutation_generator	permutation_generator
	Random permutation generator for sequence [0, quasi-factor)

Public Types inherited from cds::intrusive::SegmentedQueue< GC, T, Traits >
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 const &val)
	Inserts a new element at last segment of the queue. More...

bool	enqueue (value_type &&val)
	Inserts a new element at last segment of the queue, move semantics.

template<typename Func >
bool	enqueue_with (Func f)
	Enqueues data to the queue using a functor. More...

bool	push (value_type const &val)
	Synonym for `enqueue( value_type const& )` member function.

bool	push (value_type &&val)
	Synonym for `enqueue( value_type&& )` member function.

template<typename Func >
bool	push_with (Func f)
	Synonym for `enqueue_with()` member 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...

template<typename Func >
bool	pop_with (Func f)
	Synonym for `dequeue_with()` function.

bool	pop (value_type &dest)
	Synonym for `dequeue()` function.

bool	empty () const
	Checks if the queue is empty. More...

void	clear ()
	Clear the queue. More...

size_t	size () const
	Returns queue's item count.

const stat &	statistics () const
	Returns reference to internal statistics. More...

size_t	quasi_factor () const
	Returns quasi factor, a power-of-two number.

Public Member Functions inherited from cds::intrusive::SegmentedQueue< GC, T, Traits >
	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_type *	dequeue ()
	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_type *	pop ()
	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 stat &	statistics () 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 = base_class::c_nHazardPtrCount
	Count of hazard pointer required for the algorithm.

Static Public Attributes inherited from cds::intrusive::SegmentedQueue< GC, T, Traits >
static const size_t	c_nHazardPtrCount = 2
	Count of hazard pointer required for the algorithm.

Additional Inherited Members
Protected Attributes inherited from cds::intrusive::SegmentedQueue< GC, T, Traits >
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::container::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. It means that the consumer dequeues any item from the current first segment.

Template parameters:

GC - a garbage collector, possible types are cds::gc::HP, cds::gc::DHP
T - the type of values stored in the queue
Traits - queue type traits, default is segmented_queue::traits. segmented_queue::make_traits metafunction can be used to construct your type traits.

Constructor & Destructor Documentation

◆ SegmentedQueue()

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

cds::container::SegmentedQueue< GC, T, Traits >::SegmentedQueue ( size_t nQuasiFactor )

inline

Initializes the empty queue.

Parameters

nQuasiFactor Quasi 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::container::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.

◆ dequeue()

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

bool cds::container::SegmentedQueue< 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<class GC , typename T , typename Traits = segmented_queue::traits>

template<typename Func >

bool cds::container::SegmentedQueue< 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::MSQueue< 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<class GC , typename T , typename Traits = segmented_queue::traits>

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

◆ enqueue()

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

bool cds::container::SegmentedQueue< GC, T, Traits >::enqueue ( value_type const & val )

inline

Inserts a new element at last segment of the queue.

The function makes queue node in dynamic memory calling copy constructor for val and then it calls intrusive::SEgmentedQueue::enqueue. Returns true if success, false otherwise.

◆ enqueue_with()

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

template<typename Func >

bool cds::container::SegmentedQueue< GC, T, Traits >::enqueue_with ( Func f )

inline

Enqueues data to the 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::SegmentedQueue< cds::gc::HP, Foo > myQueue;
Bar bar;
myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );

◆ statistics()

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

const stat& cds::container::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/container/segmented_queue.h

Public Types

Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

◆ SegmentedQueue()

Member Function Documentation

◆ clear()

◆ dequeue()

◆ dequeue_with()

◆ empty()

◆ enqueue()

◆ enqueue_with()

◆ statistics()

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