/*
* Copyright (C) 2009 The Guava Authors
*
* Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
* in compliance with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software distributed under the License
* is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
* or implied. See the License for the specific language governing permissions and limitations under
* the License.
*/
package com.google.common.collect;
import static com.google.common.base.
Preconditions.checkNotNull;
import static com.google.common.collect.
CollectPreconditions.checkRemove;
import com.google.common.annotations.
VisibleForTesting;
import com.google.common.base.
Equivalence;
import com.google.common.base.
Ticker;
import com.google.common.collect.
GenericMapMaker.
NullListener;
import com.google.common.collect.
MapMaker.
RemovalCause;
import com.google.common.collect.
MapMaker.
RemovalListener;
import com.google.common.collect.
MapMaker.
RemovalNotification;
import com.google.common.primitives.
Ints;
import java.io.
IOException;
import java.io.
ObjectInputStream;
import java.io.
ObjectOutputStream;
import java.io.
Serializable;
import java.lang.ref.
Reference;
import java.lang.ref.
ReferenceQueue;
import java.lang.ref.
SoftReference;
import java.lang.ref.
WeakReference;
import java.util.
AbstractCollection;
import java.util.
AbstractMap;
import java.util.
AbstractQueue;
import java.util.
AbstractSet;
import java.util.
Collection;
import java.util.
Iterator;
import java.util.
Map;
import java.util.
NoSuchElementException;
import java.util.
Queue;
import java.util.
Set;
import java.util.concurrent.
CancellationException;
import java.util.concurrent.
ConcurrentLinkedQueue;
import java.util.concurrent.
ConcurrentMap;
import java.util.concurrent.
ExecutionException;
import java.util.concurrent.
TimeUnit;
import java.util.concurrent.atomic.
AtomicInteger;
import java.util.concurrent.atomic.
AtomicReferenceArray;
import java.util.concurrent.locks.
ReentrantLock;
import java.util.logging.
Level;
import java.util.logging.
Logger;
import javax.annotation.
Nullable;
import javax.annotation.concurrent.
GuardedBy;
/**
* The concurrent hash map implementation built by {@link MapMaker}.
*
* <p>This implementation is heavily derived from revision 1.96 of <a
* href="http://tinyurl.com/ConcurrentHashMap">ConcurrentHashMap.java</a>.
*
* @author Bob Lee
* @author Charles Fry
* @author Doug Lea ({@code ConcurrentHashMap})
*/
class
MapMakerInternalMap<K, V>
extends
AbstractMap<K, V> implements
ConcurrentMap<K, V>,
Serializable {
/*
* The basic strategy is to subdivide the table among Segments, each of which itself is a
* concurrently readable hash table. The map supports non-blocking reads and concurrent writes
* across different segments.
*
* If a maximum size is specified, a best-effort bounding is performed per segment, using a
* page-replacement algorithm to determine which entries to evict when the capacity has been
* exceeded.
*
* The page replacement algorithm's data structures are kept casually consistent with the map. The
* ordering of writes to a segment is sequentially consistent. An update to the map and recording
* of reads may not be immediately reflected on the algorithm's data structures. These structures
* are guarded by a lock and operations are applied in batches to avoid lock contention. The
* penalty of applying the batches is spread across threads so that the amortized cost is slightly
* higher than performing just the operation without enforcing the capacity constraint.
*
* This implementation uses a per-segment queue to record a memento of the additions, removals,
* and accesses that were performed on the map. The queue is drained on writes and when it exceeds
* its capacity threshold.
*
* The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit
* rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation
* operates per-segment rather than globally for increased implementation simplicity. We expect
* the cache hit rate to be similar to that of a global LRU algorithm.
*/
// Constants
/**
* 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.
*/
static final int
MAXIMUM_CAPACITY =
Ints.
MAX_POWER_OF_TWO;
/** The maximum number of segments to allow; used to bound constructor arguments. */
static final int
MAX_SEGMENTS = 1 << 16; // slightly conservative
/** Number of (unsynchronized) retries in the containsValue method. */
static final int
CONTAINS_VALUE_RETRIES = 3;
/**
* 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.
*
* <p>This must be a (2^n)-1 as it is used as a mask.
*/
static final int
DRAIN_THRESHOLD = 0x3F;
/**
* Maximum number of entries to be drained in a single cleanup run. This applies independently to
* the cleanup queue and both reference queues.
*/
// TODO(fry): empirically optimize this
static final int
DRAIN_MAX = 16;
static final long
CLEANUP_EXECUTOR_DELAY_SECS = 60;
// Fields
private static final
Logger logger =
Logger.
getLogger(
MapMakerInternalMap.class.
getName());
/**
* Mask value for indexing into segments. The upper bits of a key's hash code are used to choose
* the segment.
*/
final transient int
segmentMask;
/**
* Shift value for indexing within segments. Helps prevent entries that end up in the same segment
* from also ending up in the same bucket.
*/
final transient int
segmentShift;
/** The segments, each of which is a specialized hash table. */
final transient
Segment<K, V>[]
segments;
/** The concurrency level. */
final int
concurrencyLevel;
/** Strategy for comparing keys. */
final
Equivalence<
Object>
keyEquivalence;
/** Strategy for comparing values. */
final
Equivalence<
Object>
valueEquivalence;
/** Strategy for referencing keys. */
final
Strength keyStrength;
/** Strategy for referencing values. */
final
Strength valueStrength;
/** The maximum size of this map. MapMaker.UNSET_INT if there is no maximum. */
final int
maximumSize;
/** How long after the last access to an entry the map will retain that entry. */
final long
expireAfterAccessNanos;
/** How long after the last write to an entry the map will retain that entry. */
final long
expireAfterWriteNanos;
/** Entries waiting to be consumed by the removal listener. */
// TODO(fry): define a new type which creates event objects and automates the clear logic
final
Queue<
RemovalNotification<K, V>>
removalNotificationQueue;
/**
* A listener that is invoked when an entry is removed due to expiration or garbage collection of
* soft/weak entries.
*/
final
RemovalListener<K, V>
removalListener;
/** Factory used to create new entries. */
final transient
EntryFactory entryFactory;
/** Measures time in a testable way. */
final
Ticker ticker;
/**
* Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
*/
MapMakerInternalMap(
MapMaker builder) {
concurrencyLevel =
Math.
min(
builder.
getConcurrencyLevel(),
MAX_SEGMENTS);
keyStrength =
builder.
getKeyStrength();
valueStrength =
builder.
getValueStrength();
keyEquivalence =
builder.
getKeyEquivalence();
valueEquivalence =
valueStrength.
defaultEquivalence();
maximumSize =
builder.
maximumSize;
expireAfterAccessNanos =
builder.
getExpireAfterAccessNanos();
expireAfterWriteNanos =
builder.
getExpireAfterWriteNanos();
entryFactory =
EntryFactory.
getFactory(
keyStrength,
expires(),
evictsBySize());
ticker =
builder.
getTicker();
removalListener =
builder.
getRemovalListener();
removalNotificationQueue = (
removalListener ==
NullListener.
INSTANCE)
?
MapMakerInternalMap.<
RemovalNotification<K, V>>
discardingQueue()
: new
ConcurrentLinkedQueue<
RemovalNotification<K, V>>();
int
initialCapacity =
Math.
min(
builder.
getInitialCapacity(),
MAXIMUM_CAPACITY);
if (
evictsBySize()) {
initialCapacity =
Math.
min(
initialCapacity,
maximumSize);
}
// Find power-of-two sizes best matching arguments. Constraints:
// (segmentCount <= maximumSize)
// && (concurrencyLevel > maximumSize || segmentCount > concurrencyLevel)
int
segmentShift = 0;
int
segmentCount = 1;
while (
segmentCount <
concurrencyLevel
&& (!
evictsBySize() ||
segmentCount * 2 <=
maximumSize)) {
++
segmentShift;
segmentCount <<= 1;
}
this.
segmentShift = 32 -
segmentShift;
segmentMask =
segmentCount - 1;
this.
segments =
newSegmentArray(
segmentCount);
int
segmentCapacity =
initialCapacity /
segmentCount;
if (
segmentCapacity *
segmentCount <
initialCapacity) {
++
segmentCapacity;
}
int
segmentSize = 1;
while (
segmentSize <
segmentCapacity) {
segmentSize <<= 1;
}
if (
evictsBySize()) {
// Ensure sum of segment max sizes = overall max size
int
maximumSegmentSize =
maximumSize /
segmentCount + 1;
int
remainder =
maximumSize %
segmentCount;
for (int
i = 0;
i < this.
segments.length; ++
i) {
if (
i ==
remainder) {
maximumSegmentSize--;
}
this.
segments[
i] =
createSegment(
segmentSize,
maximumSegmentSize);
}
} else {
for (int
i = 0;
i < this.
segments.length; ++
i) {
this.
segments[
i] =
createSegment(
segmentSize,
MapMaker.
UNSET_INT);
}
}
}
boolean
evictsBySize() {
return
maximumSize !=
MapMaker.
UNSET_INT;
}
boolean
expires() {
return
expiresAfterWrite() ||
expiresAfterAccess();
}
boolean
expiresAfterWrite() {
return
expireAfterWriteNanos > 0;
}
boolean
expiresAfterAccess() {
return
expireAfterAccessNanos > 0;
}
boolean
usesKeyReferences() {
return
keyStrength !=
Strength.
STRONG;
}
boolean
usesValueReferences() {
return
valueStrength !=
Strength.
STRONG;
}
enum
Strength {
/*
* TODO(kevinb): If we strongly reference the value and aren't computing, we needn't wrap the
* value. This could save ~8 bytes per entry.
*/
STRONG {
@
Override
<K, V>
ValueReference<K, V>
referenceValue(
Segment<K, V>
segment,
ReferenceEntry<K, V>
entry, V
value) {
return new
StrongValueReference<K, V>(
value);
}
@
Override
Equivalence<
Object>
defaultEquivalence() {
return
Equivalence.
equals();
}
},
SOFT {
@
Override
<K, V>
ValueReference<K, V>
referenceValue(
Segment<K, V>
segment,
ReferenceEntry<K, V>
entry, V
value) {
return new
SoftValueReference<K, V>(
segment.
valueReferenceQueue,
value,
entry);
}
@
Override
Equivalence<
Object>
defaultEquivalence() {
return
Equivalence.
identity();
}
},
WEAK {
@
Override
<K, V>
ValueReference<K, V>
referenceValue(
Segment<K, V>
segment,
ReferenceEntry<K, V>
entry, V
value) {
return new
WeakValueReference<K, V>(
segment.
valueReferenceQueue,
value,
entry);
}
@
Override
Equivalence<
Object>
defaultEquivalence() {
return
Equivalence.
identity();
}
};
/**
* Creates a reference for the given value according to this value strength.
*/
abstract <K, V>
ValueReference<K, V>
referenceValue(
Segment<K, V>
segment,
ReferenceEntry<K, V>
entry, V
value);
/**
* Returns the default equivalence strategy used to compare and hash keys or values referenced
* at this strength. This strategy will be used unless the user explicitly specifies an
* alternate strategy.
*/
abstract
Equivalence<
Object>
defaultEquivalence();
}
/**
* Creates new entries.
*/
enum
EntryFactory {
STRONG {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
StrongEntry<K, V>(
key,
hash,
next);
}
},
STRONG_EXPIRABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
StrongExpirableEntry<K, V>(
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyExpirableEntry(
original,
newEntry);
return
newEntry;
}
},
STRONG_EVICTABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
StrongEvictableEntry<K, V>(
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyEvictableEntry(
original,
newEntry);
return
newEntry;
}
},
STRONG_EXPIRABLE_EVICTABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
StrongExpirableEvictableEntry<K, V>(
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyExpirableEntry(
original,
newEntry);
copyEvictableEntry(
original,
newEntry);
return
newEntry;
}
},
WEAK {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
WeakEntry<K, V>(
segment.
keyReferenceQueue,
key,
hash,
next);
}
},
WEAK_EXPIRABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
WeakExpirableEntry<K, V>(
segment.
keyReferenceQueue,
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyExpirableEntry(
original,
newEntry);
return
newEntry;
}
},
WEAK_EVICTABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
WeakEvictableEntry<K, V>(
segment.
keyReferenceQueue,
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyEvictableEntry(
original,
newEntry);
return
newEntry;
}
},
WEAK_EXPIRABLE_EVICTABLE {
@
Override
<K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return new
WeakExpirableEvictableEntry<K, V>(
segment.
keyReferenceQueue,
key,
hash,
next);
}
@
Override
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
ReferenceEntry<K, V>
newEntry = super.copyEntry(
segment,
original,
newNext);
copyExpirableEntry(
original,
newEntry);
copyEvictableEntry(
original,
newEntry);
return
newEntry;
}
};
/**
* Masks used to compute indices in the following table.
*/
static final int
EXPIRABLE_MASK = 1;
static final int
EVICTABLE_MASK = 2;
/**
* Look-up table for factories. First dimension is the reference type. The second dimension is
* the result of OR-ing the feature masks.
*/
static final
EntryFactory[][]
factories = {
{
STRONG,
STRONG_EXPIRABLE,
STRONG_EVICTABLE,
STRONG_EXPIRABLE_EVICTABLE },
{}, // no support for SOFT keys
{
WEAK,
WEAK_EXPIRABLE,
WEAK_EVICTABLE,
WEAK_EXPIRABLE_EVICTABLE }
};
static
EntryFactory getFactory(
Strength keyStrength, boolean
expireAfterWrite,
boolean
evictsBySize) {
int
flags = (
expireAfterWrite ?
EXPIRABLE_MASK : 0) | (
evictsBySize ?
EVICTABLE_MASK : 0);
return
factories[
keyStrength.
ordinal()][
flags];
}
/**
* Creates a new entry.
*
* @param segment to create the entry for
* @param key of the entry
* @param hash of the key
* @param next entry in the same bucket
*/
abstract <K, V>
ReferenceEntry<K, V>
newEntry(
Segment<K, V>
segment, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next);
/**
* Copies an entry, assigning it a new {@code next} entry.
*
* @param original the entry to copy
* @param newNext entry in the same bucket
*/
@
GuardedBy("Segment.this")
<K, V>
ReferenceEntry<K, V>
copyEntry(
Segment<K, V>
segment,
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
return
newEntry(
segment,
original.
getKey(),
original.
getHash(),
newNext);
}
@
GuardedBy("Segment.this")
<K, V> void
copyExpirableEntry(
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newEntry) {
// TODO(fry): when we link values instead of entries this method can go
// away, as can connectExpirables, nullifyExpirable.
newEntry.
setExpirationTime(
original.
getExpirationTime());
connectExpirables(
original.
getPreviousExpirable(),
newEntry);
connectExpirables(
newEntry,
original.
getNextExpirable());
nullifyExpirable(
original);
}
@
GuardedBy("Segment.this")
<K, V> void
copyEvictableEntry(
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newEntry) {
// TODO(fry): when we link values instead of entries this method can go
// away, as can connectEvictables, nullifyEvictable.
connectEvictables(
original.
getPreviousEvictable(),
newEntry);
connectEvictables(
newEntry,
original.
getNextEvictable());
nullifyEvictable(
original);
}
}
/**
* A reference to a value.
*/
interface
ValueReference<K, V> {
/**
* Gets the value. Does not block or throw exceptions.
*/
V
get();
/**
* Waits for a value that may still be computing. Unlike get(), this method can block (in the
* case of FutureValueReference).
*
* @throws ExecutionException if the computing thread throws an exception
*/
V
waitForValue() throws
ExecutionException;
/**
* Returns the entry associated with this value reference, or {@code null} if this value
* reference is independent of any entry.
*/
ReferenceEntry<K, V>
getEntry();
/**
* Creates a copy of this reference for the given entry.
*
* <p>{@code value} may be null only for a loading reference.
*/
ValueReference<K, V>
copyFor(
ReferenceQueue<V>
queue, @
Nullable V
value,
ReferenceEntry<K, V>
entry);
/**
* Clears this reference object.
*
* @param newValue the new value reference which will replace this one; this is only used during
* computation to immediately notify blocked threads of the new value
*/
void
clear(@
Nullable ValueReference<K, V>
newValue);
/**
* Returns {@code true} if the value type is a computing reference (regardless of whether or not
* computation has completed). This is necessary to distiguish between partially-collected
* entries and computing entries, which need to be cleaned up differently.
*/
boolean
isComputingReference();
}
/**
* Placeholder. Indicates that the value hasn't been set yet.
*/
static final
ValueReference<
Object,
Object>
UNSET = new
ValueReference<
Object,
Object>() {
@
Override
public
Object get() {
return null;
}
@
Override
public
ReferenceEntry<
Object,
Object>
getEntry() {
return null;
}
@
Override
public
ValueReference<
Object,
Object>
copyFor(
ReferenceQueue<
Object>
queue,
@
Nullable Object value,
ReferenceEntry<
Object,
Object>
entry) {
return this;
}
@
Override
public boolean
isComputingReference() {
return false;
}
@
Override
public
Object waitForValue() {
return null;
}
@
Override
public void
clear(
ValueReference<
Object,
Object>
newValue) {}
};
/**
* Singleton placeholder that indicates a value is being computed.
*/
@
SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static <K, V>
ValueReference<K, V>
unset() {
return (
ValueReference<K, V>)
UNSET;
}
/**
* An entry in a reference map.
*
* Entries in the map can be in the following states:
*
* Valid:
* - Live: valid key/value are set
* - Computing: computation is pending
*
* Invalid:
* - Expired: time expired (key/value may still be set)
* - Collected: key/value was partially collected, but not yet cleaned up
*/
interface
ReferenceEntry<K, V> {
/**
* Gets the value reference from this entry.
*/
ValueReference<K, V>
getValueReference();
/**
* Sets the value reference for this entry.
*/
void
setValueReference(
ValueReference<K, V>
valueReference);
/**
* Gets the next entry in the chain.
*/
ReferenceEntry<K, V>
getNext();
/**
* Gets the entry's hash.
*/
int
getHash();
/**
* Gets the key for this entry.
*/
K
getKey();
/*
* Used by entries that are expirable. Expirable entries are maintained in a doubly-linked list.
* New entries are added at the tail of the list at write time; stale entries are expired from
* the head of the list.
*/
/**
* Gets the entry expiration time in ns.
*/
long
getExpirationTime();
/**
* Sets the entry expiration time in ns.
*/
void
setExpirationTime(long
time);
/**
* Gets the next entry in the recency list.
*/
ReferenceEntry<K, V>
getNextExpirable();
/**
* Sets the next entry in the recency list.
*/
void
setNextExpirable(
ReferenceEntry<K, V>
next);
/**
* Gets the previous entry in the recency list.
*/
ReferenceEntry<K, V>
getPreviousExpirable();
/**
* Sets the previous entry in the recency list.
*/
void
setPreviousExpirable(
ReferenceEntry<K, V>
previous);
/*
* Implemented by entries that are evictable. Evictable entries are maintained in a
* doubly-linked list. New entries are added at the tail of the list at write time and stale
* entries are expired from the head of the list.
*/
/**
* Gets the next entry in the recency list.
*/
ReferenceEntry<K, V>
getNextEvictable();
/**
* Sets the next entry in the recency list.
*/
void
setNextEvictable(
ReferenceEntry<K, V>
next);
/**
* Gets the previous entry in the recency list.
*/
ReferenceEntry<K, V>
getPreviousEvictable();
/**
* Sets the previous entry in the recency list.
*/
void
setPreviousEvictable(
ReferenceEntry<K, V>
previous);
}
private enum
NullEntry implements
ReferenceEntry<
Object,
Object> {
INSTANCE;
@
Override
public
ValueReference<
Object,
Object>
getValueReference() {
return null;
}
@
Override
public void
setValueReference(
ValueReference<
Object,
Object>
valueReference) {}
@
Override
public
ReferenceEntry<
Object,
Object>
getNext() {
return null;
}
@
Override
public int
getHash() {
return 0;
}
@
Override
public
Object getKey() {
return null;
}
@
Override
public long
getExpirationTime() {
return 0;
}
@
Override
public void
setExpirationTime(long
time) {}
@
Override
public
ReferenceEntry<
Object,
Object>
getNextExpirable() {
return this;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<
Object,
Object>
next) {}
@
Override
public
ReferenceEntry<
Object,
Object>
getPreviousExpirable() {
return this;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<
Object,
Object>
previous) {}
@
Override
public
ReferenceEntry<
Object,
Object>
getNextEvictable() {
return this;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<
Object,
Object>
next) {}
@
Override
public
ReferenceEntry<
Object,
Object>
getPreviousEvictable() {
return this;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<
Object,
Object>
previous) {}
}
abstract static class
AbstractReferenceEntry<K, V> implements
ReferenceEntry<K, V> {
@
Override
public
ValueReference<K, V>
getValueReference() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setValueReference(
ValueReference<K, V>
valueReference) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNext() {
throw new
UnsupportedOperationException();
}
@
Override
public int
getHash() {
throw new
UnsupportedOperationException();
}
@
Override
public K
getKey() {
throw new
UnsupportedOperationException();
}
@
Override
public long
getExpirationTime() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setExpirationTime(long
time) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
}
@
SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static <K, V>
ReferenceEntry<K, V>
nullEntry() {
return (
ReferenceEntry<K, V>)
NullEntry.
INSTANCE;
}
static final
Queue<? extends
Object>
DISCARDING_QUEUE = new
AbstractQueue<
Object>() {
@
Override
public boolean
offer(
Object o) {
return true;
}
@
Override
public
Object peek() {
return null;
}
@
Override
public
Object poll() {
return null;
}
@
Override
public int
size() {
return 0;
}
@
Override
public
Iterator<
Object>
iterator() {
return
Iterators.
emptyIterator();
}
};
/**
* Queue that discards all elements.
*/
@
SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static <E>
Queue<E>
discardingQueue() {
return (
Queue)
DISCARDING_QUEUE;
}
/*
* Note: All of this duplicate code sucks, but it saves a lot of memory. If only Java had mixins!
* To maintain this code, make a change for the strong reference type. Then, cut and paste, and
* replace "Strong" with "Soft" or "Weak" within the pasted text. The primary difference is that
* strong entries store the key reference directly while soft and weak entries delegate to their
* respective superclasses.
*/
/**
* Used for strongly-referenced keys.
*/
static class
StrongEntry<K, V> implements
ReferenceEntry<K, V> {
final K
key;
StrongEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
this.
key =
key;
this.
hash =
hash;
this.
next =
next;
}
@
Override
public K
getKey() {
return this.
key;
}
// null expiration
@
Override
public long
getExpirationTime() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setExpirationTime(long
time) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// null eviction
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// The code below is exactly the same for each entry type.
final int
hash;
final
ReferenceEntry<K, V>
next;
volatile
ValueReference<K, V>
valueReference =
unset();
@
Override
public
ValueReference<K, V>
getValueReference() {
return
valueReference;
}
@
Override
public void
setValueReference(
ValueReference<K, V>
valueReference) {
ValueReference<K, V>
previous = this.
valueReference;
this.
valueReference =
valueReference;
previous.
clear(
valueReference);
}
@
Override
public int
getHash() {
return
hash;
}
@
Override
public
ReferenceEntry<K, V>
getNext() {
return
next;
}
}
static final class
StrongExpirableEntry<K, V> extends
StrongEntry<K, V>
implements
ReferenceEntry<K, V> {
StrongExpirableEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
}
static final class
StrongEvictableEntry<K, V>
extends
StrongEntry<K, V> implements
ReferenceEntry<K, V> {
StrongEvictableEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
key,
hash,
next);
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
static final class
StrongExpirableEvictableEntry<K, V>
extends
StrongEntry<K, V> implements
ReferenceEntry<K, V> {
StrongExpirableEvictableEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
/**
* Used for softly-referenced keys.
*/
static class
SoftEntry<K, V> extends
SoftReference<K> implements
ReferenceEntry<K, V> {
SoftEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
key,
queue);
this.
hash =
hash;
this.
next =
next;
}
@
Override
public K
getKey() {
return
get();
}
// null expiration
@
Override
public long
getExpirationTime() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setExpirationTime(long
time) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// null eviction
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// The code below is exactly the same for each entry type.
final int
hash;
final
ReferenceEntry<K, V>
next;
volatile
ValueReference<K, V>
valueReference =
unset();
@
Override
public
ValueReference<K, V>
getValueReference() {
return
valueReference;
}
@
Override
public void
setValueReference(
ValueReference<K, V>
valueReference) {
ValueReference<K, V>
previous = this.
valueReference;
this.
valueReference =
valueReference;
previous.
clear(
valueReference);
}
@
Override
public int
getHash() {
return
hash;
}
@
Override
public
ReferenceEntry<K, V>
getNext() {
return
next;
}
}
static final class
SoftExpirableEntry<K, V>
extends
SoftEntry<K, V> implements
ReferenceEntry<K, V> {
SoftExpirableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
}
static final class
SoftEvictableEntry<K, V>
extends
SoftEntry<K, V> implements
ReferenceEntry<K, V> {
SoftEvictableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
static final class
SoftExpirableEvictableEntry<K, V>
extends
SoftEntry<K, V> implements
ReferenceEntry<K, V> {
SoftExpirableEvictableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
/**
* Used for weakly-referenced keys.
*/
static class
WeakEntry<K, V> extends
WeakReference<K> implements
ReferenceEntry<K, V> {
WeakEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
key,
queue);
this.
hash =
hash;
this.
next =
next;
}
@
Override
public K
getKey() {
return
get();
}
// null expiration
@
Override
public long
getExpirationTime() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setExpirationTime(long
time) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// null eviction
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
throw new
UnsupportedOperationException();
}
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
throw new
UnsupportedOperationException();
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
throw new
UnsupportedOperationException();
}
// The code below is exactly the same for each entry type.
final int
hash;
final
ReferenceEntry<K, V>
next;
volatile
ValueReference<K, V>
valueReference =
unset();
@
Override
public
ValueReference<K, V>
getValueReference() {
return
valueReference;
}
@
Override
public void
setValueReference(
ValueReference<K, V>
valueReference) {
ValueReference<K, V>
previous = this.
valueReference;
this.
valueReference =
valueReference;
previous.
clear(
valueReference);
}
@
Override
public int
getHash() {
return
hash;
}
@
Override
public
ReferenceEntry<K, V>
getNext() {
return
next;
}
}
static final class
WeakExpirableEntry<K, V>
extends
WeakEntry<K, V> implements
ReferenceEntry<K, V> {
WeakExpirableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
}
static final class
WeakEvictableEntry<K, V>
extends
WeakEntry<K, V> implements
ReferenceEntry<K, V> {
WeakEvictableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
static final class
WeakExpirableEvictableEntry<K, V>
extends
WeakEntry<K, V> implements
ReferenceEntry<K, V> {
WeakExpirableEvictableEntry(
ReferenceQueue<K>
queue, K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
super(
queue,
key,
hash,
next);
}
// The code below is exactly the same for each expirable entry type.
volatile long
time =
Long.
MAX_VALUE;
@
Override
public long
getExpirationTime() {
return
time;
}
@
Override
public void
setExpirationTime(long
time) {
this.
time =
time;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousExpirable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
// The code below is exactly the same for each evictable entry type.
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
nextEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
previousEvictable =
nullEntry();
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
}
/**
* References a weak value.
*/
static final class
WeakValueReference<K, V>
extends
WeakReference<V> implements
ValueReference<K, V> {
final
ReferenceEntry<K, V>
entry;
WeakValueReference(
ReferenceQueue<V>
queue, V
referent,
ReferenceEntry<K, V>
entry) {
super(
referent,
queue);
this.
entry =
entry;
}
@
Override
public
ReferenceEntry<K, V>
getEntry() {
return
entry;
}
@
Override
public void
clear(
ValueReference<K, V>
newValue) {
clear();
}
@
Override
public
ValueReference<K, V>
copyFor(
ReferenceQueue<V>
queue, V
value,
ReferenceEntry<K, V>
entry) {
return new
WeakValueReference<K, V>(
queue,
value,
entry);
}
@
Override
public boolean
isComputingReference() {
return false;
}
@
Override
public V
waitForValue() {
return
get();
}
}
/**
* References a soft value.
*/
static final class
SoftValueReference<K, V>
extends
SoftReference<V> implements
ValueReference<K, V> {
final
ReferenceEntry<K, V>
entry;
SoftValueReference(
ReferenceQueue<V>
queue, V
referent,
ReferenceEntry<K, V>
entry) {
super(
referent,
queue);
this.
entry =
entry;
}
@
Override
public
ReferenceEntry<K, V>
getEntry() {
return
entry;
}
@
Override
public void
clear(
ValueReference<K, V>
newValue) {
clear();
}
@
Override
public
ValueReference<K, V>
copyFor(
ReferenceQueue<V>
queue, V
value,
ReferenceEntry<K, V>
entry) {
return new
SoftValueReference<K, V>(
queue,
value,
entry);
}
@
Override
public boolean
isComputingReference() {
return false;
}
@
Override
public V
waitForValue() {
return
get();
}
}
/**
* References a strong value.
*/
static final class
StrongValueReference<K, V> implements
ValueReference<K, V> {
final V
referent;
StrongValueReference(V
referent) {
this.
referent =
referent;
}
@
Override
public V
get() {
return
referent;
}
@
Override
public
ReferenceEntry<K, V>
getEntry() {
return null;
}
@
Override
public
ValueReference<K, V>
copyFor(
ReferenceQueue<V>
queue, V
value,
ReferenceEntry<K, V>
entry) {
return this;
}
@
Override
public boolean
isComputingReference() {
return false;
}
@
Override
public V
waitForValue() {
return
get();
}
@
Override
public void
clear(
ValueReference<K, V>
newValue) {}
}
/**
* 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.
*
* @param h hash code
*/
static int
rehash(int
h) {
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
// TODO(kevinb): use Hashing/move this to Hashing?
h += (
h << 15) ^ 0xffffcd7d;
h ^= (
h >>> 10);
h += (
h << 3);
h ^= (
h >>> 6);
h += (
h << 2) + (
h << 14);
return
h ^ (
h >>> 16);
}
/**
* This method is a convenience for testing. Code should call {@link Segment#newEntry} directly.
*/
@
GuardedBy("Segment.this")
@
VisibleForTesting
ReferenceEntry<K, V>
newEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return
segmentFor(
hash).
newEntry(
key,
hash,
next);
}
/**
* This method is a convenience for testing. Code should call {@link Segment#copyEntry} directly.
*/
@
GuardedBy("Segment.this")
@
VisibleForTesting
ReferenceEntry<K, V>
copyEntry(
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
int
hash =
original.
getHash();
return
segmentFor(
hash).
copyEntry(
original,
newNext);
}
/**
* This method is a convenience for testing. Code should call {@link Segment#setValue} instead.
*/
@
GuardedBy("Segment.this")
@
VisibleForTesting
ValueReference<K, V>
newValueReference(
ReferenceEntry<K, V>
entry, V
value) {
int
hash =
entry.
getHash();
return
valueStrength.
referenceValue(
segmentFor(
hash),
entry,
value);
}
int
hash(
Object key) {
int
h =
keyEquivalence.
hash(
key);
return
rehash(
h);
}
void
reclaimValue(
ValueReference<K, V>
valueReference) {
ReferenceEntry<K, V>
entry =
valueReference.
getEntry();
int
hash =
entry.
getHash();
segmentFor(
hash).
reclaimValue(
entry.
getKey(),
hash,
valueReference);
}
void
reclaimKey(
ReferenceEntry<K, V>
entry) {
int
hash =
entry.
getHash();
segmentFor(
hash).
reclaimKey(
entry,
hash);
}
/**
* This method is a convenience for testing. Code should call {@link Segment#getLiveValue}
* instead.
*/
@
VisibleForTesting
boolean
isLive(
ReferenceEntry<K, V>
entry) {
return
segmentFor(
entry.
getHash()).
getLiveValue(
entry) != null;
}
/**
* Returns the segment that should be used for a key with the given hash.
*
* @param hash the hash code for the key
* @return the segment
*/
Segment<K, V>
segmentFor(int
hash) {
// TODO(fry): Lazily create segments?
return
segments[(
hash >>>
segmentShift) &
segmentMask];
}
Segment<K, V>
createSegment(int
initialCapacity, int
maxSegmentSize) {
return new
Segment<K, V>(this,
initialCapacity,
maxSegmentSize);
}
/**
* Gets the value from an entry. Returns {@code null} if the entry is invalid,
* partially-collected, computing, or expired. Unlike {@link Segment#getLiveValue} this method
* does not attempt to clean up stale entries.
*/
V
getLiveValue(
ReferenceEntry<K, V>
entry) {
if (
entry.
getKey() == null) {
return null;
}
V
value =
entry.
getValueReference().
get();
if (
value == null) {
return null;
}
if (
expires() &&
isExpired(
entry)) {
return null;
}
return
value;
}
// expiration
/**
* Returns {@code true} if the entry has expired.
*/
boolean
isExpired(
ReferenceEntry<K, V>
entry) {
return
isExpired(
entry,
ticker.
read());
}
/**
* Returns {@code true} if the entry has expired.
*/
boolean
isExpired(
ReferenceEntry<K, V>
entry, long
now) {
// if the expiration time had overflowed, this "undoes" the overflow
return
now -
entry.
getExpirationTime() > 0;
}
@
GuardedBy("Segment.this")
static <K, V> void
connectExpirables(
ReferenceEntry<K, V>
previous,
ReferenceEntry<K, V>
next) {
previous.
setNextExpirable(
next);
next.
setPreviousExpirable(
previous);
}
@
GuardedBy("Segment.this")
static <K, V> void
nullifyExpirable(
ReferenceEntry<K, V>
nulled) {
ReferenceEntry<K, V>
nullEntry =
nullEntry();
nulled.
setNextExpirable(
nullEntry);
nulled.
setPreviousExpirable(
nullEntry);
}
// eviction
/**
* Notifies listeners that an entry has been automatically removed due to expiration, eviction,
* or eligibility for garbage collection. This should be called every time expireEntries or
* evictEntry is called (once the lock is released).
*/
void
processPendingNotifications() {
RemovalNotification<K, V>
notification;
while ((
notification =
removalNotificationQueue.
poll()) != null) {
try {
removalListener.
onRemoval(
notification);
} catch (
Exception e) {
logger.
log(
Level.
WARNING, "Exception thrown by removal listener",
e);
}
}
}
/** Links the evitables together. */
@
GuardedBy("Segment.this")
static <K, V> void
connectEvictables(
ReferenceEntry<K, V>
previous,
ReferenceEntry<K, V>
next) {
previous.
setNextEvictable(
next);
next.
setPreviousEvictable(
previous);
}
@
GuardedBy("Segment.this")
static <K, V> void
nullifyEvictable(
ReferenceEntry<K, V>
nulled) {
ReferenceEntry<K, V>
nullEntry =
nullEntry();
nulled.
setNextEvictable(
nullEntry);
nulled.
setPreviousEvictable(
nullEntry);
}
@
SuppressWarnings("unchecked")
final
Segment<K, V>[]
newSegmentArray(int
ssize) {
return new
Segment[
ssize];
}
// Inner Classes
/**
* Segments are specialized versions of hash tables. This subclass inherits from ReentrantLock
* opportunistically, just to simplify some locking and avoid separate construction.
*/
@
SuppressWarnings("serial") // This class is never serialized.
static class
Segment<K, V> extends
ReentrantLock {
/*
* TODO(fry): Consider copying variables (like evictsBySize) from outer class into this class.
* It will require more memory but will reduce indirection.
*/
/*
* Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so 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.)
*
* 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.
*/
final
MapMakerInternalMap<K, V>
map;
/**
* The number of live elements in this segment's region. This does not include unset elements
* which are awaiting cleanup.
*/
volatile int
count;
/**
* 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) must retry.
*/
int
modCount;
/**
* The table is expanded when its size exceeds this threshold. (The value of this field is
* always {@code (int) (capacity * 0.75)}.)
*/
int
threshold;
/**
* The per-segment table.
*/
volatile
AtomicReferenceArray<
ReferenceEntry<K, V>>
table;
/**
* The maximum size of this map. MapMaker.UNSET_INT if there is no maximum.
*/
final int
maxSegmentSize;
/**
* The key reference queue contains entries whose keys have been garbage collected, and which
* need to be cleaned up internally.
*/
final
ReferenceQueue<K>
keyReferenceQueue;
/**
* The value reference queue contains value references whose values have been garbage collected,
* and which need to be cleaned up internally.
*/
final
ReferenceQueue<V>
valueReferenceQueue;
/**
* The recency queue is used to record which entries were accessed for updating the eviction
* list's ordering. It is drained as a batch operation when either the DRAIN_THRESHOLD is
* crossed or a write occurs on the segment.
*/
final
Queue<
ReferenceEntry<K, V>>
recencyQueue;
/**
* A counter of the number of reads since the last write, used to drain queues on a small
* fraction of read operations.
*/
final
AtomicInteger readCount = new
AtomicInteger();
/**
* A queue of elements currently in the map, ordered by access time. Elements are added to the
* tail of the queue on access/write.
*/
@
GuardedBy("Segment.this")
final
Queue<
ReferenceEntry<K, V>>
evictionQueue;
/**
* A queue of elements currently in the map, ordered by expiration time (either access or write
* time). Elements are added to the tail of the queue on access/write.
*/
@
GuardedBy("Segment.this")
final
Queue<
ReferenceEntry<K, V>>
expirationQueue;
Segment(
MapMakerInternalMap<K, V>
map, int
initialCapacity, int
maxSegmentSize) {
this.
map =
map;
this.
maxSegmentSize =
maxSegmentSize;
initTable(
newEntryArray(
initialCapacity));
keyReferenceQueue =
map.
usesKeyReferences()
? new
ReferenceQueue<K>() : null;
valueReferenceQueue =
map.
usesValueReferences()
? new
ReferenceQueue<V>() : null;
recencyQueue = (
map.
evictsBySize() ||
map.
expiresAfterAccess())
? new
ConcurrentLinkedQueue<
ReferenceEntry<K, V>>()
:
MapMakerInternalMap.<
ReferenceEntry<K, V>>
discardingQueue();
evictionQueue =
map.
evictsBySize()
? new
EvictionQueue<K, V>()
:
MapMakerInternalMap.<
ReferenceEntry<K, V>>
discardingQueue();
expirationQueue =
map.
expires()
? new
ExpirationQueue<K, V>()
:
MapMakerInternalMap.<
ReferenceEntry<K, V>>
discardingQueue();
}
AtomicReferenceArray<
ReferenceEntry<K, V>>
newEntryArray(int
size) {
return new
AtomicReferenceArray<
ReferenceEntry<K, V>>(
size);
}
void
initTable(
AtomicReferenceArray<
ReferenceEntry<K, V>>
newTable) {
this.
threshold =
newTable.
length() * 3 / 4; // 0.75
if (this.
threshold ==
maxSegmentSize) {
// prevent spurious expansion before eviction
this.
threshold++;
}
this.
table =
newTable;
}
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
newEntry(K
key, int
hash, @
Nullable ReferenceEntry<K, V>
next) {
return
map.
entryFactory.
newEntry(this,
key,
hash,
next);
}
/**
* Copies {@code original} into a new entry chained to {@code newNext}. Returns the new entry,
* or {@code null} if {@code original} was already garbage collected.
*/
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
copyEntry(
ReferenceEntry<K, V>
original,
ReferenceEntry<K, V>
newNext) {
if (
original.
getKey() == null) {
// key collected
return null;
}
ValueReference<K, V>
valueReference =
original.
getValueReference();
V
value =
valueReference.
get();
if ((
value == null) && !
valueReference.
isComputingReference()) {
// value collected
return null;
}
ReferenceEntry<K, V>
newEntry =
map.
entryFactory.
copyEntry(this,
original,
newNext);
newEntry.
setValueReference(
valueReference.
copyFor(this.
valueReferenceQueue,
value,
newEntry));
return
newEntry;
}
/**
* Sets a new value of an entry. Adds newly created entries at the end of the expiration queue.
*/
@
GuardedBy("Segment.this")
void
setValue(
ReferenceEntry<K, V>
entry, V
value) {
ValueReference<K, V>
valueReference =
map.
valueStrength.
referenceValue(this,
entry,
value);
entry.
setValueReference(
valueReference);
recordWrite(
entry);
}
// reference queues, for garbage collection cleanup
/**
* Cleanup collected entries when the lock is available.
*/
void
tryDrainReferenceQueues() {
if (
tryLock()) {
try {
drainReferenceQueues();
} finally {
unlock();
}
}
}
/**
* Drain the key and value reference queues, cleaning up internal entries containing garbage
* collected keys or values.
*/
@
GuardedBy("Segment.this")
void
drainReferenceQueues() {
if (
map.
usesKeyReferences()) {
drainKeyReferenceQueue();
}
if (
map.
usesValueReferences()) {
drainValueReferenceQueue();
}
}
@
GuardedBy("Segment.this")
void
drainKeyReferenceQueue() {
Reference<? extends K>
ref;
int
i = 0;
while ((
ref =
keyReferenceQueue.
poll()) != null) {
@
SuppressWarnings("unchecked")
ReferenceEntry<K, V>
entry = (
ReferenceEntry<K, V>)
ref;
map.
reclaimKey(
entry);
if (++
i ==
DRAIN_MAX) {
break;
}
}
}
@
GuardedBy("Segment.this")
void
drainValueReferenceQueue() {
Reference<? extends V>
ref;
int
i = 0;
while ((
ref =
valueReferenceQueue.
poll()) != null) {
@
SuppressWarnings("unchecked")
ValueReference<K, V>
valueReference = (
ValueReference<K, V>)
ref;
map.
reclaimValue(
valueReference);
if (++
i ==
DRAIN_MAX) {
break;
}
}
}
/**
* Clears all entries from the key and value reference queues.
*/
void
clearReferenceQueues() {
if (
map.
usesKeyReferences()) {
clearKeyReferenceQueue();
}
if (
map.
usesValueReferences()) {
clearValueReferenceQueue();
}
}
void
clearKeyReferenceQueue() {
while (
keyReferenceQueue.
poll() != null) {}
}
void
clearValueReferenceQueue() {
while (
valueReferenceQueue.
poll() != null) {}
}
// recency queue, shared by expiration and eviction
/**
* Records the relative order in which this read was performed by adding {@code entry} to the
* recency queue. At write-time, or when the queue is full past the threshold, the queue will
* be drained and the entries therein processed.
*
* <p>Note: locked reads should use {@link #recordLockedRead}.
*/
void
recordRead(
ReferenceEntry<K, V>
entry) {
if (
map.
expiresAfterAccess()) {
recordExpirationTime(
entry,
map.
expireAfterAccessNanos);
}
recencyQueue.
add(
entry);
}
/**
* Updates the eviction metadata that {@code entry} was just read. This currently amounts to
* adding {@code entry} to relevant eviction lists.
*
* <p>Note: this method should only be called under lock, as it directly manipulates the
* eviction queues. Unlocked reads should use {@link #recordRead}.
*/
@
GuardedBy("Segment.this")
void
recordLockedRead(
ReferenceEntry<K, V>
entry) {
evictionQueue.
add(
entry);
if (
map.
expiresAfterAccess()) {
recordExpirationTime(
entry,
map.
expireAfterAccessNanos);
expirationQueue.
add(
entry);
}
}
/**
* Updates eviction metadata that {@code entry} was just written. This currently amounts to
* adding {@code entry} to relevant eviction lists.
*/
@
GuardedBy("Segment.this")
void
recordWrite(
ReferenceEntry<K, V>
entry) {
// we are already under lock, so drain the recency queue immediately
drainRecencyQueue();
evictionQueue.
add(
entry);
if (
map.
expires()) {
// currently MapMaker ensures that expireAfterWrite and
// expireAfterAccess are mutually exclusive
long
expiration =
map.
expiresAfterAccess()
?
map.
expireAfterAccessNanos
:
map.
expireAfterWriteNanos;
recordExpirationTime(
entry,
expiration);
expirationQueue.
add(
entry);
}
}
/**
* Drains the recency queue, updating eviction metadata that the entries therein were read in
* the specified relative order. This currently amounts to adding them to relevant eviction
* lists (accounting for the fact that they could have been removed from the map since being
* added to the recency queue).
*/
@
GuardedBy("Segment.this")
void
drainRecencyQueue() {
ReferenceEntry<K, V>
e;
while ((
e =
recencyQueue.
poll()) != null) {
// An entry may be in the recency queue despite it being removed from
// the map . This can occur when the entry was concurrently read while a
// writer is removing it from the segment or after a clear has removed
// all of the segment's entries.
if (
evictionQueue.
contains(
e)) {
evictionQueue.
add(
e);
}
if (
map.
expiresAfterAccess() &&
expirationQueue.
contains(
e)) {
expirationQueue.
add(
e);
}
}
}
// expiration
void
recordExpirationTime(
ReferenceEntry<K, V>
entry, long
expirationNanos) {
// might overflow, but that's okay (see isExpired())
entry.
setExpirationTime(
map.
ticker.
read() +
expirationNanos);
}
/**
* Cleanup expired entries when the lock is available.
*/
void
tryExpireEntries() {
if (
tryLock()) {
try {
expireEntries();
} finally {
unlock();
// don't call postWriteCleanup as we're in a read
}
}
}
@
GuardedBy("Segment.this")
void
expireEntries() {
drainRecencyQueue();
if (
expirationQueue.
isEmpty()) {
// There's no point in calling nanoTime() if we have no entries to
// expire.
return;
}
long
now =
map.
ticker.
read();
ReferenceEntry<K, V>
e;
while ((
e =
expirationQueue.
peek()) != null &&
map.
isExpired(
e,
now)) {
if (!
removeEntry(
e,
e.
getHash(),
RemovalCause.
EXPIRED)) {
throw new
AssertionError();
}
}
}
// eviction
void
enqueueNotification(
ReferenceEntry<K, V>
entry,
RemovalCause cause) {
enqueueNotification(
entry.
getKey(),
entry.
getHash(),
entry.
getValueReference().
get(),
cause);
}
void
enqueueNotification(@
Nullable K
key, int
hash, @
Nullable V
value,
RemovalCause cause) {
if (
map.
removalNotificationQueue !=
DISCARDING_QUEUE) {
RemovalNotification<K, V>
notification = new
RemovalNotification<K, V>(
key,
value,
cause);
map.
removalNotificationQueue.
offer(
notification);
}
}
/**
* Performs eviction if the segment is full. This should only be called prior to adding a new
* entry and increasing {@code count}.
*
* @return {@code true} if eviction occurred
*/
@
GuardedBy("Segment.this")
boolean
evictEntries() {
if (
map.
evictsBySize() &&
count >=
maxSegmentSize) {
drainRecencyQueue();
ReferenceEntry<K, V>
e =
evictionQueue.
remove();
if (!
removeEntry(
e,
e.
getHash(),
RemovalCause.
SIZE)) {
throw new
AssertionError();
}
return true;
}
return false;
}
/**
* Returns first entry of bin for given hash.
*/
ReferenceEntry<K, V>
getFirst(int
hash) {
// read this volatile field only once
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
return
table.
get(
hash & (
table.
length() - 1));
}
// Specialized implementations of map methods
ReferenceEntry<K, V>
getEntry(
Object key, int
hash) {
if (
count != 0) { // read-volatile
for (
ReferenceEntry<K, V>
e =
getFirst(
hash);
e != null;
e =
e.
getNext()) {
if (
e.
getHash() !=
hash) {
continue;
}
K
entryKey =
e.
getKey();
if (
entryKey == null) {
tryDrainReferenceQueues();
continue;
}
if (
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
return
e;
}
}
}
return null;
}
ReferenceEntry<K, V>
getLiveEntry(
Object key, int
hash) {
ReferenceEntry<K, V>
e =
getEntry(
key,
hash);
if (
e == null) {
return null;
} else if (
map.
expires() &&
map.
isExpired(
e)) {
tryExpireEntries();
return null;
}
return
e;
}
V
get(
Object key, int
hash) {
try {
ReferenceEntry<K, V>
e =
getLiveEntry(
key,
hash);
if (
e == null) {
return null;
}
V
value =
e.
getValueReference().
get();
if (
value != null) {
recordRead(
e);
} else {
tryDrainReferenceQueues();
}
return
value;
} finally {
postReadCleanup();
}
}
boolean
containsKey(
Object key, int
hash) {
try {
if (
count != 0) { // read-volatile
ReferenceEntry<K, V>
e =
getLiveEntry(
key,
hash);
if (
e == null) {
return false;
}
return
e.
getValueReference().
get() != null;
}
return false;
} finally {
postReadCleanup();
}
}
/**
* This method is a convenience for testing. Code should call {@link
* MapMakerInternalMap#containsValue} directly.
*/
@
VisibleForTesting
boolean
containsValue(
Object value) {
try {
if (
count != 0) { // read-volatile
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
length =
table.
length();
for (int
i = 0;
i <
length; ++
i) {
for (
ReferenceEntry<K, V>
e =
table.
get(
i);
e != null;
e =
e.
getNext()) {
V
entryValue =
getLiveValue(
e);
if (
entryValue == null) {
continue;
}
if (
map.
valueEquivalence.
equivalent(
value,
entryValue)) {
return true;
}
}
}
}
return false;
} finally {
postReadCleanup();
}
}
V
put(K
key, int
hash, V
value, boolean
onlyIfAbsent) {
lock();
try {
preWriteCleanup();
int
newCount = this.
count + 1;
if (
newCount > this.
threshold) { // ensure capacity
expand();
newCount = this.
count + 1;
}
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
// Look for an existing entry.
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
// We found an existing entry.
ValueReference<K, V>
valueReference =
e.
getValueReference();
V
entryValue =
valueReference.
get();
if (
entryValue == null) {
++
modCount;
setValue(
e,
value);
if (!
valueReference.
isComputingReference()) {
enqueueNotification(
key,
hash,
entryValue,
RemovalCause.
COLLECTED);
newCount = this.
count; // count remains unchanged
} else if (
evictEntries()) { // evictEntries after setting new value
newCount = this.
count + 1;
}
this.
count =
newCount; // write-volatile
return null;
} else if (
onlyIfAbsent) {
// Mimic
// "if (!map.containsKey(key)) ...
// else return map.get(key);
recordLockedRead(
e);
return
entryValue;
} else {
// clobber existing entry, count remains unchanged
++
modCount;
enqueueNotification(
key,
hash,
entryValue,
RemovalCause.
REPLACED);
setValue(
e,
value);
return
entryValue;
}
}
}
// Create a new entry.
++
modCount;
ReferenceEntry<K, V>
newEntry =
newEntry(
key,
hash,
first);
setValue(
newEntry,
value);
table.
set(
index,
newEntry);
if (
evictEntries()) { // evictEntries after setting new value
newCount = this.
count + 1;
}
this.
count =
newCount; // write-volatile
return null;
} finally {
unlock();
postWriteCleanup();
}
}
/**
* Expands the table if possible.
*/
@
GuardedBy("Segment.this")
void
expand() {
AtomicReferenceArray<
ReferenceEntry<K, V>>
oldTable =
table;
int
oldCapacity =
oldTable.
length();
if (
oldCapacity >=
MAXIMUM_CAPACITY) {
return;
}
/*
* Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move with a power of two offset.
* We eliminate unnecessary node creation by catching cases where old nodes can be reused
* because their next fields won't change. Statistically, at the default threshold, only
* about one-sixth of them need cloning when a table doubles. The nodes they replace will be
* garbage collectable as soon as they are no longer referenced by any reader thread that may
* be in the midst of traversing table right now.
*/
int
newCount =
count;
AtomicReferenceArray<
ReferenceEntry<K, V>>
newTable =
newEntryArray(
oldCapacity << 1);
threshold =
newTable.
length() * 3 / 4;
int
newMask =
newTable.
length() - 1;
for (int
oldIndex = 0;
oldIndex <
oldCapacity; ++
oldIndex) {
// We need to guarantee that any existing reads of old Map can
// proceed. So we cannot yet null out each bin.
ReferenceEntry<K, V>
head =
oldTable.
get(
oldIndex);
if (
head != null) {
ReferenceEntry<K, V>
next =
head.
getNext();
int
headIndex =
head.
getHash() &
newMask;
// Single node on list
if (
next == null) {
newTable.
set(
headIndex,
head);
} else {
// Reuse the consecutive sequence of nodes with the same target
// index from the end of the list. tail points to the first
// entry in the reusable list.
ReferenceEntry<K, V>
tail =
head;
int
tailIndex =
headIndex;
for (
ReferenceEntry<K, V>
e =
next;
e != null;
e =
e.
getNext()) {
int
newIndex =
e.
getHash() &
newMask;
if (
newIndex !=
tailIndex) {
// The index changed. We'll need to copy the previous entry.
tailIndex =
newIndex;
tail =
e;
}
}
newTable.
set(
tailIndex,
tail);
// Clone nodes leading up to the tail.
for (
ReferenceEntry<K, V>
e =
head;
e !=
tail;
e =
e.
getNext()) {
int
newIndex =
e.
getHash() &
newMask;
ReferenceEntry<K, V>
newNext =
newTable.
get(
newIndex);
ReferenceEntry<K, V>
newFirst =
copyEntry(
e,
newNext);
if (
newFirst != null) {
newTable.
set(
newIndex,
newFirst);
} else {
removeCollectedEntry(
e);
newCount--;
}
}
}
}
}
table =
newTable;
this.
count =
newCount;
}
boolean
replace(K
key, int
hash, V
oldValue, V
newValue) {
lock();
try {
preWriteCleanup();
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
// If the value disappeared, this entry is partially collected,
// and we should pretend like it doesn't exist.
ValueReference<K, V>
valueReference =
e.
getValueReference();
V
entryValue =
valueReference.
get();
if (
entryValue == null) {
if (
isCollected(
valueReference)) {
int
newCount = this.
count - 1;
++
modCount;
enqueueNotification(
entryKey,
hash,
entryValue,
RemovalCause.
COLLECTED);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
}
return false;
}
if (
map.
valueEquivalence.
equivalent(
oldValue,
entryValue)) {
++
modCount;
enqueueNotification(
key,
hash,
entryValue,
RemovalCause.
REPLACED);
setValue(
e,
newValue);
return true;
} else {
// Mimic
// "if (map.containsKey(key) && map.get(key).equals(oldValue))..."
recordLockedRead(
e);
return false;
}
}
}
return false;
} finally {
unlock();
postWriteCleanup();
}
}
V
replace(K
key, int
hash, V
newValue) {
lock();
try {
preWriteCleanup();
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
// If the value disappeared, this entry is partially collected,
// and we should pretend like it doesn't exist.
ValueReference<K, V>
valueReference =
e.
getValueReference();
V
entryValue =
valueReference.
get();
if (
entryValue == null) {
if (
isCollected(
valueReference)) {
int
newCount = this.
count - 1;
++
modCount;
enqueueNotification(
entryKey,
hash,
entryValue,
RemovalCause.
COLLECTED);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
}
return null;
}
++
modCount;
enqueueNotification(
key,
hash,
entryValue,
RemovalCause.
REPLACED);
setValue(
e,
newValue);
return
entryValue;
}
}
return null;
} finally {
unlock();
postWriteCleanup();
}
}
V
remove(
Object key, int
hash) {
lock();
try {
preWriteCleanup();
int
newCount = this.
count - 1;
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
ValueReference<K, V>
valueReference =
e.
getValueReference();
V
entryValue =
valueReference.
get();
RemovalCause cause;
if (
entryValue != null) {
cause =
RemovalCause.
EXPLICIT;
} else if (
isCollected(
valueReference)) {
cause =
RemovalCause.
COLLECTED;
} else {
return null;
}
++
modCount;
enqueueNotification(
entryKey,
hash,
entryValue,
cause);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
return
entryValue;
}
}
return null;
} finally {
unlock();
postWriteCleanup();
}
}
boolean
remove(
Object key, int
hash,
Object value) {
lock();
try {
preWriteCleanup();
int
newCount = this.
count - 1;
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
ValueReference<K, V>
valueReference =
e.
getValueReference();
V
entryValue =
valueReference.
get();
RemovalCause cause;
if (
map.
valueEquivalence.
equivalent(
value,
entryValue)) {
cause =
RemovalCause.
EXPLICIT;
} else if (
isCollected(
valueReference)) {
cause =
RemovalCause.
COLLECTED;
} else {
return false;
}
++
modCount;
enqueueNotification(
entryKey,
hash,
entryValue,
cause);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
return (
cause ==
RemovalCause.
EXPLICIT);
}
}
return false;
} finally {
unlock();
postWriteCleanup();
}
}
void
clear() {
if (
count != 0) {
lock();
try {
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
if (
map.
removalNotificationQueue !=
DISCARDING_QUEUE) {
for (int
i = 0;
i <
table.
length(); ++
i) {
for (
ReferenceEntry<K, V>
e =
table.
get(
i);
e != null;
e =
e.
getNext()) {
// Computing references aren't actually in the map yet.
if (!
e.
getValueReference().
isComputingReference()) {
enqueueNotification(
e,
RemovalCause.
EXPLICIT);
}
}
}
}
for (int
i = 0;
i <
table.
length(); ++
i) {
table.
set(
i, null);
}
clearReferenceQueues();
evictionQueue.
clear();
expirationQueue.
clear();
readCount.
set(0);
++
modCount;
count = 0; // write-volatile
} finally {
unlock();
postWriteCleanup();
}
}
}
/**
* Removes an entry from within a table. All entries following the removed node can stay, but
* all preceding ones need to be cloned.
*
* <p>This method does not decrement count for the removed entry, but does decrement count for
* all partially collected entries which are skipped. As such callers which are modifying count
* must re-read it after calling removeFromChain.
*
* @param first the first entry of the table
* @param entry the entry being removed from the table
* @return the new first entry for the table
*/
@
GuardedBy("Segment.this")
ReferenceEntry<K, V>
removeFromChain(
ReferenceEntry<K, V>
first,
ReferenceEntry<K, V>
entry) {
evictionQueue.
remove(
entry);
expirationQueue.
remove(
entry);
int
newCount =
count;
ReferenceEntry<K, V>
newFirst =
entry.
getNext();
for (
ReferenceEntry<K, V>
e =
first;
e !=
entry;
e =
e.
getNext()) {
ReferenceEntry<K, V>
next =
copyEntry(
e,
newFirst);
if (
next != null) {
newFirst =
next;
} else {
removeCollectedEntry(
e);
newCount--;
}
}
this.
count =
newCount;
return
newFirst;
}
void
removeCollectedEntry(
ReferenceEntry<K, V>
entry) {
enqueueNotification(
entry,
RemovalCause.
COLLECTED);
evictionQueue.
remove(
entry);
expirationQueue.
remove(
entry);
}
/**
* Removes an entry whose key has been garbage collected.
*/
boolean
reclaimKey(
ReferenceEntry<K, V>
entry, int
hash) {
lock();
try {
int
newCount =
count - 1;
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
if (
e ==
entry) {
++
modCount;
enqueueNotification(
e.
getKey(),
hash,
e.
getValueReference().
get(),
RemovalCause.
COLLECTED);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
return true;
}
}
return false;
} finally {
unlock();
postWriteCleanup();
}
}
/**
* Removes an entry whose value has been garbage collected.
*/
boolean
reclaimValue(K
key, int
hash,
ValueReference<K, V>
valueReference) {
lock();
try {
int
newCount = this.
count - 1;
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
ValueReference<K, V>
v =
e.
getValueReference();
if (
v ==
valueReference) {
++
modCount;
enqueueNotification(
key,
hash,
valueReference.
get(),
RemovalCause.
COLLECTED);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
return true;
}
return false;
}
}
return false;
} finally {
unlock();
if (!
isHeldByCurrentThread()) { // don't cleanup inside of put
postWriteCleanup();
}
}
}
/**
* Clears a value that has not yet been set, and thus does not require count to be modified.
*/
boolean
clearValue(K
key, int
hash,
ValueReference<K, V>
valueReference) {
lock();
try {
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
K
entryKey =
e.
getKey();
if (
e.
getHash() ==
hash &&
entryKey != null
&&
map.
keyEquivalence.
equivalent(
key,
entryKey)) {
ValueReference<K, V>
v =
e.
getValueReference();
if (
v ==
valueReference) {
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
table.
set(
index,
newFirst);
return true;
}
return false;
}
}
return false;
} finally {
unlock();
postWriteCleanup();
}
}
@
GuardedBy("Segment.this")
boolean
removeEntry(
ReferenceEntry<K, V>
entry, int
hash,
RemovalCause cause) {
int
newCount = this.
count - 1;
AtomicReferenceArray<
ReferenceEntry<K, V>>
table = this.
table;
int
index =
hash & (
table.
length() - 1);
ReferenceEntry<K, V>
first =
table.
get(
index);
for (
ReferenceEntry<K, V>
e =
first;
e != null;
e =
e.
getNext()) {
if (
e ==
entry) {
++
modCount;
enqueueNotification(
e.
getKey(),
hash,
e.
getValueReference().
get(),
cause);
ReferenceEntry<K, V>
newFirst =
removeFromChain(
first,
e);
newCount = this.
count - 1;
table.
set(
index,
newFirst);
this.
count =
newCount; // write-volatile
return true;
}
}
return false;
}
/**
* Returns {@code true} if the value has been partially collected, meaning that the value is
* null and it is not computing.
*/
boolean
isCollected(
ValueReference<K, V>
valueReference) {
if (
valueReference.
isComputingReference()) {
return false;
}
return (
valueReference.
get() == null);
}
/**
* Gets the value from an entry. Returns {@code null} if the entry is invalid,
* partially-collected, computing, or expired.
*/
V
getLiveValue(
ReferenceEntry<K, V>
entry) {
if (
entry.
getKey() == null) {
tryDrainReferenceQueues();
return null;
}
V
value =
entry.
getValueReference().
get();
if (
value == null) {
tryDrainReferenceQueues();
return null;
}
if (
map.
expires() &&
map.
isExpired(
entry)) {
tryExpireEntries();
return null;
}
return
value;
}
/**
* Performs routine cleanup following a read. Normally cleanup happens during writes, or from
* the cleanupExecutor. If cleanup is not observed after a sufficient number of reads, try
* cleaning up from the read thread.
*/
void
postReadCleanup() {
if ((
readCount.
incrementAndGet() &
DRAIN_THRESHOLD) == 0) {
runCleanup();
}
}
/**
* Performs routine cleanup prior to executing a write. This should be called every time a
* write thread acquires the segment lock, immediately after acquiring the lock.
*
* <p>Post-condition: expireEntries has been run.
*/
@
GuardedBy("Segment.this")
void
preWriteCleanup() {
runLockedCleanup();
}
/**
* Performs routine cleanup following a write.
*/
void
postWriteCleanup() {
runUnlockedCleanup();
}
void
runCleanup() {
runLockedCleanup();
runUnlockedCleanup();
}
void
runLockedCleanup() {
if (
tryLock()) {
try {
drainReferenceQueues();
expireEntries(); // calls drainRecencyQueue
readCount.
set(0);
} finally {
unlock();
}
}
}
void
runUnlockedCleanup() {
// locked cleanup may generate notifications we can send unlocked
if (!
isHeldByCurrentThread()) {
map.
processPendingNotifications();
}
}
}
// Queues
/**
* A custom queue for managing eviction order. Note that this is tightly integrated with {@code
* ReferenceEntry}, upon which it relies to perform its linking.
*
* <p>Note that this entire implementation makes the assumption that all elements which are in
* the map are also in this queue, and that all elements not in the queue are not in the map.
*
* <p>The benefits of creating our own queue are that (1) we can replace elements in the middle
* of the queue as part of copyEvictableEntry, and (2) the contains method is highly optimized
* for the current model.
*/
static final class
EvictionQueue<K, V> extends
AbstractQueue<
ReferenceEntry<K, V>> {
final
ReferenceEntry<K, V>
head = new
AbstractReferenceEntry<K, V>() {
ReferenceEntry<K, V>
nextEvictable = this;
@
Override
public
ReferenceEntry<K, V>
getNextEvictable() {
return
nextEvictable;
}
@
Override
public void
setNextEvictable(
ReferenceEntry<K, V>
next) {
this.
nextEvictable =
next;
}
ReferenceEntry<K, V>
previousEvictable = this;
@
Override
public
ReferenceEntry<K, V>
getPreviousEvictable() {
return
previousEvictable;
}
@
Override
public void
setPreviousEvictable(
ReferenceEntry<K, V>
previous) {
this.
previousEvictable =
previous;
}
};
// implements Queue
@
Override
public boolean
offer(
ReferenceEntry<K, V>
entry) {
// unlink
connectEvictables(
entry.
getPreviousEvictable(),
entry.
getNextEvictable());
// add to tail
connectEvictables(
head.
getPreviousEvictable(),
entry);
connectEvictables(
entry,
head);
return true;
}
@
Override
public
ReferenceEntry<K, V>
peek() {
ReferenceEntry<K, V>
next =
head.
getNextEvictable();
return (
next ==
head) ? null :
next;
}
@
Override
public
ReferenceEntry<K, V>
poll() {
ReferenceEntry<K, V>
next =
head.
getNextEvictable();
if (
next ==
head) {
return null;
}
remove(
next);
return
next;
}
@
Override
@
SuppressWarnings("unchecked")
public boolean
remove(
Object o) {
ReferenceEntry<K, V>
e = (
ReferenceEntry)
o;
ReferenceEntry<K, V>
previous =
e.
getPreviousEvictable();
ReferenceEntry<K, V>
next =
e.
getNextEvictable();
connectEvictables(
previous,
next);
nullifyEvictable(
e);
return
next !=
NullEntry.
INSTANCE;
}
@
Override
@
SuppressWarnings("unchecked")
public boolean
contains(
Object o) {
ReferenceEntry<K, V>
e = (
ReferenceEntry)
o;
return
e.
getNextEvictable() !=
NullEntry.
INSTANCE;
}
@
Override
public boolean
isEmpty() {
return
head.
getNextEvictable() ==
head;
}
@
Override
public int
size() {
int
size = 0;
for (
ReferenceEntry<K, V>
e =
head.
getNextEvictable();
e !=
head;
e =
e.
getNextEvictable()) {
size++;
}
return
size;
}
@
Override
public void
clear() {
ReferenceEntry<K, V>
e =
head.
getNextEvictable();
while (
e !=
head) {
ReferenceEntry<K, V>
next =
e.
getNextEvictable();
nullifyEvictable(
e);
e =
next;
}
head.
setNextEvictable(
head);
head.
setPreviousEvictable(
head);
}
@
Override
public
Iterator<
ReferenceEntry<K, V>>
iterator() {
return new
AbstractSequentialIterator<
ReferenceEntry<K, V>>(
peek()) {
@
Override
protected
ReferenceEntry<K, V>
computeNext(
ReferenceEntry<K, V>
previous) {
ReferenceEntry<K, V>
next =
previous.
getNextEvictable();
return (
next ==
head) ? null :
next;
}
};
}
}
/**
* A custom queue for managing expiration order. Note that this is tightly integrated with
* {@code ReferenceEntry}, upon which it reliese to perform its linking.
*
* <p>Note that this entire implementation makes the assumption that all elements which are in
* the map are also in this queue, and that all elements not in the queue are not in the map.
*
* <p>The benefits of creating our own queue are that (1) we can replace elements in the middle
* of the queue as part of copyEvictableEntry, and (2) the contains method is highly optimized
* for the current model.
*/
static final class
ExpirationQueue<K, V> extends
AbstractQueue<
ReferenceEntry<K, V>> {
final
ReferenceEntry<K, V>
head = new
AbstractReferenceEntry<K, V>() {
@
Override
public long
getExpirationTime() {
return
Long.
MAX_VALUE;
}
@
Override
public void
setExpirationTime(long
time) {}
ReferenceEntry<K, V>
nextExpirable = this;
@
Override
public
ReferenceEntry<K, V>
getNextExpirable() {
return
nextExpirable;
}
@
Override
public void
setNextExpirable(
ReferenceEntry<K, V>
next) {
this.
nextExpirable =
next;
}
ReferenceEntry<K, V>
previousExpirable = this;
@
Override
public
ReferenceEntry<K, V>
getPreviousExpirable() {
return
previousExpirable;
}
@
Override
public void
setPreviousExpirable(
ReferenceEntry<K, V>
previous) {
this.
previousExpirable =
previous;
}
};
// implements Queue
@
Override
public boolean
offer(
ReferenceEntry<K, V>
entry) {
// unlink
connectExpirables(
entry.
getPreviousExpirable(),
entry.
getNextExpirable());
// add to tail
connectExpirables(
head.
getPreviousExpirable(),
entry);
connectExpirables(
entry,
head);
return true;
}
@
Override
public
ReferenceEntry<K, V>
peek() {
ReferenceEntry<K, V>
next =
head.
getNextExpirable();
return (
next ==
head) ? null :
next;
}
@
Override
public
ReferenceEntry<K, V>
poll() {
ReferenceEntry<K, V>
next =
head.
getNextExpirable();
if (
next ==
head) {
return null;
}
remove(
next);
return
next;
}
@
Override
@
SuppressWarnings("unchecked")
public boolean
remove(
Object o) {
ReferenceEntry<K, V>
e = (
ReferenceEntry)
o;
ReferenceEntry<K, V>
previous =
e.
getPreviousExpirable();
ReferenceEntry<K, V>
next =
e.
getNextExpirable();
connectExpirables(
previous,
next);
nullifyExpirable(
e);
return
next !=
NullEntry.
INSTANCE;
}
@
Override
@
SuppressWarnings("unchecked")
public boolean
contains(
Object o) {
ReferenceEntry<K, V>
e = (
ReferenceEntry)
o;
return
e.
getNextExpirable() !=
NullEntry.
INSTANCE;
}
@
Override
public boolean
isEmpty() {
return
head.
getNextExpirable() ==
head;
}
@
Override
public int
size() {
int
size = 0;
for (
ReferenceEntry<K, V>
e =
head.
getNextExpirable();
e !=
head;
e =
e.
getNextExpirable()) {
size++;
}
return
size;
}
@
Override
public void
clear() {
ReferenceEntry<K, V>
e =
head.
getNextExpirable();
while (
e !=
head) {
ReferenceEntry<K, V>
next =
e.
getNextExpirable();
nullifyExpirable(
e);
e =
next;
}
head.
setNextExpirable(
head);
head.
setPreviousExpirable(
head);
}
@
Override
public
Iterator<
ReferenceEntry<K, V>>
iterator() {
return new
AbstractSequentialIterator<
ReferenceEntry<K, V>>(
peek()) {
@
Override
protected
ReferenceEntry<K, V>
computeNext(
ReferenceEntry<K, V>
previous) {
ReferenceEntry<K, V>
next =
previous.
getNextExpirable();
return (
next ==
head) ? null :
next;
}
};
}
}
static final class
CleanupMapTask implements
Runnable {
final
WeakReference<
MapMakerInternalMap<?, ?>>
mapReference;
public
CleanupMapTask(
MapMakerInternalMap<?, ?>
map) {
this.
mapReference = new
WeakReference<
MapMakerInternalMap<?, ?>>(
map);
}
@
Override
public void
run() {
MapMakerInternalMap<?, ?>
map =
mapReference.
get();
if (
map == null) {
throw new
CancellationException();
}
for (
Segment<?, ?>
segment :
map.
segments) {
segment.
runCleanup();
}
}
}
// ConcurrentMap methods
@
Override
public boolean
isEmpty() {
/*
* Sum per-segment modCounts to avoid mis-reporting when elements are concurrently added and
* removed in one segment while checking another, in which case the table was never actually
* empty at any point. (The sum ensures accuracy up through at least 1<<31 per-segment
* modifications before recheck.) Method containsValue() uses similar constructions for
* stability checks.
*/
long
sum = 0L;
Segment<K, V>[]
segments = this.
segments;
for (int
i = 0;
i <
segments.length; ++
i) {
if (
segments[
i].
count != 0) {
return false;
}
sum +=
segments[
i].
modCount;
}
if (
sum != 0L) { // recheck unless no modifications
for (int
i = 0;
i <
segments.length; ++
i) {
if (
segments[
i].
count != 0) {
return false;
}
sum -=
segments[
i].
modCount;
}
if (
sum != 0L) {
return false;
}
}
return true;
}
@
Override
public int
size() {
Segment<K, V>[]
segments = this.
segments;
long
sum = 0;
for (int
i = 0;
i <
segments.length; ++
i) {
sum +=
segments[
i].
count;
}
return
Ints.
saturatedCast(
sum);
}
@
Override
public V
get(@
Nullable Object key) {
if (
key == null) {
return null;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
get(
key,
hash);
}
/**
* Returns the internal entry for the specified key. The entry may be computing, expired, or
* partially collected. Does not impact recency ordering.
*/
ReferenceEntry<K, V>
getEntry(@
Nullable Object key) {
if (
key == null) {
return null;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
getEntry(
key,
hash);
}
@
Override
public boolean
containsKey(@
Nullable Object key) {
if (
key == null) {
return false;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
containsKey(
key,
hash);
}
@
Override
public boolean
containsValue(@
Nullable Object value) {
if (
value == null) {
return false;
}
// This implementation is patterned after ConcurrentHashMap, but without the locking. The only
// way for it to return a false negative would be for the target value to jump around in the map
// such that none of the subsequent iterations observed it, despite the fact that at every point
// in time it was present somewhere int the map. This becomes increasingly unlikely as
// CONTAINS_VALUE_RETRIES increases, though without locking it is theoretically possible.
final
Segment<K, V>[]
segments = this.
segments;
long
last = -1L;
for (int
i = 0;
i <
CONTAINS_VALUE_RETRIES;
i++) {
long
sum = 0L;
for (
Segment<K, V>
segment :
segments) {
// ensure visibility of most recent completed write
@
SuppressWarnings({"UnusedDeclaration", "unused"})
int
c =
segment.
count; // read-volatile
AtomicReferenceArray<
ReferenceEntry<K, V>>
table =
segment.
table;
for (int
j = 0;
j <
table.
length();
j++) {
for (
ReferenceEntry<K, V>
e =
table.
get(
j);
e != null;
e =
e.
getNext()) {
V
v =
segment.
getLiveValue(
e);
if (
v != null &&
valueEquivalence.
equivalent(
value,
v)) {
return true;
}
}
}
sum +=
segment.
modCount;
}
if (
sum ==
last) {
break;
}
last =
sum;
}
return false;
}
@
Override
public V
put(K
key, V
value) {
checkNotNull(
key);
checkNotNull(
value);
int
hash =
hash(
key);
return
segmentFor(
hash).
put(
key,
hash,
value, false);
}
@
Override
public V
putIfAbsent(K
key, V
value) {
checkNotNull(
key);
checkNotNull(
value);
int
hash =
hash(
key);
return
segmentFor(
hash).
put(
key,
hash,
value, true);
}
@
Override
public void
putAll(
Map<? extends K, ? extends V>
m) {
for (
Entry<? extends K, ? extends V>
e :
m.
entrySet()) {
put(
e.
getKey(),
e.
getValue());
}
}
@
Override
public V
remove(@
Nullable Object key) {
if (
key == null) {
return null;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
remove(
key,
hash);
}
@
Override
public boolean
remove(@
Nullable Object key, @
Nullable Object value) {
if (
key == null ||
value == null) {
return false;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
remove(
key,
hash,
value);
}
@
Override
public boolean
replace(K
key, @
Nullable V
oldValue, V
newValue) {
checkNotNull(
key);
checkNotNull(
newValue);
if (
oldValue == null) {
return false;
}
int
hash =
hash(
key);
return
segmentFor(
hash).
replace(
key,
hash,
oldValue,
newValue);
}
@
Override
public V
replace(K
key, V
value) {
checkNotNull(
key);
checkNotNull(
value);
int
hash =
hash(
key);
return
segmentFor(
hash).
replace(
key,
hash,
value);
}
@
Override
public void
clear() {
for (
Segment<K, V>
segment :
segments) {
segment.
clear();
}
}
transient
Set<K>
keySet;
@
Override
public
Set<K>
keySet() {
Set<K>
ks =
keySet;
return (
ks != null) ?
ks : (
keySet = new
KeySet());
}
transient
Collection<V>
values;
@
Override
public
Collection<V>
values() {
Collection<V>
vs =
values;
return (
vs != null) ?
vs : (
values = new
Values());
}
transient
Set<
Entry<K, V>>
entrySet;
@
Override
public
Set<
Entry<K, V>>
entrySet() {
Set<
Entry<K, V>>
es =
entrySet;
return (
es != null) ?
es : (
entrySet = new
EntrySet());
}
// Iterator Support
abstract class
HashIterator<E> implements
Iterator<E> {
int
nextSegmentIndex;
int
nextTableIndex;
Segment<K, V>
currentSegment;
AtomicReferenceArray<
ReferenceEntry<K, V>>
currentTable;
ReferenceEntry<K, V>
nextEntry;
WriteThroughEntry nextExternal;
WriteThroughEntry lastReturned;
HashIterator() {
nextSegmentIndex =
segments.length - 1;
nextTableIndex = -1;
advance();
}
@
Override
public abstract E
next();
final void
advance() {
nextExternal = null;
if (
nextInChain()) {
return;
}
if (
nextInTable()) {
return;
}
while (
nextSegmentIndex >= 0) {
currentSegment =
segments[
nextSegmentIndex--];
if (
currentSegment.
count != 0) {
currentTable =
currentSegment.
table;
nextTableIndex =
currentTable.
length() - 1;
if (
nextInTable()) {
return;
}
}
}
}
/**
* Finds the next entry in the current chain. Returns {@code true} if an entry was found.
*/
boolean
nextInChain() {
if (
nextEntry != null) {
for (
nextEntry =
nextEntry.
getNext();
nextEntry != null;
nextEntry =
nextEntry.
getNext()) {
if (
advanceTo(
nextEntry)) {
return true;
}
}
}
return false;
}
/**
* Finds the next entry in the current table. Returns {@code true} if an entry was found.
*/
boolean
nextInTable() {
while (
nextTableIndex >= 0) {
if ((
nextEntry =
currentTable.
get(
nextTableIndex--)) != null) {
if (
advanceTo(
nextEntry) ||
nextInChain()) {
return true;
}
}
}
return false;
}
/**
* Advances to the given entry. Returns {@code true} if the entry was valid, {@code false} if it
* should be skipped.
*/
boolean
advanceTo(
ReferenceEntry<K, V>
entry) {
try {
K
key =
entry.
getKey();
V
value =
getLiveValue(
entry);
if (
value != null) {
nextExternal = new
WriteThroughEntry(
key,
value);
return true;
} else {
// Skip stale entry.
return false;
}
} finally {
currentSegment.
postReadCleanup();
}
}
@
Override
public boolean
hasNext() {
return
nextExternal != null;
}
WriteThroughEntry nextEntry() {
if (
nextExternal == null) {
throw new
NoSuchElementException();
}
lastReturned =
nextExternal;
advance();
return
lastReturned;
}
@
Override
public void
remove() {
checkRemove(
lastReturned != null);
MapMakerInternalMap.this.
remove(
lastReturned.
getKey());
lastReturned = null;
}
}
final class
KeyIterator extends
HashIterator<K> {
@
Override
public K
next() {
return
nextEntry().
getKey();
}
}
final class
ValueIterator extends
HashIterator<V> {
@
Override
public V
next() {
return
nextEntry().
getValue();
}
}
/**
* Custom Entry class used by EntryIterator.next(), that relays setValue changes to the
* underlying map.
*/
final class
WriteThroughEntry extends
AbstractMapEntry<K, V> {
final K
key; // non-null
V
value; // non-null
WriteThroughEntry(K
key, V
value) {
this.
key =
key;
this.
value =
value;
}
@
Override
public K
getKey() {
return
key;
}
@
Override
public V
getValue() {
return
value;
}
@
Override
public boolean
equals(@
Nullable Object object) {
// Cannot use key and value equivalence
if (
object instanceof
Entry) {
Entry<?, ?>
that = (
Entry<?, ?>)
object;
return
key.
equals(
that.
getKey()) &&
value.
equals(
that.
getValue());
}
return false;
}
@
Override
public int
hashCode() {
// Cannot use key and value equivalence
return
key.
hashCode() ^
value.
hashCode();
}
@
Override
public V
setValue(V
newValue) {
V
oldValue =
put(
key,
newValue);
value =
newValue; // only if put succeeds
return
oldValue;
}
}
final class
EntryIterator extends
HashIterator<
Entry<K, V>> {
@
Override
public
Entry<K, V>
next() {
return
nextEntry();
}
}
final class
KeySet extends
AbstractSet<K> {
@
Override
public
Iterator<K>
iterator() {
return new
KeyIterator();
}
@
Override
public int
size() {
return
MapMakerInternalMap.this.
size();
}
@
Override
public boolean
isEmpty() {
return
MapMakerInternalMap.this.
isEmpty();
}
@
Override
public boolean
contains(
Object o) {
return
MapMakerInternalMap.this.
containsKey(
o);
}
@
Override
public boolean
remove(
Object o) {
return
MapMakerInternalMap.this.
remove(
o) != null;
}
@
Override
public void
clear() {
MapMakerInternalMap.this.
clear();
}
}
final class
Values extends
AbstractCollection<V> {
@
Override
public
Iterator<V>
iterator() {
return new
ValueIterator();
}
@
Override
public int
size() {
return
MapMakerInternalMap.this.
size();
}
@
Override
public boolean
isEmpty() {
return
MapMakerInternalMap.this.
isEmpty();
}
@
Override
public boolean
contains(
Object o) {
return
MapMakerInternalMap.this.
containsValue(
o);
}
@
Override
public void
clear() {
MapMakerInternalMap.this.
clear();
}
}
final class
EntrySet extends
AbstractSet<
Entry<K, V>> {
@
Override
public
Iterator<
Entry<K, V>>
iterator() {
return new
EntryIterator();
}
@
Override
public boolean
contains(
Object o) {
if (!(
o instanceof
Entry)) {
return false;
}
Entry<?, ?>
e = (
Entry<?, ?>)
o;
Object key =
e.
getKey();
if (
key == null) {
return false;
}
V
v =
MapMakerInternalMap.this.
get(
key);
return
v != null &&
valueEquivalence.
equivalent(
e.
getValue(),
v);
}
@
Override
public boolean
remove(
Object o) {
if (!(
o instanceof
Entry)) {
return false;
}
Entry<?, ?>
e = (
Entry<?, ?>)
o;
Object key =
e.
getKey();
return
key != null &&
MapMakerInternalMap.this.
remove(
key,
e.
getValue());
}
@
Override
public int
size() {
return
MapMakerInternalMap.this.
size();
}
@
Override
public boolean
isEmpty() {
return
MapMakerInternalMap.this.
isEmpty();
}
@
Override
public void
clear() {
MapMakerInternalMap.this.
clear();
}
}
// Serialization Support
private static final long
serialVersionUID = 5;
Object writeReplace() {
return new
SerializationProxy<K, V>(
keyStrength,
valueStrength,
keyEquivalence,
valueEquivalence,
expireAfterWriteNanos,
expireAfterAccessNanos,
maximumSize,
concurrencyLevel,
removalListener, this);
}
/**
* The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
* circular dependency is present, so the proxy must be able to behave as the map itself.
*/
abstract static class
AbstractSerializationProxy<K, V>
extends
ForwardingConcurrentMap<K, V> implements
Serializable {
private static final long
serialVersionUID = 3;
final
Strength keyStrength;
final
Strength valueStrength;
final
Equivalence<
Object>
keyEquivalence;
final
Equivalence<
Object>
valueEquivalence;
final long
expireAfterWriteNanos;
final long
expireAfterAccessNanos;
final int
maximumSize;
final int
concurrencyLevel;
final
RemovalListener<? super K, ? super V>
removalListener;
transient
ConcurrentMap<K, V>
delegate;
AbstractSerializationProxy(
Strength keyStrength,
Strength valueStrength,
Equivalence<
Object>
keyEquivalence,
Equivalence<
Object>
valueEquivalence,
long
expireAfterWriteNanos, long
expireAfterAccessNanos, int
maximumSize,
int
concurrencyLevel,
RemovalListener<? super K, ? super V>
removalListener,
ConcurrentMap<K, V>
delegate) {
this.
keyStrength =
keyStrength;
this.
valueStrength =
valueStrength;
this.
keyEquivalence =
keyEquivalence;
this.
valueEquivalence =
valueEquivalence;
this.
expireAfterWriteNanos =
expireAfterWriteNanos;
this.
expireAfterAccessNanos =
expireAfterAccessNanos;
this.
maximumSize =
maximumSize;
this.
concurrencyLevel =
concurrencyLevel;
this.
removalListener =
removalListener;
this.
delegate =
delegate;
}
@
Override
protected
ConcurrentMap<K, V>
delegate() {
return
delegate;
}
void
writeMapTo(
ObjectOutputStream out) throws
IOException {
out.
writeInt(
delegate.
size());
for (
Entry<K, V>
entry :
delegate.
entrySet()) {
out.
writeObject(
entry.
getKey());
out.
writeObject(
entry.
getValue());
}
out.
writeObject(null); // terminate entries
}
@
SuppressWarnings("deprecation") // serialization of deprecated feature
MapMaker readMapMaker(
ObjectInputStream in) throws
IOException {
int
size =
in.
readInt();
MapMaker mapMaker = new
MapMaker()
.
initialCapacity(
size)
.
setKeyStrength(
keyStrength)
.
setValueStrength(
valueStrength)
.
keyEquivalence(
keyEquivalence)
.
concurrencyLevel(
concurrencyLevel);
mapMaker.
removalListener(
removalListener);
if (
expireAfterWriteNanos > 0) {
mapMaker.
expireAfterWrite(
expireAfterWriteNanos,
TimeUnit.
NANOSECONDS);
}
if (
expireAfterAccessNanos > 0) {
mapMaker.
expireAfterAccess(
expireAfterAccessNanos,
TimeUnit.
NANOSECONDS);
}
if (
maximumSize !=
MapMaker.
UNSET_INT) {
mapMaker.
maximumSize(
maximumSize);
}
return
mapMaker;
}
@
SuppressWarnings("unchecked")
void
readEntries(
ObjectInputStream in) throws
IOException,
ClassNotFoundException {
while (true) {
K
key = (K)
in.
readObject();
if (
key == null) {
break; // terminator
}
V
value = (V)
in.
readObject();
delegate.
put(
key,
value);
}
}
}
/**
* The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
* circular dependency is present, so the proxy must be able to behave as the map itself.
*/
private static final class
SerializationProxy<K, V> extends
AbstractSerializationProxy<K, V> {
private static final long
serialVersionUID = 3;
SerializationProxy(
Strength keyStrength,
Strength valueStrength,
Equivalence<
Object>
keyEquivalence,
Equivalence<
Object>
valueEquivalence,
long
expireAfterWriteNanos, long
expireAfterAccessNanos, int
maximumSize,
int
concurrencyLevel,
RemovalListener<? super K, ? super V>
removalListener,
ConcurrentMap<K, V>
delegate) {
super(
keyStrength,
valueStrength,
keyEquivalence,
valueEquivalence,
expireAfterWriteNanos,
expireAfterAccessNanos,
maximumSize,
concurrencyLevel,
removalListener,
delegate);
}
private void
writeObject(
ObjectOutputStream out) throws
IOException {
out.
defaultWriteObject();
writeMapTo(
out);
}
private void
readObject(
ObjectInputStream in) throws
IOException,
ClassNotFoundException {
in.
defaultReadObject();
MapMaker mapMaker =
readMapMaker(
in);
delegate =
mapMaker.
makeMap();
readEntries(
in);
}
private
Object readResolve() {
return
delegate;
}
}
}