pion-net  4.0.9
stack.hpp
1 // Copyright (C) 2008 Tim Blechmann
2 //
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)
6 
7 // Disclaimer: Not a Boost library.
8 
9 #ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
10 #define BOOST_LOCKFREE_STACK_HPP_INCLUDED
11 
12 #include <boost/checked_delete.hpp>
13 
14 #include <boost/static_assert.hpp>
15 #include <boost/type_traits/is_base_of.hpp>
16 
17 #include <boost/lockfree/detail/tagged_ptr.hpp>
18 #include <boost/lockfree/detail/freelist.hpp>
19 #include <boost/noncopyable.hpp>
20 
21 
22 namespace boost
23 {
24 namespace lockfree
25 {
26 template <typename T,
27  typename freelist_t = caching_freelist_t,
28  typename Alloc = std::allocator<T>
29  >
30 class stack:
31  boost::noncopyable
32 {
33  struct node
34  {
35  node(T const & v):
36  v(v)
37  {}
38 
39  tagged_ptr<node> next;
40  T v;
41  };
42 
43  typedef tagged_ptr<node> ptr_type;
44 
45  typedef typename Alloc::template rebind<node>::other node_allocator;
46 /* typedef typename detail::select_freelist<node, node_allocator, freelist_t>::type pool_t; */
47 
48  typedef typename boost::mpl::if_<boost::is_same<freelist_t, caching_freelist_t>,
51  >::type pool_t;
52 
53 public:
54  static const bool is_lockfree = node::tagged_ptr::is_lockfree;
55 
56  stack(void):
57  tos(NULL), pool(128)
58  {}
59 
60  explicit stack(std::size_t n):
61  tos(NULL), pool(n)
62  {}
63 
64  bool push(T const & v)
65  {
66  node * newnode = alloc_node(v);
67 
68  if (newnode == 0)
69  return false;
70 
71  ptr_type old_tos;
72  do
73  {
74  old_tos.set(tos);
75  newnode->next.set_ptr(old_tos.get_ptr());
76  }
77  while (!tos.cas(old_tos, newnode));
78 
79  return true;
80  }
81 
82  bool pop(T * ret)
83  {
84  for (;;)
85  {
86  ptr_type old_tos;
87  old_tos.set(tos);
88 
89  if (!old_tos)
90  return false;
91 
92  node * new_tos = old_tos->next.get_ptr();
93 
94  if (tos.cas(old_tos, new_tos))
95  {
96  *ret = old_tos->v;
97  dealloc_node(old_tos.get_ptr());
98  return true;
99  }
100  }
101  }
102 
103  bool empty(void) const
104  {
105  return tos == NULL;
106  }
107 
108 private:
109  node * alloc_node(T const & t)
110  {
111  node * chunk = pool.allocate();
112  new(chunk) node(t);
113  return chunk;
114  }
115 
116  void dealloc_node(node * n)
117  {
118  n->~node();
119  pool.deallocate(n);
120  }
121 
122  ptr_type tos;
123 
124  static const int padding_size = 64 - sizeof(ptr_type); /* cache lines on current cpus seem to
125  * be 64 byte */
126  char padding[padding_size];
127 
128  pool_t pool;
129 };
130 
131 
132 } /* namespace lockfree */
133 } /* namespace boost */
134 
135 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */