1 // Copyright (C) 2008 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/checked_delete.hpp>
14 #include <boost/static_assert.hpp>
15 #include <boost/type_traits/is_base_of.hpp>
17 #include <boost/lockfree/detail/tagged_ptr.hpp>
18 #include <boost/lockfree/detail/freelist.hpp>
19 #include <boost/noncopyable.hpp>
27 typename freelist_t
= caching_freelist_t
,
28 typename Alloc
= std::allocator
<T
>
35 typedef tagged_ptr
<node
> tagged_ptr_t
;
45 typedef tagged_ptr
<node
> ptr_type
;
47 typedef typename
Alloc::template rebind
<node
>::other node_allocator
;
48 /* typedef typename detail::select_freelist<node, node_allocator, freelist_t>::type pool_t; */
50 typedef typename
boost::mpl::if_
<boost::is_same
<freelist_t
, caching_freelist_t
>,
51 caching_freelist
<node
, node_allocator
>,
52 static_freelist
<node
, node_allocator
>
56 static const bool is_lockfree
= node::tagged_ptr_t::is_lockfree
;
62 explicit stack(std::size_t n
):
66 bool push(T
const & v
)
68 node
* newnode
= alloc_node(v
);
77 newnode
->next
.set_ptr(old_tos
.get_ptr());
79 while (!tos
.cas(old_tos
, newnode
));
88 ptr_type
old_tos(tos
);
92 read_memory_barrier();
94 node
* new_tos
= old_tos
->next
.get_ptr();
96 if (tos
.cas(old_tos
, new_tos
))
99 dealloc_node(old_tos
.get_ptr());
105 bool empty(void) const
107 return tos
.get_ptr() == NULL
;
111 node
* alloc_node(T
const & t
)
113 node
* chunk
= pool
.allocate();
118 void dealloc_node(node
* n
)
124 volatile ptr_type tos
;
126 static const int padding_size
= 64 - sizeof(ptr_type
); /* cache lines on current cpus seem to
128 char padding
[padding_size
];
134 } /* namespace lockfree */
135 } /* namespace boost */
137 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */