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

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

Type Parameters:

E - Type of elements stored in the set

All Implemented Interfaces:

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

public class LockFreeSet<E>
extends java.lang.Object
implements java.util.Set<E>

This is an implementation of lock-free hashset data structure, based on algorithm described in two paper

• "Split-Ordered Lists - Lock-free Resizable Hash Tables" by Ori Shalev Tel Aviv University and Nir Shavit Tel-Aviv University and Sun Microsystems Laboratories
• "High Performance Dynamic Lock-Free Hash Tables and List-Based Set" by Maged M. Michael.

The internal data structure is a single linked list, which uses the same algorithm as LockFreeOrderedList. Elements are sorted by "binary reversal" of hash of elements. Additionally, an array of dummy nodes is stored to allow quick access to elements in the middle of elements. Elements are wrapped by HashLinkNode before stored into set.

Author:

Zhi Gan

Constructor Summary

LockFreeSet()
Create a new LockFreeSet.

LockFreeSet(int expectedSize)

LockFreeSet(int expectedSize, float loadFactor)
Create a new set with explicitly specified expected size and load factor.

Method Summary

boolean	add(E e)
boolean	addAll(java.util.Collection<? extends E> c)
void	clear()
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection<?> c)
boolean	isEmpty()
java.util.Iterator<E>	iterator()
boolean	remove(java.lang.Object o)
boolean	removeAll(java.util.Collection<?> c)
boolean	retainAll(java.util.Collection<?> c) This method is not thread-safe.
int	size()
java.lang.Object[]	toArray() This method puts all elements of set into an array and returns it.
<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.Set

equals, hashCode

Constructor Detail

LockFreeSet

public LockFreeSet(int expectedSize,
                   float loadFactor)

Create a new set with explicitly specified expected size and load factor. The number of dummy nodes has a maximum of 512*expectedSize. This isn't a limitation of actual elements stored in set. But the average search number will increase if number of elements is bigger than 512*expectedSize

Parameters:

expectedSize - the estimated size of set

loadFactor - average load factor. Number of dummy nodes will expand 2X if the actual load factor is higher than this parameter.

LockFreeSet

public LockFreeSet(int expectedSize)

Parameters:

expectedSize - expected set size.

LockFreeSet

public LockFreeSet()

Create a new LockFreeSet. The default expected size is 512. And load factor defaults to 0.75f

Method Detail

add

public boolean add(E e)

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.Set<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.Set<E>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.Set<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.Set<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.Set<E>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection<E>

Specified by:

isEmpty in interface java.util.Set<E>

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

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.Set<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.Set<E>

retainAll

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

This method is not thread-safe. It's programmer's responsibility to ensure there is no other threads modifying the set simultaneously.

Specified by:

retainAll in interface java.util.Collection<E>

Specified by:

retainAll in interface java.util.Set<E>

Parameters:

c - collection containing elements to be retained in this set

Returns:

true if this set changed as a result of the call

size

public int size()

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.Set<E>

toArray

public java.lang.Object[] toArray()

This method puts all elements of set into an array and returns it. This method is not thread-safe. It's programmer's responsibility to ensure there is no other threads modifying the set simultaneously. Under the hood, this method use iterator to collect elements inside the set.

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.Set<E>

Returns:

an array containing all the elements in this set

toArray

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

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.Set<E>