Public Member Functions
|void||enqueue (const T &x)|
|Insert an element into the tail of queue. |
|bool||dequeue (T &val)|
|Remove a specified element by value. |
|Check to see if queue is empty. |
|Get the size of the queue at this point. |
|bool||peekFront (T &ret)|
|Get the first element of the queue. If the queue is empty return false, else return true and assign the first to the parameter. |
First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java Concurrency Package. This paper presents a new dynamic-memory lock-free FIFO queue algorithm that performs consistently better than the Michael and Scott queue.
The key idea behind our new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent. It is a practical example of an optimistic approach to reduction of synchronization overhead in concurrent data structures.
LockFreeQueue maintain a doubly-linked list, but to construct the "backwards" direction, the path of prev pointers needed by dequeues.
Sample performance results here.
The following operations are thread-safe and scalable (but see notes in method javadoc): first, offer, poll, peek
The following operations are not thread-safe: size, iterator
|T||type of element in the queue|
|void amino::ShavitQueue< T >::enqueue||(||const T &||x||)||
Insert an element into the tail of queue.
|x||The element to be added|
|bool amino::ShavitQueue< T >::dequeue||(||T &||val||)||
Remove a specified element by value.
|val||The element to be removed|
If a prev pointer is found to be inconsistent, we run a fixList method along the chain of next pointers which is guaranteed to be consistent
|bool amino::ShavitQueue< T >::empty||(||)||
Check to see if queue is empty.
|int amino::ShavitQueue< T >::size||(||)||
Get the size of the queue at this point.
|bool amino::ShavitQueue< T >::peekFront||(||T &||ret||)||
Get the first element of the queue. If the queue is empty return false, else return true and assign the first to the parameter.
|ret||The first element of the queue. It is valid if return true.|