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

java.lang.Object
  org.amino.ds.lockfree.LockFreeList<E>

Type Parameters:

E - the type of elements held in this collection

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>

Direct Known Subclasses:

LockFreeOrderedList

public class LockFreeList<E>
extends java.lang.Object
implements java.util.List<E>

This is an implementation of a lock-free linked list data structure. The implementation is according to the paper High Performance Dynamic Lock-Free Hash Tables and List-Based Sets by Maged M. Michael, 2002. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.research.ibm.com/people/m/michael/spaa-2002.pdf

This lock-free linked list is an unbounded thread-safe linked list. A LockFreeList is an appropriate choice when many threads will share access to a common collection. This list does not permit null elements.

This is a lock-free implementation intended for highly scalable add, remove and contains which is thread safe. All method related to index is not implemented. Add() will add the element to the head of the list which is different with the normal list.

Author:

Xiao Jun Dai

Nested Class Summary

protected static class	LockFreeList.Entry<E> internal node definition.
protected static class	LockFreeList.ListStateHolder<E> hold state between two function calls.

Field Summary

protected java.util.concurrent.atomic.AtomicMarkableReference<LockFreeList.Entry<E>>

head Pointer to header node, initialized to a dummy node.

Constructor Summary

LockFreeList()
Constructs an empty list.

Method Summary

boolean	add(E e) Adds the specified element to the head of this list.
void	add(int index, E element)
boolean	addAll(java.util.Collection<? extends E> c)
boolean	addAll(int index, java.util.Collection<? extends E> c)
void	clear() Removes all of the elements from this list (optional operation).
boolean	contains(java.lang.Object o) Returns true if this list contains the specified element.
boolean	containsAll(java.util.Collection<?> c)
E	get(int index)
int	indexOf(java.lang.Object o)
boolean	isEmpty()
java.util.Iterator<E>	iterator()
int	lastIndexOf(java.lang.Object o)
java.util.ListIterator<E>	listIterator()
java.util.ListIterator<E>	listIterator(int index)
E	remove(int index)
boolean	remove(java.lang.Object o)
boolean	removeAll(java.util.Collection<?> c)
boolean	retainAll(java.util.Collection<?> c)
E	set(int index, E element)
int	size()
java.util.List<E>	subList(int fromIndex, int toIndex)
java.lang.Object[]	toArray()
<T> T[]	toArray(T[] a)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.List

equals, hashCode

Field Detail

head

protected java.util.concurrent.atomic.AtomicMarkableReference<LockFreeList.Entry<E>> head

Pointer to header node, initialized to a dummy node. The first actual node is at head.getNext().

Constructor Detail

LockFreeList

public LockFreeList()

Constructs an empty list.

Method Detail

add

public boolean add(E e)

Adds the specified element to the head of this list. NOTICE: add the element to the head of the list which is different with the normal list.

Thread Safe

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Parameters:

e - the element to add.

Returns:

true (as per the general contract of Collection.add).

clear

public void clear()

Removes all of the elements from this list (optional operation). This list will be empty after this call returns (unless it throws an exception).

Thread Safe

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.List<E>

contains

public boolean contains(java.lang.Object o)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that o.equals(e).

Thread Safe

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.List<E>

Parameters:

o - element whose presence in this list is to be tested.

Returns:

true if this list contains the specified element.

isEmpty

public boolean isEmpty()

Thread Safe

Specified by:

isEmpty in interface java.util.Collection<E>

Specified by:

isEmpty in interface java.util.List<E>

remove

public boolean remove(java.lang.Object o)

Thread Safe

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.List<E>

iterator

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

Not Thread Safe

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.List<E>

size

public int size()

Not Thread Safe

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.List<E>

add

public void add(int index,
                E element)

Specified by:

add in interface java.util.List<E>

addAll

public boolean addAll(int index,
                      java.util.Collection<? extends E> c)

Specified by:

addAll in interface java.util.List<E>

get

public E get(int index)

Specified by:

get in interface java.util.List<E>

indexOf

public int indexOf(java.lang.Object o)

Specified by:

indexOf in interface java.util.List<E>

lastIndexOf

public int lastIndexOf(java.lang.Object o)

Specified by:

lastIndexOf in interface java.util.List<E>

listIterator

public java.util.ListIterator<E> listIterator()

Specified by:

listIterator in interface java.util.List<E>

listIterator

public java.util.ListIterator<E> listIterator(int index)

Specified by:

listIterator in interface java.util.List<E>

remove

public E remove(int index)

Specified by:

remove in interface java.util.List<E>

removeAll

public boolean removeAll(java.util.Collection<?> c)

Specified by:

removeAll in interface java.util.Collection<E>

Specified by:

removeAll in interface java.util.List<E>

retainAll

public boolean retainAll(java.util.Collection<?> c)

Specified by:

retainAll in interface java.util.Collection<E>

Specified by:

retainAll in interface java.util.List<E>

set

public E set(int index,
             E element)

Specified by:

set in interface java.util.List<E>

subList

public java.util.List<E> subList(int fromIndex,
                                 int toIndex)

Specified by:

subList in interface java.util.List<E>

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

toArray

public <T> T[] toArray(T[] a)

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

addAll

public boolean addAll(java.util.Collection<? extends E> c)

Specified by:

addAll in interface java.util.Collection<E>

Specified by:

addAll in interface java.util.List<E>

containsAll

public boolean containsAll(java.util.Collection<?> c)

Specified by:

containsAll in interface java.util.Collection<E>

Specified by:

containsAll in interface java.util.List<E>