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

java.lang.Object
  org.amino.ds.lockfree.LockFreeList<E>
      org.amino.ds.lockfree.LockFreeOrderedList<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>

public class LockFreeOrderedList<E>
extends LockFreeList<E>

This an implementation of a lock-free ordered 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

An unbounded thread-safe linked list which its element is ordered. A LockFreeOrderedList is an appropriate choice when many threads will share access to a common collection. This list does not permit null elements. All elements in the list is ordered according to compare()

This is a lock-free implementation intended for highly scalable add, remove and contains which is thread safe. All mothed related to index is not thread safe. 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

Nested classes/interfaces inherited from class org.amino.ds.lockfree.LockFreeList

LockFreeList.Entry<E>, LockFreeList.ListStateHolder<E>

Field Summary

Fields inherited from class org.amino.ds.lockfree.LockFreeList

head

Constructor Summary

LockFreeOrderedList()
Creates a LockfreeList that is initially empty.

LockFreeOrderedList(java.util.Collection<? extends E> c)
Creates a LockfreeList initially containing the elements of the given collection, added in traversal order of the collection's iterator.

Method Summary

boolean

add(E e) Adds the specified element to this list.

Methods inherited from class org.amino.ds.lockfree.LockFreeList

add, addAll, addAll, clear, contains, containsAll, get, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, retainAll, set, size, subList, toArray, toArray

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

Constructor Detail

LockFreeOrderedList

public LockFreeOrderedList()

Creates a LockfreeList that is initially empty.

LockFreeOrderedList

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

Creates a LockfreeList initially containing the elements of the given collection, added in traversal order of the collection's iterator.

Parameters:

c - the collection of elements to initially contain

Method Detail

add

public boolean add(E e)

Adds the specified element to this list.

Thread Safe

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Overrides:

add in class LockFreeList<E>

Parameters:

e - the element to add.

Returns:

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