carb::container::LocklessStack

Defined in carb/container/LocklessStack.h

template<class T, LocklessStackLink<T> T::* U> class LocklessStack : protected detail::LocklessStackBase<T, U>

Implements a lockless stack: a LIFO container that is thread-safe yet requires no kernel involvement.

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

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

Popping is done through LocklessStack::pop(), which is also entirely thread-safe. Multiple threads may all attempt to pop from the same LocklessStack simultaneously.

Simple example:

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

LocklessStack<Foo, &Foo::m_link> stack;
stack.push(new Foo);
Foo* p = stack.pop();
delete p;

Thread Safety: LocklessStack is entirely thread-safe except where declared otherwise. No allocation happens with a LocklessStack; 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 LocklessStackLink member within T (see above example).

Public Functions

constexpr LocklessStack() = default: Constructor.

inline ~LocklessStack()

Destructor.

Asserts that isEmpty() returns true.

inline bool isEmpty() const

Indicates whether the stack is empty.

Warning

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

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

inline bool push(T *p)

Pushes an item onto the stack.

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

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

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

Note

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

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 stack 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 stack.

Note

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

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 stack was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

inline T *pop()

Pops an item from the top of the stack if available.

Returns: An item popped from the stack. If the stack was empty, then nullptr is returned.

inline void popAll(): Empties the stack.

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 stack 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 the stack when this function returns.

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

inline bool pushNotify(T *p)

Pushes an item onto the stack 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 the stack was empty prior to push; false otherwise. Note that this is atomically correct as opposed to calling isEmpty() before push().

inline T *popWait()

Blocks the calling thread until an item is available and returns it.

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

See also

pop(), wait()

Returns: The first item popped from the stack.

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

Blocks the calling thread until an item is available and returns it or a timeout elapses.

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

See also

pop(), waitFor()

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

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

Blocks the calling thread until an item is available and returns it or the clock reaches a time point.

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

See also

pop(), waitUntil()

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

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

Note

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

Note

Though wait() returns, another thread may have popped the available item making the stack empty again. Use popWait() 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 the stack is non-empty or a specified duration has passed.

Note

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

Note

Requires notification that the stack 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 the stack is non-empty or a specific time is reached.

Note

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

Note

Requires notification that the stack 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(), popWait(), popWaitFor(), or popWaitUntil() to wake and check the stack.

inline void notifyAll()

Notifies all waiting threads.

Notifies all threads waiting in wait(), waitFor(), waitUntil(), popWait(), popWaitFor(), or popWaitUntil() to wake and check the stack.