/*
* 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.base.Preconditions.checkState;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalences;
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}.
*
*
This implementation is heavily derived from revision 1.96 of ConcurrentHashMap.java .
*
* @author Bob Lee
* @author Charles Fry
* @author Doug Lea ({@code ConcurrentHashMap})
*/
class MapMakerInternalMap
extends AbstractMap implements ConcurrentMap, 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.
*
* 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[] segments;
/** The concurrency level. */
final int concurrencyLevel;
/** Strategy for comparing keys. */
final Equivalence keyEquivalence;
/** Strategy for comparing values. */
final Equivalence 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> removalNotificationQueue;
/**
* A listener that is invoked when an entry is removed due to expiration or garbage collection of
* soft/weak entries.
*/
final RemovalListener 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 = builder.getValueEquivalence();
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.>discardingQueue()
: new ConcurrentLinkedQueue>();
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
ValueReference referenceValue(
Segment segment, ReferenceEntry entry, V value) {
return new StrongValueReference(value);
}
@Override
Equivalence defaultEquivalence() {
return Equivalences.equals();
}
},
SOFT {
@Override
ValueReference referenceValue(
Segment segment, ReferenceEntry entry, V value) {
return new SoftValueReference(segment.valueReferenceQueue, value, entry);
}
@Override
Equivalence defaultEquivalence() {
return Equivalences.identity();
}
},
WEAK {
@Override
ValueReference referenceValue(
Segment segment, ReferenceEntry entry, V value) {
return new WeakValueReference(segment.valueReferenceQueue, value, entry);
}
@Override
Equivalence defaultEquivalence() {
return Equivalences.identity();
}
};
/**
* Creates a reference for the given value according to this value strength.
*/
abstract ValueReference referenceValue(
Segment segment, ReferenceEntry 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 defaultEquivalence();
}
/**
* Creates new entries.
*/
enum EntryFactory {
STRONG {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new StrongEntry(key, hash, next);
}
},
STRONG_EXPIRABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new StrongExpirableEntry(key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyExpirableEntry(original, newEntry);
return newEntry;
}
},
STRONG_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new StrongEvictableEntry(key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyEvictableEntry(original, newEntry);
return newEntry;
}
},
STRONG_EXPIRABLE_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new StrongExpirableEvictableEntry(key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyExpirableEntry(original, newEntry);
copyEvictableEntry(original, newEntry);
return newEntry;
}
},
SOFT {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new SoftEntry(segment.keyReferenceQueue, key, hash, next);
}
},
SOFT_EXPIRABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new SoftExpirableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyExpirableEntry(original, newEntry);
return newEntry;
}
},
SOFT_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new SoftEvictableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyEvictableEntry(original, newEntry);
return newEntry;
}
},
SOFT_EXPIRABLE_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new SoftExpirableEvictableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyExpirableEntry(original, newEntry);
copyEvictableEntry(original, newEntry);
return newEntry;
}
},
WEAK {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new WeakEntry(segment.keyReferenceQueue, key, hash, next);
}
},
WEAK_EXPIRABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new WeakExpirableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyExpirableEntry(original, newEntry);
return newEntry;
}
},
WEAK_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new WeakEvictableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry newEntry = super.copyEntry(segment, original, newNext);
copyEvictableEntry(original, newEntry);
return newEntry;
}
},
WEAK_EXPIRABLE_EVICTABLE {
@Override
ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry next) {
return new WeakExpirableEvictableEntry(segment.keyReferenceQueue, key, hash, next);
}
@Override
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
ReferenceEntry 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 },
{ SOFT, SOFT_EXPIRABLE, SOFT_EVICTABLE, SOFT_EXPIRABLE_EVICTABLE },
{ 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 ReferenceEntry newEntry(
Segment segment, K key, int hash, @Nullable ReferenceEntry 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")
ReferenceEntry copyEntry(
Segment segment, ReferenceEntry original, ReferenceEntry newNext) {
return newEntry(segment, original.getKey(), original.getHash(), newNext);
}
@GuardedBy("Segment.this")
void copyExpirableEntry(ReferenceEntry original, ReferenceEntry 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")
void copyEvictableEntry(ReferenceEntry original, ReferenceEntry 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 {
/**
* 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 getEntry();
/**
* Creates a copy of this reference for the given entry.
*/
ValueReference copyFor(ReferenceQueue queue, ReferenceEntry 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 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 UNSET = new ValueReference() {
@Override
public Object get() {
return null;
}
@Override
public ReferenceEntry getEntry() {
return null;
}
@Override
public ValueReference copyFor(
ReferenceQueue queue, ReferenceEntry entry) {
return this;
}
@Override
public boolean isComputingReference() {
return false;
}
@Override
public Object waitForValue() {
return null;
}
@Override
public void clear(ValueReference newValue) {}
};
/**
* Singleton placeholder that indicates a value is being computed.
*/
@SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static ValueReference unset() {
return (ValueReference) 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 {
/**
* Gets the value reference from this entry.
*/
ValueReference getValueReference();
/**
* Sets the value reference for this entry.
*/
void setValueReference(ValueReference valueReference);
/**
* Gets the next entry in the chain.
*/
ReferenceEntry 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 getNextExpirable();
/**
* Sets the next entry in the recency list.
*/
void setNextExpirable(ReferenceEntry next);
/**
* Gets the previous entry in the recency list.
*/
ReferenceEntry getPreviousExpirable();
/**
* Sets the previous entry in the recency list.
*/
void setPreviousExpirable(ReferenceEntry 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 getNextEvictable();
/**
* Sets the next entry in the recency list.
*/
void setNextEvictable(ReferenceEntry next);
/**
* Gets the previous entry in the recency list.
*/
ReferenceEntry getPreviousEvictable();
/**
* Sets the previous entry in the recency list.
*/
void setPreviousEvictable(ReferenceEntry previous);
}
private enum NullEntry implements ReferenceEntry {
INSTANCE;
@Override
public ValueReference getValueReference() {
return null;
}
@Override
public void setValueReference(ValueReference valueReference) {}
@Override
public ReferenceEntry 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 getNextExpirable() {
return this;
}
@Override
public void setNextExpirable(ReferenceEntry next) {}
@Override
public ReferenceEntry getPreviousExpirable() {
return this;
}
@Override
public void setPreviousExpirable(ReferenceEntry previous) {}
@Override
public ReferenceEntry getNextEvictable() {
return this;
}
@Override
public void setNextEvictable(ReferenceEntry next) {}
@Override
public ReferenceEntry getPreviousEvictable() {
return this;
}
@Override
public void setPreviousEvictable(ReferenceEntry previous) {}
}
static abstract class AbstractReferenceEntry implements ReferenceEntry {
@Override
public ValueReference getValueReference() {
throw new UnsupportedOperationException();
}
@Override
public void setValueReference(ValueReference valueReference) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry 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 getNextExpirable() {
throw new UnsupportedOperationException();
}
@Override
public void setNextExpirable(ReferenceEntry next) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry getPreviousExpirable() {
throw new UnsupportedOperationException();
}
@Override
public void setPreviousExpirable(ReferenceEntry previous) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry getNextEvictable() {
throw new UnsupportedOperationException();
}
@Override
public void setNextEvictable(ReferenceEntry next) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry getPreviousEvictable() {
throw new UnsupportedOperationException();
}
@Override
public void setPreviousEvictable(ReferenceEntry previous) {
throw new UnsupportedOperationException();
}
}
@SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static ReferenceEntry nullEntry() {
return (ReferenceEntry) NullEntry.INSTANCE;
}
static final Queue extends Object> DISCARDING_QUEUE = new AbstractQueue() {
@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 iterator() {
return Iterators.emptyIterator();
}
};
/**
* Queue that discards all elements.
*/
@SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
static Queue 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 implements ReferenceEntry {
final K key;
StrongEntry(K key, int hash, @Nullable ReferenceEntry 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 getNextExpirable() {
throw new UnsupportedOperationException();
}
@Override
public void setNextExpirable(ReferenceEntry next) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry getPreviousExpirable() {
throw new UnsupportedOperationException();
}
@Override
public void setPreviousExpirable(ReferenceEntry previous) {
throw new UnsupportedOperationException();
}
// null eviction
@Override
public ReferenceEntry getNextEvictable() {
throw new UnsupportedOperationException();
}
@Override
public void setNextEvictable(ReferenceEntry next) {
throw new UnsupportedOperationException();
}
@Override
public ReferenceEntry getPreviousEvictable() {
throw new UnsupportedOperationException();
}
@Override
public void setPreviousEvictable(ReferenceEntry previous) {
throw new UnsupportedOperationException();
}
// The code below is exactly the same for each entry type.
final int hash;
final ReferenceEntry next;
volatile ValueReference valueReference = unset();
@Override
public ValueReference getValueReference() {
return valueReference;
}
@Override
public void setValueReference(ValueReference valueReference) {
ValueReference previous = this.valueReference;
this.valueReference = valueReference;
previous.clear(valueReference);
}
@Override
public int getHash() {
return hash;
}
@Override
public ReferenceEntry getNext() {
return next;
}
}
static final class StrongExpirableEntry extends StrongEntry
implements ReferenceEntry {
StrongExpirableEntry(K key, int hash, @Nullable ReferenceEntry 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 nextExpirable = nullEntry();
@Override
public ReferenceEntry getNextExpirable() {
return nextExpirable;
}
@Override
public void setNextExpirable(ReferenceEntry next) {
this.nextExpirable = next;
}
@GuardedBy("Segment.this")
ReferenceEntry previousExpirable = nullEntry();
@Override
public ReferenceEntry getPreviousExpirable() {
return previousExpirable;
}
@Override
public void setPreviousExpirable(ReferenceEntry previous) {
this.previousExpirable = previous;
}
}
static final class StrongEvictableEntry
extends StrongEntry implements ReferenceEntry