org.amino.ds.lockfree
Class LockFreeDeque<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          org.amino.ds.lockfree.LockFreeDeque<E>

Type Parameters:

E - type of element in the deque

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>, java.util.Deque<E>, java.util.Queue<E>

public class LockFreeDeque<E>
extends java.util.AbstractQueue<E>
implements java.util.Deque<E>

This Deque implementation is based on the algorithm defined in the follwoing paper: CAS-Based Lock-Free Algorithm for Shared Deques By Maged M. Michael

As the terminology between below description differs from the Deque interface defined in Java 6, please translate left = last and right = first. Right => First, Left => Last

The deque is a double ended queue. Insertion and deletion can happen at both ends. The basic deque is maintained as a doubly linked list. An anchor data structure which comprise of 2 pointers (left and right) is used to keep track of the leftmost and rightmost element of the deque. A deque status flag is maintained to keep track of the state of the deque.

The deque is said to be in a stable state when it is 1) empty, 2) contains a single item and both the anchor pointers point to the item and 3) for all nodes x in the deque, x.right.left = x unless x is the rightmost node and x.left.right = x unless x is the leftmost node.

There are 4 unstable states for the deque. A deque can be unstable only if it has 2 or more elements. Also, only one end of the deque can have problems at any given time and the status has to show that it is unstable with the flag having a value of RPUSH or LPUSH depending on the problem side (right or left). Unstable states: 1) x.left.right != x, where x is the rightmost node. Deque status flag = RPUSH 2) x.right.left != x, where x is the leftmost node. Deque status flag = LPUSH It is acceptable for a deque to have no problems but the status flag may show that it is in an unstable state. So, the deque may have a status of RPUSH or LPUSH but still be coherent (the other two unstable states)

Insertion or deletion from either end can only be done on a stable deque. If the deque is in an unstable state it has to be stabilized first before the operation can proceed. After a right insertion the deque status is changed to an RPUSH atomically with the insertion. Similarly after a left insertion the deque status is changed to LPUSH atomically with the insertion. To put the deque back to a stable state the pointers have to be made coherent.

Thread Safety:
Follow methods are NOT thread-safe:

1. contains(Object)
2. iterator()
3. descendingIterator()

Author:

raja, ganzhi

Constructor Summary

LockFreeDeque()

Method Summary

void	addFirst(E d) This is the method that does a right push into the Deque.
void	addLast(E d) This is the method that does a left push into the Deque.
void	clear() Removes all elements, clears the deque.
boolean	contains(java.lang.Object o) Contains function is not thread safe.
java.util.Iterator<E>	descendingIterator()
E	getFirst()
E	getLast()
boolean	isEmpty() Checks to see if the deque is empty or not.
java.util.Iterator<E>	iterator()
boolean	offer(E e) Inserts element e at the tail of this deque.
boolean	offerFirst(E e)
boolean	offerLast(E e)
E	peek() Returns the first element of this deque, or null if deque is empty.
E	peekFirst()
E	peekLast()
E	poll() Returns and removes first (head) element of this deque, or null if this deque is empty.
E	pollFirst() This is the method to pop the Right node from the Deque.
E	pollLast()
E	pop()
void	push(E e)
E	remove() Returns and removes the first element in this deque.
boolean	remove(java.lang.Object o) Remove first occurrence of specified object o in this deque.
E	removeFirst()
boolean	removeFirstOccurrence(java.lang.Object o)
E	removeLast()
boolean	removeLastOccurrence(java.lang.Object o)
int	size()

Methods inherited from class java.util.AbstractQueue

add, addAll, element

Methods inherited from class java.util.AbstractCollection

containsAll, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Deque

add, element

Methods inherited from interface java.util.Collection

addAll, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Constructor Detail

LockFreeDeque

public LockFreeDeque()

Method Detail

offer

public boolean offer(E e)

Inserts element e at the tail of this deque. Preferable to addLast(E).

Specified by:

offer in interface java.util.Deque<E>

Specified by:

offer in interface java.util.Queue<E>

Parameters:

e - element to insert

Returns:

true if the element was successfully added, false otherwise.

peek

public E peek()

Returns the first element of this deque, or null if deque is empty. Element is not removed.

Specified by:

peek in interface java.util.Deque<E>

Specified by:

peek in interface java.util.Queue<E>

Returns:

head of this deque, or null if deque is empty.

poll

public E poll()

Returns and removes first (head) element of this deque, or null if this deque is empty.

Specified by:

poll in interface java.util.Deque<E>

Specified by:

poll in interface java.util.Queue<E>

Returns:

head of this deque, or null if empty.

remove

public E remove()

Returns and removes the first element in this deque.

Specified by:

remove in interface java.util.Deque<E>

Specified by:

remove in interface java.util.Queue<E>

Overrides:

remove in class java.util.AbstractQueue<E>

Returns:

the head of this deque.

descendingIterator

public java.util.Iterator<E> descendingIterator()

Specified by:

descendingIterator in interface java.util.Deque<E>

getFirst

public E getFirst()

Specified by:

getFirst in interface java.util.Deque<E>

getLast

public E getLast()

Specified by:

getLast in interface java.util.Deque<E>

offerFirst

public boolean offerFirst(E e)

Specified by:

offerFirst in interface java.util.Deque<E>

offerLast

public boolean offerLast(E e)

Specified by:

offerLast in interface java.util.Deque<E>

removeFirst

public E removeFirst()

Specified by:

removeFirst in interface java.util.Deque<E>

removeFirstOccurrence

public boolean removeFirstOccurrence(java.lang.Object o)

Specified by:

removeFirstOccurrence in interface java.util.Deque<E>

removeLast

public E removeLast()

Specified by:

removeLast in interface java.util.Deque<E>

removeLastOccurrence

public boolean removeLastOccurrence(java.lang.Object o)

Specified by:

removeLastOccurrence in interface java.util.Deque<E>

clear

public void clear()

Removes all elements, clears the deque.

Specified by:

clear in interface java.util.Collection<E>

Overrides:

clear in class java.util.AbstractQueue<E>

contains

public boolean contains(java.lang.Object o)

Contains function is not thread safe. It can only be used when no other threads are modifying this deque.

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.Deque<E>

Overrides:

contains in class java.util.AbstractCollection<E>

Parameters:

o - is the Object we are looking for.

Throws:

java.lang.UnsupportedOperationException

isEmpty

public boolean isEmpty()

Checks to see if the deque is empty or not.

Specified by:

isEmpty in interface java.util.Collection<E>

Overrides:

isEmpty in class java.util.AbstractCollection<E>

Returns:

true if deque is empty

iterator

public java.util.Iterator<E> iterator()

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in interface java.util.Deque<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

remove

public boolean remove(java.lang.Object o)

Remove first occurrence of specified object o in this deque.

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.Deque<E>

Overrides:

remove in class java.util.AbstractCollection<E>

Parameters:

o - element to be removed, if present.

Returns:

true if an element was removed.

size

public int size()

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.Deque<E>

Specified by:

size in class java.util.AbstractCollection<E>

Returns:

size of the deque

addFirst

public void addFirst(E d)

This is the method that does a right push into the Deque. It takes the data as input, creates a deque node with the data and then pushes it onto the deque from right.

Specified by:

addFirst in interface java.util.Deque<E>

Parameters:

d - element being added

peekFirst

public E peekFirst()

Specified by:

peekFirst in interface java.util.Deque<E>

pollFirst

public E pollFirst()

This is the method to pop the Right node from the Deque.

Specified by:

pollFirst in interface java.util.Deque<E>

Returns:

head of this deque, or null if empty.

addLast

public void addLast(E d)

This is the method that does a left push into the Deque. It takes the data as input, creates a deque node with the data and then pushes it onto the deque from left.

Specified by:

addLast in interface java.util.Deque<E>

Parameters:

d - element to add

peekLast

public E peekLast()

Specified by:

peekLast in interface java.util.Deque<E>

pollLast

public E pollLast()

Specified by:

pollLast in interface java.util.Deque<E>

pop

public E pop()

Specified by:

pop in interface java.util.Deque<E>

Returns:

element popped

push

public void push(E e)

Specified by:

push in interface java.util.Deque<E>

Parameters:

e - element pushed