amino::ShavitQueue< T > Class Template Reference

This is an implementation of a lock-free FIFO queue data structure. The implementation is according to the paper An Optimistic Approach to Lock-Free FIFO Queues by Edya Ladan-Mozes and Nir Shavit, 2004. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.springerlink.com/content/h84dfexjftdal4p4/. More...

#include <queue_shavit.h>

List of all members.

Public Member Functions
	ShavitQueue ()
	constructor
	~ShavitQueue ()
	destructor
void	enqueue (const T &x)
	Insert an element into the tail of queue.
bool	dequeue (T &val)
	Remove a specified element by value.
bool	empty ()
	Check to see if queue is empty.
int	size ()
	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.
Classes
class	QueueItem

---

Detailed Description

template<typename T>
class amino::ShavitQueue< T >

This is an implementation of a lock-free FIFO queue data structure. The implementation is according to the paper An Optimistic Approach to Lock-Free FIFO Queues by Edya Ladan-Mozes and Nir Shavit, 2004. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.springerlink.com/content/h84dfexjftdal4p4/.

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

Author:

Xiao Jun Dai

Template Parameters:

T

type of element in the queue

---

Constructor & Destructor Documentation

template<typename T>

amino::ShavitQueue< T >::ShavitQueue

(

)

[inline]

constructor

template<typename T>

amino::ShavitQueue< T >::~ShavitQueue

(

)

[inline]

destructor

---

Member Function Documentation

template<typename T>

void amino::ShavitQueue< T >::enqueue

(

const T &

x

)

[inline]

Insert an element into the tail of queue.

Parameters:

x

The element to be added

template<typename T>

bool amino::ShavitQueue< T >::dequeue

(

T &

val

)

[inline]

Remove a specified element by value.

Parameters:

val

The element to be removed

Returns:

If the value exists in the queue, remove it and return true. else return false.

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

template<typename T>

bool amino::ShavitQueue< T >::empty

(

)

[inline]

Check to see if queue is empty.

Returns:

true if empty, or false.

template<typename T>

int amino::ShavitQueue< T >::size

(

)

[inline]

Get the size of the queue at this point.

Returns:

the number of elements in the queue

template<typename T>

bool amino::ShavitQueue< T >::peekFront

(

T &

ret

)

[inline]

Get the first element of the queue. If the queue is empty return false, else return true and assign the first to the parameter.

Parameters:

ret

The first element of the queue. It is valid if return true.

Returns:

If the queue is empty return false, else return true.

---

The documentation for this class was generated from the following file:

• include/amino/queue_shavit.h