water.nbhm

Class NonBlockingSetInt

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<java.lang.Integer>

water.nbhm.NonBlockingSetInt

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<java.lang.Integer>, java.util.Collection<java.lang.Integer>, java.util.Set<java.lang.Integer>

public class NonBlockingSetInt
extends java.util.AbstractSet<java.lang.Integer>
implements java.io.Serializable

A multi-threaded bit-vector set, implemented as an array of primitive longs. All operations are non-blocking and multi-threaded safe. contains(int) calls are roughly the same speed as a {load, mask} sequence. add(int) and remove(int) calls are a tad more expensive than a {load, mask, store} sequence because they must use a CAS. The bit-vector is auto-sizing.

General note of caution: The Set API allows the use of Integer with silent autoboxing - which can be very expensive if many calls are being made. Since autoboxing is silent you may not be aware that this is going on. The built-in API takes lower-case ints and is much more efficient.

Space: space is used in proportion to the largest element, as opposed to the number of elements (as is the case with hash-table based Set implementations). Space is approximately (largest_element/8 + 64) bytes. The implementation is a simple bit-vector using CAS for update.

Since:

1.5

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
NonBlockingSetInt() Create a new empty bit-vector

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(int i) Add i to the set.
boolean	add(java.lang.Integer i) Add i to the set.
void	clear() Empty the bitvector.
boolean	contains(int i) Test if i is in the set.
boolean	contains(java.lang.Object o) Test if o is in the set.
java.util.Iterator<java.lang.Integer>	iterator() Standard Java Iterator.
int	length() Approx largest element in set; at least as big (but max might be smaller).
void	print() Verbose printout of internal structure for debugging.
boolean	remove(int i) Remove i from the set.
boolean	remove(java.lang.Object o) Remove o from the set.
int	size() Current count of elements in the set.

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, 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.Set

addAll, containsAll, isEmpty, retainAll, toArray, toArray

Constructor Detail

NonBlockingSetInt

public NonBlockingSetInt()

Create a new empty bit-vector

Method Detail

add

public boolean add(java.lang.Integer i)

Add i to the set. Uppercase Integer version of add, requires auto-unboxing. When possible use the int version of add(int) for efficiency.

Specified by:

add in interface java.util.Collection<java.lang.Integer>

Specified by:

add in interface java.util.Set<java.lang.Integer>

Overrides:

add in class java.util.AbstractCollection<java.lang.Integer>

Returns:

true if i was added to the set.

Throws:

java.lang.IllegalArgumentException - if i is negative.

contains

public boolean contains(java.lang.Object o)

Test if o is in the set. This is the uppercase Integer version of contains, requires a type-check and auto-unboxing. When possible use the int version of contains(int) for efficiency.

Specified by:

contains in interface java.util.Collection<java.lang.Integer>

Specified by:

contains in interface java.util.Set<java.lang.Integer>

Overrides:

contains in class java.util.AbstractCollection<java.lang.Integer>

Returns:

true if i was in the set.

remove

public boolean remove(java.lang.Object o)

Remove o from the set. This is the uppercase Integer version of remove, requires a type-check and auto-unboxing. When possible use the int version of remove(int) for efficiency.

Specified by:

remove in interface java.util.Collection<java.lang.Integer>

Specified by:

remove in interface java.util.Set<java.lang.Integer>

Overrides:

remove in class java.util.AbstractCollection<java.lang.Integer>

Returns:

true if i was removed to the set.

add

public boolean add(int i)

Add i to the set. This is the lower-case 'int' version of add(java.lang.Integer) - no autoboxing. Negative values throw IllegalArgumentException.

Returns:

true if i was added to the set.

Throws:

java.lang.IllegalArgumentException - if i is negative.

contains

public boolean contains(int i)

Test if i is in the set. This is the lower-case 'int' version of contains(java.lang.Object) - no autoboxing.

Returns:

true if i was int the set.

remove

public boolean remove(int i)

Remove i from the set. This is the fast lower-case 'int' version of remove(java.lang.Object) - no autoboxing.

Returns:

true if i was added to the set.

size

public int size()

Current count of elements in the set. Due to concurrent racing updates, the size is only ever approximate. Updates due to the calling thread are immediately visible to calling thread.

Specified by:

size in interface java.util.Collection<java.lang.Integer>

Specified by:

size in interface java.util.Set<java.lang.Integer>

Specified by:

size in class java.util.AbstractCollection<java.lang.Integer>

Returns:

count of elements.

length

public int length()

Approx largest element in set; at least as big (but max might be smaller).

clear

public void clear()

Empty the bitvector.

Specified by:

clear in interface java.util.Collection<java.lang.Integer>

Specified by:

clear in interface java.util.Set<java.lang.Integer>

Overrides:

clear in class java.util.AbstractCollection<java.lang.Integer>

print

public void print()

Verbose printout of internal structure for debugging.

iterator

public java.util.Iterator<java.lang.Integer> iterator()

Standard Java Iterator. Not very efficient because it auto-boxes the returned values.

Specified by:

iterator in interface java.lang.Iterable<java.lang.Integer>

Specified by:

iterator in interface java.util.Collection<java.lang.Integer>

Specified by:

iterator in interface java.util.Set<java.lang.Integer>

Specified by:

iterator in class java.util.AbstractCollection<java.lang.Integer>