Class template stack

boost::lockfree::stack

Synopsis

// In header: <boost/lockfree/stack.hpp>

template<typename T, typename... Options> 
class stack {
public:
  // types
  typedef T                                 value_type;
  typedef implementation_defined::allocator allocator; 
  typedef implementation_defined::size_type size_type; 

  // public member functions
  bool is_lock_free(void) const;
  explicit stack(void);
  template<typename U, typename Enabler = std::enable_if< has_capacity > > 
    explicit stack(typename boost::allocator_rebind< node_allocator, U >::type const &);
  template<typename Enabler = std::enable_if< has_capacity > > 
    explicit stack(allocator const &);
  template<typename Enabler = std::enable_if< !has_capacity > > 
    explicit stack(size_type);
  stack(const stack &) = delete;
  stack & operator=(const stack &) = delete;
  stack(stack &&) = delete;
  stack & operator=(stack &&) = delete;
  template<typename U, typename Enabler = std::enable_if< !has_capacity > > 
    stack(size_type, 
          typename boost::allocator_rebind< node_allocator, U >::type const &);
  template<typename Enabler = std::enable_if< !has_capacity > > 
    stack(size_type, node_allocator const &);
  template<typename Enabler = std::enable_if< !has_capacity > > 
    void reserve(size_type);
  template<typename Enabler = std::enable_if< !has_capacity > > 
    void reserve_unsafe(size_type);
  ~stack(void);
  bool push(const T &);
  bool push(T &&);
  bool bounded_push(const T &);
  bool bounded_push(T &&);
  template<typename ConstIterator> 
    ConstIterator push(ConstIterator, ConstIterator);
  template<std::size_t Extent> size_type push(boost::span< const T, Extent >);
  template<typename ConstIterator> 
    ConstIterator bounded_push(ConstIterator, ConstIterator);
  template<std::size_t Extent> 
    size_type bounded_push(boost::span< const T, Extent >);
  bool unsynchronized_push(const T &);
  bool unsynchronized_push(T &&);
  template<typename ConstIterator> 
    ConstIterator unsynchronized_push(ConstIterator, ConstIterator);
  template<std::size_t Extent> 
    size_type unsynchronized_push(boost::span< const T, Extent >);
  bool pop(T &);
  template<typename U, 
           typename Enabler = std::enable_if< std::is_convertible< T, U >::value > > 
    bool pop(U &);
  std::optional< T > pop(uses_optional_t);
  template<typename U> std::optional< U > pop(uses_optional_t);
  bool unsynchronized_pop(T &);
  template<typename U, 
           typename Enabler = std::enable_if< std::is_convertible< T, U >::value > > 
    bool unsynchronized_pop(U &);
  template<typename Functor> bool consume_one(Functor &&);
  template<typename Functor> size_t consume_all(Functor &&);
  template<typename Functor> size_t consume_all_atomic(Functor &&);
  template<typename Functor> size_t consume_all_atomic_reversed(Functor &&);
  bool empty(void) const;
};

Description

The stack class provides a multi-writer/multi-reader stack, pushing and popping is lock-free, construction/destruction has to be synchronized. It uses a freelist for memory management, freed nodes are pushed to the freelist and not returned to the OS before the stack is destroyed.

Policies:

boost::lockfree::fixed_sized<>, defaults to boost::lockfree::fixed_sized<false>
Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior.
If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed by array indexing. This limits the possible size of the stack to the number of elements that can be addressed by the index type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way to achieve lock-freedom.
boost::lockfree::capacity<>, optional
If this template argument is passed to the options, the size of the stack is set at compile-time.
It this option implies fixed_sized<true>
boost::lockfree::allocator<>, defaults to boost::lockfree::allocator<std::allocator<void>>
Specifies the allocator that is used for the internal freelist

Requirements:

T must have a copy constructor or a move constructor

`stack` public member functions

bool is_lock_free(void) const;

	Warning
It only checks, if the top stack node and the freelist can be modified in a lock-free manner. On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics, there is no possibility to provide a completely accurate implementation, because one would need to test every internal node, which is impossible if further nodes will be allocated from the operating system.

Warning

It only checks, if the top stack node and the freelist can be modified in a lock-free manner. On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics, there is no possibility to provide a completely accurate implementation, because one would need to test every internal node, which is impossible if further nodes will be allocated from the operating system.

Returns:

true, if implementation is lock-free.

```
explicit stack(void);
```
Construct a fixed-sized stack

Requires:

Must specify a capacity<> argument

template<typename U, typename Enabler = std::enable_if< has_capacity > > 
  explicit stack(typename boost::allocator_rebind< node_allocator, U >::type const & alloc);

Construct a fixed-sized stack with a custom allocator

Requires:

Must specify a capacity<> argument

template<typename Enabler = std::enable_if< has_capacity > > 
  explicit stack(allocator const & alloc);

Construct a fixed-sized stack with a custom allocator

Requires:

Must specify a capacity<> argument

```
template<typename Enabler = std::enable_if< !has_capacity > > 
  explicit stack(size_type n);
```
Construct a variable-sized stack

Allocate n nodes initially for the freelist

Requires:

Must not specify a capacity<> argument
```
stack(const stack &) = delete;
```

stack & operator=(const stack &) = delete;

```
stack(stack &&) = delete;
```
```
stack & operator=(stack &&) = delete;
```

template<typename U, typename Enabler = std::enable_if< !has_capacity > > 
  stack(size_type n, 
        typename boost::allocator_rebind< node_allocator, U >::type const & alloc);

Construct a variable-sized stack with a custom allocator

Allocate n nodes initially for the freelist

Requires:

Must not specify a capacity<> argument

```
template<typename Enabler = std::enable_if< !has_capacity > > 
  stack(size_type n, node_allocator const & alloc);
```
Construct a variable-sized stack with a custom allocator

Allocate n nodes initially for the freelist

Requires:

Must not specify a capacity<> argument
```
template<typename Enabler = std::enable_if< !has_capacity > > 
  void reserve(size_type n);
```
Allocate n nodes for freelist

Note

thread-safe, may block if memory allocator blocks

Requires:

only valid if no capacity<> argument given
```
template<typename Enabler = std::enable_if< !has_capacity > > 
  void reserve_unsafe(size_type n);
```
Allocate n nodes for freelist

Note

not thread-safe, may block if memory allocator blocks

Requires:

only valid if no capacity<> argument given
```
~stack(void);
```
Destroys stack, free all nodes from freelist.

Note

not thread-safe
```
bool push(const T & v);
```
Pushes object t to the stack.

Note

Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.

Throws:
if memory allocator throws
```
bool push(T && v);
```
Pushes object t to the stack.

Note

Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.

Throws:
if memory allocator throws
```
bool bounded_push(const T & v);
```
Pushes object t to the stack.

Note

Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.
```
bool bounded_push(T && v);
```
Pushes object t to the stack.

Note

Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.
```
template<typename ConstIterator> 
  ConstIterator push(ConstIterator begin, ConstIterator end);
```
Pushes as many objects from the range [begin, end) as freelist node can be allocated.

Note

Operation is applied atomically

Note

Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Returns:

iterator to the first element, which has not been pushed

Throws:
if memory allocator throws
```
template<std::size_t Extent> size_type push(boost::span< const T, Extent > t);
```
Pushes as many objects from the span as freelist node can be allocated.

Note

Operation is applied atomically

Note

Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Returns:

Number of elements pushed

Throws:
if memory allocator throws
```
template<typename ConstIterator> 
  ConstIterator bounded_push(ConstIterator begin, ConstIterator end);
```
Pushes as many objects from the range [begin, end) as freelist node can be allocated.

Note

Operation is applied atomically

Note

Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail

Returns:

iterator to the first element, which has not been pushed

Throws:
if memory allocator throws
```
template<std::size_t Extent> 
  size_type bounded_push(boost::span< const T, Extent > t);
```
Pushes as many objects from the span as freelist node can be allocated.

Note

Operation is applied atomically

Note

Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail

Returns:

Number of elements pushed

Throws:
if memory allocator throws
```
bool unsynchronized_push(const T & v);
```
Pushes object t to the stack.

Note

Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.

Throws:
if memory allocator throws
```
bool unsynchronized_push(T && v);
```
Pushes object t to the stack.

Note

Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Postconditions:

object will be pushed to the stack, if internal node can be allocated

Returns:

true, if the push operation is successful.

Throws:
if memory allocator throws
```
template<typename ConstIterator> 
  ConstIterator unsynchronized_push(ConstIterator begin, ConstIterator end);
```
Pushes as many objects from the range [begin, end) as freelist node can be allocated.

Note

Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Returns:

iterator to the first element, which has not been pushed

Throws:
if memory allocator throws
```
template<std::size_t Extent> 
  size_type unsynchronized_push(boost::span< const T, Extent > t);
```
Pushes as many objects from the span as freelist node can be allocated.

Note

Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Returns:

iterator to the first element, which has not been pushed

Throws:
if memory allocator throws
```
bool pop(T & ret);
```
Pops object from stack.

Note

Thread-safe and non-blocking

Postconditions:

if pop operation is successful, object will be copied to ret.

Returns:

true, if the pop operation is successful, false if stack was empty.

template<typename U, 
         typename Enabler = std::enable_if< std::is_convertible< T, U >::value > > 
  bool pop(U & ret);

Pops object from stack.

	Note
	Thread-safe and non-blocking

Requires:	type T must be convertible to U
Postconditions:	if pop operation is successful, object will be copied to ret.
Returns:	true, if the pop operation is successful, false if stack was empty.

```
std::optional< T > pop(uses_optional_t);
```
Pops object from stack, returning a std::optional<>

Note

Thread-safe and non-blocking

Returns:

std::optional with value if successful, std::nullopt if stack is empty.
```
template<typename U> std::optional< U > pop(uses_optional_t);
```
Pops object from stack, returning a std::optional<>

Note

Thread-safe and non-blocking

Requires:

type T must be convertible to U

Returns:

std::optional with value if successful, std::nullopt if stack is empty.
```
bool unsynchronized_pop(T & ret);
```
Pops object from stack.

Note

Not thread-safe, but non-blocking

Postconditions:

if pop operation is successful, object will be copied to ret.

Returns:

true, if the pop operation is successful, false if stack was empty.

template<typename U, 
         typename Enabler = std::enable_if< std::is_convertible< T, U >::value > > 
  bool unsynchronized_pop(U & ret);

Pops object from stack.

	Note
	Not thread-safe, but non-blocking

Requires:	type T must be convertible to U
Postconditions:	if pop operation is successful, object will be copied to ret.
Returns:	true, if the pop operation is successful, false if stack was empty.

```
template<typename Functor> bool consume_one(Functor && f);
```
consumes one element via a functor

pops one element from the stack and applies the functor on this object

Note

Thread-safe and non-blocking, if functor is thread-safe and non-blocking

Returns:

true, if one element was consumed
```
template<typename Functor> size_t consume_all(Functor && f);
```
consumes all elements via a functor

sequentially pops all elements from the stack and applies the functor on each object

Note

Thread-safe and non-blocking, if functor is thread-safe and non-blocking

Returns:

number of elements that are consumed
```
template<typename Functor> size_t consume_all_atomic(Functor && f);
```
consumes all elements via a functor

atomically pops all elements from the stack and applies the functor on each object

Note

Thread-safe and non-blocking, if functor is thread-safe and non-blocking

Returns:

number of elements that are consumed
```
template<typename Functor> size_t consume_all_atomic_reversed(Functor && f);
```
consumes all elements via a functor

atomically pops all elements from the stack and applies the functor on each object in reversed order

Note

Thread-safe and non-blocking, if functor is thread-safe and non-blocking

Returns:

number of elements that are consumed

bool empty(void) const;

	Note
	It only guarantees that at some point during the execution of the function the stack has been empty. It is rarely practical to use this value in program logic, because the stack can be modified by other threads.

Returns:

true, if stack is empty.

	Note
	Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

Postconditions:	object will be pushed to the stack, if internal node can be allocated
Returns:	true, if the push operation is successful.
Throws:	if memory allocator throws

	Note
	Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail

Returns:	iterator to the first element, which has not been pushed
Throws:	if memory allocator throws

Returns:	Number of elements pushed
Throws:	if memory allocator throws

	Note
	Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

	Note
	Thread-safe and non-blocking, if functor is thread-safe and non-blocking

	Note
	Operation is applied atomically

	Note
	Operation is applied atomically

	Note
	Operation is applied atomically

	Note
	Operation is applied atomically

Boost C++ Libraries