pion-net  4.0.9
fifo.hpp
1 // lock-free fifo queue from
2 // Michael, M. M. and Scott, M. L.,
3 // "simple, fast and practical non-blocking and blocking concurrent queue algorithms"
4 //
5 // implementation for c++
6 //
7 // Copyright (C) 2008 Tim Blechmann
8 //
9 // Distributed under the Boost Software License, Version 1.0. (See
10 // accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12 
13 // Disclaimer: Not a Boost library.
14 
15 #ifndef BOOST_LOCKFREE_FIFO_HPP_INCLUDED
16 #define BOOST_LOCKFREE_FIFO_HPP_INCLUDED
17 
18 #include <boost/lockfree/atomic_int.hpp>
19 #include <boost/lockfree/detail/tagged_ptr.hpp>
20 #include <boost/lockfree/detail/freelist.hpp>
21 
22 #include <boost/static_assert.hpp>
23 #include <boost/type_traits/is_pod.hpp>
24 
25 #include <memory> /* std::auto_ptr */
26 #include <boost/scoped_ptr.hpp>
27 #include <boost/shared_ptr.hpp>
28 #include <boost/noncopyable.hpp>
29 
30 namespace boost
31 {
32 namespace lockfree
33 {
34 
35 namespace detail
36 {
37 
38 template <typename T, typename freelist_t, typename Alloc>
39 class fifo:
40  boost::noncopyable
41 {
42  BOOST_STATIC_ASSERT(boost::is_pod<T>::value);
43 
44  struct BOOST_LOCKFREE_CACHELINE_ALIGNMENT node
45  {
46  typedef tagged_ptr<node> tagged_ptr_t;
47 
48  node(T const & v):
49  data(v)
50  {
51  next.set(NULL, next.get_tag()+1); /* increment tag to avoid ABA problem */
52  }
53 
54  node (void):
55  next(NULL)
56  {}
57 
58  tagged_ptr_t next;
59  T data;
60  };
61 
63 
64  typedef typename Alloc::template rebind<node>::other node_allocator;
65 /* typedef typename select_freelist<node, node_allocator, freelist_t>::type pool_t; */
66 
67  typedef typename boost::mpl::if_<boost::is_same<freelist_t, caching_freelist_t>,
70  >::type pool_t;
71 
72 public:
73  static const bool is_lockfree = node::tagged_ptr_t::is_lockfree;
74 
75  fifo(void):
76  pool(128)
77  {
78  node * n = alloc_node();
79  head_.set_ptr(n);
80  tail_.set_ptr(n);
81  }
82 
83  explicit fifo(std::size_t initial_nodes):
84  pool(initial_nodes)
85  {
86  node * n = alloc_node();
87  head_.set_ptr(n);
88  tail_.set_ptr(n);
89  }
90 
91  ~fifo(void)
92  {
93  assert(empty());
94  dealloc_node(head_.get_ptr());
95  }
96 
97  bool empty(void)
98  {
99  return head_.get_ptr() == tail_.get_ptr();
100  }
101 
102  bool enqueue(T const & t)
103  {
104  node * n = alloc_node(t);
105 
106  if (n == NULL)
107  return false;
108 
109  for (;;)
110  {
111  atomic_node_ptr tail (tail_);
112  read_memory_barrier();
113  atomic_node_ptr next (tail->next);
114 
115  if (likely(tail == tail_))
116  {
117  if (next.get_ptr() == 0)
118  {
119  if ( tail->next.cas(next, n) )
120  {
121  tail_.cas(tail, n);
122  return true;
123  }
124  }
125  else
126  tail_.cas(tail, next.get_ptr());
127  }
128  }
129  }
130 
131  bool dequeue (T * ret)
132  {
133  for (;;)
134  {
135  atomic_node_ptr head (head_);
136  read_memory_barrier();
137 
138  atomic_node_ptr tail(tail_);
139  node * next = head->next.get_ptr();
140 
141  if (likely(head == head_))
142  {
143  if (head.get_ptr() == tail.get_ptr())
144  {
145  if (next == 0)
146  return false;
147 
148  tail_.cas(tail, next);
149  }
150  else
151  {
152  *ret = next->data;
153  if (head_.cas(head, next))
154  {
155  dealloc_node(head.get_ptr());
156 
157  return true;
158  }
159  }
160  }
161  }
162  }
163 
164 private:
165  node * alloc_node(void)
166  {
167  node * chunk = pool.allocate();
168  new(chunk) node();
169  return chunk;
170  }
171 
172  node * alloc_node(T const & t)
173  {
174  node * chunk = pool.allocate();
175  new(chunk) node(t);
176  return chunk;
177  }
178 
179  void dealloc_node(node * n)
180  {
181  n->~node();
182  pool.deallocate(n);
183  }
184 
185  atomic_node_ptr head_;
186  static const int padding_size = 64 - sizeof(atomic_node_ptr); /* cache lines on current cpus seem to
187  * be 64 byte */
188  char padding1[padding_size];
189  atomic_node_ptr tail_;
190  char padding2[padding_size];
191 
192  pool_t pool;
193 };
194 
195 } /* namespace detail */
196 
201 template <typename T,
202  typename freelist_t = caching_freelist_t,
203  typename Alloc = std::allocator<T>
204  >
205 class fifo:
206  public detail::fifo<T, freelist_t, Alloc>
207 {
208 public:
209  fifo(void)
210  {}
211 
212  explicit fifo(std::size_t initial_nodes):
214  {}
215 };
216 
217 
223 template <typename T, typename freelist_t, typename Alloc>
224 class fifo<T*, freelist_t, Alloc>:
226 {
228 
229  template <typename smart_ptr>
230  bool dequeue_smart_ptr(smart_ptr & ptr)
231  {
232  T * result = 0;
233  bool success = fifo_t::dequeue(&result);
234 
235  if (success)
236  ptr.reset(result);
237  return success;
238  }
239 
240 public:
241  fifo(void)
242  {}
243 
244  explicit fifo(std::size_t initial_nodes):
245  fifo_t(initial_nodes)
246  {}
247 
248  bool enqueue(T * t)
249  {
250  return fifo_t::enqueue(t);
251  }
252 
253  bool dequeue (T ** ret)
254  {
255  return fifo_t::dequeue(ret);
256  }
257 
258  bool dequeue (std::auto_ptr<T> & ret)
259  {
260  return dequeue_smart_ptr(ret);
261  }
262 
263  bool dequeue (boost::scoped_ptr<T> & ret)
264  {
265  BOOST_STATIC_ASSERT(sizeof(boost::scoped_ptr<T>) == sizeof(T*));
266  return dequeue(reinterpret_cast<T**>(&ret));
267  }
268 
269  bool dequeue (boost::shared_ptr<T> & ret)
270  {
271  return dequeue_smart_ptr(ret);
272  }
273 };
274 
275 } /* namespace lockfree */
276 } /* namespace boost */
277 
278 
279 #endif /* BOOST_LOCKFREE_FIFO_HPP_INCLUDED */