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

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          org.amino.ds.lockfree.LockFreeVector<E>

Type Parameters:

E - type of element in the vector

All Implemented Interfaces:

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

public class LockFreeVector<E>
extends java.util.AbstractList<E>

It is a thread safe and lock-free vector. This class implement algorithm from:
"Lock-free Dynamically Resizable Arrays"
Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup
Texas A&M University College Station, TX 77843-3112
{dechev, peter.pirkelbauer}@tamu.edu, bs@cs.tamu.edu This vector supports dynamic expansion of vector in a lock-free manner. The elements are stored in an array of segments. The fist segment (with an index of '0') can contain 8 elements. See FIRST_BUCKET_SIZE. The nth segment can contain 8*(2**n) elements.

Author:

Zhi Gan

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

LockFreeVector()
Create a new lock-free vector.

Method Summary

boolean	add(E object)
E	get(int index) Get element with the index.
E	popBack() Remove the last element in the vector.
void	pushBack(E e) add e at the end of vector.
void	reserve(int newSize) reserve more space.
E	set(int index, E e) Set the element with index to e.
int	size() return size of vector.

Methods inherited from class java.util.AbstractList

add, addAll, clear, equals, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, remove, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

LockFreeVector

public LockFreeVector()

Create a new lock-free vector.

Method Detail

pushBack

public void pushBack(E e)

add e at the end of vector.

Parameters:

e - element added

popBack

public E popBack()

Remove the last element in the vector. We don't shrink size of segments here. So the memory of vector never shrink.

Returns:

element removed

get

public E get(int index)

Get element with the index.

Specified by:

get in interface java.util.List<E>

Specified by:

get in class java.util.AbstractList<E>

Parameters:

index - index

Returns:

element with the index

set

public E set(int index,
             E e)

Set the element with index to e.

Specified by:

set in interface java.util.List<E>

Overrides:

set in class java.util.AbstractList<E>

Parameters:

index - index of element to be reset

e - element to set

Returns:

old value

reserve

public void reserve(int newSize)

reserve more space.

Parameters:

newSize - new size be reserved

size

public int size()

return size of vector.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.List<E>

Specified by:

size in class java.util.AbstractCollection<E>

Returns:

size of vector

add

public boolean add(E object)

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Overrides:

add in class java.util.AbstractList<E>