View Javadoc
1   /*
2    * Copyright (C) 2009 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.cache;
16  
17  import static com.google.common.base.Preconditions.checkNotNull;
18  import static com.google.common.base.Preconditions.checkState;
19  import static com.google.common.cache.CacheBuilder.NULL_TICKER;
20  import static com.google.common.cache.CacheBuilder.UNSET_INT;
21  import static com.google.common.util.concurrent.Futures.transform;
22  import static com.google.common.util.concurrent.MoreExecutors.directExecutor;
23  import static com.google.common.util.concurrent.Uninterruptibles.getUninterruptibly;
24  import static java.util.concurrent.TimeUnit.NANOSECONDS;
25  
26  import com.google.common.annotations.GwtCompatible;
27  import com.google.common.annotations.GwtIncompatible;
28  import com.google.common.annotations.VisibleForTesting;
29  import com.google.common.base.Equivalence;
30  import com.google.common.base.Stopwatch;
31  import com.google.common.base.Ticker;
32  import com.google.common.cache.AbstractCache.SimpleStatsCounter;
33  import com.google.common.cache.AbstractCache.StatsCounter;
34  import com.google.common.cache.CacheBuilder.NullListener;
35  import com.google.common.cache.CacheBuilder.OneWeigher;
36  import com.google.common.cache.CacheLoader.InvalidCacheLoadException;
37  import com.google.common.cache.CacheLoader.UnsupportedLoadingOperationException;
38  import com.google.common.cache.LocalCache.AbstractCacheSet;
39  import com.google.common.collect.AbstractSequentialIterator;
40  import com.google.common.collect.ImmutableMap;
41  import com.google.common.collect.ImmutableSet;
42  import com.google.common.collect.Iterators;
43  import com.google.common.collect.Maps;
44  import com.google.common.collect.Sets;
45  import com.google.common.primitives.Ints;
46  import com.google.common.util.concurrent.ExecutionError;
47  import com.google.common.util.concurrent.Futures;
48  import com.google.common.util.concurrent.ListenableFuture;
49  import com.google.common.util.concurrent.SettableFuture;
50  import com.google.common.util.concurrent.UncheckedExecutionException;
51  import com.google.common.util.concurrent.Uninterruptibles;
52  import com.google.j2objc.annotations.Weak;
53  import com.google.j2objc.annotations.WeakOuter;
54  import java.io.IOException;
55  import java.io.ObjectInputStream;
56  import java.io.Serializable;
57  import java.lang.ref.Reference;
58  import java.lang.ref.ReferenceQueue;
59  import java.lang.ref.SoftReference;
60  import java.lang.ref.WeakReference;
61  import java.util.AbstractCollection;
62  import java.util.AbstractMap;
63  import java.util.AbstractQueue;
64  import java.util.AbstractSet;
65  import java.util.ArrayList;
66  import java.util.Collection;
67  import java.util.Iterator;
68  import java.util.Map;
69  import java.util.Map.Entry;
70  import java.util.NoSuchElementException;
71  import java.util.Queue;
72  import java.util.Set;
73  import java.util.concurrent.Callable;
74  import java.util.concurrent.ConcurrentLinkedQueue;
75  import java.util.concurrent.ConcurrentMap;
76  import java.util.concurrent.ExecutionException;
77  import java.util.concurrent.TimeUnit;
78  import java.util.concurrent.atomic.AtomicInteger;
79  import java.util.concurrent.atomic.AtomicReferenceArray;
80  import java.util.concurrent.locks.ReentrantLock;
81  import java.util.function.BiFunction;
82  import java.util.function.BiPredicate;
83  import java.util.function.Function;
84  import java.util.function.Predicate;
85  import java.util.logging.Level;
86  import java.util.logging.Logger;
87  import javax.annotation.Nullable;
88  import javax.annotation.concurrent.GuardedBy;
89  
90  /**
91   * The concurrent hash map implementation built by {@link CacheBuilder}.
92   *
93   * <p>This implementation is heavily derived from revision 1.96 of
94   * <a href="http://tinyurl.com/ConcurrentHashMap">ConcurrentHashMap.java</a>.
95   *
96   * @author Charles Fry
97   * @author Bob Lee ({@code com.google.common.collect.MapMaker})
98   * @author Doug Lea ({@code ConcurrentHashMap})
99   */
100 @GwtCompatible(emulated = true)
101 class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
102 
103   /*
104    * The basic strategy is to subdivide the table among Segments, each of which itself is a
105    * concurrently readable hash table. The map supports non-blocking reads and concurrent writes
106    * across different segments.
107    *
108    * If a maximum size is specified, a best-effort bounding is performed per segment, using a
109    * page-replacement algorithm to determine which entries to evict when the capacity has been
110    * exceeded.
111    *
112    * The page replacement algorithm's data structures are kept casually consistent with the map. The
113    * ordering of writes to a segment is sequentially consistent. An update to the map and recording
114    * of reads may not be immediately reflected on the algorithm's data structures. These structures
115    * are guarded by a lock and operations are applied in batches to avoid lock contention. The
116    * penalty of applying the batches is spread across threads so that the amortized cost is slightly
117    * higher than performing just the operation without enforcing the capacity constraint.
118    *
119    * This implementation uses a per-segment queue to record a memento of the additions, removals,
120    * and accesses that were performed on the map. The queue is drained on writes and when it exceeds
121    * its capacity threshold.
122    *
123    * The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit
124    * rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation
125    * operates per-segment rather than globally for increased implementation simplicity. We expect
126    * the cache hit rate to be similar to that of a global LRU algorithm.
127    */
128 
129   // Constants
130 
131   /**
132    * The maximum capacity, used if a higher value is implicitly specified by either of the
133    * constructors with arguments. MUST be a power of two {@code <= 1<<30} to ensure that entries are
134    * indexable using ints.
135    */
136   static final int MAXIMUM_CAPACITY = 1 << 30;
137 
138   /** The maximum number of segments to allow; used to bound constructor arguments. */
139   static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
140 
141   /** Number of (unsynchronized) retries in the containsValue method. */
142   static final int CONTAINS_VALUE_RETRIES = 3;
143 
144   /**
145    * Number of cache access operations that can be buffered per segment before the cache's recency
146    * ordering information is updated. This is used to avoid lock contention by recording a memento
147    * of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs.
148    *
149    * <p>This must be a (2^n)-1 as it is used as a mask.
150    */
151   static final int DRAIN_THRESHOLD = 0x3F;
152 
153   /**
154    * Maximum number of entries to be drained in a single cleanup run. This applies independently to
155    * the cleanup queue and both reference queues.
156    */
157   // TODO(fry): empirically optimize this
158   static final int DRAIN_MAX = 16;
159 
160   // Fields
161 
162   static final Logger logger = Logger.getLogger(LocalCache.class.getName());
163 
164   /**
165    * Mask value for indexing into segments. The upper bits of a key's hash code are used to choose
166    * the segment.
167    */
168   final int segmentMask;
169 
170   /**
171    * Shift value for indexing within segments. Helps prevent entries that end up in the same segment
172    * from also ending up in the same bucket.
173    */
174   final int segmentShift;
175 
176   /** The segments, each of which is a specialized hash table. */
177   final Segment<K, V>[] segments;
178 
179   /** The concurrency level. */
180   final int concurrencyLevel;
181 
182   /** Strategy for comparing keys. */
183   final Equivalence<Object> keyEquivalence;
184 
185   /** Strategy for comparing values. */
186   final Equivalence<Object> valueEquivalence;
187 
188   /** Strategy for referencing keys. */
189   final Strength keyStrength;
190 
191   /** Strategy for referencing values. */
192   final Strength valueStrength;
193 
194   /** The maximum weight of this map. UNSET_INT if there is no maximum. */
195   final long maxWeight;
196 
197   /** Weigher to weigh cache entries. */
198   final Weigher<K, V> weigher;
199 
200   /** How long after the last access to an entry the map will retain that entry. */
201   final long expireAfterAccessNanos;
202 
203   /** How long after the last write to an entry the map will retain that entry. */
204   final long expireAfterWriteNanos;
205 
206   /** How long after the last write an entry becomes a candidate for refresh. */
207   final long refreshNanos;
208 
209   /** Entries waiting to be consumed by the removal listener. */
210   // TODO(fry): define a new type which creates event objects and automates the clear logic
211   final Queue<RemovalNotification<K, V>> removalNotificationQueue;
212 
213   /**
214    * A listener that is invoked when an entry is removed due to expiration or garbage collection of
215    * soft/weak entries.
216    */
217   final RemovalListener<K, V> removalListener;
218 
219   /** Measures time in a testable way. */
220   final Ticker ticker;
221 
222   /** Factory used to create new entries. */
223   final EntryFactory entryFactory;
224 
225   /**
226    * Accumulates global cache statistics. Note that there are also per-segments stats counters which
227    * must be aggregated to obtain a global stats view.
228    */
229   final StatsCounter globalStatsCounter;
230 
231   /**
232    * The default cache loader to use on loading operations.
233    */
234   @Nullable final CacheLoader<? super K, V> defaultLoader;
235 
236   /**
237    * Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
238    */
239   LocalCache(
240       CacheBuilder<? super K, ? super V> builder, @Nullable CacheLoader<? super K, V> loader) {
241     concurrencyLevel = Math.min(builder.getConcurrencyLevel(), MAX_SEGMENTS);
242 
243     keyStrength = builder.getKeyStrength();
244     valueStrength = builder.getValueStrength();
245 
246     keyEquivalence = builder.getKeyEquivalence();
247     valueEquivalence = builder.getValueEquivalence();
248 
249     maxWeight = builder.getMaximumWeight();
250     weigher = builder.getWeigher();
251     expireAfterAccessNanos = builder.getExpireAfterAccessNanos();
252     expireAfterWriteNanos = builder.getExpireAfterWriteNanos();
253     refreshNanos = builder.getRefreshNanos();
254 
255     removalListener = builder.getRemovalListener();
256     removalNotificationQueue =
257         (removalListener == NullListener.INSTANCE)
258             ? LocalCache.<RemovalNotification<K, V>>discardingQueue()
259             : new ConcurrentLinkedQueue<RemovalNotification<K, V>>();
260 
261     ticker = builder.getTicker(recordsTime());
262     entryFactory = EntryFactory.getFactory(keyStrength, usesAccessEntries(), usesWriteEntries());
263     globalStatsCounter = builder.getStatsCounterSupplier().get();
264     defaultLoader = loader;
265 
266     int initialCapacity = Math.min(builder.getInitialCapacity(), MAXIMUM_CAPACITY);
267     if (evictsBySize() && !customWeigher()) {
268       initialCapacity = Math.min(initialCapacity, (int) maxWeight);
269     }
270 
271     // Find the lowest power-of-two segmentCount that exceeds concurrencyLevel, unless
272     // maximumSize/Weight is specified in which case ensure that each segment gets at least 10
273     // entries. The special casing for size-based eviction is only necessary because that eviction
274     // happens per segment instead of globally, so too many segments compared to the maximum size
275     // will result in random eviction behavior.
276     int segmentShift = 0;
277     int segmentCount = 1;
278     while (segmentCount < concurrencyLevel && (!evictsBySize() || segmentCount * 20 <= maxWeight)) {
279       ++segmentShift;
280       segmentCount <<= 1;
281     }
282     this.segmentShift = 32 - segmentShift;
283     segmentMask = segmentCount - 1;
284 
285     this.segments = newSegmentArray(segmentCount);
286 
287     int segmentCapacity = initialCapacity / segmentCount;
288     if (segmentCapacity * segmentCount < initialCapacity) {
289       ++segmentCapacity;
290     }
291 
292     int segmentSize = 1;
293     while (segmentSize < segmentCapacity) {
294       segmentSize <<= 1;
295     }
296 
297     if (evictsBySize()) {
298       // Ensure sum of segment max weights = overall max weights
299       long maxSegmentWeight = maxWeight / segmentCount + 1;
300       long remainder = maxWeight % segmentCount;
301       for (int i = 0; i < this.segments.length; ++i) {
302         if (i == remainder) {
303           maxSegmentWeight--;
304         }
305         this.segments[i] =
306             createSegment(segmentSize, maxSegmentWeight, builder.getStatsCounterSupplier().get());
307       }
308     } else {
309       for (int i = 0; i < this.segments.length; ++i) {
310         this.segments[i] =
311             createSegment(segmentSize, UNSET_INT, builder.getStatsCounterSupplier().get());
312       }
313     }
314   }
315 
316   boolean evictsBySize() {
317     return maxWeight >= 0;
318   }
319 
320   boolean customWeigher() {
321     return weigher != OneWeigher.INSTANCE;
322   }
323 
324   boolean expires() {
325     return expiresAfterWrite() || expiresAfterAccess();
326   }
327 
328   boolean expiresAfterWrite() {
329     return expireAfterWriteNanos > 0;
330   }
331 
332   boolean expiresAfterAccess() {
333     return expireAfterAccessNanos > 0;
334   }
335 
336   boolean refreshes() {
337     return refreshNanos > 0;
338   }
339 
340   boolean usesAccessQueue() {
341     return expiresAfterAccess() || evictsBySize();
342   }
343 
344   boolean usesWriteQueue() {
345     return expiresAfterWrite();
346   }
347 
348   boolean recordsWrite() {
349     return expiresAfterWrite() || refreshes();
350   }
351 
352   boolean recordsAccess() {
353     return expiresAfterAccess();
354   }
355 
356   boolean recordsTime() {
357     return recordsWrite() || recordsAccess();
358   }
359 
360   boolean usesWriteEntries() {
361     return usesWriteQueue() || recordsWrite();
362   }
363 
364   boolean usesAccessEntries() {
365     return usesAccessQueue() || recordsAccess();
366   }
367 
368   boolean usesKeyReferences() {
369     return keyStrength != Strength.STRONG;
370   }
371 
372   boolean usesValueReferences() {
373     return valueStrength != Strength.STRONG;
374   }
375 
376   enum Strength {
377     /*
378      * TODO(kevinb): If we strongly reference the value and aren't loading, we needn't wrap the
379      * value. This could save ~8 bytes per entry.
380      */
381 
382     STRONG {
383       @Override
384       <K, V> ValueReference<K, V> referenceValue(
385           Segment<K, V> segment, ReferenceEntry<K, V> entry, V value, int weight) {
386         return (weight == 1)
387             ? new StrongValueReference<K, V>(value)
388             : new WeightedStrongValueReference<K, V>(value, weight);
389       }
390 
391       @Override
392       Equivalence<Object> defaultEquivalence() {
393         return Equivalence.equals();
394       }
395     },
396     SOFT {
397       @Override
398       <K, V> ValueReference<K, V> referenceValue(
399           Segment<K, V> segment, ReferenceEntry<K, V> entry, V value, int weight) {
400         return (weight == 1)
401             ? new SoftValueReference<K, V>(segment.valueReferenceQueue, value, entry)
402             : new WeightedSoftValueReference<K, V>(
403                 segment.valueReferenceQueue, value, entry, weight);
404       }
405 
406       @Override
407       Equivalence<Object> defaultEquivalence() {
408         return Equivalence.identity();
409       }
410     },
411     WEAK {
412       @Override
413       <K, V> ValueReference<K, V> referenceValue(
414           Segment<K, V> segment, ReferenceEntry<K, V> entry, V value, int weight) {
415         return (weight == 1)
416             ? new WeakValueReference<K, V>(segment.valueReferenceQueue, value, entry)
417             : new WeightedWeakValueReference<K, V>(
418                 segment.valueReferenceQueue, value, entry, weight);
419       }
420 
421       @Override
422       Equivalence<Object> defaultEquivalence() {
423         return Equivalence.identity();
424       }
425     };
426 
427     /**
428      * Creates a reference for the given value according to this value strength.
429      */
430     abstract <K, V> ValueReference<K, V> referenceValue(
431         Segment<K, V> segment, ReferenceEntry<K, V> entry, V value, int weight);
432 
433     /**
434      * Returns the default equivalence strategy used to compare and hash keys or values referenced
435      * at this strength. This strategy will be used unless the user explicitly specifies an
436      * alternate strategy.
437      */
438     abstract Equivalence<Object> defaultEquivalence();
439   }
440 
441   /**
442    * Creates new entries.
443    */
444   enum EntryFactory {
445     STRONG {
446       @Override
447       <K, V> ReferenceEntry<K, V> newEntry(
448           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
449         return new StrongEntry<>(key, hash, next);
450       }
451     },
452     STRONG_ACCESS {
453       @Override
454       <K, V> ReferenceEntry<K, V> newEntry(
455           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
456         return new StrongAccessEntry<>(key, hash, next);
457       }
458 
459       @Override
460       <K, V> ReferenceEntry<K, V> copyEntry(
461           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
462         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
463         copyAccessEntry(original, newEntry);
464         return newEntry;
465       }
466     },
467     STRONG_WRITE {
468       @Override
469       <K, V> ReferenceEntry<K, V> newEntry(
470           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
471         return new StrongWriteEntry<>(key, hash, next);
472       }
473 
474       @Override
475       <K, V> ReferenceEntry<K, V> copyEntry(
476           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
477         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
478         copyWriteEntry(original, newEntry);
479         return newEntry;
480       }
481     },
482     STRONG_ACCESS_WRITE {
483       @Override
484       <K, V> ReferenceEntry<K, V> newEntry(
485           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
486         return new StrongAccessWriteEntry<>(key, hash, next);
487       }
488 
489       @Override
490       <K, V> ReferenceEntry<K, V> copyEntry(
491           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
492         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
493         copyAccessEntry(original, newEntry);
494         copyWriteEntry(original, newEntry);
495         return newEntry;
496       }
497     },
498     WEAK {
499       @Override
500       <K, V> ReferenceEntry<K, V> newEntry(
501           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
502         return new WeakEntry<>(segment.keyReferenceQueue, key, hash, next);
503       }
504     },
505     WEAK_ACCESS {
506       @Override
507       <K, V> ReferenceEntry<K, V> newEntry(
508           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
509         return new WeakAccessEntry<>(segment.keyReferenceQueue, key, hash, next);
510       }
511 
512       @Override
513       <K, V> ReferenceEntry<K, V> copyEntry(
514           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
515         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
516         copyAccessEntry(original, newEntry);
517         return newEntry;
518       }
519     },
520     WEAK_WRITE {
521       @Override
522       <K, V> ReferenceEntry<K, V> newEntry(
523           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
524         return new WeakWriteEntry<>(segment.keyReferenceQueue, key, hash, next);
525       }
526 
527       @Override
528       <K, V> ReferenceEntry<K, V> copyEntry(
529           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
530         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
531         copyWriteEntry(original, newEntry);
532         return newEntry;
533       }
534     },
535     WEAK_ACCESS_WRITE {
536       @Override
537       <K, V> ReferenceEntry<K, V> newEntry(
538           Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
539         return new WeakAccessWriteEntry<>(segment.keyReferenceQueue, key, hash, next);
540       }
541 
542       @Override
543       <K, V> ReferenceEntry<K, V> copyEntry(
544           Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
545         ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
546         copyAccessEntry(original, newEntry);
547         copyWriteEntry(original, newEntry);
548         return newEntry;
549       }
550     };
551 
552     // Masks used to compute indices in the following table.
553 
554     static final int ACCESS_MASK = 1;
555     static final int WRITE_MASK = 2;
556     static final int WEAK_MASK = 4;
557 
558     /**
559      * Look-up table for factories.
560      */
561     static final EntryFactory[] factories = {
562       STRONG,
563       STRONG_ACCESS,
564       STRONG_WRITE,
565       STRONG_ACCESS_WRITE,
566       WEAK,
567       WEAK_ACCESS,
568       WEAK_WRITE,
569       WEAK_ACCESS_WRITE,
570     };
571 
572     static EntryFactory getFactory(
573         Strength keyStrength, boolean usesAccessQueue, boolean usesWriteQueue) {
574       int flags =
575           ((keyStrength == Strength.WEAK) ? WEAK_MASK : 0)
576               | (usesAccessQueue ? ACCESS_MASK : 0)
577               | (usesWriteQueue ? WRITE_MASK : 0);
578       return factories[flags];
579     }
580 
581     /**
582      * Creates a new entry.
583      *
584      * @param segment to create the entry for
585      * @param key of the entry
586      * @param hash of the key
587      * @param next entry in the same bucket
588      */
589     abstract <K, V> ReferenceEntry<K, V> newEntry(
590         Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next);
591 
592     /**
593      * Copies an entry, assigning it a new {@code next} entry.
594      *
595      * @param original the entry to copy
596      * @param newNext entry in the same bucket
597      */
598     // Guarded By Segment.this
599     <K, V> ReferenceEntry<K, V> copyEntry(
600         Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
601       return newEntry(segment, original.getKey(), original.getHash(), newNext);
602     }
603 
604     // Guarded By Segment.this
605     <K, V> void copyAccessEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
606       // TODO(fry): when we link values instead of entries this method can go
607       // away, as can connectAccessOrder, nullifyAccessOrder.
608       newEntry.setAccessTime(original.getAccessTime());
609 
610       connectAccessOrder(original.getPreviousInAccessQueue(), newEntry);
611       connectAccessOrder(newEntry, original.getNextInAccessQueue());
612 
613       nullifyAccessOrder(original);
614     }
615 
616     // Guarded By Segment.this
617     <K, V> void copyWriteEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
618       // TODO(fry): when we link values instead of entries this method can go
619       // away, as can connectWriteOrder, nullifyWriteOrder.
620       newEntry.setWriteTime(original.getWriteTime());
621 
622       connectWriteOrder(original.getPreviousInWriteQueue(), newEntry);
623       connectWriteOrder(newEntry, original.getNextInWriteQueue());
624 
625       nullifyWriteOrder(original);
626     }
627   }
628 
629   /**
630    * A reference to a value.
631    */
632   interface ValueReference<K, V> {
633     /**
634      * Returns the value. Does not block or throw exceptions.
635      */
636     @Nullable
637     V get();
638 
639     /**
640      * Waits for a value that may still be loading. Unlike get(), this method can block (in the case
641      * of FutureValueReference).
642      *
643      * @throws ExecutionException if the loading thread throws an exception
644      * @throws ExecutionError if the loading thread throws an error
645      */
646     V waitForValue() throws ExecutionException;
647 
648     /**
649      * Returns the weight of this entry. This is assumed to be static between calls to setValue.
650      */
651     int getWeight();
652 
653     /**
654      * Returns the entry associated with this value reference, or {@code null} if this value
655      * reference is independent of any entry.
656      */
657     @Nullable
658     ReferenceEntry<K, V> getEntry();
659 
660     /**
661      * Creates a copy of this reference for the given entry.
662      *
663      * <p>{@code value} may be null only for a loading reference.
664      */
665     ValueReference<K, V> copyFor(
666         ReferenceQueue<V> queue, @Nullable V value, ReferenceEntry<K, V> entry);
667 
668     /**
669      * Notify pending loads that a new value was set. This is only relevant to loading value
670      * references.
671      */
672     void notifyNewValue(@Nullable V newValue);
673 
674     /**
675      * Returns true if a new value is currently loading, regardless of whether or not there is an
676      * existing value. It is assumed that the return value of this method is constant for any given
677      * ValueReference instance.
678      */
679     boolean isLoading();
680 
681     /**
682      * Returns true if this reference contains an active value, meaning one that is still considered
683      * present in the cache. Active values consist of live values, which are returned by cache
684      * lookups, and dead values, which have been evicted but awaiting removal. Non-active values
685      * consist strictly of loading values, though during refresh a value may be both active and
686      * loading.
687      */
688     boolean isActive();
689   }
690 
691   /**
692    * Placeholder. Indicates that the value hasn't been set yet.
693    */
694   static final ValueReference<Object, Object> UNSET =
695       new ValueReference<Object, Object>() {
696         @Override
697         public Object get() {
698           return null;
699         }
700 
701         @Override
702         public int getWeight() {
703           return 0;
704         }
705 
706         @Override
707         public ReferenceEntry<Object, Object> getEntry() {
708           return null;
709         }
710 
711         @Override
712         public ValueReference<Object, Object> copyFor(
713             ReferenceQueue<Object> queue,
714             @Nullable Object value,
715             ReferenceEntry<Object, Object> entry) {
716           return this;
717         }
718 
719         @Override
720         public boolean isLoading() {
721           return false;
722         }
723 
724         @Override
725         public boolean isActive() {
726           return false;
727         }
728 
729         @Override
730         public Object waitForValue() {
731           return null;
732         }
733 
734         @Override
735         public void notifyNewValue(Object newValue) {}
736       };
737 
738   /**
739    * Singleton placeholder that indicates a value is being loaded.
740    */
741   @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
742   static <K, V> ValueReference<K, V> unset() {
743     return (ValueReference<K, V>) UNSET;
744   }
745 
746   /**
747    * An entry in a reference map.
748    *
749    * <p>Entries in the map can be in the following states:
750    *
751    * <p>Valid:
752    *
753    * <ul>
754    *   <li>Live: valid key/value are set
755    *   <li>Loading: loading is pending
756    * </ul>
757    *
758    * <p>Invalid:
759    *
760    * <ul>
761    *   <li>Expired: time expired (key/value may still be set)
762    *   <li>Collected: key/value was partially collected, but not yet cleaned up
763    *   <li>Unset: marked as unset, awaiting cleanup or reuse
764    * </ul>
765    */
766   interface ReferenceEntry<K, V> {
767     /**
768      * Returns the value reference from this entry.
769      */
770     ValueReference<K, V> getValueReference();
771 
772     /**
773      * Sets the value reference for this entry.
774      */
775     void setValueReference(ValueReference<K, V> valueReference);
776 
777     /**
778      * Returns the next entry in the chain.
779      */
780     @Nullable
781     ReferenceEntry<K, V> getNext();
782 
783     /**
784      * Returns the entry's hash.
785      */
786     int getHash();
787 
788     /**
789      * Returns the key for this entry.
790      */
791     @Nullable
792     K getKey();
793 
794     /*
795      * Used by entries that use access order. Access entries are maintained in a doubly-linked list.
796      * New entries are added at the tail of the list at write time; stale entries are expired from
797      * the head of the list.
798      */
799 
800     /**
801      * Returns the time that this entry was last accessed, in ns.
802      */
803     long getAccessTime();
804 
805     /**
806      * Sets the entry access time in ns.
807      */
808     void setAccessTime(long time);
809 
810     /**
811      * Returns the next entry in the access queue.
812      */
813     ReferenceEntry<K, V> getNextInAccessQueue();
814 
815     /**
816      * Sets the next entry in the access queue.
817      */
818     void setNextInAccessQueue(ReferenceEntry<K, V> next);
819 
820     /**
821      * Returns the previous entry in the access queue.
822      */
823     ReferenceEntry<K, V> getPreviousInAccessQueue();
824 
825     /**
826      * Sets the previous entry in the access queue.
827      */
828     void setPreviousInAccessQueue(ReferenceEntry<K, V> previous);
829 
830     /*
831      * Implemented by entries that use write order. Write entries are maintained in a doubly-linked
832      * list. New entries are added at the tail of the list at write time and stale entries are
833      * expired from the head of the list.
834      */
835 
836     /**
837      * Returns the time that this entry was last written, in ns.
838      */
839     long getWriteTime();
840 
841     /**
842      * Sets the entry write time in ns.
843      */
844     void setWriteTime(long time);
845 
846     /**
847      * Returns the next entry in the write queue.
848      */
849     ReferenceEntry<K, V> getNextInWriteQueue();
850 
851     /**
852      * Sets the next entry in the write queue.
853      */
854     void setNextInWriteQueue(ReferenceEntry<K, V> next);
855 
856     /**
857      * Returns the previous entry in the write queue.
858      */
859     ReferenceEntry<K, V> getPreviousInWriteQueue();
860 
861     /**
862      * Sets the previous entry in the write queue.
863      */
864     void setPreviousInWriteQueue(ReferenceEntry<K, V> previous);
865   }
866 
867   private enum NullEntry implements ReferenceEntry<Object, Object> {
868     INSTANCE;
869 
870     @Override
871     public ValueReference<Object, Object> getValueReference() {
872       return null;
873     }
874 
875     @Override
876     public void setValueReference(ValueReference<Object, Object> valueReference) {}
877 
878     @Override
879     public ReferenceEntry<Object, Object> getNext() {
880       return null;
881     }
882 
883     @Override
884     public int getHash() {
885       return 0;
886     }
887 
888     @Override
889     public Object getKey() {
890       return null;
891     }
892 
893     @Override
894     public long getAccessTime() {
895       return 0;
896     }
897 
898     @Override
899     public void setAccessTime(long time) {}
900 
901     @Override
902     public ReferenceEntry<Object, Object> getNextInAccessQueue() {
903       return this;
904     }
905 
906     @Override
907     public void setNextInAccessQueue(ReferenceEntry<Object, Object> next) {}
908 
909     @Override
910     public ReferenceEntry<Object, Object> getPreviousInAccessQueue() {
911       return this;
912     }
913 
914     @Override
915     public void setPreviousInAccessQueue(ReferenceEntry<Object, Object> previous) {}
916 
917     @Override
918     public long getWriteTime() {
919       return 0;
920     }
921 
922     @Override
923     public void setWriteTime(long time) {}
924 
925     @Override
926     public ReferenceEntry<Object, Object> getNextInWriteQueue() {
927       return this;
928     }
929 
930     @Override
931     public void setNextInWriteQueue(ReferenceEntry<Object, Object> next) {}
932 
933     @Override
934     public ReferenceEntry<Object, Object> getPreviousInWriteQueue() {
935       return this;
936     }
937 
938     @Override
939     public void setPreviousInWriteQueue(ReferenceEntry<Object, Object> previous) {}
940   }
941 
942   abstract static class AbstractReferenceEntry<K, V> implements ReferenceEntry<K, V> {
943     @Override
944     public ValueReference<K, V> getValueReference() {
945       throw new UnsupportedOperationException();
946     }
947 
948     @Override
949     public void setValueReference(ValueReference<K, V> valueReference) {
950       throw new UnsupportedOperationException();
951     }
952 
953     @Override
954     public ReferenceEntry<K, V> getNext() {
955       throw new UnsupportedOperationException();
956     }
957 
958     @Override
959     public int getHash() {
960       throw new UnsupportedOperationException();
961     }
962 
963     @Override
964     public K getKey() {
965       throw new UnsupportedOperationException();
966     }
967 
968     @Override
969     public long getAccessTime() {
970       throw new UnsupportedOperationException();
971     }
972 
973     @Override
974     public void setAccessTime(long time) {
975       throw new UnsupportedOperationException();
976     }
977 
978     @Override
979     public ReferenceEntry<K, V> getNextInAccessQueue() {
980       throw new UnsupportedOperationException();
981     }
982 
983     @Override
984     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
985       throw new UnsupportedOperationException();
986     }
987 
988     @Override
989     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
990       throw new UnsupportedOperationException();
991     }
992 
993     @Override
994     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
995       throw new UnsupportedOperationException();
996     }
997 
998     @Override
999     public long getWriteTime() {
1000       throw new UnsupportedOperationException();
1001     }
1002 
1003     @Override
1004     public void setWriteTime(long time) {
1005       throw new UnsupportedOperationException();
1006     }
1007 
1008     @Override
1009     public ReferenceEntry<K, V> getNextInWriteQueue() {
1010       throw new UnsupportedOperationException();
1011     }
1012 
1013     @Override
1014     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1015       throw new UnsupportedOperationException();
1016     }
1017 
1018     @Override
1019     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1020       throw new UnsupportedOperationException();
1021     }
1022 
1023     @Override
1024     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1025       throw new UnsupportedOperationException();
1026     }
1027   }
1028 
1029   @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
1030   static <K, V> ReferenceEntry<K, V> nullEntry() {
1031     return (ReferenceEntry<K, V>) NullEntry.INSTANCE;
1032   }
1033 
1034   static final Queue<?> DISCARDING_QUEUE =
1035       new AbstractQueue<Object>() {
1036         @Override
1037         public boolean offer(Object o) {
1038           return true;
1039         }
1040 
1041         @Override
1042         public Object peek() {
1043           return null;
1044         }
1045 
1046         @Override
1047         public Object poll() {
1048           return null;
1049         }
1050 
1051         @Override
1052         public int size() {
1053           return 0;
1054         }
1055 
1056         @Override
1057         public Iterator<Object> iterator() {
1058           return ImmutableSet.of().iterator();
1059         }
1060       };
1061 
1062   /**
1063    * Queue that discards all elements.
1064    */
1065   @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
1066   static <E> Queue<E> discardingQueue() {
1067     return (Queue) DISCARDING_QUEUE;
1068   }
1069 
1070   /*
1071    * Note: All of this duplicate code sucks, but it saves a lot of memory. If only Java had mixins!
1072    * To maintain this code, make a change for the strong reference type. Then, cut and paste, and
1073    * replace "Strong" with "Soft" or "Weak" within the pasted text. The primary difference is that
1074    * strong entries store the key reference directly while soft and weak entries delegate to their
1075    * respective superclasses.
1076    */
1077 
1078   /**
1079    * Used for strongly-referenced keys.
1080    */
1081   static class StrongEntry<K, V> extends AbstractReferenceEntry<K, V> {
1082     final K key;
1083 
1084     StrongEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1085       this.key = key;
1086       this.hash = hash;
1087       this.next = next;
1088     }
1089 
1090     @Override
1091     public K getKey() {
1092       return this.key;
1093     }
1094 
1095     // The code below is exactly the same for each entry type.
1096 
1097     final int hash;
1098     final ReferenceEntry<K, V> next;
1099     volatile ValueReference<K, V> valueReference = unset();
1100 
1101     @Override
1102     public ValueReference<K, V> getValueReference() {
1103       return valueReference;
1104     }
1105 
1106     @Override
1107     public void setValueReference(ValueReference<K, V> valueReference) {
1108       this.valueReference = valueReference;
1109     }
1110 
1111     @Override
1112     public int getHash() {
1113       return hash;
1114     }
1115 
1116     @Override
1117     public ReferenceEntry<K, V> getNext() {
1118       return next;
1119     }
1120   }
1121 
1122   static final class StrongAccessEntry<K, V> extends StrongEntry<K, V> {
1123     StrongAccessEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1124       super(key, hash, next);
1125     }
1126 
1127     // The code below is exactly the same for each access entry type.
1128 
1129     volatile long accessTime = Long.MAX_VALUE;
1130 
1131     @Override
1132     public long getAccessTime() {
1133       return accessTime;
1134     }
1135 
1136     @Override
1137     public void setAccessTime(long time) {
1138       this.accessTime = time;
1139     }
1140 
1141     // Guarded By Segment.this
1142     ReferenceEntry<K, V> nextAccess = nullEntry();
1143 
1144     @Override
1145     public ReferenceEntry<K, V> getNextInAccessQueue() {
1146       return nextAccess;
1147     }
1148 
1149     @Override
1150     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
1151       this.nextAccess = next;
1152     }
1153 
1154     // Guarded By Segment.this
1155     ReferenceEntry<K, V> previousAccess = nullEntry();
1156 
1157     @Override
1158     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
1159       return previousAccess;
1160     }
1161 
1162     @Override
1163     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
1164       this.previousAccess = previous;
1165     }
1166   }
1167 
1168   static final class StrongWriteEntry<K, V> extends StrongEntry<K, V> {
1169     StrongWriteEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1170       super(key, hash, next);
1171     }
1172 
1173     // The code below is exactly the same for each write entry type.
1174 
1175     volatile long writeTime = Long.MAX_VALUE;
1176 
1177     @Override
1178     public long getWriteTime() {
1179       return writeTime;
1180     }
1181 
1182     @Override
1183     public void setWriteTime(long time) {
1184       this.writeTime = time;
1185     }
1186 
1187     // Guarded By Segment.this
1188     ReferenceEntry<K, V> nextWrite = nullEntry();
1189 
1190     @Override
1191     public ReferenceEntry<K, V> getNextInWriteQueue() {
1192       return nextWrite;
1193     }
1194 
1195     @Override
1196     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1197       this.nextWrite = next;
1198     }
1199 
1200     // Guarded By Segment.this
1201     ReferenceEntry<K, V> previousWrite = nullEntry();
1202 
1203     @Override
1204     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1205       return previousWrite;
1206     }
1207 
1208     @Override
1209     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1210       this.previousWrite = previous;
1211     }
1212   }
1213 
1214   static final class StrongAccessWriteEntry<K, V> extends StrongEntry<K, V> {
1215     StrongAccessWriteEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1216       super(key, hash, next);
1217     }
1218 
1219     // The code below is exactly the same for each access entry type.
1220 
1221     volatile long accessTime = Long.MAX_VALUE;
1222 
1223     @Override
1224     public long getAccessTime() {
1225       return accessTime;
1226     }
1227 
1228     @Override
1229     public void setAccessTime(long time) {
1230       this.accessTime = time;
1231     }
1232 
1233     // Guarded By Segment.this
1234     ReferenceEntry<K, V> nextAccess = nullEntry();
1235 
1236     @Override
1237     public ReferenceEntry<K, V> getNextInAccessQueue() {
1238       return nextAccess;
1239     }
1240 
1241     @Override
1242     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
1243       this.nextAccess = next;
1244     }
1245 
1246     // Guarded By Segment.this
1247     ReferenceEntry<K, V> previousAccess = nullEntry();
1248 
1249     @Override
1250     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
1251       return previousAccess;
1252     }
1253 
1254     @Override
1255     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
1256       this.previousAccess = previous;
1257     }
1258 
1259     // The code below is exactly the same for each write entry type.
1260 
1261     volatile long writeTime = Long.MAX_VALUE;
1262 
1263     @Override
1264     public long getWriteTime() {
1265       return writeTime;
1266     }
1267 
1268     @Override
1269     public void setWriteTime(long time) {
1270       this.writeTime = time;
1271     }
1272 
1273     // Guarded By Segment.this
1274     ReferenceEntry<K, V> nextWrite = nullEntry();
1275 
1276     @Override
1277     public ReferenceEntry<K, V> getNextInWriteQueue() {
1278       return nextWrite;
1279     }
1280 
1281     @Override
1282     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1283       this.nextWrite = next;
1284     }
1285 
1286     // Guarded By Segment.this
1287     ReferenceEntry<K, V> previousWrite = nullEntry();
1288 
1289     @Override
1290     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1291       return previousWrite;
1292     }
1293 
1294     @Override
1295     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1296       this.previousWrite = previous;
1297     }
1298   }
1299 
1300   /**
1301    * Used for weakly-referenced keys.
1302    */
1303   static class WeakEntry<K, V> extends WeakReference<K> implements ReferenceEntry<K, V> {
1304     WeakEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1305       super(key, queue);
1306       this.hash = hash;
1307       this.next = next;
1308     }
1309 
1310     @Override
1311     public K getKey() {
1312       return get();
1313     }
1314 
1315     /*
1316      * It'd be nice to get these for free from AbstractReferenceEntry, but we're already extending
1317      * WeakReference<K>.
1318      */
1319 
1320     // null access
1321 
1322     @Override
1323     public long getAccessTime() {
1324       throw new UnsupportedOperationException();
1325     }
1326 
1327     @Override
1328     public void setAccessTime(long time) {
1329       throw new UnsupportedOperationException();
1330     }
1331 
1332     @Override
1333     public ReferenceEntry<K, V> getNextInAccessQueue() {
1334       throw new UnsupportedOperationException();
1335     }
1336 
1337     @Override
1338     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
1339       throw new UnsupportedOperationException();
1340     }
1341 
1342     @Override
1343     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
1344       throw new UnsupportedOperationException();
1345     }
1346 
1347     @Override
1348     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
1349       throw new UnsupportedOperationException();
1350     }
1351 
1352     // null write
1353 
1354     @Override
1355     public long getWriteTime() {
1356       throw new UnsupportedOperationException();
1357     }
1358 
1359     @Override
1360     public void setWriteTime(long time) {
1361       throw new UnsupportedOperationException();
1362     }
1363 
1364     @Override
1365     public ReferenceEntry<K, V> getNextInWriteQueue() {
1366       throw new UnsupportedOperationException();
1367     }
1368 
1369     @Override
1370     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1371       throw new UnsupportedOperationException();
1372     }
1373 
1374     @Override
1375     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1376       throw new UnsupportedOperationException();
1377     }
1378 
1379     @Override
1380     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1381       throw new UnsupportedOperationException();
1382     }
1383 
1384     // The code below is exactly the same for each entry type.
1385 
1386     final int hash;
1387     final ReferenceEntry<K, V> next;
1388     volatile ValueReference<K, V> valueReference = unset();
1389 
1390     @Override
1391     public ValueReference<K, V> getValueReference() {
1392       return valueReference;
1393     }
1394 
1395     @Override
1396     public void setValueReference(ValueReference<K, V> valueReference) {
1397       this.valueReference = valueReference;
1398     }
1399 
1400     @Override
1401     public int getHash() {
1402       return hash;
1403     }
1404 
1405     @Override
1406     public ReferenceEntry<K, V> getNext() {
1407       return next;
1408     }
1409   }
1410 
1411   static final class WeakAccessEntry<K, V> extends WeakEntry<K, V> {
1412     WeakAccessEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1413       super(queue, key, hash, next);
1414     }
1415 
1416     // The code below is exactly the same for each access entry type.
1417 
1418     volatile long accessTime = Long.MAX_VALUE;
1419 
1420     @Override
1421     public long getAccessTime() {
1422       return accessTime;
1423     }
1424 
1425     @Override
1426     public void setAccessTime(long time) {
1427       this.accessTime = time;
1428     }
1429 
1430     // Guarded By Segment.this
1431     ReferenceEntry<K, V> nextAccess = nullEntry();
1432 
1433     @Override
1434     public ReferenceEntry<K, V> getNextInAccessQueue() {
1435       return nextAccess;
1436     }
1437 
1438     @Override
1439     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
1440       this.nextAccess = next;
1441     }
1442 
1443     // Guarded By Segment.this
1444     ReferenceEntry<K, V> previousAccess = nullEntry();
1445 
1446     @Override
1447     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
1448       return previousAccess;
1449     }
1450 
1451     @Override
1452     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
1453       this.previousAccess = previous;
1454     }
1455   }
1456 
1457   static final class WeakWriteEntry<K, V> extends WeakEntry<K, V> {
1458     WeakWriteEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1459       super(queue, key, hash, next);
1460     }
1461 
1462     // The code below is exactly the same for each write entry type.
1463 
1464     volatile long writeTime = Long.MAX_VALUE;
1465 
1466     @Override
1467     public long getWriteTime() {
1468       return writeTime;
1469     }
1470 
1471     @Override
1472     public void setWriteTime(long time) {
1473       this.writeTime = time;
1474     }
1475 
1476     // Guarded By Segment.this
1477     ReferenceEntry<K, V> nextWrite = nullEntry();
1478 
1479     @Override
1480     public ReferenceEntry<K, V> getNextInWriteQueue() {
1481       return nextWrite;
1482     }
1483 
1484     @Override
1485     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1486       this.nextWrite = next;
1487     }
1488 
1489     // Guarded By Segment.this
1490     ReferenceEntry<K, V> previousWrite = nullEntry();
1491 
1492     @Override
1493     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1494       return previousWrite;
1495     }
1496 
1497     @Override
1498     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1499       this.previousWrite = previous;
1500     }
1501   }
1502 
1503   static final class WeakAccessWriteEntry<K, V> extends WeakEntry<K, V> {
1504     WeakAccessWriteEntry(
1505         ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1506       super(queue, key, hash, next);
1507     }
1508 
1509     // The code below is exactly the same for each access entry type.
1510 
1511     volatile long accessTime = Long.MAX_VALUE;
1512 
1513     @Override
1514     public long getAccessTime() {
1515       return accessTime;
1516     }
1517 
1518     @Override
1519     public void setAccessTime(long time) {
1520       this.accessTime = time;
1521     }
1522 
1523     // Guarded By Segment.this
1524     ReferenceEntry<K, V> nextAccess = nullEntry();
1525 
1526     @Override
1527     public ReferenceEntry<K, V> getNextInAccessQueue() {
1528       return nextAccess;
1529     }
1530 
1531     @Override
1532     public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
1533       this.nextAccess = next;
1534     }
1535 
1536     // Guarded By Segment.this
1537     ReferenceEntry<K, V> previousAccess = nullEntry();
1538 
1539     @Override
1540     public ReferenceEntry<K, V> getPreviousInAccessQueue() {
1541       return previousAccess;
1542     }
1543 
1544     @Override
1545     public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
1546       this.previousAccess = previous;
1547     }
1548 
1549     // The code below is exactly the same for each write entry type.
1550 
1551     volatile long writeTime = Long.MAX_VALUE;
1552 
1553     @Override
1554     public long getWriteTime() {
1555       return writeTime;
1556     }
1557 
1558     @Override
1559     public void setWriteTime(long time) {
1560       this.writeTime = time;
1561     }
1562 
1563     // Guarded By Segment.this
1564     ReferenceEntry<K, V> nextWrite = nullEntry();
1565 
1566     @Override
1567     public ReferenceEntry<K, V> getNextInWriteQueue() {
1568       return nextWrite;
1569     }
1570 
1571     @Override
1572     public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
1573       this.nextWrite = next;
1574     }
1575 
1576     // Guarded By Segment.this
1577     ReferenceEntry<K, V> previousWrite = nullEntry();
1578 
1579     @Override
1580     public ReferenceEntry<K, V> getPreviousInWriteQueue() {
1581       return previousWrite;
1582     }
1583 
1584     @Override
1585     public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
1586       this.previousWrite = previous;
1587     }
1588   }
1589 
1590   /**
1591    * References a weak value.
1592    */
1593   static class WeakValueReference<K, V> extends WeakReference<V> implements ValueReference<K, V> {
1594     final ReferenceEntry<K, V> entry;
1595 
1596     WeakValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
1597       super(referent, queue);
1598       this.entry = entry;
1599     }
1600 
1601     @Override
1602     public int getWeight() {
1603       return 1;
1604     }
1605 
1606     @Override
1607     public ReferenceEntry<K, V> getEntry() {
1608       return entry;
1609     }
1610 
1611     @Override
1612     public void notifyNewValue(V newValue) {}
1613 
1614     @Override
1615     public ValueReference<K, V> copyFor(
1616         ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1617       return new WeakValueReference<>(queue, value, entry);
1618     }
1619 
1620     @Override
1621     public boolean isLoading() {
1622       return false;
1623     }
1624 
1625     @Override
1626     public boolean isActive() {
1627       return true;
1628     }
1629 
1630     @Override
1631     public V waitForValue() {
1632       return get();
1633     }
1634   }
1635 
1636   /**
1637    * References a soft value.
1638    */
1639   static class SoftValueReference<K, V> extends SoftReference<V> implements ValueReference<K, V> {
1640     final ReferenceEntry<K, V> entry;
1641 
1642     SoftValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
1643       super(referent, queue);
1644       this.entry = entry;
1645     }
1646 
1647     @Override
1648     public int getWeight() {
1649       return 1;
1650     }
1651 
1652     @Override
1653     public ReferenceEntry<K, V> getEntry() {
1654       return entry;
1655     }
1656 
1657     @Override
1658     public void notifyNewValue(V newValue) {}
1659 
1660     @Override
1661     public ValueReference<K, V> copyFor(
1662         ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1663       return new SoftValueReference<>(queue, value, entry);
1664     }
1665 
1666     @Override
1667     public boolean isLoading() {
1668       return false;
1669     }
1670 
1671     @Override
1672     public boolean isActive() {
1673       return true;
1674     }
1675 
1676     @Override
1677     public V waitForValue() {
1678       return get();
1679     }
1680   }
1681 
1682   /**
1683    * References a strong value.
1684    */
1685   static class StrongValueReference<K, V> implements ValueReference<K, V> {
1686     final V referent;
1687 
1688     StrongValueReference(V referent) {
1689       this.referent = referent;
1690     }
1691 
1692     @Override
1693     public V get() {
1694       return referent;
1695     }
1696 
1697     @Override
1698     public int getWeight() {
1699       return 1;
1700     }
1701 
1702     @Override
1703     public ReferenceEntry<K, V> getEntry() {
1704       return null;
1705     }
1706 
1707     @Override
1708     public ValueReference<K, V> copyFor(
1709         ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1710       return this;
1711     }
1712 
1713     @Override
1714     public boolean isLoading() {
1715       return false;
1716     }
1717 
1718     @Override
1719     public boolean isActive() {
1720       return true;
1721     }
1722 
1723     @Override
1724     public V waitForValue() {
1725       return get();
1726     }
1727 
1728     @Override
1729     public void notifyNewValue(V newValue) {}
1730   }
1731 
1732   /**
1733    * References a weak value.
1734    */
1735   static final class WeightedWeakValueReference<K, V> extends WeakValueReference<K, V> {
1736     final int weight;
1737 
1738     WeightedWeakValueReference(
1739         ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry, int weight) {
1740       super(queue, referent, entry);
1741       this.weight = weight;
1742     }
1743 
1744     @Override
1745     public int getWeight() {
1746       return weight;
1747     }
1748 
1749     @Override
1750     public ValueReference<K, V> copyFor(
1751         ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1752       return new WeightedWeakValueReference<>(queue, value, entry, weight);
1753     }
1754   }
1755 
1756   /**
1757    * References a soft value.
1758    */
1759   static final class WeightedSoftValueReference<K, V> extends SoftValueReference<K, V> {
1760     final int weight;
1761 
1762     WeightedSoftValueReference(
1763         ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry, int weight) {
1764       super(queue, referent, entry);
1765       this.weight = weight;
1766     }
1767 
1768     @Override
1769     public int getWeight() {
1770       return weight;
1771     }
1772 
1773     @Override
1774     public ValueReference<K, V> copyFor(
1775         ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1776       return new WeightedSoftValueReference<>(queue, value, entry, weight);
1777     }
1778   }
1779 
1780   /**
1781    * References a strong value.
1782    */
1783   static final class WeightedStrongValueReference<K, V> extends StrongValueReference<K, V> {
1784     final int weight;
1785 
1786     WeightedStrongValueReference(V referent, int weight) {
1787       super(referent);
1788       this.weight = weight;
1789     }
1790 
1791     @Override
1792     public int getWeight() {
1793       return weight;
1794     }
1795   }
1796 
1797   /**
1798    * Applies a supplemental hash function to a given hash code, which defends against poor quality
1799    * hash functions. This is critical when the concurrent hash map uses power-of-two length hash
1800    * tables, that otherwise encounter collisions for hash codes that do not differ in lower or upper
1801    * bits.
1802    *
1803    * @param h hash code
1804    */
1805   static int rehash(int h) {
1806     // Spread bits to regularize both segment and index locations,
1807     // using variant of single-word Wang/Jenkins hash.
1808     // TODO(kevinb): use Hashing/move this to Hashing?
1809     h += (h << 15) ^ 0xffffcd7d;
1810     h ^= (h >>> 10);
1811     h += (h << 3);
1812     h ^= (h >>> 6);
1813     h += (h << 2) + (h << 14);
1814     return h ^ (h >>> 16);
1815   }
1816 
1817   /**
1818    * This method is a convenience for testing. Code should call {@link Segment#newEntry} directly.
1819    */
1820   @VisibleForTesting
1821   ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
1822     Segment<K, V> segment = segmentFor(hash);
1823     segment.lock();
1824     try {
1825       return segment.newEntry(key, hash, next);
1826     } finally {
1827       segment.unlock();
1828     }
1829   }
1830 
1831   /**
1832    * This method is a convenience for testing. Code should call {@link Segment#copyEntry} directly.
1833    */
1834   // Guarded By Segment.this
1835   @VisibleForTesting
1836   ReferenceEntry<K, V> copyEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
1837     int hash = original.getHash();
1838     return segmentFor(hash).copyEntry(original, newNext);
1839   }
1840 
1841   /**
1842    * This method is a convenience for testing. Code should call {@link Segment#setValue} instead.
1843    */
1844   // Guarded By Segment.this
1845   @VisibleForTesting
1846   ValueReference<K, V> newValueReference(ReferenceEntry<K, V> entry, V value, int weight) {
1847     int hash = entry.getHash();
1848     return valueStrength.referenceValue(segmentFor(hash), entry, checkNotNull(value), weight);
1849   }
1850 
1851   int hash(@Nullable Object key) {
1852     int h = keyEquivalence.hash(key);
1853     return rehash(h);
1854   }
1855 
1856   void reclaimValue(ValueReference<K, V> valueReference) {
1857     ReferenceEntry<K, V> entry = valueReference.getEntry();
1858     int hash = entry.getHash();
1859     segmentFor(hash).reclaimValue(entry.getKey(), hash, valueReference);
1860   }
1861 
1862   void reclaimKey(ReferenceEntry<K, V> entry) {
1863     int hash = entry.getHash();
1864     segmentFor(hash).reclaimKey(entry, hash);
1865   }
1866 
1867   /**
1868    * This method is a convenience for testing. Code should call {@link Segment#getLiveValue}
1869    * instead.
1870    */
1871   @VisibleForTesting
1872   boolean isLive(ReferenceEntry<K, V> entry, long now) {
1873     return segmentFor(entry.getHash()).getLiveValue(entry, now) != null;
1874   }
1875 
1876   /**
1877    * Returns the segment that should be used for a key with the given hash.
1878    *
1879    * @param hash the hash code for the key
1880    * @return the segment
1881    */
1882   Segment<K, V> segmentFor(int hash) {
1883     // TODO(fry): Lazily create segments?
1884     return segments[(hash >>> segmentShift) & segmentMask];
1885   }
1886 
1887   Segment<K, V> createSegment(
1888       int initialCapacity, long maxSegmentWeight, StatsCounter statsCounter) {
1889     return new Segment<>(this, initialCapacity, maxSegmentWeight, statsCounter);
1890   }
1891 
1892   /**
1893    * Gets the value from an entry. Returns null if the entry is invalid, partially-collected,
1894    * loading, or expired. Unlike {@link Segment#getLiveValue} this method does not attempt to
1895    * cleanup stale entries. As such it should only be called outside of a segment context, such as
1896    * during iteration.
1897    */
1898   @Nullable
1899   V getLiveValue(ReferenceEntry<K, V> entry, long now) {
1900     if (entry.getKey() == null) {
1901       return null;
1902     }
1903     V value = entry.getValueReference().get();
1904     if (value == null) {
1905       return null;
1906     }
1907 
1908     if (isExpired(entry, now)) {
1909       return null;
1910     }
1911     return value;
1912   }
1913 
1914   // expiration
1915 
1916   /**
1917    * Returns true if the entry has expired.
1918    */
1919   boolean isExpired(ReferenceEntry<K, V> entry, long now) {
1920     checkNotNull(entry);
1921     if (expiresAfterAccess() && (now - entry.getAccessTime() >= expireAfterAccessNanos)) {
1922       return true;
1923     }
1924     if (expiresAfterWrite() && (now - entry.getWriteTime() >= expireAfterWriteNanos)) {
1925       return true;
1926     }
1927     return false;
1928   }
1929 
1930   // queues
1931 
1932   // Guarded By Segment.this
1933   static <K, V> void connectAccessOrder(ReferenceEntry<K, V> previous, ReferenceEntry<K, V> next) {
1934     previous.setNextInAccessQueue(next);
1935     next.setPreviousInAccessQueue(previous);
1936   }
1937 
1938   // Guarded By Segment.this
1939   static <K, V> void nullifyAccessOrder(ReferenceEntry<K, V> nulled) {
1940     ReferenceEntry<K, V> nullEntry = nullEntry();
1941     nulled.setNextInAccessQueue(nullEntry);
1942     nulled.setPreviousInAccessQueue(nullEntry);
1943   }
1944 
1945   // Guarded By Segment.this
1946   static <K, V> void connectWriteOrder(ReferenceEntry<K, V> previous, ReferenceEntry<K, V> next) {
1947     previous.setNextInWriteQueue(next);
1948     next.setPreviousInWriteQueue(previous);
1949   }
1950 
1951   // Guarded By Segment.this
1952   static <K, V> void nullifyWriteOrder(ReferenceEntry<K, V> nulled) {
1953     ReferenceEntry<K, V> nullEntry = nullEntry();
1954     nulled.setNextInWriteQueue(nullEntry);
1955     nulled.setPreviousInWriteQueue(nullEntry);
1956   }
1957 
1958   /**
1959    * Notifies listeners that an entry has been automatically removed due to expiration, eviction, or
1960    * eligibility for garbage collection. This should be called every time expireEntries or
1961    * evictEntry is called (once the lock is released).
1962    */
1963   void processPendingNotifications() {
1964     RemovalNotification<K, V> notification;
1965     while ((notification = removalNotificationQueue.poll()) != null) {
1966       try {
1967         removalListener.onRemoval(notification);
1968       } catch (Throwable e) {
1969         logger.log(Level.WARNING, "Exception thrown by removal listener", e);
1970       }
1971     }
1972   }
1973 
1974   @SuppressWarnings("unchecked")
1975   final Segment<K, V>[] newSegmentArray(int ssize) {
1976     return new Segment[ssize];
1977   }
1978 
1979   // Inner Classes
1980 
1981   /**
1982    * Segments are specialized versions of hash tables. This subclass inherits from ReentrantLock
1983    * opportunistically, just to simplify some locking and avoid separate construction.
1984    */
1985   @SuppressWarnings("serial") // This class is never serialized.
1986   static class Segment<K, V> extends ReentrantLock {
1987 
1988     /*
1989      * TODO(fry): Consider copying variables (like evictsBySize) from outer class into this class.
1990      * It will require more memory but will reduce indirection.
1991      */
1992 
1993     /*
1994      * Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so can
1995      * be read without locking. Next fields of nodes are immutable (final). All list additions are
1996      * performed at the front of each bin. This makes it easy to check changes, and also fast to
1997      * traverse. When nodes would otherwise be changed, new nodes are created to replace them. This
1998      * works well for hash tables since the bin lists tend to be short. (The average length is less
1999      * than two.)
2000      *
2001      * Read operations can thus proceed without locking, but rely on selected uses of volatiles to
2002      * ensure that completed write operations performed by other threads are noticed. For most
2003      * purposes, the "count" field, tracking the number of elements, serves as that volatile
2004      * variable ensuring visibility. This is convenient because this field needs to be read in many
2005      * read operations anyway:
2006      *
2007      * - All (unsynchronized) read operations must first read the "count" field, and should not look
2008      * at table entries if it is 0.
2009      *
2010      * - All (synchronized) write operations should write to the "count" field after structurally
2011      * changing any bin. The operations must not take any action that could even momentarily cause a
2012      * concurrent read operation to see inconsistent data. This is made easier by the nature of the
2013      * read operations in Map. For example, no operation can reveal that the table has grown but the
2014      * threshold has not yet been updated, so there are no atomicity requirements for this with
2015      * respect to reads.
2016      *
2017      * As a guide, all critical volatile reads and writes to the count field are marked in code
2018      * comments.
2019      */
2020 
2021     @Weak final LocalCache<K, V> map;
2022 
2023     /**
2024      * The number of live elements in this segment's region.
2025      */
2026     volatile int count;
2027 
2028     /**
2029      * The weight of the live elements in this segment's region.
2030      */
2031     @GuardedBy("this")
2032     long totalWeight;
2033 
2034     /**
2035      * Number of updates that alter the size of the table. This is used during bulk-read methods to
2036      * make sure they see a consistent snapshot: If modCounts change during a traversal of segments
2037      * loading size or checking containsValue, then we might have an inconsistent view of state so
2038      * (usually) must retry.
2039      */
2040     int modCount;
2041 
2042     /**
2043      * The table is expanded when its size exceeds this threshold. (The value of this field is
2044      * always {@code (int) (capacity * 0.75)}.)
2045      */
2046     int threshold;
2047 
2048     /**
2049      * The per-segment table.
2050      */
2051     volatile AtomicReferenceArray<ReferenceEntry<K, V>> table;
2052 
2053     /**
2054      * The maximum weight of this segment. UNSET_INT if there is no maximum.
2055      */
2056     final long maxSegmentWeight;
2057 
2058     /**
2059      * The key reference queue contains entries whose keys have been garbage collected, and which
2060      * need to be cleaned up internally.
2061      */
2062     final ReferenceQueue<K> keyReferenceQueue;
2063 
2064     /**
2065      * The value reference queue contains value references whose values have been garbage collected,
2066      * and which need to be cleaned up internally.
2067      */
2068     final ReferenceQueue<V> valueReferenceQueue;
2069 
2070     /**
2071      * The recency queue is used to record which entries were accessed for updating the access
2072      * list's ordering. It is drained as a batch operation when either the DRAIN_THRESHOLD is
2073      * crossed or a write occurs on the segment.
2074      */
2075     final Queue<ReferenceEntry<K, V>> recencyQueue;
2076 
2077     /**
2078      * A counter of the number of reads since the last write, used to drain queues on a small
2079      * fraction of read operations.
2080      */
2081     final AtomicInteger readCount = new AtomicInteger();
2082 
2083     /**
2084      * A queue of elements currently in the map, ordered by write time. Elements are added to the
2085      * tail of the queue on write.
2086      */
2087     @GuardedBy("this")
2088     final Queue<ReferenceEntry<K, V>> writeQueue;
2089 
2090     /**
2091      * A queue of elements currently in the map, ordered by access time. Elements are added to the
2092      * tail of the queue on access (note that writes count as accesses).
2093      */
2094     @GuardedBy("this")
2095     final Queue<ReferenceEntry<K, V>> accessQueue;
2096 
2097     /** Accumulates cache statistics. */
2098     final StatsCounter statsCounter;
2099 
2100     Segment(
2101         LocalCache<K, V> map,
2102         int initialCapacity,
2103         long maxSegmentWeight,
2104         StatsCounter statsCounter) {
2105       this.map = map;
2106       this.maxSegmentWeight = maxSegmentWeight;
2107       this.statsCounter = checkNotNull(statsCounter);
2108       initTable(newEntryArray(initialCapacity));
2109 
2110       keyReferenceQueue = map.usesKeyReferences() ? new ReferenceQueue<K>() : null;
2111 
2112       valueReferenceQueue = map.usesValueReferences() ? new ReferenceQueue<V>() : null;
2113 
2114       recencyQueue =
2115           map.usesAccessQueue()
2116               ? new ConcurrentLinkedQueue<ReferenceEntry<K, V>>()
2117               : LocalCache.<ReferenceEntry<K, V>>discardingQueue();
2118 
2119       writeQueue =
2120           map.usesWriteQueue()
2121               ? new WriteQueue<K, V>()
2122               : LocalCache.<ReferenceEntry<K, V>>discardingQueue();
2123 
2124       accessQueue =
2125           map.usesAccessQueue()
2126               ? new AccessQueue<K, V>()
2127               : LocalCache.<ReferenceEntry<K, V>>discardingQueue();
2128     }
2129 
2130     AtomicReferenceArray<ReferenceEntry<K, V>> newEntryArray(int size) {
2131       return new AtomicReferenceArray<>(size);
2132     }
2133 
2134     void initTable(AtomicReferenceArray<ReferenceEntry<K, V>> newTable) {
2135       this.threshold = newTable.length() * 3 / 4; // 0.75
2136       if (!map.customWeigher() && this.threshold == maxSegmentWeight) {
2137         // prevent spurious expansion before eviction
2138         this.threshold++;
2139       }
2140       this.table = newTable;
2141     }
2142 
2143     @GuardedBy("this")
2144     ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
2145       return map.entryFactory.newEntry(this, checkNotNull(key), hash, next);
2146     }
2147 
2148     /**
2149      * Copies {@code original} into a new entry chained to {@code newNext}. Returns the new entry,
2150      * or {@code null} if {@code original} was already garbage collected.
2151      */
2152     @GuardedBy("this")
2153     ReferenceEntry<K, V> copyEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
2154       if (original.getKey() == null) {
2155         // key collected
2156         return null;
2157       }
2158 
2159       ValueReference<K, V> valueReference = original.getValueReference();
2160       V value = valueReference.get();
2161       if ((value == null) && valueReference.isActive()) {
2162         // value collected
2163         return null;
2164       }
2165 
2166       ReferenceEntry<K, V> newEntry = map.entryFactory.copyEntry(this, original, newNext);
2167       newEntry.setValueReference(valueReference.copyFor(this.valueReferenceQueue, value, newEntry));
2168       return newEntry;
2169     }
2170 
2171     /**
2172      * Sets a new value of an entry. Adds newly created entries at the end of the access queue.
2173      */
2174     @GuardedBy("this")
2175     void setValue(ReferenceEntry<K, V> entry, K key, V value, long now) {
2176       ValueReference<K, V> previous = entry.getValueReference();
2177       int weight = map.weigher.weigh(key, value);
2178       checkState(weight >= 0, "Weights must be non-negative");
2179 
2180       ValueReference<K, V> valueReference =
2181           map.valueStrength.referenceValue(this, entry, value, weight);
2182       entry.setValueReference(valueReference);
2183       recordWrite(entry, weight, now);
2184       previous.notifyNewValue(value);
2185     }
2186 
2187     // loading
2188 
2189     V get(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
2190       checkNotNull(key);
2191       checkNotNull(loader);
2192       try {
2193         if (count != 0) { // read-volatile
2194           // don't call getLiveEntry, which would ignore loading values
2195           ReferenceEntry<K, V> e = getEntry(key, hash);
2196           if (e != null) {
2197             long now = map.ticker.read();
2198             V value = getLiveValue(e, now);
2199             if (value != null) {
2200               recordRead(e, now);
2201               statsCounter.recordHits(1);
2202               return scheduleRefresh(e, key, hash, value, now, loader);
2203             }
2204             ValueReference<K, V> valueReference = e.getValueReference();
2205             if (valueReference.isLoading()) {
2206               return waitForLoadingValue(e, key, valueReference);
2207             }
2208           }
2209         }
2210 
2211         // at this point e is either null or expired;
2212         return lockedGetOrLoad(key, hash, loader);
2213       } catch (ExecutionException ee) {
2214         Throwable cause = ee.getCause();
2215         if (cause instanceof Error) {
2216           throw new ExecutionError((Error) cause);
2217         } else if (cause instanceof RuntimeException) {
2218           throw new UncheckedExecutionException(cause);
2219         }
2220         throw ee;
2221       } finally {
2222         postReadCleanup();
2223       }
2224     }
2225 
2226     V lockedGetOrLoad(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
2227       ReferenceEntry<K, V> e;
2228       ValueReference<K, V> valueReference = null;
2229       LoadingValueReference<K, V> loadingValueReference = null;
2230       boolean createNewEntry = true;
2231 
2232       lock();
2233       try {
2234         // re-read ticker once inside the lock
2235         long now = map.ticker.read();
2236         preWriteCleanup(now);
2237 
2238         int newCount = this.count - 1;
2239         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2240         int index = hash & (table.length() - 1);
2241         ReferenceEntry<K, V> first = table.get(index);
2242 
2243         for (e = first; e != null; e = e.getNext()) {
2244           K entryKey = e.getKey();
2245           if (e.getHash() == hash
2246               && entryKey != null
2247               && map.keyEquivalence.equivalent(key, entryKey)) {
2248             valueReference = e.getValueReference();
2249             if (valueReference.isLoading()) {
2250               createNewEntry = false;
2251             } else {
2252               V value = valueReference.get();
2253               if (value == null) {
2254                 enqueueNotification(
2255                     entryKey, hash, value, valueReference.getWeight(), RemovalCause.COLLECTED);
2256               } else if (map.isExpired(e, now)) {
2257                 // This is a duplicate check, as preWriteCleanup already purged expired
2258                 // entries, but let's accomodate an incorrect expiration queue.
2259                 enqueueNotification(
2260                     entryKey, hash, value, valueReference.getWeight(), RemovalCause.EXPIRED);
2261               } else {
2262                 recordLockedRead(e, now);
2263                 statsCounter.recordHits(1);
2264                 // we were concurrent with loading; don't consider refresh
2265                 return value;
2266               }
2267 
2268               // immediately reuse invalid entries
2269               writeQueue.remove(e);
2270               accessQueue.remove(e);
2271               this.count = newCount; // write-volatile
2272             }
2273             break;
2274           }
2275         }
2276 
2277         if (createNewEntry) {
2278           loadingValueReference = new LoadingValueReference<>();
2279 
2280           if (e == null) {
2281             e = newEntry(key, hash, first);
2282             e.setValueReference(loadingValueReference);
2283             table.set(index, e);
2284           } else {
2285             e.setValueReference(loadingValueReference);
2286           }
2287         }
2288       } finally {
2289         unlock();
2290         postWriteCleanup();
2291       }
2292 
2293       if (createNewEntry) {
2294         try {
2295           // Synchronizes on the entry to allow failing fast when a recursive load is
2296           // detected. This may be circumvented when an entry is copied, but will fail fast most
2297           // of the time.
2298           synchronized (e) {
2299             return loadSync(key, hash, loadingValueReference, loader);
2300           }
2301         } finally {
2302           statsCounter.recordMisses(1);
2303         }
2304       } else {
2305         // The entry already exists. Wait for loading.
2306         return waitForLoadingValue(e, key, valueReference);
2307       }
2308     }
2309 
2310     V waitForLoadingValue(ReferenceEntry<K, V> e, K key, ValueReference<K, V> valueReference)
2311         throws ExecutionException {
2312       if (!valueReference.isLoading()) {
2313         throw new AssertionError();
2314       }
2315 
2316       checkState(!Thread.holdsLock(e), "Recursive load of: %s", key);
2317       // don't consider expiration as we're concurrent with loading
2318       try {
2319         V value = valueReference.waitForValue();
2320         if (value == null) {
2321           throw new InvalidCacheLoadException("CacheLoader returned null for key " + key + ".");
2322         }
2323         // re-read ticker now that loading has completed
2324         long now = map.ticker.read();
2325         recordRead(e, now);
2326         return value;
2327       } finally {
2328         statsCounter.recordMisses(1);
2329       }
2330     }
2331 
2332     V compute(K key, int hash, BiFunction<? super K, ? super V, ? extends V> function) {
2333       ReferenceEntry<K, V> e;
2334       ValueReference<K, V> valueReference = null;
2335       LoadingValueReference<K, V> loadingValueReference = null;
2336       boolean createNewEntry = true;
2337       V newValue;
2338 
2339       lock();
2340       try {
2341         // re-read ticker once inside the lock
2342         long now = map.ticker.read();
2343         preWriteCleanup(now);
2344 
2345         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2346         int index = hash & (table.length() - 1);
2347         ReferenceEntry<K, V> first = table.get(index);
2348 
2349         for (e = first; e != null; e = e.getNext()) {
2350           K entryKey = e.getKey();
2351           if (e.getHash() == hash
2352               && entryKey != null
2353               && map.keyEquivalence.equivalent(key, entryKey)) {
2354             valueReference = e.getValueReference();
2355             if (map.isExpired(e, now)) {
2356               // This is a duplicate check, as preWriteCleanup already purged expired
2357               // entries, but let's accomodate an incorrect expiration queue.
2358               enqueueNotification(
2359                   entryKey,
2360                   hash,
2361                   valueReference.get(),
2362                   valueReference.getWeight(),
2363                   RemovalCause.EXPIRED);
2364             }
2365 
2366             // immediately reuse invalid entries
2367             writeQueue.remove(e);
2368             accessQueue.remove(e);
2369             createNewEntry = false;
2370             break;
2371           }
2372         }
2373 
2374         // note valueReference can be an existing value or even itself another loading value if
2375         // the value for the key is already being computed.
2376         loadingValueReference = new LoadingValueReference<>(valueReference);
2377 
2378         if (e == null) {
2379           createNewEntry = true;
2380           e = newEntry(key, hash, first);
2381           e.setValueReference(loadingValueReference);
2382           table.set(index, e);
2383         } else {
2384           e.setValueReference(loadingValueReference);
2385         }
2386 
2387         newValue = loadingValueReference.compute(key, function);
2388         if (newValue != null) {
2389           try {
2390             return getAndRecordStats(
2391                 key, hash, loadingValueReference, Futures.immediateFuture(newValue));
2392           } catch (ExecutionException exception) {
2393             throw new AssertionError("impossible; Futures.immediateFuture can't throw");
2394           }
2395         } else if (createNewEntry) {
2396           removeLoadingValue(key, hash, loadingValueReference);
2397           return null;
2398         } else {
2399           removeEntry(e, hash, RemovalCause.EXPLICIT);
2400           return null;
2401         }
2402       } finally {
2403         unlock();
2404         postWriteCleanup();
2405       }
2406     }
2407 
2408     // at most one of loadSync/loadAsync may be called for any given LoadingValueReference
2409 
2410     V loadSync(
2411         K key,
2412         int hash,
2413         LoadingValueReference<K, V> loadingValueReference,
2414         CacheLoader<? super K, V> loader)
2415         throws ExecutionException {
2416       ListenableFuture<V> loadingFuture = loadingValueReference.loadFuture(key, loader);
2417       return getAndRecordStats(key, hash, loadingValueReference, loadingFuture);
2418     }
2419 
2420     ListenableFuture<V> loadAsync(
2421         final K key,
2422         final int hash,
2423         final LoadingValueReference<K, V> loadingValueReference,
2424         CacheLoader<? super K, V> loader) {
2425       final ListenableFuture<V> loadingFuture = loadingValueReference.loadFuture(key, loader);
2426       loadingFuture.addListener(
2427           new Runnable() {
2428             @Override
2429             public void run() {
2430               try {
2431                 getAndRecordStats(key, hash, loadingValueReference, loadingFuture);
2432               } catch (Throwable t) {
2433                 logger.log(Level.WARNING, "Exception thrown during refresh", t);
2434                 loadingValueReference.setException(t);
2435               }
2436             }
2437           },
2438           directExecutor());
2439       return loadingFuture;
2440     }
2441 
2442     /**
2443      * Waits uninterruptibly for {@code newValue} to be loaded, and then records loading stats.
2444      */
2445     V getAndRecordStats(
2446         K key,
2447         int hash,
2448         LoadingValueReference<K, V> loadingValueReference,
2449         ListenableFuture<V> newValue)
2450         throws ExecutionException {
2451       V value = null;
2452       try {
2453         value = getUninterruptibly(newValue);
2454         if (value == null) {
2455           throw new InvalidCacheLoadException("CacheLoader returned null for key " + key + ".");
2456         }
2457         statsCounter.recordLoadSuccess(loadingValueReference.elapsedNanos());
2458         storeLoadedValue(key, hash, loadingValueReference, value);
2459         return value;
2460       } finally {
2461         if (value == null) {
2462           statsCounter.recordLoadException(loadingValueReference.elapsedNanos());
2463           removeLoadingValue(key, hash, loadingValueReference);
2464         }
2465       }
2466     }
2467 
2468     V scheduleRefresh(
2469         ReferenceEntry<K, V> entry,
2470         K key,
2471         int hash,
2472         V oldValue,
2473         long now,
2474         CacheLoader<? super K, V> loader) {
2475       if (map.refreshes()
2476           && (now - entry.getWriteTime() > map.refreshNanos)
2477           && !entry.getValueReference().isLoading()) {
2478         V newValue = refresh(key, hash, loader, true);
2479         if (newValue != null) {
2480           return newValue;
2481         }
2482       }
2483       return oldValue;
2484     }
2485 
2486     /**
2487      * Refreshes the value associated with {@code key}, unless another thread is already doing so.
2488      * Returns the newly refreshed value associated with {@code key} if it was refreshed inline, or
2489      * {@code null} if another thread is performing the refresh or if an error occurs during
2490      * refresh.
2491      */
2492     @Nullable
2493     V refresh(K key, int hash, CacheLoader<? super K, V> loader, boolean checkTime) {
2494       final LoadingValueReference<K, V> loadingValueReference =
2495           insertLoadingValueReference(key, hash, checkTime);
2496       if (loadingValueReference == null) {
2497         return null;
2498       }
2499 
2500       ListenableFuture<V> result = loadAsync(key, hash, loadingValueReference, loader);
2501       if (result.isDone()) {
2502         try {
2503           return Uninterruptibles.getUninterruptibly(result);
2504         } catch (Throwable t) {
2505           // don't let refresh exceptions propagate; error was already logged
2506         }
2507       }
2508       return null;
2509     }
2510 
2511     /**
2512      * Returns a newly inserted {@code LoadingValueReference}, or null if the live value reference
2513      * is already loading.
2514      */
2515     @Nullable
2516     LoadingValueReference<K, V> insertLoadingValueReference(
2517         final K key, final int hash, boolean checkTime) {
2518       ReferenceEntry<K, V> e = null;
2519       lock();
2520       try {
2521         long now = map.ticker.read();
2522         preWriteCleanup(now);
2523 
2524         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2525         int index = hash & (table.length() - 1);
2526         ReferenceEntry<K, V> first = table.get(index);
2527 
2528         // Look for an existing entry.
2529         for (e = first; e != null; e = e.getNext()) {
2530           K entryKey = e.getKey();
2531           if (e.getHash() == hash
2532               && entryKey != null
2533               && map.keyEquivalence.equivalent(key, entryKey)) {
2534             // We found an existing entry.
2535 
2536             ValueReference<K, V> valueReference = e.getValueReference();
2537             if (valueReference.isLoading()
2538                 || (checkTime && (now - e.getWriteTime() < map.refreshNanos))) {
2539               // refresh is a no-op if loading is pending
2540               // if checkTime, we want to check *after* acquiring the lock if refresh still needs
2541               // to be scheduled
2542               return null;
2543             }
2544 
2545             // continue returning old value while loading
2546             ++modCount;
2547             LoadingValueReference<K, V> loadingValueReference =
2548                 new LoadingValueReference<>(valueReference);
2549             e.setValueReference(loadingValueReference);
2550             return loadingValueReference;
2551           }
2552         }
2553 
2554         ++modCount;
2555         LoadingValueReference<K, V> loadingValueReference = new LoadingValueReference<>();
2556         e = newEntry(key, hash, first);
2557         e.setValueReference(loadingValueReference);
2558         table.set(index, e);
2559         return loadingValueReference;
2560       } finally {
2561         unlock();
2562         postWriteCleanup();
2563       }
2564     }
2565 
2566     // reference queues, for garbage collection cleanup
2567 
2568     /**
2569      * Cleanup collected entries when the lock is available.
2570      */
2571     void tryDrainReferenceQueues() {
2572       if (tryLock()) {
2573         try {
2574           drainReferenceQueues();
2575         } finally {
2576           unlock();
2577         }
2578       }
2579     }
2580 
2581     /**
2582      * Drain the key and value reference queues, cleaning up internal entries containing garbage
2583      * collected keys or values.
2584      */
2585     @GuardedBy("this")
2586     void drainReferenceQueues() {
2587       if (map.usesKeyReferences()) {
2588         drainKeyReferenceQueue();
2589       }
2590       if (map.usesValueReferences()) {
2591         drainValueReferenceQueue();
2592       }
2593     }
2594 
2595     @GuardedBy("this")
2596     void drainKeyReferenceQueue() {
2597       Reference<? extends K> ref;
2598       int i = 0;
2599       while ((ref = keyReferenceQueue.poll()) != null) {
2600         @SuppressWarnings("unchecked")
2601         ReferenceEntry<K, V> entry = (ReferenceEntry<K, V>) ref;
2602         map.reclaimKey(entry);
2603         if (++i == DRAIN_MAX) {
2604           break;
2605         }
2606       }
2607     }
2608 
2609     @GuardedBy("this")
2610     void drainValueReferenceQueue() {
2611       Reference<? extends V> ref;
2612       int i = 0;
2613       while ((ref = valueReferenceQueue.poll()) != null) {
2614         @SuppressWarnings("unchecked")
2615         ValueReference<K, V> valueReference = (ValueReference<K, V>) ref;
2616         map.reclaimValue(valueReference);
2617         if (++i == DRAIN_MAX) {
2618           break;
2619         }
2620       }
2621     }
2622 
2623     /**
2624      * Clears all entries from the key and value reference queues.
2625      */
2626     void clearReferenceQueues() {
2627       if (map.usesKeyReferences()) {
2628         clearKeyReferenceQueue();
2629       }
2630       if (map.usesValueReferences()) {
2631         clearValueReferenceQueue();
2632       }
2633     }
2634 
2635     void clearKeyReferenceQueue() {
2636       while (keyReferenceQueue.poll() != null) {}
2637     }
2638 
2639     void clearValueReferenceQueue() {
2640       while (valueReferenceQueue.poll() != null) {}
2641     }
2642 
2643     // recency queue, shared by expiration and eviction
2644 
2645     /**
2646      * Records the relative order in which this read was performed by adding {@code entry} to the
2647      * recency queue. At write-time, or when the queue is full past the threshold, the queue will be
2648      * drained and the entries therein processed.
2649      *
2650      * <p>Note: locked reads should use {@link #recordLockedRead}.
2651      */
2652     void recordRead(ReferenceEntry<K, V> entry, long now) {
2653       if (map.recordsAccess()) {
2654         entry.setAccessTime(now);
2655       }
2656       recencyQueue.add(entry);
2657     }
2658 
2659     /**
2660      * Updates the eviction metadata that {@code entry} was just read. This currently amounts to
2661      * adding {@code entry} to relevant eviction lists.
2662      *
2663      * <p>Note: this method should only be called under lock, as it directly manipulates the
2664      * eviction queues. Unlocked reads should use {@link #recordRead}.
2665      */
2666     @GuardedBy("this")
2667     void recordLockedRead(ReferenceEntry<K, V> entry, long now) {
2668       if (map.recordsAccess()) {
2669         entry.setAccessTime(now);
2670       }
2671       accessQueue.add(entry);
2672     }
2673 
2674     /**
2675      * Updates eviction metadata that {@code entry} was just written. This currently amounts to
2676      * adding {@code entry} to relevant eviction lists.
2677      */
2678     @GuardedBy("this")
2679     void recordWrite(ReferenceEntry<K, V> entry, int weight, long now) {
2680       // we are already under lock, so drain the recency queue immediately
2681       drainRecencyQueue();
2682       totalWeight += weight;
2683 
2684       if (map.recordsAccess()) {
2685         entry.setAccessTime(now);
2686       }
2687       if (map.recordsWrite()) {
2688         entry.setWriteTime(now);
2689       }
2690       accessQueue.add(entry);
2691       writeQueue.add(entry);
2692     }
2693 
2694     /**
2695      * Drains the recency queue, updating eviction metadata that the entries therein were read in
2696      * the specified relative order. This currently amounts to adding them to relevant eviction
2697      * lists (accounting for the fact that they could have been removed from the map since being
2698      * added to the recency queue).
2699      */
2700     @GuardedBy("this")
2701     void drainRecencyQueue() {
2702       ReferenceEntry<K, V> e;
2703       while ((e = recencyQueue.poll()) != null) {
2704         // An entry may be in the recency queue despite it being removed from
2705         // the map . This can occur when the entry was concurrently read while a
2706         // writer is removing it from the segment or after a clear has removed
2707         // all of the segment's entries.
2708         if (accessQueue.contains(e)) {
2709           accessQueue.add(e);
2710         }
2711       }
2712     }
2713 
2714     // expiration
2715 
2716     /**
2717      * Cleanup expired entries when the lock is available.
2718      */
2719     void tryExpireEntries(long now) {
2720       if (tryLock()) {
2721         try {
2722           expireEntries(now);
2723         } finally {
2724           unlock();
2725           // don't call postWriteCleanup as we're in a read
2726         }
2727       }
2728     }
2729 
2730     @GuardedBy("this")
2731     void expireEntries(long now) {
2732       drainRecencyQueue();
2733 
2734       ReferenceEntry<K, V> e;
2735       while ((e = writeQueue.peek()) != null && map.isExpired(e, now)) {
2736         if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
2737           throw new AssertionError();
2738         }
2739       }
2740       while ((e = accessQueue.peek()) != null && map.isExpired(e, now)) {
2741         if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
2742           throw new AssertionError();
2743         }
2744       }
2745     }
2746 
2747     // eviction
2748 
2749     @GuardedBy("this")
2750     void enqueueNotification(
2751         @Nullable K key, int hash, @Nullable V value, int weight, RemovalCause cause) {
2752       totalWeight -= weight;
2753       if (cause.wasEvicted()) {
2754         statsCounter.recordEviction();
2755       }
2756       if (map.removalNotificationQueue != DISCARDING_QUEUE) {
2757         RemovalNotification<K, V> notification = RemovalNotification.create(key, value, cause);
2758         map.removalNotificationQueue.offer(notification);
2759       }
2760     }
2761 
2762     /**
2763      * Performs eviction if the segment is over capacity. Avoids flushing the entire cache if the
2764      * newest entry exceeds the maximum weight all on its own.
2765      *
2766      * @param newest the most recently added entry
2767      */
2768     @GuardedBy("this")
2769     void evictEntries(ReferenceEntry<K, V> newest) {
2770       if (!map.evictsBySize()) {
2771         return;
2772       }
2773 
2774       drainRecencyQueue();
2775 
2776       // If the newest entry by itself is too heavy for the segment, don't bother evicting
2777       // anything else, just that
2778       if (newest.getValueReference().getWeight() > maxSegmentWeight) {
2779         if (!removeEntry(newest, newest.getHash(), RemovalCause.SIZE)) {
2780           throw new AssertionError();
2781         }
2782       }
2783 
2784       while (totalWeight > maxSegmentWeight) {
2785         ReferenceEntry<K, V> e = getNextEvictable();
2786         if (!removeEntry(e, e.getHash(), RemovalCause.SIZE)) {
2787           throw new AssertionError();
2788         }
2789       }
2790     }
2791 
2792     // TODO(fry): instead implement this with an eviction head
2793     @GuardedBy("this")
2794     ReferenceEntry<K, V> getNextEvictable() {
2795       for (ReferenceEntry<K, V> e : accessQueue) {
2796         int weight = e.getValueReference().getWeight();
2797         if (weight > 0) {
2798           return e;
2799         }
2800       }
2801       throw new AssertionError();
2802     }
2803 
2804     /**
2805      * Returns first entry of bin for given hash.
2806      */
2807     ReferenceEntry<K, V> getFirst(int hash) {
2808       // read this volatile field only once
2809       AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2810       return table.get(hash & (table.length() - 1));
2811     }
2812 
2813     // Specialized implementations of map methods
2814 
2815     @Nullable
2816     ReferenceEntry<K, V> getEntry(Object key, int hash) {
2817       for (ReferenceEntry<K, V> e = getFirst(hash); e != null; e = e.getNext()) {
2818         if (e.getHash() != hash) {
2819           continue;
2820         }
2821 
2822         K entryKey = e.getKey();
2823         if (entryKey == null) {
2824           tryDrainReferenceQueues();
2825           continue;
2826         }
2827 
2828         if (map.keyEquivalence.equivalent(key, entryKey)) {
2829           return e;
2830         }
2831       }
2832 
2833       return null;
2834     }
2835 
2836     @Nullable
2837     ReferenceEntry<K, V> getLiveEntry(Object key, int hash, long now) {
2838       ReferenceEntry<K, V> e = getEntry(key, hash);
2839       if (e == null) {
2840         return null;
2841       } else if (map.isExpired(e, now)) {
2842         tryExpireEntries(now);
2843         return null;
2844       }
2845       return e;
2846     }
2847 
2848     /**
2849      * Gets the value from an entry. Returns null if the entry is invalid, partially-collected,
2850      * loading, or expired.
2851      */
2852     V getLiveValue(ReferenceEntry<K, V> entry, long now) {
2853       if (entry.getKey() == null) {
2854         tryDrainReferenceQueues();
2855         return null;
2856       }
2857       V value = entry.getValueReference().get();
2858       if (value == null) {
2859         tryDrainReferenceQueues();
2860         return null;
2861       }
2862 
2863       if (map.isExpired(entry, now)) {
2864         tryExpireEntries(now);
2865         return null;
2866       }
2867       return value;
2868     }
2869 
2870     @Nullable
2871     V get(Object key, int hash) {
2872       try {
2873         if (count != 0) { // read-volatile
2874           long now = map.ticker.read();
2875           ReferenceEntry<K, V> e = getLiveEntry(key, hash, now);
2876           if (e == null) {
2877             return null;
2878           }
2879 
2880           V value = e.getValueReference().get();
2881           if (value != null) {
2882             recordRead(e, now);
2883             return scheduleRefresh(e, e.getKey(), hash, value, now, map.defaultLoader);
2884           }
2885           tryDrainReferenceQueues();
2886         }
2887         return null;
2888       } finally {
2889         postReadCleanup();
2890       }
2891     }
2892 
2893     boolean containsKey(Object key, int hash) {
2894       try {
2895         if (count != 0) { // read-volatile
2896           long now = map.ticker.read();
2897           ReferenceEntry<K, V> e = getLiveEntry(key, hash, now);
2898           if (e == null) {
2899             return false;
2900           }
2901           return e.getValueReference().get() != null;
2902         }
2903 
2904         return false;
2905       } finally {
2906         postReadCleanup();
2907       }
2908     }
2909 
2910     /**
2911      * This method is a convenience for testing. Code should call {@link LocalCache#containsValue}
2912      * directly.
2913      */
2914     @VisibleForTesting
2915     boolean containsValue(Object value) {
2916       try {
2917         if (count != 0) { // read-volatile
2918           long now = map.ticker.read();
2919           AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2920           int length = table.length();
2921           for (int i = 0; i < length; ++i) {
2922             for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
2923               V entryValue = getLiveValue(e, now);
2924               if (entryValue == null) {
2925                 continue;
2926               }
2927               if (map.valueEquivalence.equivalent(value, entryValue)) {
2928                 return true;
2929               }
2930             }
2931           }
2932         }
2933 
2934         return false;
2935       } finally {
2936         postReadCleanup();
2937       }
2938     }
2939 
2940     @Nullable
2941     V put(K key, int hash, V value, boolean onlyIfAbsent) {
2942       lock();
2943       try {
2944         long now = map.ticker.read();
2945         preWriteCleanup(now);
2946 
2947         int newCount = this.count + 1;
2948         if (newCount > this.threshold) { // ensure capacity
2949           expand();
2950           newCount = this.count + 1;
2951         }
2952 
2953         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
2954         int index = hash & (table.length() - 1);
2955         ReferenceEntry<K, V> first = table.get(index);
2956 
2957         // Look for an existing entry.
2958         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
2959           K entryKey = e.getKey();
2960           if (e.getHash() == hash
2961               && entryKey != null
2962               && map.keyEquivalence.equivalent(key, entryKey)) {
2963             // We found an existing entry.
2964 
2965             ValueReference<K, V> valueReference = e.getValueReference();
2966             V entryValue = valueReference.get();
2967 
2968             if (entryValue == null) {
2969               ++modCount;
2970               if (valueReference.isActive()) {
2971                 enqueueNotification(
2972                     key, hash, entryValue, valueReference.getWeight(), RemovalCause.COLLECTED);
2973                 setValue(e, key, value, now);
2974                 newCount = this.count; // count remains unchanged
2975               } else {
2976                 setValue(e, key, value, now);
2977                 newCount = this.count + 1;
2978               }
2979               this.count = newCount; // write-volatile
2980               evictEntries(e);
2981               return null;
2982             } else if (onlyIfAbsent) {
2983               // Mimic
2984               // "if (!map.containsKey(key)) ...
2985               // else return map.get(key);
2986               recordLockedRead(e, now);
2987               return entryValue;
2988             } else {
2989               // clobber existing entry, count remains unchanged
2990               ++modCount;
2991               enqueueNotification(
2992                   key, hash, entryValue, valueReference.getWeight(), RemovalCause.REPLACED);
2993               setValue(e, key, value, now);
2994               evictEntries(e);
2995               return entryValue;
2996             }
2997           }
2998         }
2999 
3000         // Create a new entry.
3001         ++modCount;
3002         ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
3003         setValue(newEntry, key, value, now);
3004         table.set(index, newEntry);
3005         newCount = this.count + 1;
3006         this.count = newCount; // write-volatile
3007         evictEntries(newEntry);
3008         return null;
3009       } finally {
3010         unlock();
3011         postWriteCleanup();
3012       }
3013     }
3014 
3015     /**
3016      * Expands the table if possible.
3017      */
3018     @GuardedBy("this")
3019     void expand() {
3020       AtomicReferenceArray<ReferenceEntry<K, V>> oldTable = table;
3021       int oldCapacity = oldTable.length();
3022       if (oldCapacity >= MAXIMUM_CAPACITY) {
3023         return;
3024       }
3025 
3026       /*
3027        * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the
3028        * elements from each bin must either stay at same index, or move with a power of two offset.
3029        * We eliminate unnecessary node creation by catching cases where old nodes can be reused
3030        * because their next fields won't change. Statistically, at the default threshold, only about
3031        * one-sixth of them need cloning when a table doubles. The nodes they replace will be garbage
3032        * collectable as soon as they are no longer referenced by any reader thread that may be in
3033        * the midst of traversing table right now.
3034        */
3035 
3036       int newCount = count;
3037       AtomicReferenceArray<ReferenceEntry<K, V>> newTable = newEntryArray(oldCapacity << 1);
3038       threshold = newTable.length() * 3 / 4;
3039       int newMask = newTable.length() - 1;
3040       for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) {
3041         // We need to guarantee that any existing reads of old Map can
3042         // proceed. So we cannot yet null out each bin.
3043         ReferenceEntry<K, V> head = oldTable.get(oldIndex);
3044 
3045         if (head != null) {
3046           ReferenceEntry<K, V> next = head.getNext();
3047           int headIndex = head.getHash() & newMask;
3048 
3049           // Single node on list
3050           if (next == null) {
3051             newTable.set(headIndex, head);
3052           } else {
3053             // Reuse the consecutive sequence of nodes with the same target
3054             // index from the end of the list. tail points to the first
3055             // entry in the reusable list.
3056             ReferenceEntry<K, V> tail = head;
3057             int tailIndex = headIndex;
3058             for (ReferenceEntry<K, V> e = next; e != null; e = e.getNext()) {
3059               int newIndex = e.getHash() & newMask;
3060               if (newIndex != tailIndex) {
3061                 // The index changed. We'll need to copy the previous entry.
3062                 tailIndex = newIndex;
3063                 tail = e;
3064               }
3065             }
3066             newTable.set(tailIndex, tail);
3067 
3068             // Clone nodes leading up to the tail.
3069             for (ReferenceEntry<K, V> e = head; e != tail; e = e.getNext()) {
3070               int newIndex = e.getHash() & newMask;
3071               ReferenceEntry<K, V> newNext = newTable.get(newIndex);
3072               ReferenceEntry<K, V> newFirst = copyEntry(e, newNext);
3073               if (newFirst != null) {
3074                 newTable.set(newIndex, newFirst);
3075               } else {
3076                 removeCollectedEntry(e);
3077                 newCount--;
3078               }
3079             }
3080           }
3081         }
3082       }
3083       table = newTable;
3084       this.count = newCount;
3085     }
3086 
3087     boolean replace(K key, int hash, V oldValue, V newValue) {
3088       lock();
3089       try {
3090         long now = map.ticker.read();
3091         preWriteCleanup(now);
3092 
3093         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3094         int index = hash & (table.length() - 1);
3095         ReferenceEntry<K, V> first = table.get(index);
3096 
3097         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3098           K entryKey = e.getKey();
3099           if (e.getHash() == hash
3100               && entryKey != null
3101               && map.keyEquivalence.equivalent(key, entryKey)) {
3102             ValueReference<K, V> valueReference = e.getValueReference();
3103             V entryValue = valueReference.get();
3104             if (entryValue == null) {
3105               if (valueReference.isActive()) {
3106                 // If the value disappeared, this entry is partially collected.
3107                 int newCount = this.count - 1;
3108                 ++modCount;
3109                 ReferenceEntry<K, V> newFirst =
3110                     removeValueFromChain(
3111                         first,
3112                         e,
3113                         entryKey,
3114                         hash,
3115                         entryValue,
3116                         valueReference,
3117                         RemovalCause.COLLECTED);
3118                 newCount = this.count - 1;
3119                 table.set(index, newFirst);
3120                 this.count = newCount; // write-volatile
3121               }
3122               return false;
3123             }
3124 
3125             if (map.valueEquivalence.equivalent(oldValue, entryValue)) {
3126               ++modCount;
3127               enqueueNotification(
3128                   key, hash, entryValue, valueReference.getWeight(), RemovalCause.REPLACED);
3129               setValue(e, key, newValue, now);
3130               evictEntries(e);
3131               return true;
3132             } else {
3133               // Mimic
3134               // "if (map.containsKey(key) && map.get(key).equals(oldValue))..."
3135               recordLockedRead(e, now);
3136               return false;
3137             }
3138           }
3139         }
3140 
3141         return false;
3142       } finally {
3143         unlock();
3144         postWriteCleanup();
3145       }
3146     }
3147 
3148     @Nullable
3149     V replace(K key, int hash, V newValue) {
3150       lock();
3151       try {
3152         long now = map.ticker.read();
3153         preWriteCleanup(now);
3154 
3155         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3156         int index = hash & (table.length() - 1);
3157         ReferenceEntry<K, V> first = table.get(index);
3158 
3159         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3160           K entryKey = e.getKey();
3161           if (e.getHash() == hash
3162               && entryKey != null
3163               && map.keyEquivalence.equivalent(key, entryKey)) {
3164             ValueReference<K, V> valueReference = e.getValueReference();
3165             V entryValue = valueReference.get();
3166             if (entryValue == null) {
3167               if (valueReference.isActive()) {
3168                 // If the value disappeared, this entry is partially collected.
3169                 int newCount = this.count - 1;
3170                 ++modCount;
3171                 ReferenceEntry<K, V> newFirst =
3172                     removeValueFromChain(
3173                         first,
3174                         e,
3175                         entryKey,
3176                         hash,
3177                         entryValue,
3178                         valueReference,
3179                         RemovalCause.COLLECTED);
3180                 newCount = this.count - 1;
3181                 table.set(index, newFirst);
3182                 this.count = newCount; // write-volatile
3183               }
3184               return null;
3185             }
3186 
3187             ++modCount;
3188             enqueueNotification(
3189                 key, hash, entryValue, valueReference.getWeight(), RemovalCause.REPLACED);
3190             setValue(e, key, newValue, now);
3191             evictEntries(e);
3192             return entryValue;
3193           }
3194         }
3195 
3196         return null;
3197       } finally {
3198         unlock();
3199         postWriteCleanup();
3200       }
3201     }
3202 
3203     @Nullable
3204     V remove(Object key, int hash) {
3205       lock();
3206       try {
3207         long now = map.ticker.read();
3208         preWriteCleanup(now);
3209 
3210         int newCount = this.count - 1;
3211         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3212         int index = hash & (table.length() - 1);
3213         ReferenceEntry<K, V> first = table.get(index);
3214 
3215         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3216           K entryKey = e.getKey();
3217           if (e.getHash() == hash
3218               && entryKey != null
3219               && map.keyEquivalence.equivalent(key, entryKey)) {
3220             ValueReference<K, V> valueReference = e.getValueReference();
3221             V entryValue = valueReference.get();
3222 
3223             RemovalCause cause;
3224             if (entryValue != null) {
3225               cause = RemovalCause.EXPLICIT;
3226             } else if (valueReference.isActive()) {
3227               cause = RemovalCause.COLLECTED;
3228             } else {
3229               // currently loading
3230               return null;
3231             }
3232 
3233             ++modCount;
3234             ReferenceEntry<K, V> newFirst =
3235                 removeValueFromChain(first, e, entryKey, hash, entryValue, valueReference, cause);
3236             newCount = this.count - 1;
3237             table.set(index, newFirst);
3238             this.count = newCount; // write-volatile
3239             return entryValue;
3240           }
3241         }
3242 
3243         return null;
3244       } finally {
3245         unlock();
3246         postWriteCleanup();
3247       }
3248     }
3249 
3250     boolean storeLoadedValue(
3251         K key, int hash, LoadingValueReference<K, V> oldValueReference, V newValue) {
3252       lock();
3253       try {
3254         long now = map.ticker.read();
3255         preWriteCleanup(now);
3256 
3257         int newCount = this.count + 1;
3258         if (newCount > this.threshold) { // ensure capacity
3259           expand();
3260           newCount = this.count + 1;
3261         }
3262 
3263         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3264         int index = hash & (table.length() - 1);
3265         ReferenceEntry<K, V> first = table.get(index);
3266 
3267         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3268           K entryKey = e.getKey();
3269           if (e.getHash() == hash
3270               && entryKey != null
3271               && map.keyEquivalence.equivalent(key, entryKey)) {
3272             ValueReference<K, V> valueReference = e.getValueReference();
3273             V entryValue = valueReference.get();
3274             // replace the old LoadingValueReference if it's live, otherwise
3275             // perform a putIfAbsent
3276             if (oldValueReference == valueReference
3277                 || (entryValue == null && valueReference != UNSET)) {
3278               ++modCount;
3279               if (oldValueReference.isActive()) {
3280                 RemovalCause cause =
3281                     (entryValue == null) ? RemovalCause.COLLECTED : RemovalCause.REPLACED;
3282                 enqueueNotification(key, hash, entryValue, oldValueReference.getWeight(), cause);
3283                 newCount--;
3284               }
3285               setValue(e, key, newValue, now);
3286               this.count = newCount; // write-volatile
3287               evictEntries(e);
3288               return true;
3289             }
3290 
3291             // the loaded value was already clobbered
3292             enqueueNotification(key, hash, newValue, 0, RemovalCause.REPLACED);
3293             return false;
3294           }
3295         }
3296 
3297         ++modCount;
3298         ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
3299         setValue(newEntry, key, newValue, now);
3300         table.set(index, newEntry);
3301         this.count = newCount; // write-volatile
3302         evictEntries(newEntry);
3303         return true;
3304       } finally {
3305         unlock();
3306         postWriteCleanup();
3307       }
3308     }
3309 
3310     boolean remove(Object key, int hash, Object value) {
3311       lock();
3312       try {
3313         long now = map.ticker.read();
3314         preWriteCleanup(now);
3315 
3316         int newCount = this.count - 1;
3317         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3318         int index = hash & (table.length() - 1);
3319         ReferenceEntry<K, V> first = table.get(index);
3320 
3321         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3322           K entryKey = e.getKey();
3323           if (e.getHash() == hash
3324               && entryKey != null
3325               && map.keyEquivalence.equivalent(key, entryKey)) {
3326             ValueReference<K, V> valueReference = e.getValueReference();
3327             V entryValue = valueReference.get();
3328 
3329             RemovalCause cause;
3330             if (map.valueEquivalence.equivalent(value, entryValue)) {
3331               cause = RemovalCause.EXPLICIT;
3332             } else if (entryValue == null && valueReference.isActive()) {
3333               cause = RemovalCause.COLLECTED;
3334             } else {
3335               // currently loading
3336               return false;
3337             }
3338 
3339             ++modCount;
3340             ReferenceEntry<K, V> newFirst =
3341                 removeValueFromChain(first, e, entryKey, hash, entryValue, valueReference, cause);
3342             newCount = this.count - 1;
3343             table.set(index, newFirst);
3344             this.count = newCount; // write-volatile
3345             return (cause == RemovalCause.EXPLICIT);
3346           }
3347         }
3348 
3349         return false;
3350       } finally {
3351         unlock();
3352         postWriteCleanup();
3353       }
3354     }
3355 
3356     void clear() {
3357       if (count != 0) { // read-volatile
3358         lock();
3359         try {
3360           long now = map.ticker.read();
3361           preWriteCleanup(now);
3362 
3363           AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3364           for (int i = 0; i < table.length(); ++i) {
3365             for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
3366               // Loading references aren't actually in the map yet.
3367               if (e.getValueReference().isActive()) {
3368                 K key = e.getKey();
3369                 V value = e.getValueReference().get();
3370                 RemovalCause cause =
3371                     (key == null || value == null) ? RemovalCause.COLLECTED : RemovalCause.EXPLICIT;
3372                 enqueueNotification(
3373                     key, e.getHash(), value, e.getValueReference().getWeight(), cause);
3374               }
3375             }
3376           }
3377           for (int i = 0; i < table.length(); ++i) {
3378             table.set(i, null);
3379           }
3380           clearReferenceQueues();
3381           writeQueue.clear();
3382           accessQueue.clear();
3383           readCount.set(0);
3384 
3385           ++modCount;
3386           count = 0; // write-volatile
3387         } finally {
3388           unlock();
3389           postWriteCleanup();
3390         }
3391       }
3392     }
3393 
3394     @GuardedBy("this")
3395     @Nullable
3396     ReferenceEntry<K, V> removeValueFromChain(
3397         ReferenceEntry<K, V> first,
3398         ReferenceEntry<K, V> entry,
3399         @Nullable K key,
3400         int hash,
3401         V value,
3402         ValueReference<K, V> valueReference,
3403         RemovalCause cause) {
3404       enqueueNotification(key, hash, value, valueReference.getWeight(), cause);
3405       writeQueue.remove(entry);
3406       accessQueue.remove(entry);
3407 
3408       if (valueReference.isLoading()) {
3409         valueReference.notifyNewValue(null);
3410         return first;
3411       } else {
3412         return removeEntryFromChain(first, entry);
3413       }
3414     }
3415 
3416     @GuardedBy("this")
3417     @Nullable
3418     ReferenceEntry<K, V> removeEntryFromChain(
3419         ReferenceEntry<K, V> first, ReferenceEntry<K, V> entry) {
3420       int newCount = count;
3421       ReferenceEntry<K, V> newFirst = entry.getNext();
3422       for (ReferenceEntry<K, V> e = first; e != entry; e = e.getNext()) {
3423         ReferenceEntry<K, V> next = copyEntry(e, newFirst);
3424         if (next != null) {
3425           newFirst = next;
3426         } else {
3427           removeCollectedEntry(e);
3428           newCount--;
3429         }
3430       }
3431       this.count = newCount;
3432       return newFirst;
3433     }
3434 
3435     @GuardedBy("this")
3436     void removeCollectedEntry(ReferenceEntry<K, V> entry) {
3437       enqueueNotification(
3438           entry.getKey(),
3439           entry.getHash(),
3440           entry.getValueReference().get(),
3441           entry.getValueReference().getWeight(),
3442           RemovalCause.COLLECTED);
3443       writeQueue.remove(entry);
3444       accessQueue.remove(entry);
3445     }
3446 
3447     /**
3448      * Removes an entry whose key has been garbage collected.
3449      */
3450     boolean reclaimKey(ReferenceEntry<K, V> entry, int hash) {
3451       lock();
3452       try {
3453         int newCount = count - 1;
3454         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3455         int index = hash & (table.length() - 1);
3456         ReferenceEntry<K, V> first = table.get(index);
3457 
3458         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3459           if (e == entry) {
3460             ++modCount;
3461             ReferenceEntry<K, V> newFirst =
3462                 removeValueFromChain(
3463                     first,
3464                     e,
3465                     e.getKey(),
3466                     hash,
3467                     e.getValueReference().get(),
3468                     e.getValueReference(),
3469                     RemovalCause.COLLECTED);
3470             newCount = this.count - 1;
3471             table.set(index, newFirst);
3472             this.count = newCount; // write-volatile
3473             return true;
3474           }
3475         }
3476 
3477         return false;
3478       } finally {
3479         unlock();
3480         postWriteCleanup();
3481       }
3482     }
3483 
3484     /**
3485      * Removes an entry whose value has been garbage collected.
3486      */
3487     boolean reclaimValue(K key, int hash, ValueReference<K, V> valueReference) {
3488       lock();
3489       try {
3490         int newCount = this.count - 1;
3491         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3492         int index = hash & (table.length() - 1);
3493         ReferenceEntry<K, V> first = table.get(index);
3494 
3495         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3496           K entryKey = e.getKey();
3497           if (e.getHash() == hash
3498               && entryKey != null
3499               && map.keyEquivalence.equivalent(key, entryKey)) {
3500             ValueReference<K, V> v = e.getValueReference();
3501             if (v == valueReference) {
3502               ++modCount;
3503               ReferenceEntry<K, V> newFirst =
3504                   removeValueFromChain(
3505                       first,
3506                       e,
3507                       entryKey,
3508                       hash,
3509                       valueReference.get(),
3510                       valueReference,
3511                       RemovalCause.COLLECTED);
3512               newCount = this.count - 1;
3513               table.set(index, newFirst);
3514               this.count = newCount; // write-volatile
3515               return true;
3516             }
3517             return false;
3518           }
3519         }
3520 
3521         return false;
3522       } finally {
3523         unlock();
3524         if (!isHeldByCurrentThread()) { // don't cleanup inside of put
3525           postWriteCleanup();
3526         }
3527       }
3528     }
3529 
3530     boolean removeLoadingValue(K key, int hash, LoadingValueReference<K, V> valueReference) {
3531       lock();
3532       try {
3533         AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3534         int index = hash & (table.length() - 1);
3535         ReferenceEntry<K, V> first = table.get(index);
3536 
3537         for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3538           K entryKey = e.getKey();
3539           if (e.getHash() == hash
3540               && entryKey != null
3541               && map.keyEquivalence.equivalent(key, entryKey)) {
3542             ValueReference<K, V> v = e.getValueReference();
3543             if (v == valueReference) {
3544               if (valueReference.isActive()) {
3545                 e.setValueReference(valueReference.getOldValue());
3546               } else {
3547                 ReferenceEntry<K, V> newFirst = removeEntryFromChain(first, e);
3548                 table.set(index, newFirst);
3549               }
3550               return true;
3551             }
3552             return false;
3553           }
3554         }
3555 
3556         return false;
3557       } finally {
3558         unlock();
3559         postWriteCleanup();
3560       }
3561     }
3562 
3563     @VisibleForTesting
3564     @GuardedBy("this")
3565     boolean removeEntry(ReferenceEntry<K, V> entry, int hash, RemovalCause cause) {
3566       int newCount = this.count - 1;
3567       AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
3568       int index = hash & (table.length() - 1);
3569       ReferenceEntry<K, V> first = table.get(index);
3570 
3571       for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
3572         if (e == entry) {
3573           ++modCount;
3574           ReferenceEntry<K, V> newFirst =
3575               removeValueFromChain(
3576                   first,
3577                   e,
3578                   e.getKey(),
3579                   hash,
3580                   e.getValueReference().get(),
3581                   e.getValueReference(),
3582                   cause);
3583           newCount = this.count - 1;
3584           table.set(index, newFirst);
3585           this.count = newCount; // write-volatile
3586           return true;
3587         }
3588       }
3589 
3590       return false;
3591     }
3592 
3593     /**
3594      * Performs routine cleanup following a read. Normally cleanup happens during writes. If cleanup
3595      * is not observed after a sufficient number of reads, try cleaning up from the read thread.
3596      */
3597     void postReadCleanup() {
3598       if ((readCount.incrementAndGet() & DRAIN_THRESHOLD) == 0) {
3599         cleanUp();
3600       }
3601     }
3602 
3603     /**
3604      * Performs routine cleanup prior to executing a write. This should be called every time a write
3605      * thread acquires the segment lock, immediately after acquiring the lock.
3606      *
3607      * <p>Post-condition: expireEntries has been run.
3608      */
3609     @GuardedBy("this")
3610     void preWriteCleanup(long now) {
3611       runLockedCleanup(now);
3612     }
3613 
3614     /**
3615      * Performs routine cleanup following a write.
3616      */
3617     void postWriteCleanup() {
3618       runUnlockedCleanup();
3619     }
3620 
3621     void cleanUp() {
3622       long now = map.ticker.read();
3623       runLockedCleanup(now);
3624       runUnlockedCleanup();
3625     }
3626 
3627     void runLockedCleanup(long now) {
3628       if (tryLock()) {
3629         try {
3630           drainReferenceQueues();
3631           expireEntries(now); // calls drainRecencyQueue
3632           readCount.set(0);
3633         } finally {
3634           unlock();
3635         }
3636       }
3637     }
3638 
3639     void runUnlockedCleanup() {
3640       // locked cleanup may generate notifications we can send unlocked
3641       if (!isHeldByCurrentThread()) {
3642         map.processPendingNotifications();
3643       }
3644     }
3645   }
3646 
3647   static class LoadingValueReference<K, V> implements ValueReference<K, V> {
3648     volatile ValueReference<K, V> oldValue;
3649 
3650     // TODO(fry): rename get, then extend AbstractFuture instead of containing SettableFuture
3651     final SettableFuture<V> futureValue = SettableFuture.create();
3652     final Stopwatch stopwatch = Stopwatch.createUnstarted();
3653 
3654     public LoadingValueReference() {
3655       this(null);
3656     }
3657 
3658     public LoadingValueReference(ValueReference<K, V> oldValue) {
3659       this.oldValue = (oldValue == null) ? LocalCache.<K, V>unset() : oldValue;
3660     }
3661 
3662     @Override
3663     public boolean isLoading() {
3664       return true;
3665     }
3666 
3667     @Override
3668     public boolean isActive() {
3669       return oldValue.isActive();
3670     }
3671 
3672     @Override
3673     public int getWeight() {
3674       return oldValue.getWeight();
3675     }
3676 
3677     public boolean set(@Nullable V newValue) {
3678       return futureValue.set(newValue);
3679     }
3680 
3681     public boolean setException(Throwable t) {
3682       return futureValue.setException(t);
3683     }
3684 
3685     private ListenableFuture<V> fullyFailedFuture(Throwable t) {
3686       return Futures.immediateFailedFuture(t);
3687     }
3688 
3689     @Override
3690     public void notifyNewValue(@Nullable V newValue) {
3691       if (newValue != null) {
3692         // The pending load was clobbered by a manual write.
3693         // Unblock all pending gets, and have them return the new value.
3694         set(newValue);
3695       } else {
3696         // The pending load was removed. Delay notifications until loading completes.
3697         oldValue = unset();
3698       }
3699 
3700       // TODO(fry): could also cancel loading if we had a handle on its future
3701     }
3702 
3703     public ListenableFuture<V> loadFuture(K key, CacheLoader<? super K, V> loader) {
3704       try {
3705         stopwatch.start();
3706         V previousValue = oldValue.get();
3707         if (previousValue == null) {
3708           V newValue = loader.load(key);
3709           return set(newValue) ? futureValue : Futures.immediateFuture(newValue);
3710         }
3711         ListenableFuture<V> newValue = loader.reload(key, previousValue);
3712         if (newValue == null) {
3713           return Futures.immediateFuture(null);
3714         }
3715         // To avoid a race, make sure the refreshed value is set into loadingValueReference
3716         // *before* returning newValue from the cache query.
3717         return transform(
3718             newValue,
3719             new com.google.common.base.Function<V, V>() {
3720               @Override
3721               public V apply(V newValue) {
3722                 LoadingValueReference.this.set(newValue);
3723                 return newValue;
3724               }
3725             },
3726             directExecutor());
3727       } catch (Throwable t) {
3728         ListenableFuture<V> result = setException(t) ? futureValue : fullyFailedFuture(t);
3729         if (t instanceof InterruptedException) {
3730           Thread.currentThread().interrupt();
3731         }
3732         return result;
3733       }
3734     }
3735 
3736     public V compute(K key, BiFunction<? super K, ? super V, ? extends V> function) {
3737       stopwatch.start();
3738       V previousValue;
3739       try {
3740         previousValue = oldValue.waitForValue();
3741       } catch (ExecutionException e) {
3742         previousValue = null;
3743       }
3744       V newValue = function.apply(key, previousValue);
3745       this.set(newValue);
3746       return newValue;
3747     }
3748 
3749     public long elapsedNanos() {
3750       return stopwatch.elapsed(NANOSECONDS);
3751     }
3752 
3753     @Override
3754     public V waitForValue() throws ExecutionException {
3755       return getUninterruptibly(futureValue);
3756     }
3757 
3758     @Override
3759     public V get() {
3760       return oldValue.get();
3761     }
3762 
3763     public ValueReference<K, V> getOldValue() {
3764       return oldValue;
3765     }
3766 
3767     @Override
3768     public ReferenceEntry<K, V> getEntry() {
3769       return null;
3770     }
3771 
3772     @Override
3773     public ValueReference<K, V> copyFor(
3774         ReferenceQueue<V> queue, @Nullable V value, ReferenceEntry<K, V> entry) {
3775       return this;
3776     }
3777   }
3778 
3779   // Queues
3780 
3781   /**
3782    * A custom queue for managing eviction order. Note that this is tightly integrated with {@code
3783    * ReferenceEntry}, upon which it relies to perform its linking.
3784    *
3785    * <p>Note that this entire implementation makes the assumption that all elements which are in the
3786    * map are also in this queue, and that all elements not in the queue are not in the map.
3787    *
3788    * <p>The benefits of creating our own queue are that (1) we can replace elements in the middle of
3789    * the queue as part of copyWriteEntry, and (2) the contains method is highly optimized for the
3790    * current model.
3791    */
3792   static final class WriteQueue<K, V> extends AbstractQueue<ReferenceEntry<K, V>> {
3793     final ReferenceEntry<K, V> head =
3794         new AbstractReferenceEntry<K, V>() {
3795 
3796           @Override
3797           public long getWriteTime() {
3798             return Long.MAX_VALUE;
3799           }
3800 
3801           @Override
3802           public void setWriteTime(long time) {}
3803 
3804           ReferenceEntry<K, V> nextWrite = this;
3805 
3806           @Override
3807           public ReferenceEntry<K, V> getNextInWriteQueue() {
3808             return nextWrite;
3809           }
3810 
3811           @Override
3812           public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
3813             this.nextWrite = next;
3814           }
3815 
3816           ReferenceEntry<K, V> previousWrite = this;
3817 
3818           @Override
3819           public ReferenceEntry<K, V> getPreviousInWriteQueue() {
3820             return previousWrite;
3821           }
3822 
3823           @Override
3824           public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
3825             this.previousWrite = previous;
3826           }
3827         };
3828 
3829     // implements Queue
3830 
3831     @Override
3832     public boolean offer(ReferenceEntry<K, V> entry) {
3833       // unlink
3834       connectWriteOrder(entry.getPreviousInWriteQueue(), entry.getNextInWriteQueue());
3835 
3836       // add to tail
3837       connectWriteOrder(head.getPreviousInWriteQueue(), entry);
3838       connectWriteOrder(entry, head);
3839 
3840       return true;
3841     }
3842 
3843     @Override
3844     public ReferenceEntry<K, V> peek() {
3845       ReferenceEntry<K, V> next = head.getNextInWriteQueue();
3846       return (next == head) ? null : next;
3847     }
3848 
3849     @Override
3850     public ReferenceEntry<K, V> poll() {
3851       ReferenceEntry<K, V> next = head.getNextInWriteQueue();
3852       if (next == head) {
3853         return null;
3854       }
3855 
3856       remove(next);
3857       return next;
3858     }
3859 
3860     @Override
3861     @SuppressWarnings("unchecked")
3862     public boolean remove(Object o) {
3863       ReferenceEntry<K, V> e = (ReferenceEntry) o;
3864       ReferenceEntry<K, V> previous = e.getPreviousInWriteQueue();
3865       ReferenceEntry<K, V> next = e.getNextInWriteQueue();
3866       connectWriteOrder(previous, next);
3867       nullifyWriteOrder(e);
3868 
3869       return next != NullEntry.INSTANCE;
3870     }
3871 
3872     @Override
3873     @SuppressWarnings("unchecked")
3874     public boolean contains(Object o) {
3875       ReferenceEntry<K, V> e = (ReferenceEntry) o;
3876       return e.getNextInWriteQueue() != NullEntry.INSTANCE;
3877     }
3878 
3879     @Override
3880     public boolean isEmpty() {
3881       return head.getNextInWriteQueue() == head;
3882     }
3883 
3884     @Override
3885     public int size() {
3886       int size = 0;
3887       for (ReferenceEntry<K, V> e = head.getNextInWriteQueue();
3888           e != head;
3889           e = e.getNextInWriteQueue()) {
3890         size++;
3891       }
3892       return size;
3893     }
3894 
3895     @Override
3896     public void clear() {
3897       ReferenceEntry<K, V> e = head.getNextInWriteQueue();
3898       while (e != head) {
3899         ReferenceEntry<K, V> next = e.getNextInWriteQueue();
3900         nullifyWriteOrder(e);
3901         e = next;
3902       }
3903 
3904       head.setNextInWriteQueue(head);
3905       head.setPreviousInWriteQueue(head);
3906     }
3907 
3908     @Override
3909     public Iterator<ReferenceEntry<K, V>> iterator() {
3910       return new AbstractSequentialIterator<ReferenceEntry<K, V>>(peek()) {
3911         @Override
3912         protected ReferenceEntry<K, V> computeNext(ReferenceEntry<K, V> previous) {
3913           ReferenceEntry<K, V> next = previous.getNextInWriteQueue();
3914           return (next == head) ? null : next;
3915         }
3916       };
3917     }
3918   }
3919 
3920   /**
3921    * A custom queue for managing access order. Note that this is tightly integrated with
3922    * {@code ReferenceEntry}, upon which it relies to perform its linking.
3923    *
3924    * <p>Note that this entire implementation makes the assumption that all elements which are in the
3925    * map are also in this queue, and that all elements not in the queue are not in the map.
3926    *
3927    * <p>The benefits of creating our own queue are that (1) we can replace elements in the middle of
3928    * the queue as part of copyWriteEntry, and (2) the contains method is highly optimized for the
3929    * current model.
3930    */
3931   static final class AccessQueue<K, V> extends AbstractQueue<ReferenceEntry<K, V>> {
3932     final ReferenceEntry<K, V> head =
3933         new AbstractReferenceEntry<K, V>() {
3934 
3935           @Override
3936           public long getAccessTime() {
3937             return Long.MAX_VALUE;
3938           }
3939 
3940           @Override
3941           public void setAccessTime(long time) {}
3942 
3943           ReferenceEntry<K, V> nextAccess = this;
3944 
3945           @Override
3946           public ReferenceEntry<K, V> getNextInAccessQueue() {
3947             return nextAccess;
3948           }
3949 
3950           @Override
3951           public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
3952             this.nextAccess = next;
3953           }
3954 
3955           ReferenceEntry<K, V> previousAccess = this;
3956 
3957           @Override
3958           public ReferenceEntry<K, V> getPreviousInAccessQueue() {
3959             return previousAccess;
3960           }
3961 
3962           @Override
3963           public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
3964             this.previousAccess = previous;
3965           }
3966         };
3967 
3968     // implements Queue
3969 
3970     @Override
3971     public boolean offer(ReferenceEntry<K, V> entry) {
3972       // unlink
3973       connectAccessOrder(entry.getPreviousInAccessQueue(), entry.getNextInAccessQueue());
3974 
3975       // add to tail
3976       connectAccessOrder(head.getPreviousInAccessQueue(), entry);
3977       connectAccessOrder(entry, head);
3978 
3979       return true;
3980     }
3981 
3982     @Override
3983     public ReferenceEntry<K, V> peek() {
3984       ReferenceEntry<K, V> next = head.getNextInAccessQueue();
3985       return (next == head) ? null : next;
3986     }
3987 
3988     @Override
3989     public ReferenceEntry<K, V> poll() {
3990       ReferenceEntry<K, V> next = head.getNextInAccessQueue();
3991       if (next == head) {
3992         return null;
3993       }
3994 
3995       remove(next);
3996       return next;
3997     }
3998 
3999     @Override
4000     @SuppressWarnings("unchecked")
4001     public boolean remove(Object o) {
4002       ReferenceEntry<K, V> e = (ReferenceEntry) o;
4003       ReferenceEntry<K, V> previous = e.getPreviousInAccessQueue();
4004       ReferenceEntry<K, V> next = e.getNextInAccessQueue();
4005       connectAccessOrder(previous, next);
4006       nullifyAccessOrder(e);
4007 
4008       return next != NullEntry.INSTANCE;
4009     }
4010 
4011     @Override
4012     @SuppressWarnings("unchecked")
4013     public boolean contains(Object o) {
4014       ReferenceEntry<K, V> e = (ReferenceEntry) o;
4015       return e.getNextInAccessQueue() != NullEntry.INSTANCE;
4016     }
4017 
4018     @Override
4019     public boolean isEmpty() {
4020       return head.getNextInAccessQueue() == head;
4021     }
4022 
4023     @Override
4024     public int size() {
4025       int size = 0;
4026       for (ReferenceEntry<K, V> e = head.getNextInAccessQueue();
4027           e != head;
4028           e = e.getNextInAccessQueue()) {
4029         size++;
4030       }
4031       return size;
4032     }
4033 
4034     @Override
4035     public void clear() {
4036       ReferenceEntry<K, V> e = head.getNextInAccessQueue();
4037       while (e != head) {
4038         ReferenceEntry<K, V> next = e.getNextInAccessQueue();
4039         nullifyAccessOrder(e);
4040         e = next;
4041       }
4042 
4043       head.setNextInAccessQueue(head);
4044       head.setPreviousInAccessQueue(head);
4045     }
4046 
4047     @Override
4048     public Iterator<ReferenceEntry<K, V>> iterator() {
4049       return new AbstractSequentialIterator<ReferenceEntry<K, V>>(peek()) {
4050         @Override
4051         protected ReferenceEntry<K, V> computeNext(ReferenceEntry<K, V> previous) {
4052           ReferenceEntry<K, V> next = previous.getNextInAccessQueue();
4053           return (next == head) ? null : next;
4054         }
4055       };
4056     }
4057   }
4058 
4059   // Cache support
4060 
4061   public void cleanUp() {
4062     for (Segment<?, ?> segment : segments) {
4063       segment.cleanUp();
4064     }
4065   }
4066 
4067   // ConcurrentMap methods
4068 
4069   @Override
4070   public boolean isEmpty() {
4071     /*
4072      * Sum per-segment modCounts to avoid mis-reporting when elements are concurrently added and
4073      * removed in one segment while checking another, in which case the table was never actually
4074      * empty at any point. (The sum ensures accuracy up through at least 1<<31 per-segment
4075      * modifications before recheck.) Method containsValue() uses similar constructions for
4076      * stability checks.
4077      */
4078     long sum = 0L;
4079     Segment<K, V>[] segments = this.segments;
4080     for (int i = 0; i < segments.length; ++i) {
4081       if (segments[i].count != 0) {
4082         return false;
4083       }
4084       sum += segments[i].modCount;
4085     }
4086 
4087     if (sum != 0L) { // recheck unless no modifications
4088       for (int i = 0; i < segments.length; ++i) {
4089         if (segments[i].count != 0) {
4090           return false;
4091         }
4092         sum -= segments[i].modCount;
4093       }
4094       if (sum != 0L) {
4095         return false;
4096       }
4097     }
4098     return true;
4099   }
4100 
4101   long longSize() {
4102     Segment<K, V>[] segments = this.segments;
4103     long sum = 0;
4104     for (int i = 0; i < segments.length; ++i) {
4105       sum += Math.max(0, segments[i].count); // see https://github.com/google/guava/issues/2108
4106     }
4107     return sum;
4108   }
4109 
4110   @Override
4111   public int size() {
4112     return Ints.saturatedCast(longSize());
4113   }
4114 
4115   @Override
4116   @Nullable
4117   public V get(@Nullable Object key) {
4118     if (key == null) {
4119       return null;
4120     }
4121     int hash = hash(key);
4122     return segmentFor(hash).get(key, hash);
4123   }
4124 
4125   @Nullable
4126   public V getIfPresent(Object key) {
4127     int hash = hash(checkNotNull(key));
4128     V value = segmentFor(hash).get(key, hash);
4129     if (value == null) {
4130       globalStatsCounter.recordMisses(1);
4131     } else {
4132       globalStatsCounter.recordHits(1);
4133     }
4134     return value;
4135   }
4136 
4137   // Only becomes available in Java 8 when it's on the interface.
4138   // @Override
4139   @Nullable
4140   public V getOrDefault(@Nullable Object key, @Nullable V defaultValue) {
4141     V result = get(key);
4142     return (result != null) ? result : defaultValue;
4143   }
4144 
4145   V get(K key, CacheLoader<? super K, V> loader) throws ExecutionException {
4146     int hash = hash(checkNotNull(key));
4147     return segmentFor(hash).get(key, hash, loader);
4148   }
4149 
4150   V getOrLoad(K key) throws ExecutionException {
4151     return get(key, defaultLoader);
4152   }
4153 
4154   ImmutableMap<K, V> getAllPresent(Iterable<?> keys) {
4155     int hits = 0;
4156     int misses = 0;
4157 
4158     Map<K, V> result = Maps.newLinkedHashMap();
4159     for (Object key : keys) {
4160       V value = get(key);
4161       if (value == null) {
4162         misses++;
4163       } else {
4164         // TODO(fry): store entry key instead of query key
4165         @SuppressWarnings("unchecked")
4166         K castKey = (K) key;
4167         result.put(castKey, value);
4168         hits++;
4169       }
4170     }
4171     globalStatsCounter.recordHits(hits);
4172     globalStatsCounter.recordMisses(misses);
4173     return ImmutableMap.copyOf(result);
4174   }
4175 
4176   ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
4177     int hits = 0;
4178     int misses = 0;
4179 
4180     Map<K, V> result = Maps.newLinkedHashMap();
4181     Set<K> keysToLoad = Sets.newLinkedHashSet();
4182     for (K key : keys) {
4183       V value = get(key);
4184       if (!result.containsKey(key)) {
4185         result.put(key, value);
4186         if (value == null) {
4187           misses++;
4188           keysToLoad.add(key);
4189         } else {
4190           hits++;
4191         }
4192       }
4193     }
4194 
4195     try {
4196       if (!keysToLoad.isEmpty()) {
4197         try {
4198           Map<K, V> newEntries = loadAll(keysToLoad, defaultLoader);
4199           for (K key : keysToLoad) {
4200             V value = newEntries.get(key);
4201             if (value == null) {
4202               throw new InvalidCacheLoadException("loadAll failed to return a value for " + key);
4203             }
4204             result.put(key, value);
4205           }
4206         } catch (UnsupportedLoadingOperationException e) {
4207           // loadAll not implemented, fallback to load
4208           for (K key : keysToLoad) {
4209             misses--; // get will count this miss
4210             result.put(key, get(key, defaultLoader));
4211           }
4212         }
4213       }
4214       return ImmutableMap.copyOf(result);
4215     } finally {
4216       globalStatsCounter.recordHits(hits);
4217       globalStatsCounter.recordMisses(misses);
4218     }
4219   }
4220 
4221   /**
4222    * Returns the result of calling {@link CacheLoader#loadAll}, or null if {@code loader} doesn't
4223    * implement {@code loadAll}.
4224    */
4225   @Nullable
4226   Map<K, V> loadAll(Set<? extends K> keys, CacheLoader<? super K, V> loader)
4227       throws ExecutionException {
4228     checkNotNull(loader);
4229     checkNotNull(keys);
4230     Stopwatch stopwatch = Stopwatch.createStarted();
4231     Map<K, V> result;
4232     boolean success = false;
4233     try {
4234       @SuppressWarnings("unchecked") // safe since all keys extend K
4235       Map<K, V> map = (Map<K, V>) loader.loadAll(keys);
4236       result = map;
4237       success = true;
4238     } catch (UnsupportedLoadingOperationException e) {
4239       success = true;
4240       throw e;
4241     } catch (InterruptedException e) {
4242       Thread.currentThread().interrupt();
4243       throw new ExecutionException(e);
4244     } catch (RuntimeException e) {
4245       throw new UncheckedExecutionException(e);
4246     } catch (Exception e) {
4247       throw new ExecutionException(e);
4248     } catch (Error e) {
4249       throw new ExecutionError(e);
4250     } finally {
4251       if (!success) {
4252         globalStatsCounter.recordLoadException(stopwatch.elapsed(NANOSECONDS));
4253       }
4254     }
4255 
4256     if (result == null) {
4257       globalStatsCounter.recordLoadException(stopwatch.elapsed(NANOSECONDS));
4258       throw new InvalidCacheLoadException(loader + " returned null map from loadAll");
4259     }
4260 
4261     stopwatch.stop();
4262     // TODO(fry): batch by segment
4263     boolean nullsPresent = false;
4264     for (Map.Entry<K, V> entry : result.entrySet()) {
4265       K key = entry.getKey();
4266       V value = entry.getValue();
4267       if (key == null || value == null) {
4268         // delay failure until non-null entries are stored
4269         nullsPresent = true;
4270       } else {
4271         put(key, value);
4272       }
4273     }
4274 
4275     if (nullsPresent) {
4276       globalStatsCounter.recordLoadException(stopwatch.elapsed(NANOSECONDS));
4277       throw new InvalidCacheLoadException(loader + " returned null keys or values from loadAll");
4278     }
4279 
4280     // TODO(fry): record count of loaded entries
4281     globalStatsCounter.recordLoadSuccess(stopwatch.elapsed(NANOSECONDS));
4282     return result;
4283   }
4284 
4285   /**
4286    * Returns the internal entry for the specified key. The entry may be loading, expired, or
4287    * partially collected.
4288    */
4289   ReferenceEntry<K, V> getEntry(@Nullable Object key) {
4290     // does not impact recency ordering
4291     if (key == null) {
4292       return null;
4293     }
4294     int hash = hash(key);
4295     return segmentFor(hash).getEntry(key, hash);
4296   }
4297 
4298   void refresh(K key) {
4299     int hash = hash(checkNotNull(key));
4300     segmentFor(hash).refresh(key, hash, defaultLoader, false);
4301   }
4302 
4303   @Override
4304   public boolean containsKey(@Nullable Object key) {
4305     // does not impact recency ordering
4306     if (key == null) {
4307       return false;
4308     }
4309     int hash = hash(key);
4310     return segmentFor(hash).containsKey(key, hash);
4311   }
4312 
4313   @Override
4314   public boolean containsValue(@Nullable Object value) {
4315     // does not impact recency ordering
4316     if (value == null) {
4317       return false;
4318     }
4319 
4320     // This implementation is patterned after ConcurrentHashMap, but without the locking. The only
4321     // way for it to return a false negative would be for the target value to jump around in the map
4322     // such that none of the subsequent iterations observed it, despite the fact that at every point
4323     // in time it was present somewhere int the map. This becomes increasingly unlikely as
4324     // CONTAINS_VALUE_RETRIES increases, though without locking it is theoretically possible.
4325     long now = ticker.read();
4326     final Segment<K, V>[] segments = this.segments;
4327     long last = -1L;
4328     for (int i = 0; i < CONTAINS_VALUE_RETRIES; i++) {
4329       long sum = 0L;
4330       for (Segment<K, V> segment : segments) {
4331         // ensure visibility of most recent completed write
4332         int unused = segment.count; // read-volatile
4333 
4334         AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
4335         for (int j = 0; j < table.length(); j++) {
4336           for (ReferenceEntry<K, V> e = table.get(j); e != null; e = e.getNext()) {
4337             V v = segment.getLiveValue(e, now);
4338             if (v != null && valueEquivalence.equivalent(value, v)) {
4339               return true;
4340             }
4341           }
4342         }
4343         sum += segment.modCount;
4344       }
4345       if (sum == last) {
4346         break;
4347       }
4348       last = sum;
4349     }
4350     return false;
4351   }
4352 
4353   @Override
4354   public V put(K key, V value) {
4355     checkNotNull(key);
4356     checkNotNull(value);
4357     int hash = hash(key);
4358     return segmentFor(hash).put(key, hash, value, false);
4359   }
4360 
4361   @Override
4362   public V putIfAbsent(K key, V value) {
4363     checkNotNull(key);
4364     checkNotNull(value);
4365     int hash = hash(key);
4366     return segmentFor(hash).put(key, hash, value, true);
4367   }
4368 
4369   @Override
4370   public V compute(K key, BiFunction<? super K, ? super V, ? extends V> function) {
4371     checkNotNull(key);
4372     checkNotNull(function);
4373     int hash = hash(key);
4374     return segmentFor(hash).compute(key, hash, function);
4375   }
4376 
4377   @Override
4378   public V computeIfAbsent(K key, Function<? super K, ? extends V> function) {
4379     checkNotNull(key);
4380     checkNotNull(function);
4381     return compute(key, (k, oldValue) -> (oldValue == null) ? function.apply(key) : oldValue);
4382   }
4383 
4384   @Override
4385   public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> function) {
4386     checkNotNull(key);
4387     checkNotNull(function);
4388     return compute(key, (k, oldValue) -> (oldValue == null) ? null : function.apply(k, oldValue));
4389   }
4390 
4391   @Override
4392   public V merge(K key, V newValue, BiFunction<? super V, ? super V, ? extends V> function) {
4393     checkNotNull(key);
4394     checkNotNull(newValue);
4395     checkNotNull(function);
4396     return compute(
4397         key, (k, oldValue) -> (oldValue == null) ? newValue : function.apply(oldValue, newValue));
4398   }
4399 
4400   @Override
4401   public void putAll(Map<? extends K, ? extends V> m) {
4402     for (Entry<? extends K, ? extends V> e : m.entrySet()) {
4403       put(e.getKey(), e.getValue());
4404     }
4405   }
4406 
4407   @Override
4408   public V remove(@Nullable Object key) {
4409     if (key == null) {
4410       return null;
4411     }
4412     int hash = hash(key);
4413     return segmentFor(hash).remove(key, hash);
4414   }
4415 
4416   @Override
4417   public boolean remove(@Nullable Object key, @Nullable Object value) {
4418     if (key == null || value == null) {
4419       return false;
4420     }
4421     int hash = hash(key);
4422     return segmentFor(hash).remove(key, hash, value);
4423   }
4424 
4425   @Override
4426   public boolean replace(K key, @Nullable V oldValue, V newValue) {
4427     checkNotNull(key);
4428     checkNotNull(newValue);
4429     if (oldValue == null) {
4430       return false;
4431     }
4432     int hash = hash(key);
4433     return segmentFor(hash).replace(key, hash, oldValue, newValue);
4434   }
4435 
4436   @Override
4437   public V replace(K key, V value) {
4438     checkNotNull(key);
4439     checkNotNull(value);
4440     int hash = hash(key);
4441     return segmentFor(hash).replace(key, hash, value);
4442   }
4443 
4444   @Override
4445   public void clear() {
4446     for (Segment<K, V> segment : segments) {
4447       segment.clear();
4448     }
4449   }
4450 
4451   void invalidateAll(Iterable<?> keys) {
4452     // TODO(fry): batch by segment
4453     for (Object key : keys) {
4454       remove(key);
4455     }
4456   }
4457 
4458   Set<K> keySet;
4459 
4460   @Override
4461   public Set<K> keySet() {
4462     // does not impact recency ordering
4463     Set<K> ks = keySet;
4464     return (ks != null) ? ks : (keySet = new KeySet(this));
4465   }
4466 
4467   Collection<V> values;
4468 
4469   @Override
4470   public Collection<V> values() {
4471     // does not impact recency ordering
4472     Collection<V> vs = values;
4473     return (vs != null) ? vs : (values = new Values(this));
4474   }
4475 
4476   Set<Entry<K, V>> entrySet;
4477 
4478   @Override
4479   @GwtIncompatible // Not supported.
4480   public Set<Entry<K, V>> entrySet() {
4481     // does not impact recency ordering
4482     Set<Entry<K, V>> es = entrySet;
4483     return (es != null) ? es : (entrySet = new EntrySet(this));
4484   }
4485 
4486   // Iterator Support
4487 
4488   abstract class HashIterator<T> implements Iterator<T> {
4489 
4490     int nextSegmentIndex;
4491     int nextTableIndex;
4492     Segment<K, V> currentSegment;
4493     AtomicReferenceArray<ReferenceEntry<K, V>> currentTable;
4494     ReferenceEntry<K, V> nextEntry;
4495     WriteThroughEntry nextExternal;
4496     WriteThroughEntry lastReturned;
4497 
4498     HashIterator() {
4499       nextSegmentIndex = segments.length - 1;
4500       nextTableIndex = -1;
4501       advance();
4502     }
4503 
4504     @Override
4505     public abstract T next();
4506 
4507     final void advance() {
4508       nextExternal = null;
4509 
4510       if (nextInChain()) {
4511         return;
4512       }
4513 
4514       if (nextInTable()) {
4515         return;
4516       }
4517 
4518       while (nextSegmentIndex >= 0) {
4519         currentSegment = segments[nextSegmentIndex--];
4520         if (currentSegment.count != 0) {
4521           currentTable = currentSegment.table;
4522           nextTableIndex = currentTable.length() - 1;
4523           if (nextInTable()) {
4524             return;
4525           }
4526         }
4527       }
4528     }
4529 
4530     /**
4531      * Finds the next entry in the current chain. Returns true if an entry was found.
4532      */
4533     boolean nextInChain() {
4534       if (nextEntry != null) {
4535         for (nextEntry = nextEntry.getNext(); nextEntry != null; nextEntry = nextEntry.getNext()) {
4536           if (advanceTo(nextEntry)) {
4537             return true;
4538           }
4539         }
4540       }
4541       return false;
4542     }
4543 
4544     /**
4545      * Finds the next entry in the current table. Returns true if an entry was found.
4546      */
4547     boolean nextInTable() {
4548       while (nextTableIndex >= 0) {
4549         if ((nextEntry = currentTable.get(nextTableIndex--)) != null) {
4550           if (advanceTo(nextEntry) || nextInChain()) {
4551             return true;
4552           }
4553         }
4554       }
4555       return false;
4556     }
4557 
4558     /**
4559      * Advances to the given entry. Returns true if the entry was valid, false if it should be
4560      * skipped.
4561      */
4562     boolean advanceTo(ReferenceEntry<K, V> entry) {
4563       try {
4564         long now = ticker.read();
4565         K key = entry.getKey();
4566         V value = getLiveValue(entry, now);
4567         if (value != null) {
4568           nextExternal = new WriteThroughEntry(key, value);
4569           return true;
4570         } else {
4571           // Skip stale entry.
4572           return false;
4573         }
4574       } finally {
4575         currentSegment.postReadCleanup();
4576       }
4577     }
4578 
4579     @Override
4580     public boolean hasNext() {
4581       return nextExternal != null;
4582     }
4583 
4584     WriteThroughEntry nextEntry() {
4585       if (nextExternal == null) {
4586         throw new NoSuchElementException();
4587       }
4588       lastReturned = nextExternal;
4589       advance();
4590       return lastReturned;
4591     }
4592 
4593     @Override
4594     public void remove() {
4595       checkState(lastReturned != null);
4596       LocalCache.this.remove(lastReturned.getKey());
4597       lastReturned = null;
4598     }
4599   }
4600 
4601   final class KeyIterator extends HashIterator<K> {
4602 
4603     @Override
4604     public K next() {
4605       return nextEntry().getKey();
4606     }
4607   }
4608 
4609   final class ValueIterator extends HashIterator<V> {
4610 
4611     @Override
4612     public V next() {
4613       return nextEntry().getValue();
4614     }
4615   }
4616 
4617   /**
4618    * Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying
4619    * map.
4620    */
4621   final class WriteThroughEntry implements Entry<K, V> {
4622     final K key; // non-null
4623     V value; // non-null
4624 
4625     WriteThroughEntry(K key, V value) {
4626       this.key = key;
4627       this.value = value;
4628     }
4629 
4630     @Override
4631     public K getKey() {
4632       return key;
4633     }
4634 
4635     @Override
4636     public V getValue() {
4637       return value;
4638     }
4639 
4640     @Override
4641     public boolean equals(@Nullable Object object) {
4642       // Cannot use key and value equivalence
4643       if (object instanceof Entry) {
4644         Entry<?, ?> that = (Entry<?, ?>) object;
4645         return key.equals(that.getKey()) && value.equals(that.getValue());
4646       }
4647       return false;
4648     }
4649 
4650     @Override
4651     public int hashCode() {
4652       // Cannot use key and value equivalence
4653       return key.hashCode() ^ value.hashCode();
4654     }
4655 
4656     @Override
4657     public V setValue(V newValue) {
4658       V oldValue = put(key, newValue);
4659       value = newValue; // only if put succeeds
4660       return oldValue;
4661     }
4662 
4663     @Override
4664     public String toString() {
4665       return getKey() + "=" + getValue();
4666     }
4667   }
4668 
4669   final class EntryIterator extends HashIterator<Entry<K, V>> {
4670 
4671     @Override
4672     public Entry<K, V> next() {
4673       return nextEntry();
4674     }
4675   }
4676 
4677   abstract class AbstractCacheSet<T> extends AbstractSet<T> {
4678     @Weak final ConcurrentMap<?, ?> map;
4679 
4680     AbstractCacheSet(ConcurrentMap<?, ?> map) {
4681       this.map = map;
4682     }
4683 
4684     @Override
4685     public int size() {
4686       return map.size();
4687     }
4688 
4689     @Override
4690     public boolean isEmpty() {
4691       return map.isEmpty();
4692     }
4693 
4694     @Override
4695     public void clear() {
4696       map.clear();
4697     }
4698 
4699     // super.toArray() may misbehave if size() is inaccurate, at least on old versions of Android.
4700     // https://code.google.com/p/android/issues/detail?id=36519 / http://r.android.com/47508
4701 
4702     @Override
4703     public Object[] toArray() {
4704       return toArrayList(this).toArray();
4705     }
4706 
4707     @Override
4708     public <E> E[] toArray(E[] a) {
4709       return toArrayList(this).toArray(a);
4710     }
4711   }
4712 
4713   private static <E> ArrayList<E> toArrayList(Collection<E> c) {
4714     // Avoid calling ArrayList(Collection), which may call back into toArray.
4715     ArrayList<E> result = new ArrayList<E>(c.size());
4716     Iterators.addAll(result, c.iterator());
4717     return result;
4718   }
4719 
4720   boolean removeIf(BiPredicate<? super K, ? super V> filter) {
4721     checkNotNull(filter);
4722     boolean changed = false;
4723     for (K key : keySet()) {
4724       while (true) {
4725         V value = get(key);
4726         if (value == null || !filter.test(key, value)) {
4727           break;
4728         } else if (LocalCache.this.remove(key, value)) {
4729           changed = true;
4730           break;
4731         }
4732       }
4733     }
4734     return changed;
4735   }
4736 
4737   @WeakOuter
4738   final class KeySet extends AbstractCacheSet<K> {
4739 
4740     KeySet(ConcurrentMap<?, ?> map) {
4741       super(map);
4742     }
4743 
4744     @Override
4745     public Iterator<K> iterator() {
4746       return new KeyIterator();
4747     }
4748 
4749     @Override
4750     public boolean contains(Object o) {
4751       return map.containsKey(o);
4752     }
4753 
4754     @Override
4755     public boolean remove(Object o) {
4756       return map.remove(o) != null;
4757     }
4758   }
4759 
4760   @WeakOuter
4761   final class Values extends AbstractCollection<V> {
4762     private final ConcurrentMap<?, ?> map;
4763 
4764     Values(ConcurrentMap<?, ?> map) {
4765       this.map = map;
4766     }
4767 
4768     @Override
4769     public int size() {
4770       return map.size();
4771     }
4772 
4773     @Override
4774     public boolean isEmpty() {
4775       return map.isEmpty();
4776     }
4777 
4778     @Override
4779     public void clear() {
4780       map.clear();
4781     }
4782 
4783     @Override
4784     public Iterator<V> iterator() {
4785       return new ValueIterator();
4786     }
4787 
4788     @Override
4789     public boolean removeIf(Predicate<? super V> filter) {
4790       checkNotNull(filter);
4791       return LocalCache.this.removeIf((k, v) -> filter.test(v));
4792     }
4793 
4794     @Override
4795     public boolean contains(Object o) {
4796       return map.containsValue(o);
4797     }
4798 
4799     // super.toArray() may misbehave if size() is inaccurate, at least on old versions of Android.
4800     // https://code.google.com/p/android/issues/detail?id=36519 / http://r.android.com/47508
4801 
4802     @Override
4803     public Object[] toArray() {
4804       return toArrayList(this).toArray();
4805     }
4806 
4807     @Override
4808     public <E> E[] toArray(E[] a) {
4809       return toArrayList(this).toArray(a);
4810     }
4811   }
4812 
4813   @WeakOuter
4814   final class EntrySet extends AbstractCacheSet<Entry<K, V>> {
4815 
4816     EntrySet(ConcurrentMap<?, ?> map) {
4817       super(map);
4818     }
4819 
4820     @Override
4821     public Iterator<Entry<K, V>> iterator() {
4822       return new EntryIterator();
4823     }
4824 
4825     @Override
4826     public boolean removeIf(Predicate<? super Entry<K, V>> filter) {
4827       checkNotNull(filter);
4828       return LocalCache.this.removeIf((k, v) -> filter.test(Maps.immutableEntry(k, v)));
4829     }
4830 
4831     @Override
4832     public boolean contains(Object o) {
4833       if (!(o instanceof Entry)) {
4834         return false;
4835       }
4836       Entry<?, ?> e = (Entry<?, ?>) o;
4837       Object key = e.getKey();
4838       if (key == null) {
4839         return false;
4840       }
4841       V v = LocalCache.this.get(key);
4842 
4843       return v != null && valueEquivalence.equivalent(e.getValue(), v);
4844     }
4845 
4846     @Override
4847     public boolean remove(Object o) {
4848       if (!(o instanceof Entry)) {
4849         return false;
4850       }
4851       Entry<?, ?> e = (Entry<?, ?>) o;
4852       Object key = e.getKey();
4853       return key != null && LocalCache.this.remove(key, e.getValue());
4854     }
4855   }
4856 
4857   // Serialization Support
4858 
4859   /**
4860    * Serializes the configuration of a LocalCache, reconstituting it as a Cache using CacheBuilder
4861    * upon deserialization. An instance of this class is fit for use by the writeReplace of
4862    * LocalManualCache.
4863    *
4864    * Unfortunately, readResolve() doesn't get called when a circular dependency is present, so the
4865    * proxy must be able to behave as the cache itself.
4866    */
4867   static class ManualSerializationProxy<K, V> extends ForwardingCache<K, V>
4868       implements Serializable {
4869     private static final long serialVersionUID = 1;
4870 
4871     final Strength keyStrength;
4872     final Strength valueStrength;
4873     final Equivalence<Object> keyEquivalence;
4874     final Equivalence<Object> valueEquivalence;
4875     final long expireAfterWriteNanos;
4876     final long expireAfterAccessNanos;
4877     final long maxWeight;
4878     final Weigher<K, V> weigher;
4879     final int concurrencyLevel;
4880     final RemovalListener<? super K, ? super V> removalListener;
4881     final Ticker ticker;
4882     final CacheLoader<? super K, V> loader;
4883 
4884     transient Cache<K, V> delegate;
4885 
4886     ManualSerializationProxy(LocalCache<K, V> cache) {
4887       this(
4888           cache.keyStrength,
4889           cache.valueStrength,
4890           cache.keyEquivalence,
4891           cache.valueEquivalence,
4892           cache.expireAfterWriteNanos,
4893           cache.expireAfterAccessNanos,
4894           cache.maxWeight,
4895           cache.weigher,
4896           cache.concurrencyLevel,
4897           cache.removalListener,
4898           cache.ticker,
4899           cache.defaultLoader);
4900     }
4901 
4902     private ManualSerializationProxy(
4903         Strength keyStrength,
4904         Strength valueStrength,
4905         Equivalence<Object> keyEquivalence,
4906         Equivalence<Object> valueEquivalence,
4907         long expireAfterWriteNanos,
4908         long expireAfterAccessNanos,
4909         long maxWeight,
4910         Weigher<K, V> weigher,
4911         int concurrencyLevel,
4912         RemovalListener<? super K, ? super V> removalListener,
4913         Ticker ticker,
4914         CacheLoader<? super K, V> loader) {
4915       this.keyStrength = keyStrength;
4916       this.valueStrength = valueStrength;
4917       this.keyEquivalence = keyEquivalence;
4918       this.valueEquivalence = valueEquivalence;
4919       this.expireAfterWriteNanos = expireAfterWriteNanos;
4920       this.expireAfterAccessNanos = expireAfterAccessNanos;
4921       this.maxWeight = maxWeight;
4922       this.weigher = weigher;
4923       this.concurrencyLevel = concurrencyLevel;
4924       this.removalListener = removalListener;
4925       this.ticker = (ticker == Ticker.systemTicker() || ticker == NULL_TICKER) ? null : ticker;
4926       this.loader = loader;
4927     }
4928 
4929     CacheBuilder<K, V> recreateCacheBuilder() {
4930       CacheBuilder<K, V> builder =
4931           CacheBuilder.newBuilder()
4932               .setKeyStrength(keyStrength)
4933               .setValueStrength(valueStrength)
4934               .keyEquivalence(keyEquivalence)
4935               .valueEquivalence(valueEquivalence)
4936               .concurrencyLevel(concurrencyLevel)
4937               .removalListener(removalListener);
4938       builder.strictParsing = false;
4939       if (expireAfterWriteNanos > 0) {
4940         builder.expireAfterWrite(expireAfterWriteNanos, TimeUnit.NANOSECONDS);
4941       }
4942       if (expireAfterAccessNanos > 0) {
4943         builder.expireAfterAccess(expireAfterAccessNanos, TimeUnit.NANOSECONDS);
4944       }
4945       if (weigher != OneWeigher.INSTANCE) {
4946         builder.weigher(weigher);
4947         if (maxWeight != UNSET_INT) {
4948           builder.maximumWeight(maxWeight);
4949         }
4950       } else {
4951         if (maxWeight != UNSET_INT) {
4952           builder.maximumSize(maxWeight);
4953         }
4954       }
4955       if (ticker != null) {
4956         builder.ticker(ticker);
4957       }
4958       return builder;
4959     }
4960 
4961     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
4962       in.defaultReadObject();
4963       CacheBuilder<K, V> builder = recreateCacheBuilder();
4964       this.delegate = builder.build();
4965     }
4966 
4967     private Object readResolve() {
4968       return delegate;
4969     }
4970 
4971     @Override
4972     protected Cache<K, V> delegate() {
4973       return delegate;
4974     }
4975   }
4976 
4977   /**
4978    * Serializes the configuration of a LocalCache, reconstituting it as an LoadingCache using
4979    * CacheBuilder upon deserialization. An instance of this class is fit for use by the writeReplace
4980    * of LocalLoadingCache.
4981    *
4982    * Unfortunately, readResolve() doesn't get called when a circular dependency is present, so the
4983    * proxy must be able to behave as the cache itself.
4984    */
4985   static final class LoadingSerializationProxy<K, V> extends ManualSerializationProxy<K, V>
4986       implements LoadingCache<K, V>, Serializable {
4987     private static final long serialVersionUID = 1;
4988 
4989     transient LoadingCache<K, V> autoDelegate;
4990 
4991     LoadingSerializationProxy(LocalCache<K, V> cache) {
4992       super(cache);
4993     }
4994 
4995     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
4996       in.defaultReadObject();
4997       CacheBuilder<K, V> builder = recreateCacheBuilder();
4998       this.autoDelegate = builder.build(loader);
4999     }
5000 
5001     @Override
5002     public V get(K key) throws ExecutionException {
5003       return autoDelegate.get(key);
5004     }
5005 
5006     @Override
5007     public V getUnchecked(K key) {
5008       return autoDelegate.getUnchecked(key);
5009     }
5010 
5011     @Override
5012     public ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
5013       return autoDelegate.getAll(keys);
5014     }
5015 
5016     @Override
5017     public final V apply(K key) {
5018       return autoDelegate.apply(key);
5019     }
5020 
5021     @Override
5022     public void refresh(K key) {
5023       autoDelegate.refresh(key);
5024     }
5025 
5026     private Object readResolve() {
5027       return autoDelegate;
5028     }
5029   }
5030 
5031   static class LocalManualCache<K, V> implements Cache<K, V>, Serializable {
5032     final LocalCache<K, V> localCache;
5033 
5034     LocalManualCache(CacheBuilder<? super K, ? super V> builder) {
5035       this(new LocalCache<K, V>(builder, null));
5036     }
5037 
5038     private LocalManualCache(LocalCache<K, V> localCache) {
5039       this.localCache = localCache;
5040     }
5041 
5042     // Cache methods
5043 
5044     @Override
5045     @Nullable
5046     public V getIfPresent(Object key) {
5047       return localCache.getIfPresent(key);
5048     }
5049 
5050     @Override
5051     public V get(K key, final Callable<? extends V> valueLoader) throws ExecutionException {
5052       checkNotNull(valueLoader);
5053       return localCache.get(
5054           key,
5055           new CacheLoader<Object, V>() {
5056             @Override
5057             public V load(Object key) throws Exception {
5058               return valueLoader.call();
5059             }
5060           });
5061     }
5062 
5063     @Override
5064     public ImmutableMap<K, V> getAllPresent(Iterable<?> keys) {
5065       return localCache.getAllPresent(keys);
5066     }
5067 
5068     @Override
5069     public void put(K key, V value) {
5070       localCache.put(key, value);
5071     }
5072 
5073     @Override
5074     public void putAll(Map<? extends K, ? extends V> m) {
5075       localCache.putAll(m);
5076     }
5077 
5078     @Override
5079     public void invalidate(Object key) {
5080       checkNotNull(key);
5081       localCache.remove(key);
5082     }
5083 
5084     @Override
5085     public void invalidateAll(Iterable<?> keys) {
5086       localCache.invalidateAll(keys);
5087     }
5088 
5089     @Override
5090     public void invalidateAll() {
5091       localCache.clear();
5092     }
5093 
5094     @Override
5095     public long size() {
5096       return localCache.longSize();
5097     }
5098 
5099     @Override
5100     public ConcurrentMap<K, V> asMap() {
5101       return localCache;
5102     }
5103 
5104     @Override
5105     public CacheStats stats() {
5106       SimpleStatsCounter aggregator = new SimpleStatsCounter();
5107       aggregator.incrementBy(localCache.globalStatsCounter);
5108       for (Segment<K, V> segment : localCache.segments) {
5109         aggregator.incrementBy(segment.statsCounter);
5110       }
5111       return aggregator.snapshot();
5112     }
5113 
5114     @Override
5115     public void cleanUp() {
5116       localCache.cleanUp();
5117     }
5118 
5119     // Serialization Support
5120 
5121     private static final long serialVersionUID = 1;
5122 
5123     Object writeReplace() {
5124       return new ManualSerializationProxy<>(localCache);
5125     }
5126   }
5127 
5128   static class LocalLoadingCache<K, V> extends LocalManualCache<K, V>
5129       implements LoadingCache<K, V> {
5130 
5131     LocalLoadingCache(
5132         CacheBuilder<? super K, ? super V> builder, CacheLoader<? super K, V> loader) {
5133       super(new LocalCache<K, V>(builder, checkNotNull(loader)));
5134     }
5135 
5136     // LoadingCache methods
5137 
5138     @Override
5139     public V get(K key) throws ExecutionException {
5140       return localCache.getOrLoad(key);
5141     }
5142 
5143     @Override
5144     public V getUnchecked(K key) {
5145       try {
5146         return get(key);
5147       } catch (ExecutionException e) {
5148         throw new UncheckedExecutionException(e.getCause());
5149       }
5150     }
5151 
5152     @Override
5153     public ImmutableMap<K, V> getAll(Iterable<? extends K> keys) throws ExecutionException {
5154       return localCache.getAll(keys);
5155     }
5156 
5157     @Override
5158     public void refresh(K key) {
5159       localCache.refresh(key);
5160     }
5161 
5162     @Override
5163     public final V apply(K key) {
5164       return getUnchecked(key);
5165     }
5166 
5167     // Serialization Support
5168 
5169     private static final long serialVersionUID = 1;
5170 
5171     @Override
5172     Object writeReplace() {
5173       return new LoadingSerializationProxy<>(localCache);
5174     }
5175   }
5176 }