MySQL 8.0.32
Source Code Documentation
Link_buf< Position > Class Template Reference

Concurrent data structure, which allows to track concurrently performed operations which locally might be dis-ordered. More...

#include <ut0link_buf.h>

Public Types

typedef Position Distance
 Type used to express distance between two positions. More...
 

Public Member Functions

 Link_buf (size_t capacity)
 Constructs the link buffer. More...
 
 Link_buf ()
 
 Link_buf (Link_buf &&rhs)
 
 Link_buf (const Link_buf &rhs)=delete
 
Link_bufoperator= (Link_buf &&rhs)
 
Link_bufoperator= (const Link_buf &rhs)=delete
 
 ~Link_buf ()
 Destructs the link buffer. More...
 
void add_link (Position from, Position to)
 Add a directed link between two given positions. More...
 
void add_link_advance_tail (Position from, Position to)
 Add a directed link between two given positions. More...
 
template<typename Stop_condition >
bool advance_tail_until (Stop_condition stop_condition, uint32_t max_retry=1)
 Advances the tail pointer in the buffer by following connected path created by links. More...
 
bool advance_tail ()
 Advances the tail pointer in the buffer without additional condition for stop. More...
 
size_t capacity () const
 
Position tail () const
 
bool has_space (Position position)
 Checks if there is space to add link at given position. More...
 
void validate_no_links (Position begin, Position end)
 Validates (using assertions) that there are no links set in the range [begin, end). More...
 
void validate_no_links ()
 Validates (using assertions) that there no links at all. More...
 

Private Member Functions

size_t slot_index (Position position) const
 Translates position expressed in original unit to position in the m_links (which is a ring buffer). More...
 
bool next_position (Position position, Position &next)
 Computes next position by looking into slots array and following single link which starts in provided position. More...
 
void free ()
 Deallocated memory, if it was allocated. More...
 

Private Attributes

size_t m_capacity
 Capacity of the buffer. More...
 
std::atomic< Distance > * m_links
 Pointer to the ring buffer (unaligned). More...
 
std::atomic< Position > m_tail
 Tail pointer in the buffer (expressed in original unit). More...
 

Detailed Description

template<typename Position = uint64_t>
class Link_buf< Position >

Concurrent data structure, which allows to track concurrently performed operations which locally might be dis-ordered.

This data structure is informed about finished concurrent operations and tracks up to which point in a total order all operations have been finished (there are no holes).

It also allows to limit the last period in which there might be holes. These holes refer to unfinished concurrent operations, which precede in the total order some operations that are already finished.

Threads might concurrently report finished operations (lock-free).

Threads might ask for maximum currently known position in total order, up to which all operations are already finished (lock-free).

Single thread might track the reported finished operations and update maximum position in total order, up to which all operations are done.

You might look at current usages of this data structure in log0buf.cc.

Member Typedef Documentation

◆ Distance

template<typename Position = uint64_t>
typedef Position Link_buf< Position >::Distance

Type used to express distance between two positions.

It could become a parameter of template if it was useful. However there is no such need currently.

Constructor & Destructor Documentation

◆ Link_buf() [1/4]

template<typename Position >
Link_buf< Position >::Link_buf ( size_t  capacity)
explicit

Constructs the link buffer.

Allocated memory for the links. Initializes the tail pointer with 0.

Parameters
[in]capacitynumber of slots in the ring buffer

◆ Link_buf() [2/4]

template<typename Position >
Link_buf< Position >::Link_buf

◆ Link_buf() [3/4]

template<typename Position >
Link_buf< Position >::Link_buf ( Link_buf< Position > &&  rhs)

◆ Link_buf() [4/4]

template<typename Position = uint64_t>
Link_buf< Position >::Link_buf ( const Link_buf< Position > &  rhs)
delete

◆ ~Link_buf()

template<typename Position >
Link_buf< Position >::~Link_buf

Destructs the link buffer.

Deallocates memory for the links.

Member Function Documentation

◆ add_link()

template<typename Position >
void Link_buf< Position >::add_link ( Position  from,
Position  to 
)
inline

Add a directed link between two given positions.

It is user's responsibility to ensure that there is space for the link. This is because it can be useful to ensure much earlier that there is space.

Parameters
[in]fromposition where the link starts
[in]toposition where the link ends (from -> to)

◆ add_link_advance_tail()

template<typename Position >
void Link_buf< Position >::add_link_advance_tail ( Position  from,
Position  to 
)
inline

Add a directed link between two given positions.

It is user's responsibility to ensure that there is space for the link. This is because it can be useful to ensure much earlier that there is space. In addition, advances the tail pointer in the buffer if possible.

Parameters
[in]fromposition where the link starts
[in]toposition where the link ends (from -> to)

◆ advance_tail()

template<typename Position >
bool Link_buf< Position >::advance_tail
inline

Advances the tail pointer in the buffer without additional condition for stop.

Stops at missing outgoing link.

See also
advance_tail_until()
Returns
true if and only if the pointer has been advanced

◆ advance_tail_until()

template<typename Position >
template<typename Stop_condition >
bool Link_buf< Position >::advance_tail_until ( Stop_condition  stop_condition,
uint32_t  max_retry = 1 
)

Advances the tail pointer in the buffer by following connected path created by links.

Starts at current position of the pointer. Stops when the provided function returns true.

Parameters
[in]stop_conditionfunction used as a stop condition; (lsn_t prev, lsn_t next) -> bool; returns false if we should follow the link prev->next, true to stop
[in]max_retrymax fails to retry
Returns
true if and only if the pointer has been advanced

◆ capacity()

template<typename Position >
size_t Link_buf< Position >::capacity
inline
Returns
capacity of the ring buffer

◆ free()

template<typename Position >
void Link_buf< Position >::free
private

Deallocated memory, if it was allocated.

◆ has_space()

template<typename Position >
bool Link_buf< Position >::has_space ( Position  position)
inline

Checks if there is space to add link at given position.

User has to use this function before adding the link, and should wait until the free space exists.

Parameters
[in]positionposition to check
Returns
true if and only if the space is free

◆ next_position()

template<typename Position >
bool Link_buf< Position >::next_position ( Position  position,
Position &  next 
)
inlineprivate

Computes next position by looking into slots array and following single link which starts in provided position.

Parameters
[in]positionposition to start
[out]nextcomputed next position
Returns
false if there was no link, true otherwise

◆ operator=() [1/2]

template<typename Position = uint64_t>
Link_buf & Link_buf< Position >::operator= ( const Link_buf< Position > &  rhs)
delete

◆ operator=() [2/2]

template<typename Position >
Link_buf< Position > & Link_buf< Position >::operator= ( Link_buf< Position > &&  rhs)

◆ slot_index()

template<typename Position >
size_t Link_buf< Position >::slot_index ( Position  position) const
inlineprivate

Translates position expressed in original unit to position in the m_links (which is a ring buffer).

Parameters
[in]positionposition in original unit
Returns
position in the m_links

◆ tail()

template<typename Position >
Position Link_buf< Position >::tail
inline
Returns
the tail pointer

◆ validate_no_links() [1/2]

template<typename Position >
void Link_buf< Position >::validate_no_links

Validates (using assertions) that there no links at all.

◆ validate_no_links() [2/2]

template<typename Position >
void Link_buf< Position >::validate_no_links ( Position  begin,
Position  end 
)

Validates (using assertions) that there are no links set in the range [begin, end).

Member Data Documentation

◆ m_capacity

template<typename Position = uint64_t>
size_t Link_buf< Position >::m_capacity
private

Capacity of the buffer.

◆ m_links

template<typename Position = uint64_t>
std::atomic<Distance>* Link_buf< Position >::m_links
private

Pointer to the ring buffer (unaligned).

◆ m_tail

template<typename Position = uint64_t>
std::atomic<Position> Link_buf< Position >::m_tail
private

Tail pointer in the buffer (expressed in original unit).


The documentation for this class was generated from the following file: