Package org.apache.commons.collections4.map

Class ConcurrentReferenceHashMap.Segment<K,V>

java.lang.Object

java.util.concurrent.locks.ReentrantLock

org.apache.commons.collections4.map.ConcurrentReferenceHashMap.Segment<K,V>

Type Parameters:

K - the type of keys maintained by this Segment.

V - the type of mapped values.

All Implemented Interfaces:

Serializable, Lock

Enclosing class:

ConcurrentReferenceHashMap<K,V>

private static final class ConcurrentReferenceHashMap.Segment<K,V>
extends ReentrantLock

Segments are specialized versions of hash tables. This subclasses from ReentrantLock opportunistically, just to simplify some locking and avoid separate construction.

Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so they can be read without locking. Next fields of nodes are immutable (final). All list additions are performed at the front of each bin. This makes it easy to check changes, and also fast to traverse. When nodes would otherwise be changed, new nodes are created to replace them. This works well for hash tables since the bin lists tend to be short. (The average length is less than two for the default load factor threshold.)

Read operations can thus proceed without locking, but rely on selected uses of volatiles to ensure that completed write operations performed by other threads are noticed. For most purposes, the "count" field, tracking the number of elements, serves as that volatile variable ensuring visibility. This is convenient because this field needs to be read in many read operations anyway:

• All (unsynchronized) read operations must first read the "count" field, and should not look at table entries if it is 0.
• All (synchronized) write operations should write to the "count" field after structurally changing any bin. The operations must not take any action that could even momentarily cause a concurrent read operation to see inconsistent data. This is made easier by the nature of the read operations in Map. For example, no operation can reveal that the table has grown but the threshold has not yet been updated, so there are no atomicity requirements for this with respect to reads.

As a guide, all critical volatile reads and writes to the count field are marked in code comments.

Field Summary

Fields

Modifier and Type	Field	Description
private int	count	The number of elements in this segment's region.
private final boolean	identityComparisons
private final ConcurrentReferenceHashMap.ReferenceType	keyType
private final float	loadFactor	The load factor for the hash table.
private int	modCount	Number of updates that alter the size of the table.
private ReferenceQueue<Object>	refQueue	The collected weak-key reference queue for this segment.
private static final long	serialVersionUID
private ConcurrentReferenceHashMap.HashEntry<K,V>[]	table	The per-segment table.
private int	threshold	The table is rehashed when its size exceeds this threshold.
private final ConcurrentReferenceHashMap.ReferenceType	valueType

Constructor Summary

Constructors

Constructor	Description
Segment(int initialCapacity, float loadFactor, ConcurrentReferenceHashMap.ReferenceType keyType, ConcurrentReferenceHashMap.ReferenceType valueType, boolean identityComparisons)

Method Summary

Modifier and Type	Method	Description
(package private) V	apply(K key, int hash, BiFunction<? super K,? super V,? extends V> remappingFunction)
(package private) V	applyIfPresent(K key, int hash, BiFunction<? super K,? super V,? extends V> remappingFunction)
(package private) void	clear()
(package private) boolean	containsKey(Object key, int hash)
(package private) boolean	containsValue(Object value)
(package private) V	get(Object key, int hash)
(package private) ConcurrentReferenceHashMap.HashEntry<K,V>	getFirst(int hash)	Gets properly casted first entry of bin for given hash.
(package private) V	getValue(K key, V value, Function<? super K,? extends V> function)
private boolean	keyEq(Object src, Object dest)
(package private) static <K, V> ConcurrentReferenceHashMap.Segment<K,V>[]	newArray(int i)
(package private) ConcurrentReferenceHashMap.HashEntry<K,V>	newHashEntry(K key, int hash, ConcurrentReferenceHashMap.HashEntry<K,V> next, V value)
(package private) V	put(K key, int hash, V value, Function<? super K,? extends V> function, boolean onlyIfAbsent)	This method must be called with exactly one of value and function non-null.
private V	putInternal(K key, int hash, V value, Function<? super K,? extends V> function, boolean onlyIfAbsent)
(package private) V	readValueUnderLock(ConcurrentReferenceHashMap.HashEntry<K,V> e)	Reads value field of an entry under lock.
(package private) int	rehash()
(package private) V	remove(Object key, int hash, Object value, boolean refRemove)	Removes match on key only if value is null, else match both.
private V	removeInternal(Object key, int hash, Object value, boolean refRemove)
(package private) void	removeStale()
(package private) V	replace(K key, int hash, V newValue)
(package private) boolean	replace(K key, int hash, V oldValue, V newValue)
private V	replaceInternal(K key, int hash, V newValue)
private boolean	replaceInternal2(K key, int hash, V oldValue, V newValue)
(package private) void	setTable(ConcurrentReferenceHashMap.HashEntry<K,V>[] newTable)	Sets table to new HashEntry array.

Methods inherited from class java.util.concurrent.locks.ReentrantLock

getHoldCount, getOwner, getQueuedThreads, getQueueLength, getWaitingThreads, getWaitQueueLength, hasQueuedThread, hasQueuedThreads, hasWaiters, isFair, isHeldByCurrentThread, isLocked, lock, lockInterruptibly, newCondition, toString, tryLock, tryLock, unlock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

serialVersionUID

private static final long serialVersionUID

See Also:

• Constant Field Values

count

private transient volatile int count

The number of elements in this segment's region.

modCount

private transient int modCount

Number of updates that alter the size of the table. This is used during bulk-read methods to make sure they see a consistent snapshot: If modCounts change during a traversal of segments computing size or checking containsValue, then we might have an inconsistent view of state so (usually) we must retry.

threshold

private transient int threshold

The table is rehashed when its size exceeds this threshold. (The value of this field is always (int)(capacity * loadFactor).)

table

private transient volatile ConcurrentReferenceHashMap.HashEntry<K,V>[] table

The per-segment table.

loadFactor

private final float loadFactor

The load factor for the hash table. Even though this value is same for all segments, it is replicated to avoid needing links to outer object.

refQueue

private transient volatile ReferenceQueue<Object> refQueue

The collected weak-key reference queue for this segment. This should be (re)initialized whenever table is assigned,

keyType

private final ConcurrentReferenceHashMap.ReferenceType keyType

valueType

private final ConcurrentReferenceHashMap.ReferenceType valueType

identityComparisons

private final boolean identityComparisons

Constructor Details

Segment

Segment(int initialCapacity,
 float loadFactor,
 ConcurrentReferenceHashMap.ReferenceType keyType,
 ConcurrentReferenceHashMap.ReferenceType valueType,
 boolean identityComparisons)

Method Details

newArray

static <K,
V>
ConcurrentReferenceHashMap.Segment<K,V>[] newArray(int i)

apply

V apply(K key,
 int hash,
 BiFunction<? super K,? super V,? extends V> remappingFunction)

applyIfPresent

V applyIfPresent(K key,
 int hash,
 BiFunction<? super K,? super V,? extends V> remappingFunction)

clear

void clear()

containsKey

boolean containsKey(Object key,
 int hash)

containsValue

boolean containsValue(Object value)

get

V get(Object key,
 int hash)

getFirst

ConcurrentReferenceHashMap.HashEntry<K,V> getFirst(int hash)

Gets properly casted first entry of bin for given hash.

getValue

V getValue(K key,
 V value,
 Function<? super K,? extends V> function)

keyEq

private boolean keyEq(Object src,
 Object dest)

newHashEntry

ConcurrentReferenceHashMap.HashEntry<K,V> newHashEntry(K key,
 int hash,
 ConcurrentReferenceHashMap.HashEntry<K,V> next,
 V value)

put

V put(K key,
 int hash,
 V value,
 Function<? super K,? extends V> function,
 boolean onlyIfAbsent)

This method must be called with exactly one of value and function non-null.

putInternal

private V putInternal(K key,
 int hash,
 V value,
 Function<? super K,? extends V> function,
 boolean onlyIfAbsent)

readValueUnderLock

V readValueUnderLock(ConcurrentReferenceHashMap.HashEntry<K,V> e)

Reads value field of an entry under lock. Called if value field ever appears to be null. This is possible only if a compiler happens to reorder a HashEntry initialization with its table assignment, which is legal under memory model but is not known to ever occur.

rehash

int rehash()

remove

V remove(Object key,
 int hash,
 Object value,
 boolean refRemove)

Removes match on key only if value is null, else match both.

removeInternal

private V removeInternal(Object key,
 int hash,
 Object value,
 boolean refRemove)

removeStale

void removeStale()

replace

V replace(K key,
 int hash,
 V newValue)

replace

boolean replace(K key,
 int hash,
 V oldValue,
 V newValue)

replaceInternal

private V replaceInternal(K key,
 int hash,
 V newValue)

replaceInternal2

private boolean replaceInternal2(K key,
 int hash,
 V oldValue,
 V newValue)

setTable

void setTable(ConcurrentReferenceHashMap.HashEntry<K,V>[] newTable)

Sets table to new HashEntry array. Call only while holding lock or in constructor.