lass::stde::lock_free_queue< T, FixedAllocator > Class Template Reference
Non-blocking, lock-free FIFO data structure. More...
#include <lock_free_queue.h>
Data Structures | |
| struct | node_t |
Public Types | |
| typedef T | value_type |
Public Member Functions | |
| lock_free_queue () | |
| ~lock_free_queue () | |
| void | push (const value_type &x) |
| push a value in the back | |
| bool | pop (value_type &x) |
| Try to pop a value from the front and store it in x. | |
Private Types | |
| typedef util::TaggedPtr< node_t > | pointer_t |
| typedef util::AllocatorThrow < util::AllocatorConcurrentFreeList < FixedAllocator > > | allocator_t |
Private Member Functions | |
| lock_free_queue (const lock_free_queue &) | |
| lock_free_queue & | operator= (const lock_free_queue &) |
| value_type *const | make_value (const value_type &x) |
| void | free_value (value_type *value) |
| node_t *const | make_node (value_type *x) |
| void | free_node (node_t *node) |
Private Attributes | |
| volatile pointer_t | head_ |
| volatile pointer_t | tail_ |
| allocator_t | node_allocator_ |
| allocator_t | value_allocator_ |
Detailed Description
template<typename T, typename FixedAllocator = util::AllocatorFixed<util::AllocatorMalloc>>
class lass::stde::lock_free_queue< T, FixedAllocator >
Non-blocking, lock-free FIFO data structure.
M. M. Michael, M. L. Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms", Proc. of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC' 96), New York, USA, pp. 267-275 (1996).
Definition at line 67 of file lock_free_queue.h.
Member Typedef Documentation
| typedef T lass::stde::lock_free_queue< T, FixedAllocator >::value_type |
Definition at line 71 of file lock_free_queue.h.
typedef util::TaggedPtr<node_t> lass::stde::lock_free_queue< T, FixedAllocator >::pointer_t [private] |
Definition at line 80 of file lock_free_queue.h.
typedef util::AllocatorThrow< util::AllocatorConcurrentFreeList<FixedAllocator> > lass::stde::lock_free_queue< T, FixedAllocator >::allocator_t [private] |
Definition at line 89 of file lock_free_queue.h.
Constructor & Destructor Documentation
| lass::stde::lock_free_queue< T, A >::lock_free_queue | ( | ) | [inline] |
Definition at line 51 of file lock_free_queue.inl.
References lass::util::TaggedPtr< T >::atomicCompareAndSwap(), lass::stde::lock_free_queue< T, FixedAllocator >::head_, LASS_ASSERT, lass::stde::lock_free_queue< T, FixedAllocator >::make_node(), and lass::stde::lock_free_queue< T, FixedAllocator >::tail_.
| lass::stde::lock_free_queue< T, A >::~lock_free_queue | ( | ) | [inline] |
Definition at line 73 of file lock_free_queue.inl.
References lass::stde::lock_free_queue< T, FixedAllocator >::free_node(), lass::util::TaggedPtr< T >::get(), lass::stde::lock_free_queue< T, FixedAllocator >::head_, and lass::stde::next().
| lass::stde::lock_free_queue< T, FixedAllocator >::lock_free_queue | ( | const lock_free_queue< T, FixedAllocator > & | ) | [private] |
Member Function Documentation
| void lass::stde::lock_free_queue< T, A >::push | ( | const value_type & | x | ) | [inline] |
push a value in the back
- exception safe: if no node of could be allocatoed, or if copy constructor of x throws, it fails gracefully.
Definition at line 91 of file lock_free_queue.inl.
References lass::util::TaggedPtr< T >::atomicCompareAndSwap(), lass::stde::lock_free_queue< T, FixedAllocator >::free_value(), lass::util::TaggedPtr< T >::get(), lass::stde::lock_free_queue< T, FixedAllocator >::make_node(), lass::stde::lock_free_queue< T, FixedAllocator >::make_value(), lass::stde::next(), lass::util::TaggedPtr< T >::tag(), and lass::stde::lock_free_queue< T, FixedAllocator >::tail_.
Referenced by lass::util::ThreadPool< TaskType, ConsumerType, IdlePolicy, ParticipationPolicy >::addTask().
| bool lass::stde::lock_free_queue< T, A >::pop | ( | value_type & | x | ) | [inline] |
Try to pop a value from the front and store it in x.
- Returns:
- false if no element could be popped.
- EXCEPTION UNSAFE: if the copy constructor of x can throw, things can go miserably wrong!
Definition at line 137 of file lock_free_queue.inl.
References lass::util::TaggedPtr< T >::atomicCompareAndSwap(), lass::stde::lock_free_queue< T, FixedAllocator >::free_node(), lass::stde::lock_free_queue< T, FixedAllocator >::free_value(), lass::util::TaggedPtr< T >::get(), lass::stde::lock_free_queue< T, FixedAllocator >::head_, lass::stde::next(), lass::util::TaggedPtr< T >::tag(), and lass::stde::lock_free_queue< T, FixedAllocator >::tail_.
Referenced by lass::util::ThreadPool< TaskType, ConsumerType, IdlePolicy, ParticipationPolicy >::clearQueue(), and lass::util::ThreadPool< TaskType, ConsumerType, IdlePolicy, ParticipationPolicy >::ConsumerThread::doRun().
| lock_free_queue& lass::stde::lock_free_queue< T, FixedAllocator >::operator= | ( | const lock_free_queue< T, FixedAllocator > & | ) | [private] |
| lock_free_queue< T, A >::value_type *const lass::stde::lock_free_queue< T, A >::make_value | ( | const value_type & | x | ) | [inline, private] |
Definition at line 186 of file lock_free_queue.inl.
References lass::util::AllocatorThrow< Allocator >::allocate(), and lass::stde::lock_free_queue< T, FixedAllocator >::value_allocator_.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::push().
| void lass::stde::lock_free_queue< T, A >::free_value | ( | value_type * | value | ) | [inline, private] |
Definition at line 204 of file lock_free_queue.inl.
References lass::stde::lock_free_queue< T, FixedAllocator >::value_allocator_.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::pop(), and lass::stde::lock_free_queue< T, FixedAllocator >::push().
| lock_free_queue< T, A >::node_t *const lass::stde::lock_free_queue< T, A >::make_node | ( | value_type * | x | ) | [inline, private] |
Definition at line 214 of file lock_free_queue.inl.
References lass::util::AllocatorThrow< Allocator >::allocate(), lass::stde::lock_free_queue< T, FixedAllocator >::node_t::next, lass::stde::lock_free_queue< T, FixedAllocator >::node_allocator_, and lass::stde::lock_free_queue< T, FixedAllocator >::node_t::value.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::lock_free_queue(), and lass::stde::lock_free_queue< T, FixedAllocator >::push().
| void lass::stde::lock_free_queue< T, A >::free_node | ( | node_t * | node | ) | [inline, private] |
Definition at line 233 of file lock_free_queue.inl.
References lass::stde::lock_free_queue< T, FixedAllocator >::node_t::next, and lass::stde::lock_free_queue< T, FixedAllocator >::node_allocator_.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::pop(), and lass::stde::lock_free_queue< T, FixedAllocator >::~lock_free_queue().
Field Documentation
volatile pointer_t lass::stde::lock_free_queue< T, FixedAllocator >::head_ [private] |
Definition at line 99 of file lock_free_queue.h.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::lock_free_queue(), lass::stde::lock_free_queue< T, FixedAllocator >::pop(), and lass::stde::lock_free_queue< T, FixedAllocator >::~lock_free_queue().
volatile pointer_t lass::stde::lock_free_queue< T, FixedAllocator >::tail_ [private] |
Definition at line 100 of file lock_free_queue.h.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::lock_free_queue(), lass::stde::lock_free_queue< T, FixedAllocator >::pop(), and lass::stde::lock_free_queue< T, FixedAllocator >::push().
allocator_t lass::stde::lock_free_queue< T, FixedAllocator >::node_allocator_ [private] |
Definition at line 101 of file lock_free_queue.h.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::free_node(), and lass::stde::lock_free_queue< T, FixedAllocator >::make_node().
allocator_t lass::stde::lock_free_queue< T, FixedAllocator >::value_allocator_ [private] |
Definition at line 102 of file lock_free_queue.h.
Referenced by lass::stde::lock_free_queue< T, FixedAllocator >::free_value(), and lass::stde::lock_free_queue< T, FixedAllocator >::make_value().
The documentation for this class was generated from the following files:
