public class WeakInterningHashSet<E> extends java.util.AbstractSet<E> implements InterningSet<E>, java.io.Serializable
interning set
that keeps weak references to its element.
This structure is particularly well suited for maintaining a cache of instances, e.g., a string pool.
All the caveats about the behavior of the garbage collector that apply for a weak hash map
apply for this implementation as well.Modifier and Type | Class and Description |
---|---|
protected static class |
WeakInterningHashSet.Entry<E>
|
protected static class |
WeakInterningHashSet.SelfCleaningEntry<E>
A specialized external entry managed by the
external queue that calls WeakInterningHashSet.SelfCleaningEntry.clear() to remove this entry from its set. |
Modifier and Type | Field and Description |
---|---|
protected int |
capacityIndex
The current index within
PRIME_CAPACITIES for the length of the entries . |
protected boolean |
containsNull
Whether or not this set contains the null value.
|
protected WeakInterningHashSet.Entry<E>[] |
entries
The table of linked entries.
|
protected java.lang.ref.ReferenceQueue<java.lang.Object> |
externalQueue
A queue used when
creating external entries and subsequently for cleaning garbage collected references. |
protected java.lang.ref.ReferenceQueue<E> |
internalQueue
|
protected int |
modCount
The modification count for fail fast iteration with
ConcurrentModificationException . |
protected static WeakInterningHashSet.Entry<java.lang.Object> |
NULL_ENTRY
A special entry used by the iterator to represent the need to yield the null value for the subsequent call to next().
|
protected static int[] |
PRIME_CAPACITIES
The capacity used for the
entries of the set will always be a prime number to help ensure uniform distribution of the hash codes. |
protected static long |
serialVersionUID |
protected int |
size
The current size of the set.
|
protected int |
threshold
The next size at which an
rehash should occur. |
Constructor and Description |
---|
WeakInterningHashSet()
Creates an instance with a minimum capacity.
|
WeakInterningHashSet(int minimumCapacity)
Creates an instance with at least the given capacity.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(E object) |
protected void |
addEntry(int index,
WeakInterningHashSet.Entry<E> entry)
Adds a new entry to the set at the given given index in the
entries . |
protected E |
asInstance(java.lang.Object object)
Returns the result of casting the object to
E , or null if the object is not an instance of E . |
protected void |
cleanup()
Polls the
internalQueue and removes any garbage collected entries. |
void |
clear()
Specialized to be more efficient.
|
boolean |
contains(java.lang.Object object) |
void |
dump()
Dumps information about the current state of the set.
|
protected boolean |
ensureCapacity()
|
protected boolean |
equals(E object,
E otherObject)
Returns whether the two objects are considered equal.
|
E |
get(E object)
Returns either the instance already contained in the set that's equal to the given object, or
null if the object is not in the set. |
protected WeakInterningHashSet.Entry<E> |
getEntry(int hashCode)
Gets the first entry in the table with exactly the given hash code.
|
void |
grow(int minimumCapacity)
Ensures that the set has at least the specified capacity.
|
protected int |
hashCode(E object)
Returns the
hash code of the object. |
protected static int |
index(int hashCode,
int capacity)
Returns the index in the
entries for the given hash code and capacity. |
E |
intern(E object)
Returns either the instance already contained in the set that's equal to the given object, or adds the object to the set and returns it.
|
java.util.Iterator<E> |
iterator() |
protected WeakInterningHashSet.Entry<E>[] |
newEntries(int capacity)
Creates a new array of
entries with the specified capacity. |
protected WeakInterningHashSet.Entry<E> |
newEntry(E object,
int hashCode)
Creates a new entry for the given referent and the given hash code.
|
protected WeakInterningHashSet.Entry<E> |
newExternalEntry(E object,
int hashCode)
Creates a new entry for the given referent and the given hash code managed by the
externalQueue . |
protected WeakInterningHashSet.Entry<E> |
newInternalEntry(E object,
int hashCode)
Creates a new entry for the given referent and the given hash code and the
internalQueue . |
protected WeakInterningHashSet.Entry<E> |
nullEntry()
Returns the
singleton entry representing the null value's entry during iteration. |
protected void |
putEntry(int index,
WeakInterningHashSet.Entry<E> entry)
|
boolean |
remove(java.lang.Object object) |
protected boolean |
removeEntry(int index,
WeakInterningHashSet.Entry<E> entry)
Finds the entry at the given index the
table and prune if from the collision chain. |
protected void |
removeEntry(WeakInterningHashSet.Entry<E> entry)
Remove an existing entry from the set. |
int |
size() |
addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
protected static final long serialVersionUID
protected static final WeakInterningHashSet.Entry<java.lang.Object> NULL_ENTRY
protected static final int[] PRIME_CAPACITIES
entries
of the set will always be a prime number to help ensure uniform distribution of the hash codes.
Each of these prime numbers is the smallest prime larger than 2^n, except for the last, which is the largest prime < Integer.MAX_VALUE
.protected int size
protected transient int capacityIndex
PRIME_CAPACITIES
for the length of the entries
.protected transient boolean containsNull
protected transient int threshold
rehash
should occur.protected transient int modCount
ConcurrentModificationException
.protected transient WeakInterningHashSet.Entry<E>[] entries
protected transient java.lang.ref.ReferenceQueue<E> internalQueue
protected final transient java.lang.ref.ReferenceQueue<java.lang.Object> externalQueue
creating
external entries and subsequently for cleaning garbage collected references.
Cleaning
garbage collected references is the responsibility of this external queue provider.
All calls to cleanup()
are guarded by whether internalQueue
value is null
, so no cleanup takes plac when there is an external reference queue.public WeakInterningHashSet()
public WeakInterningHashSet(int minimumCapacity)
public int size()
public void grow(int minimumCapacity)
protected int hashCode(E object)
hash code
of the object.
This will never be called with null
.
A derived class may specialize this to compute an alternative hash code and should generally specialize asInstance(Object)
and equals(Object, Object)
The default implementation simply uses Object.hashCode()
.protected boolean equals(E object, E otherObject)
null
.
The first argument will be an argument passed to one of the mutating methods of the set and the second will be a value already in the set.
A derived class may specialize this to check for structural equality and should generally specialize asInstance(Object)
and hashCode(Object)
.
The default implementation simply uses the Object.equals(Object)
.protected E asInstance(java.lang.Object object)
E
, or null
if the object is not an instance of E
.
This method is called by remove(Object)
and contains(Object)
which use the returned null
return false
because an object that isn't an instance of E
can't be (shouldn't be in the set) and so can't be removed.
The default implementation cannot do a checked cast so it always returns the argument via an unchecked cast.
This method should be specialized if hashCode(Object)
or equals(Object, Object)
are specialized.protected WeakInterningHashSet.Entry<E>[] newEntries(int capacity)
entries
with the specified capacity.protected boolean ensureCapacity()
size
<= threshold
.
If not, it reallocates
the entries to the next prime capacity
,
i.e., it approximate doubles the capacity,
and then rehashes
the set.
The return value indicates whether or note the entries where rehashed.protected void cleanup()
internalQueue
and removes
any garbage collected entries.public boolean remove(java.lang.Object object)
public void clear()
public boolean add(E object)
public E intern(E object)
intern
in interface InterningSet<E>
object
- the object to intern.public E get(E object)
null
if the object is not in the set.get
in interface InterningSet<E>
object
- the object to intern.null
if the object is not in the set.public boolean contains(java.lang.Object object)
public java.util.Iterator<E> iterator()
protected static int index(int hashCode, int capacity)
entries
for the given hash code and capacity.protected WeakInterningHashSet.Entry<E> getEntry(int hashCode)
WeakInterningHashSet.Entry.getNextEntry()
to yield the next entry with exactly this same hash code.protected WeakInterningHashSet.Entry<E> nullEntry()
singleton entry
representing the null
value's entry during iteration.protected final WeakInterningHashSet.Entry<E> newEntry(E object, int hashCode)
internalQueue
or externalQueue
it calls newInternalEntry(Object, int)
or newExternalEntry(Object, int)
respectively.protected WeakInterningHashSet.Entry<E> newInternalEntry(E object, int hashCode)
internalQueue
.protected WeakInterningHashSet.Entry<E> newExternalEntry(E object, int hashCode)
externalQueue
.protected void putEntry(int index, WeakInterningHashSet.Entry<E> entry)
index
- entry
- protected void addEntry(int index, WeakInterningHashSet.Entry<E> entry)
protected void removeEntry(WeakInterningHashSet.Entry<E> entry)
protected boolean removeEntry(int index, WeakInterningHashSet.Entry<E> entry)
table
and prune if from the collision chain.
Returns whether or not the entry was actually removed.public void dump()