Chris@16: //  Copyright (C) 2008-2013 Tim Blechmann
Chris@16: //
Chris@16: //  Distributed under the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
Chris@16: #define BOOST_LOCKFREE_STACK_HPP_INCLUDED
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/checked_delete.hpp>
Chris@16: #include <boost/integer_traits.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/type_traits/has_trivial_assign.hpp>
Chris@16: #include <boost/type_traits/has_trivial_destructor.hpp>
Chris@16: 
Chris@16: #include <boost/lockfree/detail/atomic.hpp>
Chris@16: #include <boost/lockfree/detail/copy_payload.hpp>
Chris@16: #include <boost/lockfree/detail/freelist.hpp>
Chris@16: #include <boost/lockfree/detail/parameter.hpp>
Chris@16: #include <boost/lockfree/detail/tagged_ptr.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101: #pragma once
Chris@101: #endif
Chris@101: 
Chris@16: namespace boost    {
Chris@16: namespace lockfree {
Chris@16: namespace detail   {
Chris@16: 
Chris@16: typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
Chris@16:                               boost::parameter::optional<tag::capacity>
Chris@16:                              > stack_signature;
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: /** The stack class provides a multi-writer/multi-reader stack, pushing and popping is lock-free,
Chris@16:  *  construction/destruction has to be synchronized. It uses a freelist for memory management,
Chris@16:  *  freed nodes are pushed to the freelist and not returned to the OS before the stack is destroyed.
Chris@16:  *
Chris@16:  *  \b Policies:
Chris@16:  *
Chris@16:  *  - \c boost::lockfree::fixed_sized<>, defaults to \c boost::lockfree::fixed_sized<false> <br>
Chris@16:  *    Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior.<br>
Chris@16:  *    If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed
Chris@16:  *    by array indexing. This limits the possible size of the stack to the number of elements that can be addressed by the index
Chris@16:  *    type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way
Chris@16:  *    to achieve lock-freedom.
Chris@16:  *
Chris@16:  *  - \c boost::lockfree::capacity<>, optional <br>
Chris@16:  *    If this template argument is passed to the options, the size of the stack is set at compile-time. <br>
Chris@16:  *    It this option implies \c fixed_sized<true>
Chris@16:  *
Chris@16:  *  - \c boost::lockfree::allocator<>, defaults to \c boost::lockfree::allocator<std::allocator<void>> <br>
Chris@16:  *    Specifies the allocator that is used for the internal freelist
Chris@16:  *
Chris@16:  *  \b Requirements:
Chris@16:  *  - T must have a copy constructor
Chris@16:  * */
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16: template <typename T,
Chris@16:           class A0 = boost::parameter::void_,
Chris@16:           class A1 = boost::parameter::void_,
Chris@16:           class A2 = boost::parameter::void_>
Chris@16: #else
Chris@16: template <typename T, ...Options>
Chris@16: #endif
Chris@16: class stack
Chris@16: {
Chris@16: private:
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16:     BOOST_STATIC_ASSERT(boost::has_trivial_assign<T>::value);
Chris@16:     BOOST_STATIC_ASSERT(boost::has_trivial_destructor<T>::value);
Chris@16: 
Chris@16:     typedef typename detail::stack_signature::bind<A0, A1, A2>::type bound_args;
Chris@16: 
Chris@16:     static const bool has_capacity = detail::extract_capacity<bound_args>::has_capacity;
Chris@16:     static const size_t capacity = detail::extract_capacity<bound_args>::capacity;
Chris@16:     static const bool fixed_sized = detail::extract_fixed_sized<bound_args>::value;
Chris@16:     static const bool node_based = !(has_capacity || fixed_sized);
Chris@16:     static const bool compile_time_sized = has_capacity;
Chris@16: 
Chris@16:     struct node
Chris@16:     {
Chris@16:         node(T const & val):
Chris@16:             v(val)
Chris@16:         {}
Chris@16: 
Chris@16:         typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_t;
Chris@16:         handle_t next;
Chris@16:         const T v;
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename detail::extract_allocator<bound_args, node>::type node_allocator;
Chris@16:     typedef typename detail::select_freelist<node, node_allocator, compile_time_sized, fixed_sized, capacity>::type pool_t;
Chris@16:     typedef typename pool_t::tagged_node_handle tagged_node_handle;
Chris@16: 
Chris@16:     // check compile-time capacity
Chris@16:     BOOST_STATIC_ASSERT((mpl::if_c<has_capacity,
Chris@16:                                    mpl::bool_<capacity - 1 < boost::integer_traits<boost::uint16_t>::const_max>,
Chris@16:                                    mpl::true_
Chris@16:                                   >::type::value));
Chris@16: 
Chris@16:     struct implementation_defined
Chris@16:     {
Chris@16:         typedef node_allocator allocator;
Chris@16:         typedef std::size_t size_type;
Chris@16:     };
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@101:     BOOST_DELETED_FUNCTION(stack(stack const&))
Chris@101:     BOOST_DELETED_FUNCTION(stack& operator= (stack const&))
Chris@16: 
Chris@16: public:
Chris@16:     typedef T value_type;
Chris@16:     typedef typename implementation_defined::allocator allocator;
Chris@16:     typedef typename implementation_defined::size_type size_type;
Chris@16: 
Chris@16:     /**
Chris@16:      * \return true, if implementation is lock-free.
Chris@16:      *
Chris@16:      * \warning It only checks, if the top stack node and the freelist can be modified in a lock-free manner.
Chris@16:      *          On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics,
Chris@16:      *          there is no possibility to provide a completely accurate implementation, because one would need to test
Chris@16:      *          every internal node, which is impossible if further nodes will be allocated from the operating system.
Chris@16:      *
Chris@16:      * */
Chris@16:     bool is_lock_free (void) const
Chris@16:     {
Chris@16:         return tos.is_lock_free() && pool.is_lock_free();
Chris@16:     }
Chris@16: 
Chris@16:     //! Construct stack
Chris@16:     // @{
Chris@16:     stack(void):
Chris@16:         pool(node_allocator(), capacity)
Chris@16:     {
Chris@16:         BOOST_ASSERT(has_capacity);
Chris@16:         initialize();
Chris@16:     }
Chris@16: 
Chris@16:     template <typename U>
Chris@16:     explicit stack(typename node_allocator::template rebind<U>::other const & alloc):
Chris@16:         pool(alloc, capacity)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(has_capacity);
Chris@16:         initialize();
Chris@16:     }
Chris@16: 
Chris@16:     explicit stack(allocator const & alloc):
Chris@16:         pool(alloc, capacity)
Chris@16:     {
Chris@16:         BOOST_ASSERT(has_capacity);
Chris@16:         initialize();
Chris@16:     }
Chris@16:     // @}
Chris@16: 
Chris@16:     //! Construct stack, allocate n nodes for the freelist.
Chris@16:     // @{
Chris@16:     explicit stack(size_type n):
Chris@16:         pool(node_allocator(), n)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!has_capacity);
Chris@16:         initialize();
Chris@16:     }
Chris@16: 
Chris@16:     template <typename U>
Chris@16:     stack(size_type n, typename node_allocator::template rebind<U>::other const & alloc):
Chris@16:         pool(alloc, n)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(!has_capacity);
Chris@16:         initialize();
Chris@16:     }
Chris@16:     // @}
Chris@16: 
Chris@16:     /** Allocate n nodes for freelist
Chris@16:      *
Chris@16:      *  \pre  only valid if no capacity<> argument given
Chris@16:      *  \note thread-safe, may block if memory allocator blocks
Chris@16:      *
Chris@16:      * */
Chris@16:     void reserve(size_type n)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(!has_capacity);
Chris@16:         pool.template reserve<true>(n);
Chris@16:     }
Chris@16: 
Chris@16:     /** Allocate n nodes for freelist
Chris@16:      *
Chris@16:      *  \pre  only valid if no capacity<> argument given
Chris@16:      *  \note not thread-safe, may block if memory allocator blocks
Chris@16:      *
Chris@16:      * */
Chris@16:     void reserve_unsafe(size_type n)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(!has_capacity);
Chris@16:         pool.template reserve<false>(n);
Chris@16:     }
Chris@16: 
Chris@16:     /** Destroys stack, free all nodes from freelist.
Chris@16:      *
Chris@16:      *  \note not thread-safe
Chris@16:      *
Chris@16:      * */
Chris@16:     ~stack(void)
Chris@16:     {
Chris@16:         T dummy;
Chris@16:         while(unsynchronized_pop(dummy))
Chris@16:         {}
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16:     void initialize(void)
Chris@16:     {
Chris@16:         tos.store(tagged_node_handle(pool.null_handle(), 0));
Chris@16:     }
Chris@16: 
Chris@16:     void link_nodes_atomic(node * new_top_node, node * end_node)
Chris@16:     {
Chris@16:         tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
Chris@16:         for (;;) {
Chris@16:             tagged_node_handle new_tos (pool.get_handle(new_top_node), old_tos.get_tag());
Chris@16:             end_node->next = pool.get_handle(old_tos);
Chris@16: 
Chris@16:             if (tos.compare_exchange_weak(old_tos, new_tos))
Chris@16:                 break;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void link_nodes_unsafe(node * new_top_node, node * end_node)
Chris@16:     {
Chris@16:         tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
Chris@16: 
Chris@16:         tagged_node_handle new_tos (pool.get_handle(new_top_node), old_tos.get_tag());
Chris@16:         end_node->next = pool.get_pointer(old_tos);
Chris@16: 
Chris@16:         tos.store(new_tos, memory_order_relaxed);
Chris@16:     }
Chris@16: 
Chris@16:     template <bool Threadsafe, bool Bounded, typename ConstIterator>
Chris@16:     tuple<node*, node*> prepare_node_list(ConstIterator begin, ConstIterator end, ConstIterator & ret)
Chris@16:     {
Chris@16:         ConstIterator it = begin;
Chris@16:         node * end_node = pool.template construct<Threadsafe, Bounded>(*it++);
Chris@16:         if (end_node == NULL) {
Chris@16:             ret = begin;
Chris@16:             return make_tuple<node*, node*>(NULL, NULL);
Chris@16:         }
Chris@16: 
Chris@16:         node * new_top_node = end_node;
Chris@16:         end_node->next = NULL;
Chris@16: 
Chris@16:         try {
Chris@16:             /* link nodes */
Chris@16:             for (; it != end; ++it) {
Chris@16:                 node * newnode = pool.template construct<Threadsafe, Bounded>(*it);
Chris@16:                 if (newnode == NULL)
Chris@16:                     break;
Chris@16:                 newnode->next = new_top_node;
Chris@16:                 new_top_node = newnode;
Chris@16:             }
Chris@16:         } catch (...) {
Chris@16:             for (node * current_node = new_top_node; current_node != NULL;) {
Chris@16:                 node * next = current_node->next;
Chris@16:                 pool.template destruct<Threadsafe>(current_node);
Chris@16:                 current_node = next;
Chris@16:             }
Chris@16:             throw;
Chris@16:         }
Chris@16:         ret = it;
Chris@16:         return make_tuple(new_top_node, end_node);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16: public:
Chris@16:     /** Pushes object t to the stack.
Chris@16:      *
Chris@16:      * \post object will be pushed to the stack, if internal node can be allocated
Chris@16:      * \returns true, if the push operation is successful.
Chris@16:      *
Chris@16:      * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
Chris@16:      *                    from the OS. This may not be lock-free.
Chris@16:      * \throws if memory allocator throws
Chris@16:      * */
Chris@16:     bool push(T const & v)
Chris@16:     {
Chris@16:         return do_push<false>(v);
Chris@16:     }
Chris@16: 
Chris@16:     /** Pushes object t to the stack.
Chris@16:      *
Chris@16:      * \post object will be pushed to the stack, if internal node can be allocated
Chris@16:      * \returns true, if the push operation is successful.
Chris@16:      *
Chris@16:      * \note Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail
Chris@16:      * */
Chris@16:     bool bounded_push(T const & v)
Chris@16:     {
Chris@16:         return do_push<true>(v);
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16: private:
Chris@16:     template <bool Bounded>
Chris@16:     bool do_push(T const & v)
Chris@16:     {
Chris@16:         node * newnode = pool.template construct<true, Bounded>(v);
Chris@16:         if (newnode == 0)
Chris@16:             return false;
Chris@16: 
Chris@16:         link_nodes_atomic(newnode, newnode);
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool Bounded, typename ConstIterator>
Chris@16:     ConstIterator do_push(ConstIterator begin, ConstIterator end)
Chris@16:     {
Chris@16:         node * new_top_node;
Chris@16:         node * end_node;
Chris@16:         ConstIterator ret;
Chris@16: 
Chris@16:         tie(new_top_node, end_node) = prepare_node_list<true, Bounded>(begin, end, ret);
Chris@16:         if (new_top_node)
Chris@16:             link_nodes_atomic(new_top_node, end_node);
Chris@16: 
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16: #endif
Chris@16: 
Chris@16:     /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
Chris@16:      *
Chris@16:      * \return iterator to the first element, which has not been pushed
Chris@16:      *
Chris@16:      * \note Operation is applied atomically
Chris@16:      * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
Chris@16:      *                    from the OS. This may not be lock-free.
Chris@16:      * \throws if memory allocator throws
Chris@16:      */
Chris@16:     template <typename ConstIterator>
Chris@16:     ConstIterator push(ConstIterator begin, ConstIterator end)
Chris@16:     {
Chris@16:         return do_push<false, ConstIterator>(begin, end);
Chris@16:     }
Chris@16: 
Chris@16:     /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
Chris@16:      *
Chris@16:      * \return iterator to the first element, which has not been pushed
Chris@16:      *
Chris@16:      * \note Operation is applied atomically
Chris@16:      * \note Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail
Chris@16:      * \throws if memory allocator throws
Chris@16:      */
Chris@16:     template <typename ConstIterator>
Chris@16:     ConstIterator bounded_push(ConstIterator begin, ConstIterator end)
Chris@16:     {
Chris@16:         return do_push<true, ConstIterator>(begin, end);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     /** Pushes object t to the stack.
Chris@16:      *
Chris@16:      * \post object will be pushed to the stack, if internal node can be allocated
Chris@16:      * \returns true, if the push operation is successful.
Chris@16:      *
Chris@16:      * \note Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
Chris@16:      *       from the OS. This may not be lock-free.
Chris@16:      * \throws if memory allocator throws
Chris@16:      * */
Chris@16:     bool unsynchronized_push(T const & v)
Chris@16:     {
Chris@16:         node * newnode = pool.template construct<false, false>(v);
Chris@16:         if (newnode == 0)
Chris@16:             return false;
Chris@16: 
Chris@16:         link_nodes_unsafe(newnode, newnode);
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
Chris@16:      *
Chris@16:      * \return iterator to the first element, which has not been pushed
Chris@16:      *
Chris@16:      * \note Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
Chris@16:      *       from the OS. This may not be lock-free.
Chris@16:      * \throws if memory allocator throws
Chris@16:      */
Chris@16:     template <typename ConstIterator>
Chris@16:     ConstIterator unsynchronized_push(ConstIterator begin, ConstIterator end)
Chris@16:     {
Chris@16:         node * new_top_node;
Chris@16:         node * end_node;
Chris@16:         ConstIterator ret;
Chris@16: 
Chris@16:         tie(new_top_node, end_node) = prepare_node_list<false, false>(begin, end, ret);
Chris@16:         if (new_top_node)
Chris@16:             link_nodes_unsafe(new_top_node, end_node);
Chris@16: 
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     /** Pops object from stack.
Chris@16:      *
Chris@16:      * \post if pop operation is successful, object will be copied to ret.
Chris@16:      * \returns true, if the pop operation is successful, false if stack was empty.
Chris@16:      *
Chris@16:      * \note Thread-safe and non-blocking
Chris@16:      *
Chris@16:      * */
Chris@16:     bool pop(T & ret)
Chris@16:     {
Chris@16:         return pop<T>(ret);
Chris@16:     }
Chris@16: 
Chris@16:     /** Pops object from stack.
Chris@16:      *
Chris@16:      * \pre type T must be convertible to U
Chris@16:      * \post if pop operation is successful, object will be copied to ret.
Chris@16:      * \returns true, if the pop operation is successful, false if stack was empty.
Chris@16:      *
Chris@16:      * \note Thread-safe and non-blocking
Chris@16:      *
Chris@16:      * */
Chris@16:     template <typename U>
Chris@16:     bool pop(U & ret)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT((boost::is_convertible<T, U>::value));
Chris@16:         detail::consume_via_copy<U> consumer(ret);
Chris@16: 
Chris@16:         return consume_one(consumer);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     /** Pops object from stack.
Chris@16:      *
Chris@16:      * \post if pop operation is successful, object will be copied to ret.
Chris@16:      * \returns true, if the pop operation is successful, false if stack was empty.
Chris@16:      *
Chris@16:      * \note Not thread-safe, but non-blocking
Chris@16:      *
Chris@16:      * */
Chris@16:     bool unsynchronized_pop(T & ret)
Chris@16:     {
Chris@16:         return unsynchronized_pop<T>(ret);
Chris@16:     }
Chris@16: 
Chris@16:     /** Pops object from stack.
Chris@16:      *
Chris@16:      * \pre type T must be convertible to U
Chris@16:      * \post if pop operation is successful, object will be copied to ret.
Chris@16:      * \returns true, if the pop operation is successful, false if stack was empty.
Chris@16:      *
Chris@16:      * \note Not thread-safe, but non-blocking
Chris@16:      *
Chris@16:      * */
Chris@16:     template <typename U>
Chris@16:     bool unsynchronized_pop(U & ret)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT((boost::is_convertible<T, U>::value));
Chris@16:         tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
Chris@16:         node * old_tos_pointer = pool.get_pointer(old_tos);
Chris@16: 
Chris@16:         if (!pool.get_pointer(old_tos))
Chris@16:             return false;
Chris@16: 
Chris@16:         node * new_tos_ptr = pool.get_pointer(old_tos_pointer->next);
Chris@16:         tagged_node_handle new_tos(pool.get_handle(new_tos_ptr), old_tos.get_next_tag());
Chris@16: 
Chris@16:         tos.store(new_tos, memory_order_relaxed);
Chris@16:         detail::copy_payload(old_tos_pointer->v, ret);
Chris@16:         pool.template destruct<false>(old_tos);
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     /** consumes one element via a functor
Chris@16:      *
Chris@16:      *  pops one element from the stack and applies the functor on this object
Chris@16:      *
Chris@16:      * \returns true, if one element was consumed
Chris@16:      *
Chris@16:      * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
Chris@16:      * */
Chris@16:     template <typename Functor>
Chris@16:     bool consume_one(Functor & f)
Chris@16:     {
Chris@16:         tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
Chris@16: 
Chris@16:         for (;;) {
Chris@16:             node * old_tos_pointer = pool.get_pointer(old_tos);
Chris@16:             if (!old_tos_pointer)
Chris@16:                 return false;
Chris@16: 
Chris@16:             tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
Chris@16: 
Chris@16:             if (tos.compare_exchange_weak(old_tos, new_tos)) {
Chris@16:                 f(old_tos_pointer->v);
Chris@16:                 pool.template destruct<true>(old_tos);
Chris@16:                 return true;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::lockfree::stack::consume_one(Functor & rhs)
Chris@16:     template <typename Functor>
Chris@16:     bool consume_one(Functor const & f)
Chris@16:     {
Chris@16:         tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
Chris@16: 
Chris@16:         for (;;) {
Chris@16:             node * old_tos_pointer = pool.get_pointer(old_tos);
Chris@16:             if (!old_tos_pointer)
Chris@16:                 return false;
Chris@16: 
Chris@16:             tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
Chris@16: 
Chris@16:             if (tos.compare_exchange_weak(old_tos, new_tos)) {
Chris@16:                 f(old_tos_pointer->v);
Chris@16:                 pool.template destruct<true>(old_tos);
Chris@16:                 return true;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     /** consumes all elements via a functor
Chris@16:      *
Chris@16:      * sequentially pops all elements from the stack and applies the functor on each object
Chris@16:      *
Chris@16:      * \returns number of elements that are consumed
Chris@16:      *
Chris@16:      * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
Chris@16:      * */
Chris@16:     template <typename Functor>
Chris@16:     size_t consume_all(Functor & f)
Chris@16:     {
Chris@16:         size_t element_count = 0;
Chris@16:         while (consume_one(f))
Chris@16:             element_count += 1;
Chris@16: 
Chris@16:         return element_count;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::lockfree::stack::consume_all(Functor & rhs)
Chris@16:     template <typename Functor>
Chris@16:     size_t consume_all(Functor const & f)
Chris@16:     {
Chris@16:         size_t element_count = 0;
Chris@16:         while (consume_one(f))
Chris@16:             element_count += 1;
Chris@16: 
Chris@16:         return element_count;
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \return true, if stack is empty.
Chris@16:      *
Chris@16:      * \note It only guarantees that at some point during the execution of the function the stack has been empty.
Chris@16:      *       It is rarely practical to use this value in program logic, because the stack can be modified by other threads.
Chris@16:      * */
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return pool.get_pointer(tos.load()) == NULL;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16:     detail::atomic<tagged_node_handle> tos;
Chris@16: 
Chris@16:     static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(tagged_node_handle);
Chris@16:     char padding[padding_size];
Chris@16: 
Chris@16:     pool_t pool;
Chris@16: #endif
Chris@16: };
Chris@16: 
Chris@16: } /* namespace lockfree */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */