1// Copyright (C) 2008-2013 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#ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
8#define BOOST_LOCKFREE_STACK_HPP_INCLUDED
9
10#include <boost/assert.hpp>
11#include <boost/checked_delete.hpp>
12#include <boost/core/allocator_access.hpp>
13#include <boost/core/no_exceptions_support.hpp>
14#include <boost/integer_traits.hpp>
15#include <boost/static_assert.hpp>
16#include <boost/tuple/tuple.hpp>
17#include <boost/type_traits/is_copy_constructible.hpp>
18
19#include <boost/lockfree/detail/atomic.hpp>
20#include <boost/lockfree/detail/copy_payload.hpp>
21#include <boost/lockfree/detail/freelist.hpp>
22#include <boost/lockfree/detail/parameter.hpp>
23#include <boost/lockfree/detail/tagged_ptr.hpp>
24
25#include <boost/lockfree/lockfree_forward.hpp>
26
27#ifdef BOOST_HAS_PRAGMA_ONCE
28#pragma once
29#endif
30
31namespace boost {
32namespace lockfree {
33namespace detail {
34
35typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
36 boost::parameter::optional<tag::capacity>
37 > stack_signature;
38
39}
40
41/** The stack class provides a multi-writer/multi-reader stack, pushing and popping is lock-free,
42 * construction/destruction has to be synchronized. It uses a freelist for memory management,
43 * freed nodes are pushed to the freelist and not returned to the OS before the stack is destroyed.
44 *
45 * \b Policies:
46 *
47 * - \c boost::lockfree::fixed_sized<>, defaults to \c boost::lockfree::fixed_sized<false> <br>
48 * Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior.<br>
49 * If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed
50 * by array indexing. This limits the possible size of the stack to the number of elements that can be addressed by the index
51 * type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way
52 * to achieve lock-freedom.
53 *
54 * - \c boost::lockfree::capacity<>, optional <br>
55 * If this template argument is passed to the options, the size of the stack is set at compile-time. <br>
56 * It this option implies \c fixed_sized<true>
57 *
58 * - \c boost::lockfree::allocator<>, defaults to \c boost::lockfree::allocator<std::allocator<void>> <br>
59 * Specifies the allocator that is used for the internal freelist
60 *
61 * \b Requirements:
62 * - T must have a copy constructor
63 * */
64#ifdef BOOST_NO_CXX11_VARIADIC_TEMPLATES
65template <typename T, class A0, class A1, class A2>
66#else
67template <typename T, typename ...Options>
68#endif
69class stack
70{
71private:
72#ifndef BOOST_DOXYGEN_INVOKED
73 BOOST_STATIC_ASSERT(boost::is_copy_constructible<T>::value);
74
75#ifdef BOOST_NO_CXX11_VARIADIC_TEMPLATES
76 typedef typename detail::stack_signature::bind<A0, A1, A2>::type bound_args;
77#else
78 typedef typename detail::stack_signature::bind<Options...>::type bound_args;
79#endif
80
81 static const bool has_capacity = detail::extract_capacity<bound_args>::has_capacity;
82 static const size_t capacity = detail::extract_capacity<bound_args>::capacity;
83 static const bool fixed_sized = detail::extract_fixed_sized<bound_args>::value;
84 static const bool node_based = !(has_capacity || fixed_sized);
85 static const bool compile_time_sized = has_capacity;
86
87 struct node
88 {
89 node(T const & val):
90 v(val)
91 {}
92
93 typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_t;
94 handle_t next;
95 const T v;
96 };
97
98 typedef typename detail::extract_allocator<bound_args, node>::type node_allocator;
99 typedef typename detail::select_freelist<node, node_allocator, compile_time_sized, fixed_sized, capacity>::type pool_t;
100 typedef typename pool_t::tagged_node_handle tagged_node_handle;
101
102 // check compile-time capacity
103 BOOST_STATIC_ASSERT((mpl::if_c<has_capacity,
104 mpl::bool_<capacity - 1 < boost::integer_traits<boost::uint16_t>::const_max>,
105 mpl::true_
106 >::type::value));
107
108 struct implementation_defined
109 {
110 typedef node_allocator allocator;
111 typedef std::size_t size_type;
112 };
113
114#endif
115
116 BOOST_DELETED_FUNCTION(stack(stack const&))
117 BOOST_DELETED_FUNCTION(stack& operator= (stack const&))
118
119public:
120 typedef T value_type;
121 typedef typename implementation_defined::allocator allocator;
122 typedef typename implementation_defined::size_type size_type;
123
124 /**
125 * \return true, if implementation is lock-free.
126 *
127 * \warning It only checks, if the top stack node and the freelist can be modified in a lock-free manner.
128 * On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics,
129 * there is no possibility to provide a completely accurate implementation, because one would need to test
130 * every internal node, which is impossible if further nodes will be allocated from the operating system.
131 *
132 * */
133 bool is_lock_free (void) const
134 {
135 return tos.is_lock_free() && pool.is_lock_free();
136 }
137
138 /** Construct a fixed-sized stack
139 *
140 * \pre Must specify a capacity<> argument
141 * */
142 stack(void):
143 pool(node_allocator(), capacity)
144 {
145 // Don't use BOOST_STATIC_ASSERT() here since it will be evaluated when compiling
146 // this function and this function may be compiled even when it isn't being used.
147 BOOST_ASSERT(has_capacity);
148 initialize();
149 }
150
151 /** Construct a fixed-sized stack with a custom allocator
152 *
153 * \pre Must specify a capacity<> argument
154 * */
155 template <typename U>
156 explicit stack(typename boost::allocator_rebind<node_allocator, U>::type const & alloc):
157 pool(alloc, capacity)
158 {
159 BOOST_STATIC_ASSERT(has_capacity);
160 initialize();
161 }
162
163 /** Construct a fixed-sized stack with a custom allocator
164 *
165 * \pre Must specify a capacity<> argument
166 * */
167 explicit stack(allocator const & alloc):
168 pool(alloc, capacity)
169 {
170 // Don't use BOOST_STATIC_ASSERT() here since it will be evaluated when compiling
171 // this function and this function may be compiled even when it isn't being used.
172 BOOST_ASSERT(has_capacity);
173 initialize();
174 }
175
176 /** Construct a variable-sized stack
177 *
178 * Allocate n nodes initially for the freelist
179 *
180 * \pre Must \b not specify a capacity<> argument
181 * */
182 explicit stack(size_type n):
183 pool(node_allocator(), n)
184 {
185 // Don't use BOOST_STATIC_ASSERT() here since it will be evaluated when compiling
186 // this function and this function may be compiled even when it isn't being used.
187 BOOST_ASSERT(!has_capacity);
188 initialize();
189 }
190
191 /** Construct a variable-sized stack with a custom allocator
192 *
193 * Allocate n nodes initially for the freelist
194 *
195 * \pre Must \b not specify a capacity<> argument
196 * */
197 template <typename U>
198 stack(size_type n, typename boost::allocator_rebind<node_allocator, U>::type const & alloc):
199 pool(alloc, n)
200 {
201 BOOST_STATIC_ASSERT(!has_capacity);
202 initialize();
203 }
204
205 /** Allocate n nodes for freelist
206 *
207 * \pre only valid if no capacity<> argument given
208 * \note thread-safe, may block if memory allocator blocks
209 *
210 * */
211 void reserve(size_type n)
212 {
213 // Don't use BOOST_STATIC_ASSERT() here since it will be evaluated when compiling
214 // this function and this function may be compiled even when it isn't being used.
215 BOOST_ASSERT(!has_capacity);
216 pool.template reserve<true>(n);
217 }
218
219 /** Allocate n nodes for freelist
220 *
221 * \pre only valid if no capacity<> argument given
222 * \note not thread-safe, may block if memory allocator blocks
223 *
224 * */
225 void reserve_unsafe(size_type n)
226 {
227 // Don't use BOOST_STATIC_ASSERT() here since it will be evaluated when compiling
228 // this function and this function may be compiled even when it isn't being used.
229 BOOST_ASSERT(!has_capacity);
230 pool.template reserve<false>(n);
231 }
232
233 /** Destroys stack, free all nodes from freelist.
234 *
235 * \note not thread-safe
236 *
237 * */
238 ~stack(void)
239 {
240 detail::consume_noop consume_functor;
241 (void)consume_all(consume_functor);
242 }
243
244private:
245#ifndef BOOST_DOXYGEN_INVOKED
246 void initialize(void)
247 {
248 tos.store(tagged_node_handle(pool.null_handle(), 0));
249 }
250
251 void link_nodes_atomic(node * new_top_node, node * end_node)
252 {
253 tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
254 for (;;) {
255 tagged_node_handle new_tos (pool.get_handle(new_top_node), old_tos.get_tag());
256 end_node->next = pool.get_handle(old_tos);
257
258 if (tos.compare_exchange_weak(old_tos, new_tos))
259 break;
260 }
261 }
262
263 void link_nodes_unsafe(node * new_top_node, node * end_node)
264 {
265 tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
266
267 tagged_node_handle new_tos (pool.get_handle(new_top_node), old_tos.get_tag());
268 end_node->next = pool.get_handle(old_tos);
269
270 tos.store(new_tos, memory_order_relaxed);
271 }
272
273 template <bool Threadsafe, bool Bounded, typename ConstIterator>
274 tuple<node*, node*> prepare_node_list(ConstIterator begin, ConstIterator end, ConstIterator & ret)
275 {
276 ConstIterator it = begin;
277 node * end_node = pool.template construct<Threadsafe, Bounded>(*it++);
278 if (end_node == NULL) {
279 ret = begin;
280 return make_tuple<node*, node*>(NULL, NULL);
281 }
282
283 node * new_top_node = end_node;
284 end_node->next = NULL;
285
286 BOOST_TRY {
287 /* link nodes */
288 for (; it != end; ++it) {
289 node * newnode = pool.template construct<Threadsafe, Bounded>(*it);
290 if (newnode == NULL)
291 break;
292 newnode->next = new_top_node;
293 new_top_node = newnode;
294 }
295 } BOOST_CATCH (...) {
296 for (node * current_node = new_top_node; current_node != NULL;) {
297 node * next = current_node->next;
298 pool.template destruct<Threadsafe>(current_node);
299 current_node = next;
300 }
301 BOOST_RETHROW;
302 }
303 BOOST_CATCH_END
304
305 ret = it;
306 return make_tuple(new_top_node, end_node);
307 }
308#endif
309
310public:
311 /** Pushes object t to the stack.
312 *
313 * \post object will be pushed to the stack, if internal node can be allocated
314 * \returns true, if the push operation is successful.
315 *
316 * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
317 * from the OS. This may not be lock-free.
318 * \throws if memory allocator throws
319 * */
320 bool push(T const & v)
321 {
322 return do_push<false>(v);
323 }
324
325 /** Pushes object t to the stack.
326 *
327 * \post object will be pushed to the stack, if internal node can be allocated
328 * \returns true, if the push operation is successful.
329 *
330 * \note Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail
331 * */
332 bool bounded_push(T const & v)
333 {
334 return do_push<true>(v);
335 }
336
337#ifndef BOOST_DOXYGEN_INVOKED
338private:
339 template <bool Bounded>
340 bool do_push(T const & v)
341 {
342 node * newnode = pool.template construct<true, Bounded>(v);
343 if (newnode == 0)
344 return false;
345
346 link_nodes_atomic(new_top_node: newnode, end_node: newnode);
347 return true;
348 }
349
350 template <bool Bounded, typename ConstIterator>
351 ConstIterator do_push(ConstIterator begin, ConstIterator end)
352 {
353 node * new_top_node;
354 node * end_node;
355 ConstIterator ret;
356
357 tie(new_top_node, end_node) = prepare_node_list<true, Bounded>(begin, end, ret);
358 if (new_top_node)
359 link_nodes_atomic(new_top_node, end_node);
360
361 return ret;
362 }
363
364public:
365#endif
366
367 /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
368 *
369 * \return iterator to the first element, which has not been pushed
370 *
371 * \note Operation is applied atomically
372 * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
373 * from the OS. This may not be lock-free.
374 * \throws if memory allocator throws
375 */
376 template <typename ConstIterator>
377 ConstIterator push(ConstIterator begin, ConstIterator end)
378 {
379 return do_push<false, ConstIterator>(begin, end);
380 }
381
382 /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
383 *
384 * \return iterator to the first element, which has not been pushed
385 *
386 * \note Operation is applied atomically
387 * \note Thread-safe and non-blocking. If internal memory pool is exhausted, the push operation will fail
388 * \throws if memory allocator throws
389 */
390 template <typename ConstIterator>
391 ConstIterator bounded_push(ConstIterator begin, ConstIterator end)
392 {
393 return do_push<true, ConstIterator>(begin, end);
394 }
395
396
397 /** Pushes object t to the stack.
398 *
399 * \post object will be pushed to the stack, if internal node can be allocated
400 * \returns true, if the push operation is successful.
401 *
402 * \note Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
403 * from the OS. This may not be lock-free.
404 * \throws if memory allocator throws
405 * */
406 bool unsynchronized_push(T const & v)
407 {
408 node * newnode = pool.template construct<false, false>(v);
409 if (newnode == 0)
410 return false;
411
412 link_nodes_unsafe(new_top_node: newnode, end_node: newnode);
413 return true;
414 }
415
416 /** Pushes as many objects from the range [begin, end) as freelist node can be allocated.
417 *
418 * \return iterator to the first element, which has not been pushed
419 *
420 * \note Not thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
421 * from the OS. This may not be lock-free.
422 * \throws if memory allocator throws
423 */
424 template <typename ConstIterator>
425 ConstIterator unsynchronized_push(ConstIterator begin, ConstIterator end)
426 {
427 node * new_top_node;
428 node * end_node;
429 ConstIterator ret;
430
431 tie(new_top_node, end_node) = prepare_node_list<false, false>(begin, end, ret);
432 if (new_top_node)
433 link_nodes_unsafe(new_top_node, end_node);
434
435 return ret;
436 }
437
438
439 /** Pops object from stack.
440 *
441 * \post if pop operation is successful, object will be copied to ret.
442 * \returns true, if the pop operation is successful, false if stack was empty.
443 *
444 * \note Thread-safe and non-blocking
445 *
446 * */
447 bool pop(T & ret)
448 {
449 return pop<T>(ret);
450 }
451
452 /** Pops object from stack.
453 *
454 * \pre type T must be convertible to U
455 * \post if pop operation is successful, object will be copied to ret.
456 * \returns true, if the pop operation is successful, false if stack was empty.
457 *
458 * \note Thread-safe and non-blocking
459 *
460 * */
461 template <typename U>
462 bool pop(U & ret)
463 {
464 BOOST_STATIC_ASSERT((boost::is_convertible<T, U>::value));
465 detail::consume_via_copy<U> consumer(ret);
466
467 return consume_one(consumer);
468 }
469
470
471 /** Pops object from stack.
472 *
473 * \post if pop operation is successful, object will be copied to ret.
474 * \returns true, if the pop operation is successful, false if stack was empty.
475 *
476 * \note Not thread-safe, but non-blocking
477 *
478 * */
479 bool unsynchronized_pop(T & ret)
480 {
481 return unsynchronized_pop<T>(ret);
482 }
483
484 /** Pops object from stack.
485 *
486 * \pre type T must be convertible to U
487 * \post if pop operation is successful, object will be copied to ret.
488 * \returns true, if the pop operation is successful, false if stack was empty.
489 *
490 * \note Not thread-safe, but non-blocking
491 *
492 * */
493 template <typename U>
494 bool unsynchronized_pop(U & ret)
495 {
496 BOOST_STATIC_ASSERT((boost::is_convertible<T, U>::value));
497 tagged_node_handle old_tos = tos.load(detail::memory_order_relaxed);
498 node * old_tos_pointer = pool.get_pointer(old_tos);
499
500 if (!pool.get_pointer(old_tos))
501 return false;
502
503 node * new_tos_ptr = pool.get_pointer(old_tos_pointer->next);
504 tagged_node_handle new_tos(pool.get_handle(new_tos_ptr), old_tos.get_next_tag());
505
506 tos.store(new_tos, memory_order_relaxed);
507 detail::copy_payload(old_tos_pointer->v, ret);
508 pool.template destruct<false>(old_tos);
509 return true;
510 }
511
512 /** consumes one element via a functor
513 *
514 * pops one element from the stack and applies the functor on this object
515 *
516 * \returns true, if one element was consumed
517 *
518 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
519 * */
520 template <typename Functor>
521 bool consume_one(Functor & f)
522 {
523 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
524
525 for (;;) {
526 node * old_tos_pointer = pool.get_pointer(old_tos);
527 if (!old_tos_pointer)
528 return false;
529
530 tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
531
532 if (tos.compare_exchange_weak(old_tos, new_tos)) {
533 f(old_tos_pointer->v);
534 pool.template destruct<true>(old_tos);
535 return true;
536 }
537 }
538 }
539
540 /// \copydoc boost::lockfree::stack::consume_one(Functor & rhs)
541 template <typename Functor>
542 bool consume_one(Functor const & f)
543 {
544 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
545
546 for (;;) {
547 node * old_tos_pointer = pool.get_pointer(old_tos);
548 if (!old_tos_pointer)
549 return false;
550
551 tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
552
553 if (tos.compare_exchange_weak(old_tos, new_tos)) {
554 f(old_tos_pointer->v);
555 pool.template destruct<true>(old_tos);
556 return true;
557 }
558 }
559 }
560
561 /** consumes all elements via a functor
562 *
563 * sequentially pops all elements from the stack and applies the functor on each object
564 *
565 * \returns number of elements that are consumed
566 *
567 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
568 * */
569 template <typename Functor>
570 size_t consume_all(Functor & f)
571 {
572 size_t element_count = 0;
573 while (consume_one(f))
574 element_count += 1;
575
576 return element_count;
577 }
578
579 /// \copydoc boost::lockfree::stack::consume_all(Functor & rhs)
580 template <typename Functor>
581 size_t consume_all(Functor const & f)
582 {
583 size_t element_count = 0;
584 while (consume_one(f))
585 element_count += 1;
586
587 return element_count;
588 }
589
590 /** consumes all elements via a functor
591 *
592 * atomically pops all elements from the stack and applies the functor on each object
593 *
594 * \returns number of elements that are consumed
595 *
596 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
597 * */
598 template <typename Functor>
599 size_t consume_all_atomic(Functor & f)
600 {
601 size_t element_count = 0;
602 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
603
604 for (;;) {
605 node * old_tos_pointer = pool.get_pointer(old_tos);
606 if (!old_tos_pointer)
607 return 0;
608
609 tagged_node_handle new_tos(pool.null_handle(), old_tos.get_next_tag());
610
611 if (tos.compare_exchange_weak(old_tos, new_tos))
612 break;
613 }
614
615 tagged_node_handle nodes_to_consume = old_tos;
616
617 for(;;) {
618 node * node_pointer = pool.get_pointer(nodes_to_consume);
619 f(node_pointer->v);
620 element_count += 1;
621
622 node * next_node = pool.get_pointer(node_pointer->next);
623
624 if (!next_node) {
625 pool.template destruct<true>(nodes_to_consume);
626 break;
627 }
628
629 tagged_node_handle next(pool.get_handle(next_node), nodes_to_consume.get_next_tag());
630 pool.template destruct<true>(nodes_to_consume);
631 nodes_to_consume = next;
632 }
633
634 return element_count;
635 }
636
637 /// \copydoc boost::lockfree::stack::consume_all_atomic(Functor & rhs)
638 template <typename Functor>
639 size_t consume_all_atomic(Functor const & f)
640 {
641 size_t element_count = 0;
642 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
643
644 for (;;) {
645 node * old_tos_pointer = pool.get_pointer(old_tos);
646 if (!old_tos_pointer)
647 return 0;
648
649 tagged_node_handle new_tos(pool.null_handle(), old_tos.get_next_tag());
650
651 if (tos.compare_exchange_weak(old_tos, new_tos))
652 break;
653 }
654
655 tagged_node_handle nodes_to_consume = old_tos;
656
657 for(;;) {
658 node * node_pointer = pool.get_pointer(nodes_to_consume);
659 f(node_pointer->v);
660 element_count += 1;
661
662 node * next_node = pool.get_pointer(node_pointer->next);
663
664 if (!next_node) {
665 pool.template destruct<true>(nodes_to_consume);
666 break;
667 }
668
669 tagged_node_handle next(pool.get_handle(next_node), nodes_to_consume.get_next_tag());
670 pool.template destruct<true>(nodes_to_consume);
671 nodes_to_consume = next;
672 }
673
674 return element_count;
675 }
676
677 /** consumes all elements via a functor
678 *
679 * atomically pops all elements from the stack and applies the functor on each object in reversed order
680 *
681 * \returns number of elements that are consumed
682 *
683 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
684 * */
685 template <typename Functor>
686 size_t consume_all_atomic_reversed(Functor & f)
687 {
688 size_t element_count = 0;
689 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
690
691 for (;;) {
692 node * old_tos_pointer = pool.get_pointer(old_tos);
693 if (!old_tos_pointer)
694 return 0;
695
696 tagged_node_handle new_tos(pool.null_handle(), old_tos.get_next_tag());
697
698 if (tos.compare_exchange_weak(old_tos, new_tos))
699 break;
700 }
701
702 tagged_node_handle nodes_to_consume = old_tos;
703
704 node * last_node_pointer = NULL;
705 tagged_node_handle nodes_in_reversed_order;
706 for(;;) {
707 node * node_pointer = pool.get_pointer(nodes_to_consume);
708 node * next_node = pool.get_pointer(node_pointer->next);
709
710 node_pointer->next = pool.get_handle(last_node_pointer);
711 last_node_pointer = node_pointer;
712
713 if (!next_node) {
714 nodes_in_reversed_order = nodes_to_consume;
715 break;
716 }
717
718 tagged_node_handle next(pool.get_handle(next_node), nodes_to_consume.get_next_tag());
719 nodes_to_consume = next;
720 }
721
722 for(;;) {
723 node * node_pointer = pool.get_pointer(nodes_in_reversed_order);
724 f(node_pointer->v);
725 element_count += 1;
726
727 node * next_node = pool.get_pointer(node_pointer->next);
728
729 if (!next_node) {
730 pool.template destruct<true>(nodes_in_reversed_order);
731 break;
732 }
733
734 tagged_node_handle next(pool.get_handle(next_node), nodes_in_reversed_order.get_next_tag());
735 pool.template destruct<true>(nodes_in_reversed_order);
736 nodes_in_reversed_order = next;
737 }
738
739 return element_count;
740 }
741
742 /// \copydoc boost::lockfree::stack::consume_all_atomic_reversed(Functor & rhs)
743 template <typename Functor>
744 size_t consume_all_atomic_reversed(Functor const & f)
745 {
746 size_t element_count = 0;
747 tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
748
749 for (;;) {
750 node * old_tos_pointer = pool.get_pointer(old_tos);
751 if (!old_tos_pointer)
752 return 0;
753
754 tagged_node_handle new_tos(pool.null_handle(), old_tos.get_next_tag());
755
756 if (tos.compare_exchange_weak(old_tos, new_tos))
757 break;
758 }
759
760 tagged_node_handle nodes_to_consume = old_tos;
761
762 node * last_node_pointer = NULL;
763 tagged_node_handle nodes_in_reversed_order;
764 for(;;) {
765 node * node_pointer = pool.get_pointer(nodes_to_consume);
766 node * next_node = pool.get_pointer(node_pointer->next);
767
768 node_pointer->next = pool.get_handle(last_node_pointer);
769 last_node_pointer = node_pointer;
770
771 if (!next_node) {
772 nodes_in_reversed_order = nodes_to_consume;
773 break;
774 }
775
776 tagged_node_handle next(pool.get_handle(next_node), nodes_to_consume.get_next_tag());
777 nodes_to_consume = next;
778 }
779
780 for(;;) {
781 node * node_pointer = pool.get_pointer(nodes_in_reversed_order);
782 f(node_pointer->v);
783 element_count += 1;
784
785 node * next_node = pool.get_pointer(node_pointer->next);
786
787 if (!next_node) {
788 pool.template destruct<true>(nodes_in_reversed_order);
789 break;
790 }
791
792 tagged_node_handle next(pool.get_handle(next_node), nodes_in_reversed_order.get_next_tag());
793 pool.template destruct<true>(nodes_in_reversed_order);
794 nodes_in_reversed_order = next;
795 }
796
797 return element_count;
798 }
799 /**
800 * \return true, if stack is empty.
801 *
802 * \note It only guarantees that at some point during the execution of the function the stack has been empty.
803 * It is rarely practical to use this value in program logic, because the stack can be modified by other threads.
804 * */
805 bool empty(void) const
806 {
807 return pool.get_pointer(tos.load()) == NULL;
808 }
809
810private:
811#ifndef BOOST_DOXYGEN_INVOKED
812 detail::atomic<tagged_node_handle> tos;
813
814 static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(tagged_node_handle);
815 char padding[padding_size];
816
817 pool_t pool;
818#endif
819};
820
821} /* namespace lockfree */
822} /* namespace boost */
823
824#endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */
825

source code of boost/libs/lockfree/include/boost/lockfree/stack.hpp