1 // Copyright (C) 2008, 2009, 2010, 2011 Tim Blechmann
3 // Distributed under the Boost Software License, Version 1.0. (See
4 // accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 // Disclaimer: Not a Boost library.
9 #ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
10 #define BOOST_LOCKFREE_STACK_HPP_INCLUDED
12 #include <boost/lockfree/detail/atomic.hpp>
13 #include <boost/checked_delete.hpp>
15 #include <boost/static_assert.hpp>
16 #include <boost/type_traits/is_base_of.hpp>
18 #include <boost/lockfree/detail/tagged_ptr.hpp>
19 #include <boost/lockfree/detail/freelist.hpp>
20 #include <boost/noncopyable.hpp>
29 /** It uses a freelist for memory management, freed nodes are pushed to the freelist and not returned to
30 * the os before the stack is destroyed.
32 * The memory management of the stack can be controlled via its freelist_t template argument. Two different
33 * freelists can be used. struct caching_freelist_t selects a caching freelist, which can allocate more nodes
34 * from the operating system, and struct static_freelist_t uses a fixed-sized freelist. With a fixed-sized
35 * freelist, the push operation may fail, while with a caching freelist, the push operation may block.
39 typename freelist_t
= caching_freelist_t
,
40 typename Alloc
= std::allocator
<T
>
46 #ifndef BOOST_DOXYGEN_INVOKED
49 typedef detail::tagged_ptr
<node
> tagged_node_ptr
;
60 typedef detail::tagged_ptr
<node
> tagged_node_ptr
;
62 typedef typename
Alloc::template rebind
<node
>::other node_allocator
;
64 typedef typename
boost::mpl::if_
<boost::is_same
<freelist_t
, caching_freelist_t
>,
65 detail::freelist_stack
<node
, true, node_allocator
>,
66 detail::freelist_stack
<node
, false, node_allocator
>
71 * \return true, if implementation is lock-free.
73 bool is_lock_free (void) const
75 return tos
.is_lock_free() && pool
.is_lock_free();
80 tos(tagged_node_ptr(NULL
, 0))
83 //! Construct stack, allocate n nodes for the freelist
84 explicit stack(std::size_t n
):
85 tos(tagged_node_ptr(NULL
, 0))
90 //! Allocate n nodes for freelist
91 void reserve(std::size_t n
)
96 /** Destroys stack, free all nodes from freelist.
98 * \warning not threadsafe
110 /** Pushes object t to the fifo. May fail, if the freelist is not able to allocate a new fifo node.
112 * \returns true, if the push operation is successful.
114 * \note Thread-safe and non-blocking
115 * \warning \b Warning: May block if node needs to be allocated from the operating system
117 bool push(T
const & v
)
119 node
* newnode
= pool
.construct(v
);
124 tagged_node_ptr old_tos
= tos
.load(detail::memory_order_relaxed
);
127 tagged_node_ptr
new_tos (newnode
, old_tos
.get_tag());
128 newnode
->next
.set_ptr(old_tos
.get_ptr());
130 if (tos
.compare_exchange_weak(old_tos
, new_tos
))
135 /** Pops object from stack.
137 * If pop operation is successful, object is written to memory location denoted by ret.
139 * \returns true, if the pop operation is successful, false if stack was empty.
141 * \note Thread-safe and non-blocking
146 tagged_node_ptr old_tos
= tos
.load(detail::memory_order_consume
);
149 if (!old_tos
.get_ptr())
152 node
* new_tos_ptr
= old_tos
->next
.get_ptr();
153 tagged_node_ptr
new_tos(new_tos_ptr
, old_tos
.get_tag() + 1);
155 if (tos
.compare_exchange_weak(old_tos
, new_tos
)) {
157 pool
.destruct(old_tos
.get_ptr());
164 * \return true, if stack is empty.
166 * \warning The state of the stack can be modified by other threads
169 bool empty(void) const
171 return tos
.load().get_ptr() == NULL
;
175 #ifndef BOOST_DOXYGEN_INVOKED
176 detail::atomic
<tagged_node_ptr
> tos
;
178 static const int padding_size
= BOOST_LOCKFREE_CACHELINE_BYTES
- sizeof(tagged_node_ptr
);
179 char padding
[padding_size
];
186 } /* namespace lockfree */
187 } /* namespace boost */
189 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */