Package com.google.common.collect
Class MapMakerInternalMap<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.common.collect.MapMakerInternalMap<K,V,E,S>
-
- Type Parameters:
K
- the type of the keys in the mapV
- the type of the values in the mapE
- the type of theMapMakerInternalMap.InternalEntry
entry implementation used internallyS
- the type of theMapMakerInternalMap.Segment
entry implementation used internally
- All Implemented Interfaces:
java.io.Serializable
,java.util.concurrent.ConcurrentMap<K,V>
,java.util.Map<K,V>
@GwtIncompatible class MapMakerInternalMap<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>> extends java.util.AbstractMap<K,V> implements java.util.concurrent.ConcurrentMap<K,V>, java.io.Serializable
The concurrent hash map implementation built byMapMaker
.This implementation is heavily derived from revision 1.96 of ConcurrentHashMap.java.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
MapMakerInternalMap.AbstractSerializationProxy<K,V>
The actual object that gets serialized.(package private) static class
MapMakerInternalMap.AbstractStrongKeyEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
Base class forMapMakerInternalMap.InternalEntry
implementations for strong keys.(package private) static class
MapMakerInternalMap.AbstractWeakKeyEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
Base class forMapMakerInternalMap.InternalEntry
implementations for weak keys.(package private) static class
MapMakerInternalMap.CleanupMapTask
(package private) static class
MapMakerInternalMap.DummyInternalEntry
A dummy implementation ofMapMakerInternalMap.InternalEntry
, solely for use in the type signature ofUNSET_WEAK_VALUE_REFERENCE
below.(package private) class
MapMakerInternalMap.EntryIterator
(package private) class
MapMakerInternalMap.EntrySet
(package private) class
MapMakerInternalMap.HashIterator<T>
(package private) static interface
MapMakerInternalMap.InternalEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
An entry in a hash table of aMapMakerInternalMap.Segment
.(package private) static interface
MapMakerInternalMap.InternalEntryHelper<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>>
A helper object for operating onMapMakerInternalMap.InternalEntry
instances in a type-safe and efficient manner.(package private) class
MapMakerInternalMap.KeyIterator
(package private) class
MapMakerInternalMap.KeySet
private static class
MapMakerInternalMap.SafeToArraySet<E>
(package private) static class
MapMakerInternalMap.Segment<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>>
Segments are specialized versions of hash tables.private static class
MapMakerInternalMap.SerializationProxy<K,V>
The actual object that gets serialized.(package private) static class
MapMakerInternalMap.Strength
(package private) static class
MapMakerInternalMap.StrongKeyStrongValueEntry<K,V>
Concrete implementation ofMapMakerInternalMap.InternalEntry
for strong keys and strong values.(package private) static class
MapMakerInternalMap.StrongKeyStrongValueSegment<K,V>
Concrete implementation ofMapMakerInternalMap.Segment
for strong keys and strong values.(package private) static class
MapMakerInternalMap.StrongKeyWeakValueEntry<K,V>
Concrete implementation ofMapMakerInternalMap.InternalEntry
for strong keys and weak values.(package private) static class
MapMakerInternalMap.StrongKeyWeakValueSegment<K,V>
Concrete implementation ofMapMakerInternalMap.Segment
for strong keys and weak values.(package private) static interface
MapMakerInternalMap.StrongValueEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
Marker interface forMapMakerInternalMap.InternalEntry
implementations for strong values.(package private) class
MapMakerInternalMap.ValueIterator
(package private) class
MapMakerInternalMap.Values
(package private) static class
MapMakerInternalMap.WeakKeyStrongValueEntry<K,V>
Concrete implementation ofMapMakerInternalMap.InternalEntry
for weak keys and strong values.(package private) static class
MapMakerInternalMap.WeakKeyStrongValueSegment<K,V>
Concrete implementation ofMapMakerInternalMap.Segment
for weak keys and strong values.(package private) static class
MapMakerInternalMap.WeakKeyWeakValueEntry<K,V>
Concrete implementation ofMapMakerInternalMap.InternalEntry
for weak keys and weak values.(package private) static class
MapMakerInternalMap.WeakKeyWeakValueSegment<K,V>
Concrete implementation ofMapMakerInternalMap.Segment
for weak keys and weak values.(package private) static interface
MapMakerInternalMap.WeakValueEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
Marker interface forMapMakerInternalMap.InternalEntry
implementations for weak values.(package private) static interface
MapMakerInternalMap.WeakValueReference<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
A weakly referenced value that also has a reference to its containing entry.(package private) static class
MapMakerInternalMap.WeakValueReferenceImpl<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
Concrete implementation ofMapMakerInternalMap.WeakValueReference
.(package private) class
MapMakerInternalMap.WriteThroughEntry
Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying map.
-
Field Summary
Fields Modifier and Type Field Description (package private) static long
CLEANUP_EXECUTOR_DELAY_SECS
(package private) int
concurrencyLevel
The concurrency level.(package private) static int
CONTAINS_VALUE_RETRIES
Number of (unsynchronized) retries in the containsValue method.(package private) static int
DRAIN_MAX
Maximum number of entries to be drained in a single cleanup run.(package private) static int
DRAIN_THRESHOLD
Number of cache access operations that can be buffered per segment before the cache's recency ordering information is updated.(package private) MapMakerInternalMap.InternalEntryHelper<K,V,E,S>
entryHelper
Strategy for handling entries and segments in a type-safe and efficient manner.(package private) java.util.Set<java.util.Map.Entry<K,V>>
entrySet
(package private) Equivalence<java.lang.Object>
keyEquivalence
Strategy for comparing keys.(package private) java.util.Set<K>
keySet
(package private) static int
MAX_SEGMENTS
The maximum number of segments to allow; used to bound constructor arguments.(package private) static int
MAXIMUM_CAPACITY
The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments.(package private) int
segmentMask
Mask value for indexing into segments.(package private) MapMakerInternalMap.Segment<K,V,E,S>[]
segments
The segments, each of which is a specialized hash table.(package private) int
segmentShift
Shift value for indexing within segments.private static long
serialVersionUID
(package private) static MapMakerInternalMap.WeakValueReference<java.lang.Object,java.lang.Object,MapMakerInternalMap.DummyInternalEntry>
UNSET_WEAK_VALUE_REFERENCE
A singletonMapMakerInternalMap.WeakValueReference
used to denote an unset value in a entry with weak values.(package private) java.util.Collection<V>
values
-
Constructor Summary
Constructors Modifier Constructor Description private
MapMakerInternalMap(MapMaker builder, MapMakerInternalMap.InternalEntryHelper<K,V,E,S> entryHelper)
Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
boolean
containsKey(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
(package private) E
copyEntry(E original, E newNext)
This method is a convenience for testing.(package private) static <K,V>
MapMakerInternalMap<K,V,? extends MapMakerInternalMap.InternalEntry<K,V,?>,?>create(MapMaker builder)
(package private) MapMakerInternalMap.Segment<K,V,E,S>
createSegment(int initialCapacity, int maxSegmentSize)
java.util.Set<java.util.Map.Entry<K,V>>
entrySet()
V
get(java.lang.Object key)
(package private) E
getEntry(java.lang.Object key)
Returns the internal entry for the specified key.(package private) V
getLiveValue(E entry)
Gets the value from an entry.(package private) int
hash(java.lang.Object key)
boolean
isEmpty()
(package private) boolean
isLiveForTesting(MapMakerInternalMap.InternalEntry<K,V,?> entry)
This method is a convenience for testing.java.util.Set<K>
keySet()
(package private) MapMakerInternalMap.Strength
keyStrength()
(package private) MapMakerInternalMap.Segment<K,V,E,S>[]
newSegmentArray(int ssize)
V
put(K key, V value)
void
putAll(java.util.Map<? extends K,? extends V> m)
V
putIfAbsent(K key, V value)
(package private) void
reclaimKey(E entry)
(package private) void
reclaimValue(MapMakerInternalMap.WeakValueReference<K,V,E> valueReference)
(package private) static int
rehash(int h)
Applies a supplemental hash function to a given hash code, which defends against poor quality hash functions.V
remove(java.lang.Object key)
boolean
remove(java.lang.Object key, java.lang.Object value)
V
replace(K key, V value)
boolean
replace(K key, V oldValue, V newValue)
(package private) MapMakerInternalMap.Segment<K,V,E,S>
segmentFor(int hash)
Returns the segment that should be used for a key with the given hash.int
size()
private static <E> java.util.ArrayList<E>
toArrayList(java.util.Collection<E> c)
(package private) static <K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>
MapMakerInternalMap.WeakValueReference<K,V,E>unsetWeakValueReference()
(package private) Equivalence<java.lang.Object>
valueEquivalence()
java.util.Collection<V>
values()
(package private) MapMakerInternalMap.Strength
valueStrength()
(package private) java.lang.Object
writeReplace()
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
-
-
-
Field Detail
-
MAXIMUM_CAPACITY
static final int MAXIMUM_CAPACITY
The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are indexable using ints.- See Also:
- Constant Field Values
-
MAX_SEGMENTS
static final int MAX_SEGMENTS
The maximum number of segments to allow; used to bound constructor arguments.- See Also:
- Constant Field Values
-
CONTAINS_VALUE_RETRIES
static final int CONTAINS_VALUE_RETRIES
Number of (unsynchronized) retries in the containsValue method.- See Also:
- Constant Field Values
-
DRAIN_THRESHOLD
static final int DRAIN_THRESHOLD
Number of cache access operations that can be buffered per segment before the cache's recency ordering information is updated. This is used to avoid lock contention by recording a memento of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs.This must be a (2^n)-1 as it is used as a mask.
- See Also:
- Constant Field Values
-
DRAIN_MAX
static final int DRAIN_MAX
Maximum number of entries to be drained in a single cleanup run. This applies independently to the cleanup queue and both reference queues.- See Also:
- Constant Field Values
-
CLEANUP_EXECUTOR_DELAY_SECS
static final long CLEANUP_EXECUTOR_DELAY_SECS
- See Also:
- Constant Field Values
-
segmentMask
final transient int segmentMask
Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment.
-
segmentShift
final transient int segmentShift
Shift value for indexing within segments. Helps prevent entries that end up in the same segment from also ending up in the same bucket.
-
segments
final transient MapMakerInternalMap.Segment<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>>[] segments
The segments, each of which is a specialized hash table.
-
concurrencyLevel
final int concurrencyLevel
The concurrency level.
-
keyEquivalence
final Equivalence<java.lang.Object> keyEquivalence
Strategy for comparing keys.
-
entryHelper
final transient MapMakerInternalMap.InternalEntryHelper<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>,S extends MapMakerInternalMap.Segment<K,V,E,S>> entryHelper
Strategy for handling entries and segments in a type-safe and efficient manner.
-
UNSET_WEAK_VALUE_REFERENCE
static final MapMakerInternalMap.WeakValueReference<java.lang.Object,java.lang.Object,MapMakerInternalMap.DummyInternalEntry> UNSET_WEAK_VALUE_REFERENCE
A singletonMapMakerInternalMap.WeakValueReference
used to denote an unset value in a entry with weak values.
-
keySet
transient java.util.Set<K> keySet
-
values
transient java.util.Collection<V> values
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
Method Detail
-
create
static <K,V> MapMakerInternalMap<K,V,? extends MapMakerInternalMap.InternalEntry<K,V,?>,?> create(MapMaker builder)
-
unsetWeakValueReference
static <K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>> MapMakerInternalMap.WeakValueReference<K,V,E> unsetWeakValueReference()
-
rehash
static int rehash(int h)
Applies a supplemental hash function to a given hash code, which defends against poor quality hash functions. This is critical when the concurrent hash map uses power-of-two length hash tables, that otherwise encounter collisions for hash codes that do not differ in lower or upper bits.- Parameters:
h
- hash code
-
copyEntry
E copyEntry(E original, E newNext)
This method is a convenience for testing. Code should callMapMakerInternalMap.Segment.copyEntry(E, E)
directly.
-
hash
int hash(java.lang.Object key)
-
reclaimValue
void reclaimValue(MapMakerInternalMap.WeakValueReference<K,V,E> valueReference)
-
reclaimKey
void reclaimKey(E entry)
-
isLiveForTesting
boolean isLiveForTesting(MapMakerInternalMap.InternalEntry<K,V,?> entry)
This method is a convenience for testing. Code should callMapMakerInternalMap.Segment.getLiveValue(E)
instead.
-
segmentFor
MapMakerInternalMap.Segment<K,V,E,S> segmentFor(int hash)
Returns the segment that should be used for a key with the given hash.- Parameters:
hash
- the hash code for the key- Returns:
- the segment
-
createSegment
MapMakerInternalMap.Segment<K,V,E,S> createSegment(int initialCapacity, int maxSegmentSize)
-
getLiveValue
V getLiveValue(E entry)
Gets the value from an entry. Returnsnull
if the entry is invalid, partially-collected or computing.
-
newSegmentArray
final MapMakerInternalMap.Segment<K,V,E,S>[] newSegmentArray(int ssize)
-
keyStrength
MapMakerInternalMap.Strength keyStrength()
-
valueStrength
MapMakerInternalMap.Strength valueStrength()
-
valueEquivalence
Equivalence<java.lang.Object> valueEquivalence()
-
isEmpty
public boolean isEmpty()
-
size
public int size()
-
get
public V get(@Nullable java.lang.Object key)
-
getEntry
E getEntry(@Nullable java.lang.Object key)
Returns the internal entry for the specified key. The entry may be computing or partially collected. Does not impact recency ordering.
-
containsKey
public boolean containsKey(@Nullable java.lang.Object key)
-
containsValue
public boolean containsValue(@Nullable java.lang.Object value)
-
remove
public V remove(@Nullable java.lang.Object key)
-
remove
public boolean remove(@Nullable java.lang.Object key, @Nullable java.lang.Object value)
-
clear
public void clear()
-
keySet
public java.util.Set<K> keySet()
-
values
public java.util.Collection<V> values()
-
toArrayList
private static <E> java.util.ArrayList<E> toArrayList(java.util.Collection<E> c)
-
writeReplace
java.lang.Object writeReplace()
-
-