`#include <queue_shavit.h>`

## 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 |

class amino::ShavitQueue< T >

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

**Template Parameters:**-
*T*type of element in the queue

template<typename T>

amino::ShavitQueue< T >::ShavitQueue | ( | ) | ` [inline]` |

constructor

template<typename T>

amino::ShavitQueue< T >::~ShavitQueue | ( | ) | ` [inline]` |

destructor

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

Generated on Tue Dec 9 13:39:39 2008 for Amino by 1.5.6