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

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          org.amino.ds.lockfree.EBDeque<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 EBDeque<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

This deque add elimination mechanism to deal with high contention rate scenario. Please read about EliminationArray to get more information. If we don't consider elimination backoff, this class implements the same algorithm as LockFreeDeque

Author:

Zhi Gan

Constructor Summary

EBDeque()
default constructor.

EBDeque(int eliminationSize)

Method Summary

boolean	add(E e) Inserts element e at the end of the deque.
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)
java.util.Iterator<E>	descendingIterator()
void	dump() It's used for debugging purpose.
E	element() Returns head (first element) of this deque, but does not remove it.
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

addAll

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.Collection

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

Constructor Detail

EBDeque

public EBDeque()

default constructor.

EBDeque

public EBDeque(int eliminationSize)

Parameters:

eliminationSize - default size of elimination array

Method Detail

dump

public void dump()

It's used for debugging purpose.

element

public E element()

Returns head (first element) of this deque, but does not remove it.

Specified by:

element in interface java.util.Deque<E>

Specified by:

element in interface java.util.Queue<E>

Overrides:

element in class java.util.AbstractQueue<E>

Returns:

head of this deque.

Throws:

java.util.NoSuchElementException

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>

add

public boolean add(E e)

Inserts element e at the end of the deque.

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.Deque<E>

Specified by:

add in interface java.util.Queue<E>

Overrides:

add in class java.util.AbstractQueue<E>

Parameters:

e - element being added to the end of the deque.

Returns:

true if add

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)

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>

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 to add

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:

element polled

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

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>

push

public void push(E e)

Specified by:

push in interface java.util.Deque<E>