ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1// lock-free queue from
2// Michael, M. M. and Scott, M. L.,
3// "simple, fast and practical non-blocking and blocking concurrent queue algorithms"
4//
5// Copyright (C) 2008, 2009, 2010, 2011 Tim Blechmann
6//
7// Distributed under the Boost Software License, Version 1.0. (See
8// accompanying file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10
11#ifndef BOOST_LOCKFREE_FIFO_HPP_INCLUDED
12#define BOOST_LOCKFREE_FIFO_HPP_INCLUDED
13
14#include <memory> /* std::auto_ptr */
15
16#include <boost/assert.hpp>
17#include <boost/noncopyable.hpp>
18#include <boost/static_assert.hpp>
19#include <boost/type_traits/has_trivial_assign.hpp>
20#include <boost/type_traits/has_trivial_destructor.hpp>
21
22#include <boost/lockfree/detail/atomic.hpp>
23#include <boost/lockfree/detail/copy_payload.hpp>
24#include <boost/lockfree/detail/freelist.hpp>
25#include <boost/lockfree/detail/parameter.hpp>
26#include <boost/lockfree/detail/tagged_ptr.hpp>
27
28namespace boost {
29namespace lockfree {
30namespace detail {
31
32typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
33 boost::parameter::optional<tag::capacity>
34 > queue_signature;
35
36} /* namespace detail */
37
38
39/** The queue class provides a multi-writer/multi-reader queue, pushing and popping is lock-free,
40 * construction/destruction has to be synchronized. It uses a freelist for memory management,
41 * freed nodes are pushed to the freelist and not returned to the OS before the queue is destroyed.
42 *
43 * \b Policies:
44 * - \ref boost::lockfree::fixed_sized, defaults to \c boost::lockfree::fixed_sized<false> \n
45 * Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior. \n
46 * If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed
47 * by array indexing. This limits the possible size of the queue to the number of elements that can be addressed by the index
48 * type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way
49 * to achieve lock-freedom.
50 *
51 * - \ref boost::lockfree::capacity, optional \n
52 * If this template argument is passed to the options, the size of the queue is set at compile-time.\n
53 * It this option implies \c fixed_sized<true>
54 *
55 * - \ref boost::lockfree::allocator, defaults to \c boost::lockfree::allocator<std::allocator<void>> \n
56 * Specifies the allocator that is used for the internal freelist
57 *
58 * \b Requirements:
59 * - T must have a copy constructor
60 * - T must have a trivial assignment operator
61 * - T must have a trivial destructor
62 *
63 * */
64#ifndef BOOST_DOXYGEN_INVOKED
65template <typename T,
66 class A0 = boost::parameter::void_,
67 class A1 = boost::parameter::void_,
68 class A2 = boost::parameter::void_>
69#else
70template <typename T, ...Options>
71#endif
72class queue:
73 boost::noncopyable
74{
75private:
76#ifndef BOOST_DOXYGEN_INVOKED
77
78#ifdef BOOST_HAS_TRIVIAL_DESTRUCTOR
79 BOOST_STATIC_ASSERT((boost::has_trivial_destructor<T>::value));
80#endif
81
82#ifdef BOOST_HAS_TRIVIAL_ASSIGN
83 BOOST_STATIC_ASSERT((boost::has_trivial_assign<T>::value));
84#endif
85
86 typedef typename detail::queue_signature::bind<A0, A1, A2>::type bound_args;
87
88 static const bool has_capacity = detail::extract_capacity<bound_args>::has_capacity;
89 static const size_t capacity = detail::extract_capacity<bound_args>::capacity;
90 static const bool fixed_sized = detail::extract_fixed_sized<bound_args>::value;
91 static const bool node_based = !(has_capacity || fixed_sized);
92 static const bool compile_time_sized = has_capacity;
93
94 struct BOOST_LOCKFREE_CACHELINE_ALIGNMENT node
95 {
96 typedef typename detail::select_tagged_handle<node, node_based>::tagged_handle_type tagged_node_handle;
97 typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_type;
98
99 node(T const & v, handle_type null_handle):
100 data(v)//, next(tagged_node_handle(0, 0))
101 {
102 /* increment tag to avoid ABA problem */
103 tagged_node_handle old_next = next.load(memory_order_relaxed);
104 tagged_node_handle new_next (null_handle, old_next.get_tag()+1);
105 next.store(new_next, memory_order_release);
106 }
107
108 node (handle_type null_handle):
109 next(tagged_node_handle(null_handle, 0))
110 {}
111
112 node(void)
113 {}
114
115 atomic<tagged_node_handle> next;
116 T data;
117 };
118
119 typedef typename detail::extract_allocator<bound_args, node>::type node_allocator;
120 typedef typename detail::select_freelist<node, node_allocator, compile_time_sized, fixed_sized, capacity>::type pool_t;
121 typedef typename pool_t::tagged_node_handle tagged_node_handle;
122 typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_type;
123
124 void initialize(void)
125 {
126 node * n = pool.template construct<true, false>(pool.null_handle());
127 tagged_node_handle dummy_node(pool.get_handle(n), 0);
128 head_.store(dummy_node, memory_order_relaxed);
129 tail_.store(dummy_node, memory_order_release);
130 }
131
132 struct implementation_defined
133 {
134 typedef node_allocator allocator;
135 typedef std::size_t size_type;
136 };
137
138#endif
139
140public:
141 typedef T value_type;
142 typedef typename implementation_defined::allocator allocator;
143 typedef typename implementation_defined::size_type size_type;
144
145 /**
146 * \return true, if implementation is lock-free.
147 *
148 * \warning It only checks, if the queue head and tail nodes and the freelist can be modified in a lock-free manner.
149 * On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics, there is
150 * no possibility to provide a completely accurate implementation, because one would need to test every internal
151 * node, which is impossible if further nodes will be allocated from the operating system.
152 * */
153 bool is_lock_free (void) const
154 {
155 return head_.is_lock_free() && tail_.is_lock_free() && pool.is_lock_free();
156 }
157
158 //! Construct queue
159 // @{
160 queue(void):
161 head_(tagged_node_handle(0, 0)),
162 tail_(tagged_node_handle(0, 0)),
163 pool(node_allocator(), capacity)
164 {
165 BOOST_ASSERT(has_capacity);
166 initialize();
167 }
168
169 template <typename U>
170 explicit queue(typename node_allocator::template rebind<U>::other const & alloc):
171 head_(tagged_node_handle(0, 0)),
172 tail_(tagged_node_handle(0, 0)),
173 pool(alloc, capacity)
174 {
175 BOOST_STATIC_ASSERT(has_capacity);
176 initialize();
177 }
178
179 explicit queue(allocator const & alloc):
180 head_(tagged_node_handle(0, 0)),
181 tail_(tagged_node_handle(0, 0)),
182 pool(alloc, capacity)
183 {
184 BOOST_ASSERT(has_capacity);
185 initialize();
186 }
187 // @}
188
189 //! Construct queue, allocate n nodes for the freelist.
190 // @{
191 explicit queue(size_type n):
192 head_(tagged_node_handle(0, 0)),
193 tail_(tagged_node_handle(0, 0)),
194 pool(node_allocator(), n + 1)
195 {
196 BOOST_ASSERT(!has_capacity);
197 initialize();
198 }
199
200 template <typename U>
201 queue(size_type n, typename node_allocator::template rebind<U>::other const & alloc):
202 head_(tagged_node_handle(0, 0)),
203 tail_(tagged_node_handle(0, 0)),
204 pool(alloc, n + 1)
205 {
206 BOOST_STATIC_ASSERT(!has_capacity);
207 initialize();
208 }
209 // @}
210
211 /** \copydoc boost::lockfree::stack::reserve
212 * */
213 void reserve(size_type n)
214 {
215 pool.template reserve<true>(n);
216 }
217
218 /** \copydoc boost::lockfree::stack::reserve_unsafe
219 * */
220 void reserve_unsafe(size_type n)
221 {
222 pool.template reserve<false>(n);
223 }
224
225 /** Destroys queue, free all nodes from freelist.
226 * */
227 ~queue(void)
228 {
229 T dummy;
230 while(unsynchronized_pop(dummy))
231 {}
232
233 pool.template destruct<false>(head_.load(memory_order_relaxed));
234 }
235
236 /** Check if the queue is empty
237 *
238 * \return true, if the queue is empty, false otherwise
239 * \note The result is only accurate, if no other thread modifies the queue. Therefore it is rarely practical to use this
240 * value in program logic.
241 * */
242 bool empty(void)
243 {
244 return pool.get_handle(head_.load()) == pool.get_handle(tail_.load());
245 }
246
247 /** Pushes object t to the queue.
248 *
249 * \post object will be pushed to the queue, if internal node can be allocated
250 * \returns true, if the push operation is successful.
251 *
252 * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
253 * from the OS. This may not be lock-free.
254 * */
255 bool push(T const & t)
256 {
257 return do_push<false>(t);
258 }
259
260 /** Pushes object t to the queue.
261 *
262 * \post object will be pushed to the queue, if internal node can be allocated
263 * \returns true, if the push operation is successful.
264 *
265 * \note Thread-safe and non-blocking. If internal memory pool is exhausted, operation will fail
266 * \throws if memory allocator throws
267 * */
268 bool bounded_push(T const & t)
269 {
270 return do_push<true>(t);
271 }
272
273
274private:
275#ifndef BOOST_DOXYGEN_INVOKED
276 template <bool Bounded>
277 bool do_push(T const & t)
278 {
279 using detail::likely;
280
281 node * n = pool.template construct<true, Bounded>(t, pool.null_handle());
282 handle_type node_handle = pool.get_handle(n);
283
284 if (n == NULL)
285 return false;
286
287 for (;;) {
288 tagged_node_handle tail = tail_.load(memory_order_acquire);
289 node * tail_node = pool.get_pointer(tail);
290 tagged_node_handle next = tail_node->next.load(memory_order_acquire);
291 node * next_ptr = pool.get_pointer(next);
292
293 tagged_node_handle tail2 = tail_.load(memory_order_acquire);
294 if (likely(tail == tail2)) {
295 if (next_ptr == 0) {
296 tagged_node_handle new_tail_next(node_handle, next.get_tag() + 1);
297 if ( tail_node->next.compare_exchange_weak(next, new_tail_next) ) {
298 tagged_node_handle new_tail(node_handle, tail.get_tag() + 1);
299 tail_.compare_exchange_strong(tail, new_tail);
300 return true;
301 }
302 }
303 else {
304 tagged_node_handle new_tail(pool.get_handle(next_ptr), tail.get_tag() + 1);
305 tail_.compare_exchange_strong(tail, new_tail);
306 }
307 }
308 }
309 }
310#endif
311
312public:
313
314 /** Pushes object t to the queue.
315 *
316 * \post object will be pushed to the queue, if internal node can be allocated
317 * \returns true, if the push operation is successful.
318 *
319 * \note Not Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
320 * from the OS. This may not be lock-free.
321 * \throws if memory allocator throws
322 * */
323 bool unsynchronized_push(T const & t)
324 {
325 node * n = pool.template construct<false, false>(t, pool.null_handle());
326
327 if (n == NULL)
328 return false;
329
330 for (;;) {
331 tagged_node_handle tail = tail_.load(memory_order_relaxed);
332 tagged_node_handle next = tail->next.load(memory_order_relaxed);
333 node * next_ptr = next.get_ptr();
334
335 if (next_ptr == 0) {
336 tail->next.store(tagged_node_handle(n, next.get_tag() + 1), memory_order_relaxed);
337 tail_.store(tagged_node_handle(n, tail.get_tag() + 1), memory_order_relaxed);
338 return true;
339 }
340 else
341 tail_.store(tagged_node_handle(next_ptr, tail.get_tag() + 1), memory_order_relaxed);
342 }
343 }
344
345 /** Pops object from queue.
346 *
347 * \post if pop operation is successful, object will be copied to ret.
348 * \returns true, if the pop operation is successful, false if queue was empty.
349 *
350 * \note Thread-safe and non-blocking
351 * */
352 bool pop (T & ret)
353 {
354 return pop<T>(ret);
355 }
356
357 /** Pops object from queue.
358 *
359 * \pre type U must be constructible by T and copyable, or T must be convertible to U
360 * \post if pop operation is successful, object will be copied to ret.
361 * \returns true, if the pop operation is successful, false if queue was empty.
362 *
363 * \note Thread-safe and non-blocking
364 * */
365 template <typename U>
366 bool pop (U & ret)
367 {
368 using detail::likely;
369 for (;;) {
370 tagged_node_handle head = head_.load(memory_order_acquire);
371 node * head_ptr = pool.get_pointer(head);
372
373 tagged_node_handle tail = tail_.load(memory_order_acquire);
374 tagged_node_handle next = head_ptr->next.load(memory_order_acquire);
375 node * next_ptr = pool.get_pointer(next);
376
377 tagged_node_handle head2 = head_.load(memory_order_acquire);
378 if (likely(head == head2)) {
379 if (pool.get_handle(head) == pool.get_handle(tail)) {
380 if (next_ptr == 0)
381 return false;
382
383 tagged_node_handle new_tail(pool.get_handle(next), tail.get_tag() + 1);
384 tail_.compare_exchange_strong(tail, new_tail);
385
386 } else {
387 if (next_ptr == 0)
388 /* this check is not part of the original algorithm as published by michael and scott
389 *
390 * however we reuse the tagged_ptr part for the freelist and clear the next part during node
391 * allocation. we can observe a null-pointer here.
392 * */
393 continue;
394 detail::copy_payload(next_ptr->data, ret);
395
396 tagged_node_handle new_head(pool.get_handle(next), head.get_tag() + 1);
397 if (head_.compare_exchange_weak(head, new_head)) {
398 pool.template destruct<true>(head);
399 return true;
400 }
401 }
402 }
403 }
404 }
405
406 /** Pops object from queue.
407 *
408 * \post if pop operation is successful, object will be copied to ret.
409 * \returns true, if the pop operation is successful, false if queue was empty.
410 *
411 * \note Not thread-safe, but non-blocking
412 *
413 * */
414 bool unsynchronized_pop (T & ret)
415 {
416 return unsynchronized_pop<T>(ret);
417 }
418
419 /** Pops object from queue.
420 *
421 * \pre type U must be constructible by T and copyable, or T must be convertible to U
422 * \post if pop operation is successful, object will be copied to ret.
423 * \returns true, if the pop operation is successful, false if queue was empty.
424 *
425 * \note Not thread-safe, but non-blocking
426 *
427 * */
428 template <typename U>
429 bool unsynchronized_pop (U & ret)
430 {
431 for (;;) {
432 tagged_node_handle head = head_.load(memory_order_relaxed);
433 node * head_ptr = pool.get_pointer(head);
434 tagged_node_handle tail = tail_.load(memory_order_relaxed);
435 tagged_node_handle next = head_ptr->next.load(memory_order_relaxed);
436 node * next_ptr = pool.get_pointer(next);
437
438 if (pool.get_handle(head) == pool.get_handle(tail)) {
439 if (next_ptr == 0)
440 return false;
441
442 tagged_node_handle new_tail(pool.get_handle(next), tail.get_tag() + 1);
443 tail_.store(new_tail);
444 } else {
445 if (next_ptr == 0)
446 /* this check is not part of the original algorithm as published by michael and scott
447 *
448 * however we reuse the tagged_ptr part for the freelist and clear the next part during node
449 * allocation. we can observe a null-pointer here.
450 * */
451 continue;
452 detail::copy_payload(next_ptr->data, ret);
453 tagged_node_handle new_head(pool.get_handle(next), head.get_tag() + 1);
454 head_.store(new_head);
455 pool.template destruct<false>(head);
456 return true;
457 }
458 }
459 }
460
461private:
462#ifndef BOOST_DOXYGEN_INVOKED
463 atomic<tagged_node_handle> head_;
464 static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(tagged_node_handle);
465 char padding1[padding_size];
466 atomic<tagged_node_handle> tail_;
467 char padding2[padding_size];
468
469 pool_t pool;
470#endif
471};
472
473} /* namespace lockfree */
474} /* namespace boost */
475
476#endif /* BOOST_LOCKFREE_FIFO_HPP_INCLUDED */