Package org.jctools.maps
Class NonBlockingSetInt
- All Implemented Interfaces:
Serializable
,Iterable<Integer>
,Collection<Integer>
,Set<Integer>
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
private static final class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate NonBlockingSetInt.NBSI
private static final long
private static final long
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
add
(int i) Addi
to the set.boolean
Addi
to the set.private final boolean
void
clear()
Empty the bitvector.boolean
contains
(int i) Test ifi
is in the set.boolean
Test ifo
is in the set.iterator()
Standard JavaIterator
.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.private void
boolean
remove
(int i) Removei
from the set.boolean
Removeo
from the set.int
size()
Current count of elements in the set.private void
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.Collection
parallelStream, removeIf, stream, toArray
Methods inherited from interface java.util.Set
addAll, containsAll, isEmpty, retainAll, spliterator, toArray, toArray
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
_nbsi_offset
private static final long _nbsi_offset -
_nbsi
-
-
Constructor Details
-
NonBlockingSetInt
public NonBlockingSetInt()Create a new empty bit-vector
-
-
Method Details
-
CAS_nbsi
-
add
Addi
to the set. UppercaseInteger
version of add, requires auto-unboxing. When possible use theint
version ofadd(int)
for efficiency.- Specified by:
add
in interfaceCollection<Integer>
- Specified by:
add
in interfaceSet<Integer>
- Overrides:
add
in classAbstractCollection<Integer>
- Returns:
- true if i was added to the set.
- Throws:
IllegalArgumentException
- if i is negative.
-
contains
Test ifo
is in the set. This is the uppercaseInteger
version of contains, requires a type-check and auto-unboxing. When possible use theint
version ofcontains(int)
for efficiency.- Specified by:
contains
in interfaceCollection<Integer>
- Specified by:
contains
in interfaceSet<Integer>
- Overrides:
contains
in classAbstractCollection<Integer>
- Returns:
- true if i was in the set.
-
remove
Removeo
from the set. This is the uppercaseInteger
version of remove, requires a type-check and auto-unboxing. When possible use theint
version ofremove(int)
for efficiency.- Specified by:
remove
in interfaceCollection<Integer>
- Specified by:
remove
in interfaceSet<Integer>
- Overrides:
remove
in classAbstractCollection<Integer>
- Returns:
- true if i was removed to the set.
-
add
public boolean add(int i) Addi
to the set. This is the lower-case 'int
' version ofadd(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 ifi
is in the set. This is the lower-case 'int
' version ofcontains(java.lang.Object)
- no autoboxing.- Returns:
- true if i was int the set.
-
remove
public boolean remove(int i) Removei
from the set. This is the fast lower-case 'int
' version ofremove(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 interfaceCollection<Integer>
- Specified by:
size
in interfaceSet<Integer>
- Specified by:
size
in classAbstractCollection<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 interfaceCollection<Integer>
- Specified by:
clear
in interfaceSet<Integer>
- Overrides:
clear
in classAbstractCollection<Integer>
-
print
public void print()Verbose printout of internal structure for debugging. -
iterator
Standard JavaIterator
. Not very efficient because it auto-boxes the returned values. -
writeObject
- Throws:
IOException
-
readObject
- Throws:
IOException
ClassNotFoundException
-