pion-net  4.0.9
freelist.hpp
1 // lock-free freelist
2 //
3 // Copyright (C) 2008, 2009 Tim Blechmann
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 
9 // Disclaimer: Not a Boost library.
10 
11 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
12 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
13 
14 #include <boost/lockfree/detail/tagged_ptr.hpp>
15 #include <boost/lockfree/atomic_int.hpp>
16 #include <boost/noncopyable.hpp>
17 
18 #include <boost/mpl/map.hpp>
19 #include <boost/mpl/apply.hpp>
20 #include <boost/mpl/at.hpp>
21 #include <boost/type_traits/is_pod.hpp>
22 
23 #include <algorithm> /* for std::min */
24 
25 namespace boost
26 {
27 namespace lockfree
28 {
29 namespace detail
30 {
31 
32 template <typename T, typename Alloc = std::allocator<T> >
34  private boost::noncopyable,
35  private Alloc
36 {
37 public:
38  T * allocate (void)
39  {
40  return Alloc::allocate(1);
41  }
42 
43  void deallocate (T * n)
44  {
45  Alloc::deallocate(n, 1);
46  }
47 };
48 
49 } /* namespace detail */
50 
52 template <typename T,
53  std::size_t maximum_size = 64,
54  typename Alloc = std::allocator<T> >
55 class freelist:
56  private detail::dummy_freelist<T, Alloc>
57 {
58  struct freelist_node
59  {
61  };
62 
64 
65 public:
66  freelist(void):
67  pool_(NULL)
68  {}
69 
70  explicit freelist(std::size_t initial_nodes):
71  pool_(NULL)
72  {
73  for (std::size_t i = 0; i != std::min(initial_nodes, maximum_size); ++i)
74  {
76  deallocate(node);
77  }
78  }
79 
80  ~freelist(void)
81  {
82  free_memory_pool();
83  }
84 
85  T * allocate (void)
86  {
87  for(;;)
88  {
89  tagged_ptr old_pool(pool_);
90 
91  if (!old_pool)
93 
94  freelist_node * new_pool = old_pool->next.get_ptr();
95 
96  if (pool_.cas(old_pool, new_pool))
97  {
98  --free_list_size;
99  return reinterpret_cast<T*>(old_pool.get_ptr());
100  }
101  }
102  }
103 
104  void deallocate (T * n)
105  {
106  if (free_list_size > maximum_size)
107  {
109  return;
110  }
111 
112  for(;;)
113  {
114  tagged_ptr old_pool (pool_);
115 
116  freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
117 
118  new_pool->next.set_ptr(old_pool.get_ptr());
119 
120  if (pool_.cas(old_pool, new_pool))
121  {
122  --free_list_size;
123  return;
124  }
125  }
126  }
127 
128 private:
129  void free_memory_pool(void)
130  {
131  tagged_ptr current (pool_);
132 
133  while (current)
134  {
135  freelist_node * n = current.get_ptr();
136  current.set(current->next);
137  detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n));
138  }
139  }
140 
141  tagged_ptr pool_;
142  atomic_int<unsigned long> free_list_size;
143 };
144 
145 template <typename T, typename Alloc = std::allocator<T> >
147  private detail::dummy_freelist<T, Alloc>
148 {
149  struct freelist_node
150  {
152  };
153 
155 
156 public:
157  caching_freelist(void):
158  pool_(NULL)
159  {}
160 
161  explicit caching_freelist(std::size_t initial_nodes):
162  pool_(NULL)
163  {
164  for (std::size_t i = 0; i != initial_nodes; ++i)
165  {
167  deallocate(node);
168  }
169  }
170 
171  ~caching_freelist(void)
172  {
173  free_memory_pool();
174  }
175 
176  T * allocate (void)
177  {
178  for(;;)
179  {
180  tagged_ptr old_pool(pool_);
181 
182  if (!old_pool)
184 
185  freelist_node * new_pool = old_pool->next.get_ptr();
186 
187  if (pool_.cas(old_pool, new_pool))
188  return reinterpret_cast<T*>(old_pool.get_ptr());
189  }
190  }
191 
192  void deallocate (T * n)
193  {
194  for(;;)
195  {
196  tagged_ptr old_pool (pool_);
197 
198  freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
199 
200  new_pool->next.set_ptr(old_pool.get_ptr());
201 
202  if (pool_.cas(old_pool,new_pool))
203  return;
204  }
205  }
206 
207 private:
208  void free_memory_pool(void)
209  {
210  tagged_ptr current (pool_);
211 
212  while (current)
213  {
214  freelist_node * n = current.get_ptr();
215  current.set(current->next);
216  detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n));
217  }
218  }
219 
220  tagged_ptr pool_;
221 };
222 
223 template <typename T, typename Alloc = std::allocator<T> >
225  private Alloc
226 {
227  struct freelist_node
228  {
230  };
231 
233 
234 public:
235  explicit static_freelist(std::size_t max_nodes):
236  pool_(NULL), total_nodes(max_nodes)
237  {
238  chunks = Alloc::allocate(max_nodes);
239  for (std::size_t i = 0; i != max_nodes; ++i)
240  {
241  T * node = chunks + i;
242  deallocate(node);
243  }
244  }
245 
246  ~static_freelist(void)
247  {
248  Alloc::deallocate(chunks, total_nodes);
249  }
250 
251  T * allocate (void)
252  {
253  for(;;)
254  {
255  tagged_ptr old_pool(pool_);
256 
257  if (!old_pool)
258  return 0; /* allocation fails */
259 
260  freelist_node * new_pool = old_pool->next.get_ptr();
261 
262  if (pool_.cas(old_pool, new_pool))
263  return reinterpret_cast<T*>(old_pool.get_ptr());
264  }
265  }
266 
267  void deallocate (T * n)
268  {
269  for(;;)
270  {
271  tagged_ptr old_pool (pool_);
272 
273  freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
274 
275  new_pool->next.set_ptr(old_pool.get_ptr());
276 
277  if (pool_.cas(old_pool,new_pool))
278  return;
279  }
280  }
281 
282 private:
283  tagged_ptr pool_;
284 
285  const std::size_t total_nodes;
286  T* chunks;
287 };
288 
289 
292 
293 namespace detail
294 {
295 
296 #if 0
297 template <typename T, typename Alloc, typename tag>
298 struct select_freelist
299 {
300 private:
301  typedef typename Alloc::template rebind<T>::other Allocator;
302 
305 
306  typedef typename boost::mpl::map<
307  boost::mpl::pair < caching_freelist_t, cfl/* typename boost::lockfree::caching_freelist<T, Alloc> */ >,
308  boost::mpl::pair < static_freelist_t, sfl/* typename boost::lockfree::static_freelist<T, Alloc> */ >,
309  int
310  > freelists;
311 public:
312  typedef typename boost::mpl::at<freelists, tag>::type type;
313 };
314 #endif
315 
316 } /* namespace detail */
317 } /* namespace lockfree */
318 } /* namespace boost */
319 
320 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */
bool cas(tagged_ptr const &oldval, T *newptr)
void set(tagged_ptr const &p)