org.cliffc.high_scale_lib
Class NonBlockingSetInt

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<Integer>
          org.cliffc.high_scale_lib.NonBlockingSetInt

All Implemented Interfaces:

Serializable, Iterable<Integer>, Collection<Integer>, Set<Integer>

public class NonBlockingSetInt
extends AbstractSet<Integer>
implements 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

Author:

Cliff Click

See Also:

Serialized Form

Constructor Summary

NonBlockingSetInt()
Create a new empty bit-vector

Method Summary

boolean	add(int i) Add i to the set.
boolean	add(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(Object o) Test if o is in the set.
Iterator<Integer>	iterator() Standard Java Iterator.
void	print() Verbose printout of internal structure for debugging.
boolean	remove(int i) Remove i from the set.
boolean	remove(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

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(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 Collection<Integer>

Specified by:

add in interface Set<Integer>

Overrides:

add in class AbstractCollection<Integer>

Returns:

true if i was added to the set.

Throws:

IllegalArgumentException - if i is negative.

contains

public boolean contains(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 Collection<Integer>

Specified by:

contains in interface Set<Integer>

Overrides:

contains in class AbstractCollection<Integer>

Returns:

true if i was in the set.

remove

public boolean remove(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 Collection<Integer>

Specified by:

remove in interface Set<Integer>

Overrides:

remove in class AbstractCollection<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:

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 Collection<Integer>

Specified by:

size in interface Set<Integer>

Specified by:

size in class AbstractCollection<Integer>

Returns:

count of elements.

clear

public void clear()

Empty the bitvector.

Specified by:

clear in interface Collection<Integer>

Specified by:

clear in interface Set<Integer>

Overrides:

clear in class AbstractCollection<Integer>

print

public void print()

Verbose printout of internal structure for debugging.

iterator

public Iterator<Integer> iterator()

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

Specified by:

iterator in interface Iterable<Integer>

Specified by:

iterator in interface Collection<Integer>

Specified by:

iterator in interface Set<Integer>

Specified by:

iterator in class AbstractCollection<Integer>