...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::lockfree::stack
// In header: <boost/lockfree/stack.hpp> template<typename T, typename A0, typename A1, typename A2> class stack { public: // member classes/structs/unions template<typename T, typename A0, typename A1, typename A2> struct implementation_defined { // types typedef node_allocator allocator; typedef std::size_t size_type; }; template<typename T, typename A0, typename A1, typename A2> struct node { // types typedef unspecified handle_t; // construct/copy/destruct node(T const &); // public data members handle_t next; const T v; }; // construct/copy/destruct stack(void); template<typename U> explicit stack(typename boost::allocator_rebind< node_allocator, U >::type const &); explicit stack(allocator const &); explicit stack(size_type); template<typename U> stack(size_type, typename boost::allocator_rebind< node_allocator, U >::type const &); ~stack(void); // private member functions BOOST_STATIC_ASSERT(boost::is_copy_constructible< T >::value); BOOST_STATIC_ASSERT((mpl::if_c< has_capacity, mpl::bool_< capacity - 1< boost::integer_traits< boost::uint16_t >::const_max >, mpl::true_ >::type::value)); BOOST_DELETED_FUNCTION(stack(stack const &)); bool is_lock_free(void) const; void reserve(size_type); void reserve_unsafe(size_type); void initialize(void); void link_nodes_atomic(node *, node *); void link_nodes_unsafe(node *, node *); template<bool Threadsafe, bool Bounded, typename ConstIterator> tuple< node *, node * > prepare_node_list(ConstIterator, ConstIterator, ConstIterator &); template<bool Bounded> bool do_push(T const &); template<bool Bounded, typename ConstIterator> ConstIterator do_push(ConstIterator, ConstIterator); // public member functions bool push(T const &); bool bounded_push(T const &); template<typename ConstIterator> ConstIterator push(ConstIterator, ConstIterator); template<typename ConstIterator> ConstIterator bounded_push(ConstIterator, ConstIterator); bool unsynchronized_push(T const &); template<typename ConstIterator> ConstIterator unsynchronized_push(ConstIterator, ConstIterator); bool pop(T &); template<typename U> bool pop(U &); bool unsynchronized_pop(T &); template<typename U> bool unsynchronized_pop(U &); template<typename Functor> bool consume_one(Functor &); template<typename Functor> bool consume_one(Functor const &); template<typename Functor> size_t consume_all(Functor &); template<typename Functor> size_t consume_all(Functor const &); template<typename Functor> size_t consume_all_atomic(Functor &); template<typename Functor> size_t consume_all_atomic(Functor const &); template<typename Functor> size_t consume_all_atomic_reversed(Functor &); template<typename Functor> size_t consume_all_atomic_reversed(Functor const &); bool empty(void) const; };
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
stack
public
construct/copy/destructstack(void);
Construct a fixed-sized stack
Requires: |
Must specify a capacity<> argument |
template<typename U> 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 |
explicit stack(allocator const & alloc);
Construct a fixed-sized stack with a custom allocator
Requires: |
Must specify a capacity<> argument |
explicit stack(size_type n);
Construct a variable-sized stack
Allocate n nodes initially for the freelist
Requires: |
Must not specify a capacity<> argument |
template<typename U> 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 |
~stack(void);
Destroys stack, free all nodes from freelist.
Note | |
---|---|
not thread-safe |
stack
private member functionsBOOST_STATIC_ASSERT(boost::is_copy_constructible< T >::value);
BOOST_STATIC_ASSERT((mpl::if_c< has_capacity, mpl::bool_< capacity - 1< boost::integer_traits< boost::uint16_t >::const_max >, mpl::true_ >::type::value));
BOOST_DELETED_FUNCTION(stack(stack const &));
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. |
Returns: |
true, if implementation is lock-free. |
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 |
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 |
void initialize(void);
void link_nodes_atomic(node * new_top_node, node * end_node);
void link_nodes_unsafe(node * new_top_node, node * end_node);
template<bool Threadsafe, bool Bounded, typename ConstIterator> tuple< node *, node * > prepare_node_list(ConstIterator begin, ConstIterator end, ConstIterator & ret);
template<bool Bounded> bool do_push(T const & v);
template<bool Bounded, typename ConstIterator> ConstIterator do_push(ConstIterator begin, ConstIterator end);
stack
public member functionsbool push(T const & 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(T const & 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<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 |
bool unsynchronized_push(T const & 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 |
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> 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. |
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> 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> bool consume_one(Functor const & 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(Functor const & 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(Functor const & 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 |
template<typename Functor> size_t consume_all_atomic_reversed(Functor const & 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. |