org.amino.utility
Class EliminationArray

java.lang.Object
  org.amino.utility.EliminationArray

All Implemented Interfaces:

IEliminationArray

public class EliminationArray
extends java.lang.Object
implements IEliminationArray

A global elimination array class for several data structures. It can be used to reducing number of modification to central data structure. The idea comes from following observation:

If two threads execute push() or pop() operation on a stack, there is no need to modify the stack at all. We can simply transfer object from push() to the pop() and both operations succeed.

Two arrays are created to store two type of operations, which are inversion of each other. It can be used to stack, deque, and even list. The algorithm comes from following paper, but not exactly the same.

 A Scalable Lock-free Stack Algorithm
 Danny Hendler                Nir Shavit            Lena Yerushalmi
 School of Computer Science Tel-Aviv University & School of Computer Science
  Tel-Aviv University     Sun Microsystems           Tel-Aviv University
  Tel Aviv, Israel 69978      Laboratories          Tel Aviv, Israel 69978
  hendlerd@post.tau.ac.il    shanir@sun.com          lenay@post.tau.ac.il
 

Author:

Zhi Gan (ganzhi@gmail.com)

Constructor Summary

EliminationArray(int arraySize)
Create an EliminationArray object with specified size.

Method Summary

void	dump() dump for debug.
boolean	tryAdd(java.lang.Object obj, int backOff) Try to add element without touching the central data structure.
java.lang.Object	tryRemove(int backOff) Try to remove element without touching central data structure.

Methods inherited from class java.lang.Object

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

Constructor Detail

EliminationArray

public EliminationArray(int arraySize)

Create an EliminationArray object with specified size.

Parameters:

arraySize - Size of internal array

Method Detail

dump

public void dump()

dump for debug.

tryAdd

public boolean tryAdd(java.lang.Object obj,
                      int backOff)
               throws java.lang.InterruptedException

Try to add element without touching the central data structure. If this operation can successfully locate a removing thread, it will succeed. Else, it will sleep for several milliseconds and waiting to be located by removing threads.

Specified by:

tryAdd in interface IEliminationArray

Parameters:

obj - the adding object

backOff - time in millisecond for sleeping if match haven't been found immediately.

Returns:

true if match happened between this method and tryRemove(int)

Throws:

java.lang.InterruptedException - throw exception if interrupted

tryRemove

public java.lang.Object tryRemove(int backOff)
                           throws java.lang.InterruptedException

Try to remove element without touching central data structure. If this operation can successfully locate a adding thread, it will succeed. Else, it will sleep for several milliseconds and waiting to be located by adding threads.

Specified by:

tryRemove in interface IEliminationArray

Parameters:

backOff - time in millisecond for sleeping if match haven't been found immediately.

Returns:

null if no match. Argument to tryAdd() method if successful match

Throws:

java.lang.InterruptedException - throw exception if be interrupted