carb::container::LocklessQueue

Defined in carb/container/LocklessQueue.h

template<class T, LocklessQueueLink<T> T::* U> class LocklessQueue

Implements a lockless queue: a FIFO queue that is thread-safe yet requires no kernel synchronization.

LocklessQueue is designed to be easy-to-use. For a class Foo that you want to be contained in a LocklessQueue, it must have a member of type LocklessQueueLink<Foo>. This member is what the LocklessQueue will use for tracking data.

Pushing to LocklessQueue is simply done through LocklessQueue::push(), which is entirely thread-safe. LocklessQueue ensures first-in-first-out (FIFO) for each producer pushing to LocklessQueue. Multiple producers may be pushing into LocklessQueue simultaneously, so their items can become mingled, but each producer’s pushed items will be strongly ordered.

Popping on the other hand is different for single-consumer vs. multiple-consumer. For single-consumer (via the LocklessQueue::popSC() function) only one thread may be popping from LocklessQueue at any given time. It is up to the caller to ensure this mutual exclusivity.

If multiple-consumer is desired, use the LocklessQueue::popMC() function; it ensures additional thread safety and is therefore higher cost. Furthermore LocklessQueue::popMC() has a contention back-off capability that will attempt to solve high-contention situations with progressive spin and sleep if absolutely necessary.

Simple example:

class Foo
{
public:
    LocklessQueueLink<Foo> m_link;
};

LocklessQueue<Foo, &Foo::m_link> queue;
queue.push(new Foo);
Foo* p = queue.popSC();
delete p;

Thread Safety: LocklessQueue is entirely thread-safe except where declared otherwise. No allocation happens with a LocklessQueue; instead the caller is responsible for construction/destruction of contained objects.

Template Parameters

T – The type to contain.
U – A pointer-to-member of a LocklessQueueLink member within T (see above example).

Public Functions

inline constexpr LocklessQueue(): Constructs a new LocklessQueue.

inline LocklessQueue(LocklessQueue &&rhs)

LocklessQueue is partially movable in that it can be move-constructed from another LocklessQueue, but cannot be move-assigned.

This is to guarantee that the state of the receiving LocklessQueue is a fresh state.

LocklessQueue &operator=(LocklessQueue&&) = delete

Cannot move-assign, only move-construct.

This is to guarantee the state of the receiving LocklessQueue is a fresh state.

inline ~LocklessQueue(): Destructor.

Warning

Asserts that isEmpty() returns true.

inline bool isEmpty() const

Indicates whether the queue is empty.

Warning

Another thread may have modified the LocklessQueue before this function returns.

Returns: true if the queue appears empty; false if items appear to exist in the queue.

inline bool push(T *p)

Pushes an entry onto the LocklessQueue.

Parameters: p – The item to push into the queue.
Returns: true if the queue was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

template<class InputItRef> inline bool push(InputItRef begin, InputItRef end)

Pushes a contiguous block of entries from [ begin, end) onto the queue.

Note

All of the entries are guaranteed to remain strongly ordered and will not be interspersed with entries from other threads.

Parameters

begin – An InputIterator of the first item to push. *begin must resolve to a T&.
end – An off-the-end InputIterator after the last item to push.

Returns

true if the queue was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

template<class InputItPtr> inline bool push(InputItPtr begin, InputItPtr end)

Pushes a block of pointers-to-entries from [ begin, end) onto the queue.

Note

All of the entries are guaranteed to remain strongly ordered and will not be interspersed with entries from other threads.

Parameters

begin – An InputIterator of the first item to push. *begin must resolve to a T*.
end – An off-the-end InputIterator after the last item to push.

Returns

true if the queue was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

inline LocklessQueue eject(): Ejects all entries from this queue as a new LocklessQueue.

Note

To clear all items use popAll().

inline void steal(LocklessQueue &rhs)

Atomically steals all entries from another LocklessQueue and adds them to *this.

Effectively pops everything from rhs and then pushes everything to *this. This can be done in two steps though since everything is already linked together: first the head/tail of rhs are exchanged with nullptr in a multi-consumer manner, then since everything is already linked together they can be pushed as one group onto the end of *this. Therefore, this is much quicker than a loop that pops from one queue and pushes to another.

Parameters: rhs – A LocklessQueue to atomically steal all entries from.

inline void popAll(): Empties the queue.

Note

To perform an action on each item as it is popped, use forEach() instead.

template<class Func> inline void forEach(Func &&f)

Pops all available items from the queue calling an invocable object on each.

First, pops all available items from *this and then calls f on each.

Note

As the pop is the first thing that happens, any new entries that get pushed while the function is executing will NOT be popped and will remain in LocklessQueue when this function returns.

Parameters: f – An invocable object that accepts a T* parameter. Called for each item that was popped from the queue.

inline T *popSC()

Pop first entry (Single-consumer).

Thread Safety: May only be done in a single thread and is mutually exclusive with all other functions that modify LocklessQueue except push(). Use popMC() for a thread-safe pop function.

Warning

Debug builds will assert if a thread safety issue is detected.

Returns: the first item removed from the queue, or nullptr if the queue is empty.

inline T *popMC()

Pop first entry (Multiple-consumer).

popSC() is the single-consumer variant of this function and performs better in a single-consumer environment.

Note

In a highly-contentious situation, this function will back off and attempt to sleep in order to resolve the contention.

Returns: the first item removed from the queue, or nullptr if the queue is empty.

inline T *pop()

Pop first entry (Multiple-consumer).

popSC() is the single-consumer variant of this function and performs better in a single-consumer environment.

Note

In a highly-contentious situation, this function will back off and attempt to sleep in order to resolve the contention.

Returns: the first item removed from the queue, or nullptr if the queue is empty.

inline bool pushNotify(T *p)

Pushes an item onto the queue and notifies a waiting listener.

Equivalent to doing auto b = push(p); notifyOne(); return b;.

See also

push(), notifyOne()

Parameters: p – The item to push.
Returns: true if LocklessQueue was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

inline T *popSCWait()

Blocks the calling thread until an item is available and returns it (Single-consumer).

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popSC(), wait()

Thread Safety: May only be done in a single thread and is mutually exclusive with all other functions that modify LocklessQueue except push(). Use popMC() for a thread-safe pop function.

Warning

Debug builds will assert if a thread safety issue is detected.

Returns: The first item popped from the queue.

template<class Rep, class Period> inline T *popSCWaitFor(const std::chrono::duration<Rep, Period> &dur)

Blocks the calling thread until an item is available and returns it (Single-consumer) or a timeout elapses.

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popSC(), waitFor()

Thread Safety: May only be done in a single thread and is mutually exclusive with all other functions that modify LocklessQueue except push(). Use popMC() for a thread-safe pop function.

Warning

Debug builds will assert if a thread safety issue is detected.

Parameters: dur – The duration to wait for an item to become available.
Returns: The first item popped from the queue or nullptr if the timeout period elapses.

template<class Clock, class Duration> inline T *popSCWaitUntil(const std::chrono::time_point<Clock, Duration> &tp)

Blocks the calling thread until an item is available and returns it (Single-consumer) or the clock reaches a time point.

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popSC(), waitUntil()

Thread Safety: May only be done in a single thread and is mutually exclusive with all other functions that modify LocklessQueue except push(). Use popMC() for a thread-safe pop function.

Warning

Debug builds will assert if a thread safety issue is detected.

Parameters: tp – The time to wait until for an item to become available.
Returns: The first item popped from the queue or nullptr if the timeout period elapses.

inline T *popMCWait()

Blocks the calling thread until an item is available and returns it (Multiple-consumer).

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popMC(), wait()

Note

In a highly-contentious situation, this function will back off and attempt to sleep in order to resolve the contention.

Returns: the first item removed from the queue.

template<class Rep, class Period> inline T *popMCWaitFor(const std::chrono::duration<Rep, Period> &dur)

Blocks the calling thread until an item is available and returns it (Multiple-consumer) or a timeout elapses.

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popMC(), waitFor()

Note

In a highly-contentious situation, this function will back off and attempt to sleep in order to resolve the contention.

Parameters: dur – The duration to wait for an item to become available.
Returns: the first item removed from the queue or nullptr if the timeout period elapses.

template<class Clock, class Duration> inline T *popMCWaitUntil(const std::chrono::time_point<Clock, Duration> &tp)

Blocks the calling thread until an item is available and returns it (Multiple-consumer) or the clock reaches a time point.

Requires the item to be pushed with pushNotify(), notifyOne() or notifyAll().

See also

popMC(), waitUntil()

Note

In a highly-contentious situation, this function will back off and attempt to sleep in order to resolve the contention.

Parameters: tp – The time to wait until for an item to become available.
Returns: the first item removed from the queue or nullptr if the timeout period elapses.

inline void wait(): Waits until the queue is non-empty.

Note

Requires notification that the queue is non-empty, such as from pushNotify(), notifyOne() or notifyAll().

Note

Though wait() returns, another thread may have popped the available item making the queue empty again. Use popSCWait() / popMCWait() if it is desired to ensure that the current thread can obtain an item.

template<class Rep, class Period> inline bool waitFor(const std::chrono::duration<Rep, Period> &dur)

Waits until LocklessQueue is non-empty or a specified duration has passed.

Note

Though waitFor() returns true, another thread may have popped the available item making the queue empty again. Use popSCWaitFor() / popMCWaitFor() if it is desired to ensure that the current thread can obtain an item.

Note

Requires notification that the queue is non-empty, such as from pushNotify(), notifyOne() or notifyAll().

Parameters: dur – The duration to wait for an item to become available.
Returns: true if an item appears to be available; false if the timeout elapses.

template<class Clock, class Duration> inline bool waitUntil(const std::chrono::time_point<Clock, Duration> &tp)

Waits until LocklessQueue is non-empty or a specific time is reached.

Note

Though waitUntil() returns true, another thread may have popped the available item making the queue empty again. Use popSCWaitUntil() / popMCWaitUntil() if it is desired to ensure that the current thread can obtain an item.

Note

Requires notification that the queue is non-empty, such as from pushNotify(), notifyOne() or notifyAll().

Parameters: tp – The time to wait until for an item to become available.
Returns: true if an item appears to be available; false if the time is reached.

inline void notifyOne()

Notifies a single waiting thread.

Notifies a single thread waiting in wait(), waitFor(), waitUntil(), popSCWait(), popMCWait(), popSCWaitFor(), popMCWaitFor(), popSCWaitUntil(), or popMCWaitUntil() to wake and check the queue.

inline void notifyAll()

Notifies all waiting threads.

Notifies all threads waiting in wait(), waitFor(), waitUntil(), popSCWait(), popMCWait(), popSCWaitFor(), popMCWaitFor(), popSCWaitUntil(), or popMCWaitUntil() to wake and check the queue.