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 map

V - the type of the values in the map

E - the type of the MapMakerInternalMap.InternalEntry entry implementation used internally

S - the type of the MapMakerInternalMap.Segment entry implementation used internally

All Implemented Interfaces:

java.io.Serializable, java.util.concurrent.ConcurrentMap<K,V>, java.util.Map<K,V>

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 by MapMaker.

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 for MapMakerInternalMap.InternalEntry implementations for strong keys.
(package private) static class	MapMakerInternalMap.AbstractWeakKeyEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>	Base class for MapMakerInternalMap.InternalEntry implementations for weak keys.
(package private) static class	MapMakerInternalMap.CleanupMapTask
(package private) static class	MapMakerInternalMap.DummyInternalEntry	A dummy implementation of MapMakerInternalMap.InternalEntry, solely for use in the type signature of UNSET_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 a MapMakerInternalMap.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 on MapMakerInternalMap.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.StrongKeyDummyValueEntry<K>	Concrete implementation of MapMakerInternalMap.InternalEntry for strong keys and MapMaker.Dummy values.
(package private) static class	MapMakerInternalMap.StrongKeyDummyValueSegment<K>	Concrete implementation of MapMakerInternalMap.Segment for strong keys and MapMaker.Dummy values.
(package private) static class	MapMakerInternalMap.StrongKeyStrongValueEntry<K,V>	Concrete implementation of MapMakerInternalMap.InternalEntry for strong keys and strong values.
(package private) static class	MapMakerInternalMap.StrongKeyStrongValueSegment<K,V>	Concrete implementation of MapMakerInternalMap.Segment for strong keys and strong values.
(package private) static class	MapMakerInternalMap.StrongKeyWeakValueEntry<K,V>	Concrete implementation of MapMakerInternalMap.InternalEntry for strong keys and weak values.
(package private) static class	MapMakerInternalMap.StrongKeyWeakValueSegment<K,V>	Concrete implementation of MapMakerInternalMap.Segment for strong keys and weak values.
(package private) static interface	MapMakerInternalMap.StrongValueEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>	Marker interface for MapMakerInternalMap.InternalEntry implementations for strong values.
(package private) class	MapMakerInternalMap.ValueIterator
(package private) class	MapMakerInternalMap.Values
(package private) static class	MapMakerInternalMap.WeakKeyDummyValueEntry<K>	Concrete implementation of MapMakerInternalMap.InternalEntry for weak keys and MapMaker.Dummy values.
(package private) static class	MapMakerInternalMap.WeakKeyDummyValueSegment<K>	Concrete implementation of MapMakerInternalMap.Segment for weak keys and MapMaker.Dummy values.
(package private) static class	MapMakerInternalMap.WeakKeyStrongValueEntry<K,V>	Concrete implementation of MapMakerInternalMap.InternalEntry for weak keys and strong values.
(package private) static class	MapMakerInternalMap.WeakKeyStrongValueSegment<K,V>	Concrete implementation of MapMakerInternalMap.Segment for weak keys and strong values.
(package private) static class	MapMakerInternalMap.WeakKeyWeakValueEntry<K,V>	Concrete implementation of MapMakerInternalMap.InternalEntry for weak keys and weak values.
(package private) static class	MapMakerInternalMap.WeakKeyWeakValueSegment<K,V>	Concrete implementation of MapMakerInternalMap.Segment for weak keys and weak values.
(package private) static interface	MapMakerInternalMap.WeakValueEntry<K,V,E extends MapMakerInternalMap.InternalEntry<K,V,E>>	Marker interface for MapMakerInternalMap.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 of MapMakerInternalMap.WeakValueReference.
(package private) class	MapMakerInternalMap.WriteThroughEntry	Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying map.

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,V extends java.lang.Object>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K extends java.lang.Object,V extends java.lang.Object>

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 singleton MapMakerInternalMap.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

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)	Returns a fresh MapMakerInternalMap as specified by the given builder.
(package private) MapMakerInternalMap.Segment<K,V,E,S>	createSegment(int initialCapacity, int maxSegmentSize)
(package private) static <K> MapMakerInternalMap<K,MapMaker.Dummy,? extends MapMakerInternalMap.InternalEntry<K,MapMaker.Dummy,?>,?>	createWithDummyValues(MapMaker builder)	Returns a fresh MapMakerInternalMap with MapMaker.Dummy values but otherwise as specified by the given builder.
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.util.AbstractMap

clone, equals, hashCode, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Methods inherited from interface java.util.Map

equals, hashCode

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 no greater than 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 singleton MapMakerInternalMap.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

entrySet

transient java.util.Set<java.util.Map.Entry<K,V>> entrySet

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

Constructor Detail

MapMakerInternalMap

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 Detail

create

static <K,V> MapMakerInternalMap<K,V,? extends MapMakerInternalMap.InternalEntry<K,V,?>,?> create(MapMaker builder)

Returns a fresh MapMakerInternalMap as specified by the given builder.

createWithDummyValues

static <K> MapMakerInternalMap<K,MapMaker.Dummy,? extends MapMakerInternalMap.InternalEntry<K,MapMaker.Dummy,?>,?> createWithDummyValues(MapMaker builder)

Returns a fresh MapMakerInternalMap with MapMaker.Dummy values but otherwise as specified by the given builder. The returned MapMakerInternalMap will be optimized to saved memory. Since MapMaker.Dummy is a singleton, we don't need to store any values at all. Because of this optimization, build.getValueStrength() must be MapMakerInternalMap.Strength.STRONG.

This method is intended to only be used by the internal implementation of Interners, since a map of dummy values is the exact use case there.

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 call MapMakerInternalMap.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 call MapMakerInternalMap.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. Returns null 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()

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

getEntry

E getEntry(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(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

putIfAbsent

public V putIfAbsent(K key,
                     V value)

Specified by:

putIfAbsent in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

putIfAbsent in interface java.util.Map<K,V>

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Specified by:

putAll in interface java.util.Map<K,V>

Overrides:

putAll in class java.util.AbstractMap<K,V>

remove

public V remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

remove

public boolean remove(java.lang.Object key,
                      java.lang.Object value)

Specified by:

remove in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

remove in interface java.util.Map<K,V>

replace

public boolean replace(K key,
                       V oldValue,
                       V newValue)

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

replace

public V replace(K key,
                 V value)

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

keySet

public java.util.Set<K> keySet()

Specified by:

keySet in interface java.util.Map<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

values

public java.util.Collection<V> values()

Specified by:

values in interface java.util.Map<K,V>

Overrides:

values in class java.util.AbstractMap<K,V>

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

toArrayList

private static <E> java.util.ArrayList<E> toArrayList(java.util.Collection<E> c)

writeReplace

java.lang.Object writeReplace()