MySQL 8.1.0
Source Code Documentation

Lockfree, fixedsize bounded, multipleproducer (MP), multipleconsumer (MC), circular FIFO queue for integral elements. More...
#include <integrals_lockfree_queue.h>
Classes  
class  Iterator 
Iterator helper class to iterate over the queue staring at the virtual index pointed to by the head, up until the virtual index pointed to by the tail. More...  
Public Types  
enum class  enum_queue_state : short { SUCCESS = 0 , NO_MORE_ELEMENTS = 1 , NO_SPACE_AVAILABLE = 2 } 
using  pointer_type = T * 
using  const_pointer_type = T const * 
using  reference_type = T & 
using  const_reference_type = T const & 
using  value_type = T 
using  const_value_type = T const 
using  element_type = std::atomic< T > 
using  index_type = unsigned long long 
using  array_type = container::Atomics_array< T, I, A > 
using  atomic_type = memory::Aligned_atomic< index_type > 
Public Member Functions  
template<typename D = T, T M = Null, T F = Erased, typename J = I, typename B = A, std::enable_if_t<!std::is_same< B, std::nullptr_t >::value > * = nullptr>  
Integrals_lockfree_queue (A &alloc, size_t size)  
Constructor allowing a specific memory allocator and a specific queue capacity. More...  
template<typename D = T, T M = Null, T F = Erased, typename J = I, typename B = A, std::enable_if_t< std::is_same< B, std::nullptr_t >::value > * = nullptr>  
Integrals_lockfree_queue (size_t size)  
Constructor allowing specific queue capacity. More...  
Integrals_lockfree_queue (Integrals_lockfree_queue< T, Null, Erased, I, A > const &rhs)=delete  
Integrals_lockfree_queue (Integrals_lockfree_queue< T, Null, Erased, I, A > &&rhs)=delete  
virtual  ~Integrals_lockfree_queue ()=default 
Destructor for the class. More...  
Integrals_lockfree_queue< T, Null, Erased, I, A > &  operator= (Integrals_lockfree_queue< T, Null, Erased, I, A > const &rhs)=delete 
Integrals_lockfree_queue< T, Null, Erased, I, A > &  operator= (Integrals_lockfree_queue< T, Null, Erased, I, A > &&rhs)=delete 
array_type &  array () 
Returns the underlying instance of memory::Atomics_array which holds the allocated memory for the array of std::atomic<T> elements. More...  
void  clear () 
Sets all queue positions to Null and points the head and tail of the queue to the 0 virtual index. More...  
bool  is_empty () const 
Retrieves whether or not the head and tail of the queue are pointing to the same virtual index. More...  
bool  is_full () const 
Retrieves whether or not the tail of the queue is pointing to the same virtual index as the computed by adding the queue capacity() to the virtual index pointed to by the head of the queue. More...  
index_type  head () const 
Retrieves the virtual index that the head of the queue is pointing to. More...  
index_type  tail () const 
Retrieves the virtual index that the tail of the queue is pointing to. More...  
value_type  front () const 
Retrieves the element at the front of the queue, i.e. More...  
value_type  back () const 
Retrieves the value of the position at the back of the queue, i.e. More...  
Integrals_lockfree_queue< T, Null, Erased, I, A > &  operator>> (reference_type out) 
Retrieves the value at the virtual index pointed by the head of the queue, clears that position, updates the virtual index stored in the head and clears the value returned by get_state() , setting it to SUCCESS . More...  
Integrals_lockfree_queue< T, Null, Erased, I, A > &  operator<< (const_reference_type to_push) 
Takes the value passed on as a parameter, stores it in the virtual index pointed to by the tail of the queue, updates the virtual index stored in the tail and clears the value returned by get_state() , setting it to SUCCESS . More...  
value_type  pop () 
Retrieves the value at the virtual index pointed by the head of the queue, clears that position, updates the virtual index stored in the head and clears the value returned by get_state() , setting it to SUCCESS . More...  
Integrals_lockfree_queue< T, Null, Erased, I, A > &  push (value_type to_push) 
Takes the value passed on as a parameter, stores it in the virtual index pointed to by the tail of the queue, updates the virtual index stored in the tail and clears the value returned by get_state() , setting it to SUCCESS . More...  
Iterator  begin () const 
Retrieves an iterator instance that points to the same position pointed by the head of the queue. More...  
Iterator  end () const 
Retrieves an iterator instance that points to the same position pointed by the tail of the queue. More...  
template<typename D = T, T M = Null, T F = Erased, typename J = I, typename B = A, typename Pred , std::enable_if_t< M !=F > * = nullptr>  
size_t  erase_if (Pred predicate) 
Erases values from the queue. More...  
size_t  capacity () const 
Returns the maximum number of elements allowed to coexist in the queue. More...  
size_t  allocated_size () const 
Returns the amount of bytes needed to store the maximum number of elements allowed to coexist in the queue. More...  
Integrals_lockfree_queue< T, Null, Erased, I, A > &  clear_state () 
Clears the error state of the last performed operations, if any. More...  
enum_queue_state  get_state () const 
Retrieves the error/success state of the last performed operation. More...  
std::string  to_string () const 
Return this queue textual representation. More...  
Static Public Attributes  
static constexpr T  null_value = Null 
static constexpr T  erased_value = Erased 
static constexpr index_type  set_bit = 1ULL << 63 
static constexpr index_type  clear_bit = set_bit  1 
Private Member Functions  
size_t  translate (index_type from) const 
Translates a virtual monotonically increasing index into an index bounded to the queue capacity. More...  
enum_queue_state &  state () const 
Retrieves the thread storage duration operation state variable. More...  
Private Attributes  
size_t  m_capacity {0} 
The maximum allowed number of element allowed to coexist in the queue. More...  
array_type  m_array 
The array of atomics in which the elements will be stored. More...  
atomic_type  m_head {0} 
The virtual index being pointed to by the head of the queue. More...  
atomic_type  m_tail {0} 
The virtual index being pointed to by the tail of the queue. More...  
Friends  
std::ostream &  operator<< (std::ostream &out, Integrals_lockfree_queue< T, Null, Erased, I, A > const &in) 
Lockfree, fixedsize bounded, multipleproducer (MP), multipleconsumer (MC), circular FIFO queue for integral elements.
Monotonically ever increasing virtual indexes are used to keep track of the head and tail pointer for the sizebounded circular queue. Virtual indexes are translated into memory indexes by calculating the remainder of the integer division of the virtual index by the queue capacity. The maximum value of a virtual index is 2^63  1.
Head is the pointer to the virtual index of the first position that holds an element to be popped, if any.
Tail is the pointer to the virtual index of the first available position to push an element to, if any.
Template parameters are as follows:
T
: The integral type for the queue elements.Null
: Value of type T
, that will be used to mark a queue position as empty.Erased
: Value of type T
, that will be used to mark an queue position as erased.I
: Type of indexing to be used by the underlying array in the form of a class. Available classes are container::Padded_indexing
and container::Interleaved_indexing
, check the classes documentation for further details. The parameter defaults to container::Padded_indexing
.A
: Type of memory allocator to be used, in the form of a class (defaults to no allocator).All the available operations are threadsafe, in the strict sense of no memory problems rise from multiple threads trying to perform operations concurrently.
However, being a lockfree structure, the queue may be changing at the same time as operations access both pointers and values or a client of the API evaluates the result of the invoked operation. The operation results and returning states are always based on the thread local view of the queue state, which may be safe or unsafe to proceed with the given operation. Therefore, extra validations, clientside serialization and/or retry mechanisms may be needed while using the queue operations.
Available methods are:
pop
: if the head of the queue points to a virtual index different from the one pointed by the tail of the queue, removes the element pointed to by the head of the queue, points the head to the next virtual index and returns the retrieved value. If head and tail of the queue point to the same virtual index, the queue is empty, Null
is returned and the thread operation state is set to NO_MORE_ELEMENTS
.push
: if the tail of the queue points to a virtual index different from the one pointed by headplusqueuecapacity, sets the position pointed by tail with the provided element and points the tail to the next virtual index. If tail and head plus queue capacity point to the same virtual index, the queue is full, no operation is performed and the thread operation state is set to NO_SPACE_AVAILABLE
.capacity
: maximum number of elements allowed to coexist in the queue.head
: pointer to the virtual index of the first available element, if any.tail
: pointer to the virtual index of the first available position to add an element to. Additionally, the value returned by tail()
can also give an lowerthan approximation of the total amount of elements already pushed into the queue in between reading the virtual index tail is pointing to and evaluating it, some more elements may have been pushed.front
: the first available element. If none, Null
is returned.back
: the last available element. If none, Null
is returned.clear
: sets all positions of the underlying array to Null
and resets the virtual index pointed to by both the head and the tail of the queue to 0
.is_empty
: whether or not the head and tail of the queue point to the same virtual index.is_full
: whether or not the tail and headplusqueuecapacity point to the same virtual index.erase_if
: traverses the queue, starting at the queue relative memory index 0, stopping at the relative memory index capacity()  1
and invoking the passedon predicate over each position value, while disregarding positions that have Null
or Erased
values.Note that, if Null
and Erased
hold the same value, the resulting class will not include the erase_if
method.
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::array_type = container::Atomics_array<T, I, A> 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::atomic_type = memory::Aligned_atomic<index_type> 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::const_pointer_type = T const * 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::const_reference_type = T const & 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::const_value_type = T const 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::element_type = std::atomic<T> 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::index_type = unsigned long long 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::pointer_type = T * 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::reference_type = T & 
using container::Integrals_lockfree_queue< T, Null, Erased, I, A >::value_type = T 

strong 
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::Integrals_lockfree_queue  (  A &  alloc, 
size_t  size  
) 
Constructor allowing a specific memory allocator and a specific queue capacity.
The queue allocated memory may differ from capacity() * sizeof(T)
since additional space may be required to prevent false sharing between threads.
alloc  The memory allocator instance 
size  The queue maximum capacity 
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::Integrals_lockfree_queue  (  size_t  size  ) 
Constructor allowing specific queue capacity.
The queue allocated memory may differ from capacity() * sizeof(T)
since additional space may be required to prevent false sharing between threads.
size  The queue maximum capacity 

delete 

delete 

virtualdefault 
Destructor for the class.
size_t container::Integrals_lockfree_queue< T, Null, Erased, I, A >::allocated_size 
Returns the amount of bytes needed to store the maximum number of elements allowed to coexist in the queue.
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::array_type & container::Integrals_lockfree_queue< T, Null, Erased, I, A >::array 
Returns the underlying instance of memory::Atomics_array
which holds the allocated memory for the array of std::atomic<T>
elements.
memory::Atomics_array
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::value_type container::Integrals_lockfree_queue< T, Null, Erased, I, A >::back 
Retrieves the value of the position at the back of the queue, i.e.
the value stored in the virtual index just prior to the virtual index pointed to by the tail of the queue.
The returned value may be Null
or Erased
, whatever value that is held by the given virtual index position.
As this method is an alias for array()[tail()]
, the queue may be changed concurrently and it is possible for this method to return a value assigned to a position outside the bounds of the head and tail of the queue (between threadlocal fetch of the tail pointer and the access to the position indexed by the local value, operations moved the head to a virtual index higher than the locally stored). This means that Null
may be returned or that a value that is currently being popped may be returned.
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::Iterator container::Integrals_lockfree_queue< T, Null, Erased, I, A >::begin  (  void  )  const 
Retrieves an iterator instance that points to the same position pointed by the head of the queue.
Please, be aware that, while using standard library features that use the Iterator
requirement, like for_each
loops, std::find
, std::find_if
, etc:
Null
values at the beginning of the iteration because elements were popped just after the queue begin()
method is invoked, the moment when the iterator pointing to the same virtual index as the head of the queue is computed.size_t container::Integrals_lockfree_queue< T, Null, Erased, I, A >::capacity 
Returns the maximum number of elements allowed to coexist in the queue.
void container::Integrals_lockfree_queue< T, Null, Erased, I, A >::clear 
Sets all queue positions to Null
and points the head and tail of the queue to the 0
virtual index.
container::Integrals_lockfree_queue< T, Null, Erased, I, A > & container::Integrals_lockfree_queue< T, Null, Erased, I, A >::clear_state 
Clears the error state of the last performed operations, if any.
The operation state is a thread storage duration variable, making it a perthread state.
this
object, for chaining purposes. container::Integrals_lockfree_queue< T, Null, Erased, I, A >::Iterator container::Integrals_lockfree_queue< T, Null, Erased, I, A >::end  (  void  )  const 
Retrieves an iterator instance that points to the same position pointed by the tail of the queue.
Please, be aware that, while using standard library features that use the Iterator
requirement, like for_each
loops, std::find
, std::find_if
, etc:
end()
method is invoked, the moment when the iterator pointing to the same virtual index has the tail of the queue is computed.size_t container::Integrals_lockfree_queue< T, Null, Erased, I, A >::erase_if  (  Pred  predicate  ) 
Erases values from the queue.
The traversing is linear and not in between the virtual indexes pointed to by the head and the tail of the queue but rather between 0 and Integrals_lockfree_queue::capacity()  1
.
An element may be conditionally erased according to the evaluation of the predicate predicate
which should be any predicate which is translatable to [](value_type value) > bool
. If the predicate evaluates to true
, the value is replace by Erased
.
If both Null
and Erased
evaluate to the same value, this method will not be available after the template substitutions since erased values must be identifiable by the pop and push operations.
Check C++ documentation for the definition of Predicate
named requirement for more information.
predicate  The predicate invoked upon a given queue position and if evaluated to true will force the removal of such element. 
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::value_type container::Integrals_lockfree_queue< T, Null, Erased, I, A >::front 
Retrieves the element at the front of the queue, i.e.
the value stored in the virtual index pointed to by the head of the queue.
The returned value may be Null
, Erased
or whatever value that is held by the given virtual index position at the moment it's accessed.
As this method is an alias for array()[head()]
, the queue may be changed concurrently and, because it is a circular queue, it is possible for this method to return a value that has not been popped yet and it will not be popped in the next call for pop()
(the circular queue logic made the tail to wrap and overlap the thread local value of head).
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::enum_queue_state container::Integrals_lockfree_queue< T, Null, Erased, I, A >::get_state 
Retrieves the error/success state of the last performed operation.
The operation state is a thread storage duration variable, making it a perthread state.
Possible values are:
SUCCESS
if the operation was successfulNO_MORE_ELEMENTS
if there are no more elements to popNO_SPACE_AVAILABLE
if there is no more room for pushing elementsState may be changed by any of the pop
, push
operations.
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::index_type container::Integrals_lockfree_queue< T, Null, Erased, I, A >::head 
Retrieves the virtual index that the head of the queue is pointing to.
bool container::Integrals_lockfree_queue< T, Null, Erased, I, A >::is_empty 
Retrieves whether or not the head and tail of the queue are pointing to the same virtual index.
No evaluation of the value held in the given position is made. If, for instance, head and tail point to consecutive virtual indexes and the value stored in the position pointed to by head is Erased
, is_empty
will return false and pop
will return Null
and trigger a NO_MORE_ELEMENTS
state change.
bool container::Integrals_lockfree_queue< T, Null, Erased, I, A >::is_full 
Retrieves whether or not the tail of the queue is pointing to the same virtual index as the computed by adding the queue capacity()
to the virtual index pointed to by the head of the queue.
No evaluation of the value held in the given position is made. If, for instance, all the values stored in the positions between head and tail are Erased
, is_full
will return true and pop
will return Null
and trigger a NO_MORE_ELEMENTS
state change.
container::Integrals_lockfree_queue< T, Null, Erased, I, A > & container::Integrals_lockfree_queue< T, Null, Erased, I, A >::operator<<  (  const_reference_type  to_push  ) 
Takes the value passed on as a parameter, stores it in the virtual index pointed to by the tail of the queue, updates the virtual index stored in the tail and clears the value returned by get_state()
, setting it to SUCCESS
.
If the tail of the queue points to a virtual index that has already an element assigned (queue is full), the operation fails and the value returned by get_state()
is NO_SPACE AVAILABLE
.
to_push  The value to push into the queue. 
this
object, for chaining purposes.

delete 

delete 
container::Integrals_lockfree_queue< T, Null, Erased, I, A > & container::Integrals_lockfree_queue< T, Null, Erased, I, A >::operator>>  (  reference_type  out  ) 
Retrieves the value at the virtual index pointed by the head of the queue, clears that position, updates the virtual index stored in the head and clears the value returned by get_state()
, setting it to SUCCESS
.
If the head of the queue points to a virtual index that has no element assigned (queue is empty), the operation fails, Null
is stored in the out
parameter and the value returned by get_state()
is NO_MORE_ELEMENTS
.
out  The variable reference to store the value in. 
this
object, for chaining purposes. T container::Integrals_lockfree_queue< T, Null, Erased, I, A >::pop 
Retrieves the value at the virtual index pointed by the head of the queue, clears that position, updates the virtual index stored in the head and clears the value returned by get_state()
, setting it to SUCCESS
.
If the head of the queue points to a virtual index that has no element assigned yet (queue is empty), the operation returns Null
and the value returned by get_state()
is NO_MORE_ELEMENTS
.
Null
if no element is available for popping container::Integrals_lockfree_queue< T, Null, Erased, I, A > & container::Integrals_lockfree_queue< T, Null, Erased, I, A >::push  (  value_type  to_push  ) 
Takes the value passed on as a parameter, stores it in the virtual index pointed to by the tail of the queue, updates the virtual index stored in the tail and clears the value returned by get_state()
, setting it to SUCCESS
.
If the tail of the queue points to a virtual index that has already an element assigned (queue is full), the operation fails and the value returned by get_state()
is NO_SPACE AVAILABLE
.
to_push  The value to push into the queue. 
this
object, for chaining purposes.

private 
Retrieves the thread storage duration operation state variable.
container::Integrals_lockfree_queue< T, Null, Erased, I, A >::index_type container::Integrals_lockfree_queue< T, Null, Erased, I, A >::tail 
Retrieves the virtual index that the tail of the queue is pointing to.
std::string container::Integrals_lockfree_queue< T, Null, Erased, I, A >::to_string 
Return this
queue textual representation.
this
queue.

private 
Translates a virtual monotonically increasing index into an index bounded to the queue capacity.

friend 

staticconstexpr 

staticconstexpr 

private 
The array of atomics in which the elements will be stored.

private 
The maximum allowed number of element allowed to coexist in the queue.

private 
The virtual index being pointed to by the head of the queue.

private 
The virtual index being pointed to by the tail of the queue.

staticconstexpr 

staticconstexpr 