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.collect;
16  
17  import static com.google.common.base.Preconditions.checkNotNull;
18  import static com.google.common.collect.CollectPreconditions.checkRemove;
19  
20  import com.google.common.annotations.GwtIncompatible;
21  import com.google.common.annotations.VisibleForTesting;
22  import com.google.common.base.Equivalence;
23  import com.google.common.collect.MapMaker.Dummy;
24  import com.google.common.primitives.Ints;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import com.google.j2objc.annotations.Weak;
27  import com.google.j2objc.annotations.WeakOuter;
28  import java.io.IOException;
29  import java.io.ObjectInputStream;
30  import java.io.ObjectOutputStream;
31  import java.io.Serializable;
32  import java.lang.ref.Reference;
33  import java.lang.ref.ReferenceQueue;
34  import java.lang.ref.WeakReference;
35  import java.util.AbstractCollection;
36  import java.util.AbstractMap;
37  import java.util.AbstractSet;
38  import java.util.ArrayList;
39  import java.util.Collection;
40  import java.util.Iterator;
41  import java.util.Map;
42  import java.util.NoSuchElementException;
43  import java.util.Set;
44  import java.util.concurrent.CancellationException;
45  import java.util.concurrent.ConcurrentMap;
46  import java.util.concurrent.atomic.AtomicInteger;
47  import java.util.concurrent.atomic.AtomicReferenceArray;
48  import java.util.concurrent.locks.ReentrantLock;
49  import javax.annotation.Nullable;
50  import javax.annotation.concurrent.GuardedBy;
51  
52  /**
53   * The concurrent hash map implementation built by {@link MapMaker}.
54   *
55   * <p>This implementation is heavily derived from revision 1.96 of <a
56   * href="http://tinyurl.com/ConcurrentHashMap">ConcurrentHashMap.java</a>.
57   *
58   * @param <K> the type of the keys in the map
59   * @param <V> the type of the values in the map
60   * @param <E> the type of the {@link InternalEntry} entry implementation used internally
61   * @param <S> the type of the {@link Segment} entry implementation used internally
62   * @author Bob Lee
63   * @author Charles Fry
64   * @author Doug Lea ({@code ConcurrentHashMap})
65   */
66  // TODO(kak/cpovirk): Consider removing @CanIgnoreReturnValue from this class.
67  @GwtIncompatible
68  @SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
69  class MapMakerInternalMap<
70          K,
71          V,
72          E extends MapMakerInternalMap.InternalEntry<K, V, E>,
73          S extends MapMakerInternalMap.Segment<K, V, E, S>>
74      extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
75  
76    /*
77     * The basic strategy is to subdivide the table among Segments, each of which itself is a
78     * concurrently readable hash table. The map supports non-blocking reads and concurrent writes
79     * across different segments.
80     *
81     * The page replacement algorithm's data structures are kept casually consistent with the map. The
82     * ordering of writes to a segment is sequentially consistent. An update to the map and recording
83     * of reads may not be immediately reflected on the algorithm's data structures. These structures
84     * are guarded by a lock and operations are applied in batches to avoid lock contention. The
85     * penalty of applying the batches is spread across threads so that the amortized cost is slightly
86     * higher than performing just the operation without enforcing the capacity constraint.
87     *
88     * This implementation uses a per-segment queue to record a memento of the additions, removals,
89     * and accesses that were performed on the map. The queue is drained on writes and when it exceeds
90     * its capacity threshold.
91     *
92     * The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit
93     * rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation
94     * operates per-segment rather than globally for increased implementation simplicity. We expect
95     * the cache hit rate to be similar to that of a global LRU algorithm.
96     */
97  
98    // Constants
99  
100   /**
101    * The maximum capacity, used if a higher value is implicitly specified by either of the
102    * constructors with arguments. MUST be a power of two no greater than {@code 1<<30} to ensure
103    * that entries are indexable using ints.
104    */
105   static final int MAXIMUM_CAPACITY = Ints.MAX_POWER_OF_TWO;
106 
107   /** The maximum number of segments to allow; used to bound constructor arguments. */
108   static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
109 
110   /** Number of (unsynchronized) retries in the containsValue method. */
111   static final int CONTAINS_VALUE_RETRIES = 3;
112 
113   /**
114    * Number of cache access operations that can be buffered per segment before the cache's recency
115    * ordering information is updated. This is used to avoid lock contention by recording a memento
116    * of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs.
117    *
118    * <p>This must be a (2^n)-1 as it is used as a mask.
119    */
120   static final int DRAIN_THRESHOLD = 0x3F;
121 
122   /**
123    * Maximum number of entries to be drained in a single cleanup run. This applies independently to
124    * the cleanup queue and both reference queues.
125    */
126   // TODO(fry): empirically optimize this
127   static final int DRAIN_MAX = 16;
128 
129   static final long CLEANUP_EXECUTOR_DELAY_SECS = 60;
130 
131   // Fields
132 
133   /**
134    * Mask value for indexing into segments. The upper bits of a key's hash code are used to choose
135    * the segment.
136    */
137   final transient int segmentMask;
138 
139   /**
140    * Shift value for indexing within segments. Helps prevent entries that end up in the same segment
141    * from also ending up in the same bucket.
142    */
143   final transient int segmentShift;
144 
145   /** The segments, each of which is a specialized hash table. */
146   final transient Segment<K, V, E, S>[] segments;
147 
148   /** The concurrency level. */
149   final int concurrencyLevel;
150 
151   /** Strategy for comparing keys. */
152   final Equivalence<Object> keyEquivalence;
153 
154   /** Strategy for handling entries and segments in a type-safe and efficient manner. */
155   final transient InternalEntryHelper<K, V, E, S> entryHelper;
156 
157   /**
158    * Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
159    */
160   private MapMakerInternalMap(MapMaker builder, InternalEntryHelper<K, V, E, S> entryHelper) {
161     concurrencyLevel = Math.min(builder.getConcurrencyLevel(), MAX_SEGMENTS);
162 
163     keyEquivalence = builder.getKeyEquivalence();
164     this.entryHelper = entryHelper;
165 
166     int initialCapacity = Math.min(builder.getInitialCapacity(), MAXIMUM_CAPACITY);
167 
168     // Find power-of-two sizes best matching arguments. Constraints:
169     // (segmentCount > concurrencyLevel)
170     int segmentShift = 0;
171     int segmentCount = 1;
172     while (segmentCount < concurrencyLevel) {
173       ++segmentShift;
174       segmentCount <<= 1;
175     }
176     this.segmentShift = 32 - segmentShift;
177     segmentMask = segmentCount - 1;
178 
179     this.segments = newSegmentArray(segmentCount);
180 
181     int segmentCapacity = initialCapacity / segmentCount;
182     if (segmentCapacity * segmentCount < initialCapacity) {
183       ++segmentCapacity;
184     }
185 
186     int segmentSize = 1;
187     while (segmentSize < segmentCapacity) {
188       segmentSize <<= 1;
189     }
190 
191     for (int i = 0; i < this.segments.length; ++i) {
192       this.segments[i] = createSegment(segmentSize, MapMaker.UNSET_INT);
193     }
194   }
195 
196   /** Returns a fresh {@link MapMakerInternalMap} as specified by the given {@code builder}. */
197   static <K, V> MapMakerInternalMap<K, V, ? extends InternalEntry<K, V, ?>, ?> create(
198       MapMaker builder) {
199     if (builder.getKeyStrength() == Strength.STRONG
200         && builder.getValueStrength() == Strength.STRONG) {
201       return new MapMakerInternalMap<>(builder, StrongKeyStrongValueEntry.Helper.<K, V>instance());
202     }
203     if (builder.getKeyStrength() == Strength.STRONG
204         && builder.getValueStrength() == Strength.WEAK) {
205       return new MapMakerInternalMap<>(builder, StrongKeyWeakValueEntry.Helper.<K, V>instance());
206     }
207     if (builder.getKeyStrength() == Strength.WEAK
208         && builder.getValueStrength() == Strength.STRONG) {
209       return new MapMakerInternalMap<>(builder, WeakKeyStrongValueEntry.Helper.<K, V>instance());
210     }
211     if (builder.getKeyStrength() == Strength.WEAK && builder.getValueStrength() == Strength.WEAK) {
212       return new MapMakerInternalMap<>(builder, WeakKeyWeakValueEntry.Helper.<K, V>instance());
213     }
214     throw new AssertionError();
215   }
216 
217   /**
218    * Returns a fresh {@link MapMakerInternalMap} with {@link MapMaker.Dummy} values but otherwise as
219    * specified by the given {@code builder}. The returned {@link MapMakerInternalMap} will be
220    * optimized to saved memory. Since {@link MapMaker.Dummy} is a singleton, we don't need to store
221    * any values at all. Because of this optimization, {@code build.getValueStrength()} must
222    * be {@link Strength#STRONG}.
223    *
224    * <p>This method is intended to only be used by the internal implementation of {@link Interners},
225    * since a map of dummy values is the exact use case there.
226    */
227   static <K>
228       MapMakerInternalMap<K, Dummy, ? extends InternalEntry<K, Dummy, ?>, ?> createWithDummyValues(
229           MapMaker builder) {
230     if (builder.getKeyStrength() == Strength.STRONG
231         && builder.getValueStrength() == Strength.STRONG) {
232       return new MapMakerInternalMap<>(builder, StrongKeyDummyValueEntry.Helper.<K>instance());
233     }
234     if (builder.getKeyStrength() == Strength.WEAK
235         && builder.getValueStrength() == Strength.STRONG) {
236       return new MapMakerInternalMap<>(builder, WeakKeyDummyValueEntry.Helper.<K>instance());
237     }
238     if (builder.getValueStrength() == Strength.WEAK) {
239       throw new IllegalArgumentException("Map cannot have both weak and dummy values");
240     }
241     throw new AssertionError();
242   }
243 
244   enum Strength {
245     STRONG {
246       @Override
247       Equivalence<Object> defaultEquivalence() {
248         return Equivalence.equals();
249       }
250     },
251 
252     WEAK {
253       @Override
254       Equivalence<Object> defaultEquivalence() {
255         return Equivalence.identity();
256       }
257     };
258 
259     /**
260      * Returns the default equivalence strategy used to compare and hash keys or values referenced
261      * at this strength. This strategy will be used unless the user explicitly specifies an
262      * alternate strategy.
263      */
264     abstract Equivalence<Object> defaultEquivalence();
265   }
266 
267   /**
268    * A helper object for operating on {@link InternalEntry} instances in a type-safe and efficient
269    * manner.
270    *
271    * <p>For each of the four combinations of strong/weak key and strong/weak value, there are
272    * corresponding {@link InternalEntry}, {@link Segment}, and {@link InternalEntryHelper}
273    * implementations.
274    *
275    * @param <K> the type of the key in each entry
276    * @param <V> the type of the value in each entry
277    * @param <E> the type of the {@link InternalEntry} entry implementation
278    * @param <S> the type of the {@link Segment} entry implementation
279    */
280   interface InternalEntryHelper<
281       K, V, E extends InternalEntry<K, V, E>, S extends Segment<K, V, E, S>> {
282     /** The strength of the key type in each entry. */
283     Strength keyStrength();
284 
285     /** The strength of the value type in each entry. */
286     Strength valueStrength();
287 
288     /** Returns a freshly created segment, typed at the {@code S} type. */
289     S newSegment(MapMakerInternalMap<K, V, E, S> map, int initialCapacity, int maxSegmentSize);
290 
291     /**
292      * Returns a freshly created entry, typed at the {@code E} type, for the given {@code segment}.
293      */
294     E newEntry(S segment, K key, int hash, @Nullable E next);
295 
296     /**
297      * Returns a freshly created entry, typed at the {@code E} type, for the given {@code segment},
298      * that is a copy of the given {@code entry}.
299      */
300     E copy(S segment, E entry, @Nullable E newNext);
301 
302     /**
303      * Sets the value of the given {@code entry} in the given {@code segment} to be the given {@code
304      * value}
305      */
306     void setValue(S segment, E entry, V value);
307   }
308 
309   /**
310    * An entry in a hash table of a {@link Segment}.
311    *
312    * <p>Entries in the map can be in the following states:
313    *
314    * <p>Valid: - Live: valid key/value are set
315    *
316    * <p>Invalid: - Collected: key/value was partially collected, but not yet cleaned up
317    */
318   interface InternalEntry<K, V, E extends InternalEntry<K, V, E>> {
319     /** Gets the next entry in the chain. */
320     E getNext();
321 
322     /**
323      * Gets the entry's hash.
324      */
325     int getHash();
326 
327     /**
328      * Gets the key for this entry.
329      */
330     K getKey();
331 
332     /** Gets the value for the entry. */
333     V getValue();
334   }
335 
336   /*
337    * Note: the following classes have a lot of duplicate code. It sucks, but it saves a lot of
338    * memory. If only Java had mixins!
339    */
340 
341   /** Base class for {@link InternalEntry} implementations for strong keys. */
342   abstract static class AbstractStrongKeyEntry<K, V, E extends InternalEntry<K, V, E>>
343       implements InternalEntry<K, V, E> {
344     final K key;
345     final int hash;
346     final E next;
347 
348     AbstractStrongKeyEntry(K key, int hash, @Nullable E next) {
349       this.key = key;
350       this.hash = hash;
351       this.next = next;
352     }
353 
354     @Override
355     public K getKey() {
356       return this.key;
357     }
358 
359     @Override
360     public int getHash() {
361       return hash;
362     }
363 
364     @Override
365     public E getNext() {
366       return next;
367     }
368   }
369 
370   /** Marker interface for {@link InternalEntry} implementations for strong values. */
371   interface StrongValueEntry<K, V, E extends InternalEntry<K, V, E>>
372       extends InternalEntry<K, V, E> {}
373 
374   /** Marker interface for {@link InternalEntry} implementations for weak values. */
375   interface WeakValueEntry<K, V, E extends InternalEntry<K, V, E>> extends InternalEntry<K, V, E> {
376     /** Gets the weak value reference held by entry. */
377     WeakValueReference<K, V, E> getValueReference();
378 
379     /**
380      * Clears the weak value reference held by the entry. Should be used when the entry's value is
381      * overwritten.
382      */
383     void clearValue();
384   }
385 
386   @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
387   static <K, V, E extends InternalEntry<K, V, E>>
388       WeakValueReference<K, V, E> unsetWeakValueReference() {
389     return (WeakValueReference<K, V, E>) UNSET_WEAK_VALUE_REFERENCE;
390   }
391 
392   /** Concrete implementation of {@link InternalEntry} for strong keys and strong values. */
393   static final class StrongKeyStrongValueEntry<K, V>
394       extends AbstractStrongKeyEntry<K, V, StrongKeyStrongValueEntry<K, V>>
395       implements StrongValueEntry<K, V, StrongKeyStrongValueEntry<K, V>> {
396     @Nullable private volatile V value = null;
397 
398     StrongKeyStrongValueEntry(K key, int hash, @Nullable StrongKeyStrongValueEntry<K, V> next) {
399       super(key, hash, next);
400     }
401 
402     @Override
403     @Nullable
404     public V getValue() {
405       return value;
406     }
407 
408     void setValue(V value) {
409       this.value = value;
410     }
411 
412     StrongKeyStrongValueEntry<K, V> copy(StrongKeyStrongValueEntry<K, V> newNext) {
413       StrongKeyStrongValueEntry<K, V> newEntry =
414           new StrongKeyStrongValueEntry<>(this.key, this.hash, newNext);
415       newEntry.value = this.value;
416       return newEntry;
417     }
418 
419     /** Concrete implementation of {@link InternalEntryHelper} for strong keys and strong values. */
420     static final class Helper<K, V>
421         implements InternalEntryHelper<
422             K, V, StrongKeyStrongValueEntry<K, V>, StrongKeyStrongValueSegment<K, V>> {
423       private static final Helper<?, ?> INSTANCE = new Helper<>();
424 
425       @SuppressWarnings("unchecked")
426       static <K, V> Helper<K, V> instance() {
427         return (Helper<K, V>) INSTANCE;
428       }
429 
430       @Override
431       public Strength keyStrength() {
432         return Strength.STRONG;
433       }
434 
435       @Override
436       public Strength valueStrength() {
437         return Strength.STRONG;
438       }
439 
440       @Override
441       public StrongKeyStrongValueSegment<K, V> newSegment(
442           MapMakerInternalMap<
443                   K, V, StrongKeyStrongValueEntry<K, V>, StrongKeyStrongValueSegment<K, V>>
444               map,
445           int initialCapacity,
446           int maxSegmentSize) {
447         return new StrongKeyStrongValueSegment<>(map, initialCapacity, maxSegmentSize);
448       }
449 
450       @Override
451       public StrongKeyStrongValueEntry<K, V> copy(
452           StrongKeyStrongValueSegment<K, V> segment,
453           StrongKeyStrongValueEntry<K, V> entry,
454           @Nullable StrongKeyStrongValueEntry<K, V> newNext) {
455         return entry.copy(newNext);
456       }
457 
458       @Override
459       public void setValue(
460           StrongKeyStrongValueSegment<K, V> segment,
461           StrongKeyStrongValueEntry<K, V> entry,
462           V value) {
463         entry.setValue(value);
464       }
465 
466       @Override
467       public StrongKeyStrongValueEntry<K, V> newEntry(
468           StrongKeyStrongValueSegment<K, V> segment,
469           K key,
470           int hash,
471           @Nullable StrongKeyStrongValueEntry<K, V> next) {
472         return new StrongKeyStrongValueEntry<>(key, hash, next);
473       }
474     }
475   }
476 
477   /** Concrete implementation of {@link InternalEntry} for strong keys and weak values. */
478   static final class StrongKeyWeakValueEntry<K, V>
479       extends AbstractStrongKeyEntry<K, V, StrongKeyWeakValueEntry<K, V>>
480       implements WeakValueEntry<K, V, StrongKeyWeakValueEntry<K, V>> {
481     private volatile WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> valueReference =
482         unsetWeakValueReference();
483 
484     StrongKeyWeakValueEntry(K key, int hash, @Nullable StrongKeyWeakValueEntry<K, V> next) {
485       super(key, hash, next);
486     }
487 
488     @Override
489     public V getValue() {
490       return valueReference.get();
491     }
492 
493     @Override
494     public void clearValue() {
495       valueReference.clear();
496     }
497 
498     void setValue(V value, ReferenceQueue<V> queueForValues) {
499       WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> previous = this.valueReference;
500       this.valueReference = new WeakValueReferenceImpl<>(queueForValues, value, this);
501       previous.clear();
502     }
503 
504     StrongKeyWeakValueEntry<K, V> copy(
505         ReferenceQueue<V> queueForValues, StrongKeyWeakValueEntry<K, V> newNext) {
506       StrongKeyWeakValueEntry<K, V> newEntry = new StrongKeyWeakValueEntry<>(key, hash, newNext);
507       newEntry.valueReference = valueReference.copyFor(queueForValues, newEntry);
508       return newEntry;
509     }
510 
511     @Override
512     public WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> getValueReference() {
513       return valueReference;
514     }
515 
516     /** Concrete implementation of {@link InternalEntryHelper} for strong keys and weak values. */
517     static final class Helper<K, V>
518         implements InternalEntryHelper<
519             K, V, StrongKeyWeakValueEntry<K, V>, StrongKeyWeakValueSegment<K, V>> {
520       private static final Helper<?, ?> INSTANCE = new Helper<>();
521 
522       @SuppressWarnings("unchecked")
523       static <K, V> Helper<K, V> instance() {
524         return (Helper<K, V>) INSTANCE;
525       }
526 
527       @Override
528       public Strength keyStrength() {
529         return Strength.STRONG;
530       }
531 
532       @Override
533       public Strength valueStrength() {
534         return Strength.WEAK;
535       }
536 
537       @Override
538       public StrongKeyWeakValueSegment<K, V> newSegment(
539           MapMakerInternalMap<K, V, StrongKeyWeakValueEntry<K, V>, StrongKeyWeakValueSegment<K, V>>
540               map,
541           int initialCapacity,
542           int maxSegmentSize) {
543         return new StrongKeyWeakValueSegment<>(map, initialCapacity, maxSegmentSize);
544       }
545 
546       @Override
547       public StrongKeyWeakValueEntry<K, V> copy(
548           StrongKeyWeakValueSegment<K, V> segment,
549           StrongKeyWeakValueEntry<K, V> entry,
550           @Nullable StrongKeyWeakValueEntry<K, V> newNext) {
551         if (Segment.isCollected(entry)) {
552           return null;
553         }
554         return entry.copy(segment.queueForValues, newNext);
555       }
556 
557       @Override
558       public void setValue(
559           StrongKeyWeakValueSegment<K, V> segment, StrongKeyWeakValueEntry<K, V> entry, V value) {
560         entry.setValue(value, segment.queueForValues);
561       }
562 
563       @Override
564       public StrongKeyWeakValueEntry<K, V> newEntry(
565           StrongKeyWeakValueSegment<K, V> segment,
566           K key,
567           int hash,
568           @Nullable StrongKeyWeakValueEntry<K, V> next) {
569         return new StrongKeyWeakValueEntry<>(key, hash, next);
570       }
571     }
572   }
573 
574   /** Concrete implementation of {@link InternalEntry} for strong keys and {@link Dummy} values. */
575   static final class StrongKeyDummyValueEntry<K>
576       extends AbstractStrongKeyEntry<K, Dummy, StrongKeyDummyValueEntry<K>>
577       implements StrongValueEntry<K, Dummy, StrongKeyDummyValueEntry<K>> {
578     StrongKeyDummyValueEntry(K key, int hash, @Nullable StrongKeyDummyValueEntry<K> next) {
579       super(key, hash, next);
580     }
581 
582     @Override
583     public Dummy getValue() {
584       return Dummy.VALUE;
585     }
586 
587     void setValue(Dummy value) {}
588 
589     StrongKeyDummyValueEntry<K> copy(StrongKeyDummyValueEntry<K> newNext) {
590       return new StrongKeyDummyValueEntry<K>(this.key, this.hash, newNext);
591     }
592 
593     /**
594      * Concrete implementation of {@link InternalEntryHelper} for strong keys and {@link Dummy}
595      * values.
596      */
597     static final class Helper<K>
598         implements InternalEntryHelper<
599             K, Dummy, StrongKeyDummyValueEntry<K>, StrongKeyDummyValueSegment<K>> {
600       private static final Helper<?> INSTANCE = new Helper<>();
601 
602       @SuppressWarnings("unchecked")
603       static <K> Helper<K> instance() {
604         return (Helper<K>) INSTANCE;
605       }
606 
607       @Override
608       public Strength keyStrength() {
609         return Strength.STRONG;
610       }
611 
612       @Override
613       public Strength valueStrength() {
614         return Strength.STRONG;
615       }
616 
617       @Override
618       public StrongKeyDummyValueSegment<K> newSegment(
619           MapMakerInternalMap<K, Dummy, StrongKeyDummyValueEntry<K>, StrongKeyDummyValueSegment<K>>
620               map,
621           int initialCapacity,
622           int maxSegmentSize) {
623         return new StrongKeyDummyValueSegment<K>(map, initialCapacity, maxSegmentSize);
624       }
625 
626       @Override
627       public StrongKeyDummyValueEntry<K> copy(
628           StrongKeyDummyValueSegment<K> segment,
629           StrongKeyDummyValueEntry<K> entry,
630           @Nullable StrongKeyDummyValueEntry<K> newNext) {
631         return entry.copy(newNext);
632       }
633 
634       @Override
635       public void setValue(
636           StrongKeyDummyValueSegment<K> segment, StrongKeyDummyValueEntry<K> entry, Dummy value) {}
637 
638       @Override
639       public StrongKeyDummyValueEntry<K> newEntry(
640           StrongKeyDummyValueSegment<K> segment,
641           K key,
642           int hash,
643           @Nullable StrongKeyDummyValueEntry<K> next) {
644         return new StrongKeyDummyValueEntry<K>(key, hash, next);
645       }
646     }
647   }
648 
649   /** Base class for {@link InternalEntry} implementations for weak keys. */
650   abstract static class AbstractWeakKeyEntry<K, V, E extends InternalEntry<K, V, E>>
651       extends WeakReference<K> implements InternalEntry<K, V, E> {
652     final int hash;
653     final E next;
654 
655     AbstractWeakKeyEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable E next) {
656       super(key, queue);
657       this.hash = hash;
658       this.next = next;
659     }
660 
661     @Override
662     public K getKey() {
663       return get();
664     }
665 
666     @Override
667     public int getHash() {
668       return hash;
669     }
670 
671     @Override
672     public E getNext() {
673       return next;
674     }
675   }
676 
677   /** Concrete implementation of {@link InternalEntry} for weak keys and {@link Dummy} values. */
678   static final class WeakKeyDummyValueEntry<K>
679       extends AbstractWeakKeyEntry<K, Dummy, WeakKeyDummyValueEntry<K>>
680       implements StrongValueEntry<K, Dummy, WeakKeyDummyValueEntry<K>> {
681     WeakKeyDummyValueEntry(
682         ReferenceQueue<K> queue, K key, int hash, @Nullable WeakKeyDummyValueEntry<K> next) {
683       super(queue, key, hash, next);
684     }
685 
686     @Override
687     public Dummy getValue() {
688       return Dummy.VALUE;
689     }
690 
691     void setValue(Dummy value) {}
692 
693     WeakKeyDummyValueEntry<K> copy(
694         ReferenceQueue<K> queueForKeys, WeakKeyDummyValueEntry<K> newNext) {
695       return new WeakKeyDummyValueEntry<K>(queueForKeys, getKey(), this.hash, newNext);
696     }
697 
698     /**
699      * Concrete implementation of {@link InternalEntryHelper} for weak keys and {@link Dummy}
700      * values.
701      */
702     static final class Helper<K>
703         implements InternalEntryHelper<
704             K, Dummy, WeakKeyDummyValueEntry<K>, WeakKeyDummyValueSegment<K>> {
705       private static final Helper<?> INSTANCE = new Helper<>();
706 
707       @SuppressWarnings("unchecked")
708       static <K> Helper<K> instance() {
709         return (Helper<K>) INSTANCE;
710       }
711 
712       @Override
713       public Strength keyStrength() {
714         return Strength.WEAK;
715       }
716 
717       @Override
718       public Strength valueStrength() {
719         return Strength.STRONG;
720       }
721 
722       @Override
723       public WeakKeyDummyValueSegment<K> newSegment(
724           MapMakerInternalMap<K, Dummy, WeakKeyDummyValueEntry<K>, WeakKeyDummyValueSegment<K>> map,
725           int initialCapacity,
726           int maxSegmentSize) {
727         return new WeakKeyDummyValueSegment<K>(map, initialCapacity, maxSegmentSize);
728       }
729 
730       @Override
731       public WeakKeyDummyValueEntry<K> copy(
732           WeakKeyDummyValueSegment<K> segment,
733           WeakKeyDummyValueEntry<K> entry,
734           @Nullable WeakKeyDummyValueEntry<K> newNext) {
735         if (entry.getKey() == null) {
736           // key collected
737           return null;
738         }
739         return entry.copy(segment.queueForKeys, newNext);
740       }
741 
742       @Override
743       public void setValue(
744           WeakKeyDummyValueSegment<K> segment, WeakKeyDummyValueEntry<K> entry, Dummy value) {}
745 
746       @Override
747       public WeakKeyDummyValueEntry<K> newEntry(
748           WeakKeyDummyValueSegment<K> segment,
749           K key,
750           int hash,
751           @Nullable WeakKeyDummyValueEntry<K> next) {
752         return new WeakKeyDummyValueEntry<K>(segment.queueForKeys, key, hash, next);
753       }
754     }
755   }
756 
757   /** Concrete implementation of {@link InternalEntry} for weak keys and strong values. */
758   static final class WeakKeyStrongValueEntry<K, V>
759       extends AbstractWeakKeyEntry<K, V, WeakKeyStrongValueEntry<K, V>>
760       implements StrongValueEntry<K, V, WeakKeyStrongValueEntry<K, V>> {
761     @Nullable private volatile V value = null;
762 
763     WeakKeyStrongValueEntry(
764         ReferenceQueue<K> queue, K key, int hash, @Nullable WeakKeyStrongValueEntry<K, V> next) {
765       super(queue, key, hash, next);
766     }
767 
768     @Override
769     @Nullable
770     public V getValue() {
771       return value;
772     }
773 
774     void setValue(V value) {
775       this.value = value;
776     }
777 
778     WeakKeyStrongValueEntry<K, V> copy(
779         ReferenceQueue<K> queueForKeys, WeakKeyStrongValueEntry<K, V> newNext) {
780       WeakKeyStrongValueEntry<K, V> newEntry =
781           new WeakKeyStrongValueEntry<>(queueForKeys, getKey(), this.hash, newNext);
782       newEntry.setValue(value);
783       return newEntry;
784     }
785 
786     /** Concrete implementation of {@link InternalEntryHelper} for weak keys and strong values. */
787     static final class Helper<K, V>
788         implements InternalEntryHelper<
789             K, V, WeakKeyStrongValueEntry<K, V>, WeakKeyStrongValueSegment<K, V>> {
790       private static final Helper<?, ?> INSTANCE = new Helper<>();
791 
792       @SuppressWarnings("unchecked")
793       static <K, V> Helper<K, V> instance() {
794         return (Helper<K, V>) INSTANCE;
795       }
796 
797       @Override
798       public Strength keyStrength() {
799         return Strength.WEAK;
800       }
801 
802       @Override
803       public Strength valueStrength() {
804         return Strength.STRONG;
805       }
806 
807       @Override
808       public WeakKeyStrongValueSegment<K, V> newSegment(
809           MapMakerInternalMap<K, V, WeakKeyStrongValueEntry<K, V>, WeakKeyStrongValueSegment<K, V>>
810               map,
811           int initialCapacity,
812           int maxSegmentSize) {
813         return new WeakKeyStrongValueSegment<>(map, initialCapacity, maxSegmentSize);
814       }
815 
816       @Override
817       public WeakKeyStrongValueEntry<K, V> copy(
818           WeakKeyStrongValueSegment<K, V> segment,
819           WeakKeyStrongValueEntry<K, V> entry,
820           @Nullable WeakKeyStrongValueEntry<K, V> newNext) {
821         if (entry.getKey() == null) {
822           // key collected
823           return null;
824         }
825         return entry.copy(segment.queueForKeys, newNext);
826       }
827 
828       @Override
829       public void setValue(
830           WeakKeyStrongValueSegment<K, V> segment, WeakKeyStrongValueEntry<K, V> entry, V value) {
831         entry.setValue(value);
832       }
833 
834       @Override
835       public WeakKeyStrongValueEntry<K, V> newEntry(
836           WeakKeyStrongValueSegment<K, V> segment,
837           K key,
838           int hash,
839           @Nullable WeakKeyStrongValueEntry<K, V> next) {
840         return new WeakKeyStrongValueEntry<>(segment.queueForKeys, key, hash, next);
841       }
842     }
843   }
844 
845   /** Concrete implementation of {@link InternalEntry} for weak keys and weak values. */
846   static final class WeakKeyWeakValueEntry<K, V>
847       extends AbstractWeakKeyEntry<K, V, WeakKeyWeakValueEntry<K, V>>
848       implements WeakValueEntry<K, V, WeakKeyWeakValueEntry<K, V>> {
849     private volatile WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> valueReference =
850         unsetWeakValueReference();
851 
852     WeakKeyWeakValueEntry(
853         ReferenceQueue<K> queue, K key, int hash, @Nullable WeakKeyWeakValueEntry<K, V> next) {
854       super(queue, key, hash, next);
855     }
856 
857     @Override
858     public V getValue() {
859       return valueReference.get();
860     }
861 
862     WeakKeyWeakValueEntry<K, V> copy(
863         ReferenceQueue<K> queueForKeys,
864         ReferenceQueue<V> queueForValues,
865         WeakKeyWeakValueEntry<K, V> newNext) {
866       WeakKeyWeakValueEntry<K, V> newEntry =
867           new WeakKeyWeakValueEntry<>(queueForKeys, getKey(), this.hash, newNext);
868       newEntry.valueReference = valueReference.copyFor(queueForValues, newEntry);
869       return newEntry;
870     }
871 
872     @Override
873     public void clearValue() {
874       valueReference.clear();
875     }
876 
877     void setValue(V value, ReferenceQueue<V> queueForValues) {
878       WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> previous = this.valueReference;
879       this.valueReference = new WeakValueReferenceImpl<>(queueForValues, value, this);
880       previous.clear();
881     }
882 
883     @Override
884     public WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> getValueReference() {
885       return valueReference;
886     }
887 
888     /** Concrete implementation of {@link InternalEntryHelper} for weak keys and weak values. */
889     static final class Helper<K, V>
890         implements InternalEntryHelper<
891             K, V, WeakKeyWeakValueEntry<K, V>, WeakKeyWeakValueSegment<K, V>> {
892       private static final Helper<?, ?> INSTANCE = new Helper<>();
893 
894       @SuppressWarnings("unchecked")
895       static <K, V> Helper<K, V> instance() {
896         return (Helper<K, V>) INSTANCE;
897       }
898 
899       @Override
900       public Strength keyStrength() {
901         return Strength.WEAK;
902       }
903 
904       @Override
905       public Strength valueStrength() {
906         return Strength.WEAK;
907       }
908 
909       @Override
910       public WeakKeyWeakValueSegment<K, V> newSegment(
911           MapMakerInternalMap<K, V, WeakKeyWeakValueEntry<K, V>, WeakKeyWeakValueSegment<K, V>> map,
912           int initialCapacity,
913           int maxSegmentSize) {
914         return new WeakKeyWeakValueSegment<>(map, initialCapacity, maxSegmentSize);
915       }
916 
917       @Override
918       public WeakKeyWeakValueEntry<K, V> copy(
919           WeakKeyWeakValueSegment<K, V> segment,
920           WeakKeyWeakValueEntry<K, V> entry,
921           @Nullable WeakKeyWeakValueEntry<K, V> newNext) {
922         if (entry.getKey() == null) {
923           // key collected
924           return null;
925         }
926         if (Segment.isCollected(entry)) {
927           return null;
928         }
929         return entry.copy(segment.queueForKeys, segment.queueForValues, newNext);
930       }
931 
932       @Override
933       public void setValue(
934           WeakKeyWeakValueSegment<K, V> segment, WeakKeyWeakValueEntry<K, V> entry, V value) {
935         entry.setValue(value, segment.queueForValues);
936       }
937 
938       @Override
939       public WeakKeyWeakValueEntry<K, V> newEntry(
940           WeakKeyWeakValueSegment<K, V> segment,
941           K key,
942           int hash,
943           @Nullable WeakKeyWeakValueEntry<K, V> next) {
944         return new WeakKeyWeakValueEntry<>(segment.queueForKeys, key, hash, next);
945       }
946     }
947   }
948 
949   /** A weakly referenced value that also has a reference to its containing entry. */
950   interface WeakValueReference<K, V, E extends InternalEntry<K, V, E>> {
951     /**
952      * Returns the current value being referenced, or {@code null} if there is none (e.g. because
953      * either it got collected, or {@link #clear} was called, or it wasn't set in the first place).
954      */
955     @Nullable
956     V get();
957 
958     /** Returns the entry which contains this {@link WeakValueReference}. */
959     E getEntry();
960 
961     /** Unsets the referenced value. Subsequent calls to {@link #get} will return {@code null}. */
962     void clear();
963 
964     /**
965      * Returns a freshly created {@link WeakValueReference} for the given {@code entry} (and on the
966      * given {@code queue} with the same value as this {@link WeakValueReference}.
967      */
968     WeakValueReference<K, V, E> copyFor(ReferenceQueue<V> queue, E entry);
969   }
970 
971   /**
972    * A dummy implementation of {@link InternalEntry}, solely for use in the type signature of {@link
973    * #UNSET_WEAK_VALUE_REFERENCE} below.
974    */
975   static final class DummyInternalEntry
976       implements InternalEntry<Object, Object, DummyInternalEntry> {
977     private DummyInternalEntry() {
978       throw new AssertionError();
979     }
980 
981     @Override
982     public DummyInternalEntry getNext() {
983       throw new AssertionError();
984     }
985 
986     @Override
987     public int getHash() {
988       throw new AssertionError();
989     }
990 
991     @Override
992     public Object getKey() {
993       throw new AssertionError();
994     }
995 
996     @Override
997     public Object getValue() {
998       throw new AssertionError();
999     }
1000   }
1001 
1002   /**
1003    * A singleton {@link WeakValueReference} used to denote an unset value in a entry with weak
1004    * values.
1005    */
1006   static final WeakValueReference<Object, Object, DummyInternalEntry> UNSET_WEAK_VALUE_REFERENCE =
1007       new WeakValueReference<Object, Object, DummyInternalEntry>() {
1008         @Override
1009         public DummyInternalEntry getEntry() {
1010           return null;
1011         }
1012 
1013         @Override
1014         public void clear() {}
1015 
1016         @Override
1017         public Object get() {
1018           return null;
1019         }
1020 
1021         @Override
1022         public WeakValueReference<Object, Object, DummyInternalEntry> copyFor(
1023             ReferenceQueue<Object> queue, DummyInternalEntry entry) {
1024           return this;
1025         }
1026       };
1027 
1028   /** Concrete implementation of {@link WeakValueReference}. */
1029   static final class WeakValueReferenceImpl<K, V, E extends InternalEntry<K, V, E>>
1030       extends WeakReference<V> implements WeakValueReference<K, V, E> {
1031     @Weak final E entry;
1032 
1033     WeakValueReferenceImpl(ReferenceQueue<V> queue, V referent, E entry) {
1034       super(referent, queue);
1035       this.entry = entry;
1036     }
1037 
1038     @Override
1039     public E getEntry() {
1040       return entry;
1041     }
1042 
1043     @Override
1044     public WeakValueReference<K, V, E> copyFor(ReferenceQueue<V> queue, E entry) {
1045       return new WeakValueReferenceImpl<>(queue, get(), entry);
1046     }
1047   }
1048 
1049   /**
1050    * Applies a supplemental hash function to a given hash code, which defends against poor quality
1051    * hash functions. This is critical when the concurrent hash map uses power-of-two length hash
1052    * tables, that otherwise encounter collisions for hash codes that do not differ in lower or
1053    * upper bits.
1054    *
1055    * @param h hash code
1056    */
1057   static int rehash(int h) {
1058     // Spread bits to regularize both segment and index locations,
1059     // using variant of single-word Wang/Jenkins hash.
1060     // TODO(kevinb): use Hashing/move this to Hashing?
1061     h += (h << 15) ^ 0xffffcd7d;
1062     h ^= (h >>> 10);
1063     h += (h << 3);
1064     h ^= (h >>> 6);
1065     h += (h << 2) + (h << 14);
1066     return h ^ (h >>> 16);
1067   }
1068 
1069   /**
1070    * This method is a convenience for testing. Code should call {@link Segment#copyEntry} directly.
1071    */
1072   // Guarded By Segment.this
1073   @VisibleForTesting
1074   E copyEntry(E original, E newNext) {
1075     int hash = original.getHash();
1076     return segmentFor(hash).copyEntry(original, newNext);
1077   }
1078 
1079   int hash(Object key) {
1080     int h = keyEquivalence.hash(key);
1081     return rehash(h);
1082   }
1083 
1084   void reclaimValue(WeakValueReference<K, V, E> valueReference) {
1085     E entry = valueReference.getEntry();
1086     int hash = entry.getHash();
1087     segmentFor(hash).reclaimValue(entry.getKey(), hash, valueReference);
1088   }
1089 
1090   void reclaimKey(E entry) {
1091     int hash = entry.getHash();
1092     segmentFor(hash).reclaimKey(entry, hash);
1093   }
1094 
1095   /**
1096    * This method is a convenience for testing. Code should call {@link Segment#getLiveValue}
1097    * instead.
1098    */
1099   @VisibleForTesting
1100   boolean isLiveForTesting(InternalEntry<K, V, ?> entry) {
1101     return segmentFor(entry.getHash()).getLiveValueForTesting(entry) != null;
1102   }
1103 
1104   /**
1105    * Returns the segment that should be used for a key with the given hash.
1106    *
1107    * @param hash the hash code for the key
1108    * @return the segment
1109    */
1110   Segment<K, V, E, S> segmentFor(int hash) {
1111     // TODO(fry): Lazily create segments?
1112     return segments[(hash >>> segmentShift) & segmentMask];
1113   }
1114 
1115   Segment<K, V, E, S> createSegment(int initialCapacity, int maxSegmentSize) {
1116     return entryHelper.newSegment(this, initialCapacity, maxSegmentSize);
1117   }
1118 
1119   /**
1120    * Gets the value from an entry. Returns {@code null} if the entry is invalid, partially-collected
1121    * or computing.
1122    */
1123   V getLiveValue(E entry) {
1124     if (entry.getKey() == null) {
1125       return null;
1126     }
1127     V value = entry.getValue();
1128     if (value == null) {
1129       return null;
1130     }
1131     return value;
1132   }
1133 
1134   @SuppressWarnings("unchecked")
1135   final Segment<K, V, E, S>[] newSegmentArray(int ssize) {
1136     return new Segment[ssize];
1137   }
1138 
1139   // Inner Classes
1140 
1141   /**
1142    * Segments are specialized versions of hash tables. This subclass inherits from ReentrantLock
1143    * opportunistically, just to simplify some locking and avoid separate construction.
1144    */
1145   @SuppressWarnings("serial") // This class is never serialized.
1146   abstract static class Segment<
1147           K, V, E extends InternalEntry<K, V, E>, S extends Segment<K, V, E, S>>
1148       extends ReentrantLock {
1149 
1150     /*
1151      * Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so can
1152      * be read without locking. Next fields of nodes are immutable (final). All list additions are
1153      * performed at the front of each bin. This makes it easy to check changes, and also fast to
1154      * traverse. When nodes would otherwise be changed, new nodes are created to replace them. This
1155      * works well for hash tables since the bin lists tend to be short. (The average length is less
1156      * than two.)
1157      *
1158      * Read operations can thus proceed without locking, but rely on selected uses of volatiles to
1159      * ensure that completed write operations performed by other threads are noticed. For most
1160      * purposes, the "count" field, tracking the number of elements, serves as that volatile
1161      * variable ensuring visibility. This is convenient because this field needs to be read in many
1162      * read operations anyway:
1163      *
1164      * - All (unsynchronized) read operations must first read the "count" field, and should not
1165      * look at table entries if it is 0.
1166      *
1167      * - All (synchronized) write operations should write to the "count" field after structurally
1168      * changing any bin. The operations must not take any action that could even momentarily
1169      * cause a concurrent read operation to see inconsistent data. This is made easier by the
1170      * nature of the read operations in Map. For example, no operation can reveal that the table
1171      * has grown but the threshold has not yet been updated, so there are no atomicity requirements
1172      * for this with respect to reads.
1173      *
1174      * As a guide, all critical volatile reads and writes to the count field are marked in code
1175      * comments.
1176      */
1177 
1178     @Weak final MapMakerInternalMap<K, V, E, S> map;
1179 
1180     /**
1181      * The number of live elements in this segment's region. This does not include unset elements
1182      * which are awaiting cleanup.
1183      */
1184     volatile int count;
1185 
1186     /**
1187      * Number of updates that alter the size of the table. This is used during bulk-read methods to
1188      * make sure they see a consistent snapshot: If modCounts change during a traversal of segments
1189      * computing size or checking containsValue, then we might have an inconsistent view of state
1190      * so (usually) must retry.
1191      */
1192     int modCount;
1193 
1194     /**
1195      * The table is expanded when its size exceeds this threshold. (The value of this field is
1196      * always {@code (int) (capacity * 0.75)}.)
1197      */
1198     int threshold;
1199 
1200     /** The per-segment table. */
1201     volatile AtomicReferenceArray<E> table;
1202 
1203     /**
1204      * The maximum size of this map. MapMaker.UNSET_INT if there is no maximum.
1205      */
1206     final int maxSegmentSize;
1207 
1208     /**
1209      * A counter of the number of reads since the last write, used to drain queues on a small
1210      * fraction of read operations.
1211      */
1212     final AtomicInteger readCount = new AtomicInteger();
1213 
1214     Segment(MapMakerInternalMap<K, V, E, S> map, int initialCapacity, int maxSegmentSize) {
1215       this.map = map;
1216       this.maxSegmentSize = maxSegmentSize;
1217       initTable(newEntryArray(initialCapacity));
1218     }
1219 
1220     /**
1221      * Returns {@code this} up-casted to the specific {@link Segment} implementation type {@code S}.
1222      *
1223      * <p>This method exists so that the {@link Segment} code can be generic in terms of {@code S},
1224      * the type of the concrete implementation.
1225      */
1226     abstract S self();
1227 
1228     /** Drains the reference queues used by this segment, if any. */
1229     @GuardedBy("this")
1230     void maybeDrainReferenceQueues() {}
1231 
1232     /** Clears the reference queues used by this segment, if any. */
1233     void maybeClearReferenceQueues() {}
1234 
1235     /** Sets the value of the given {@code entry}. */
1236     void setValue(E entry, V value) {
1237       this.map.entryHelper.setValue(self(), entry, value);
1238     }
1239 
1240     /** Returns a copy of the given {@code entry}. */
1241     E copyEntry(E original, E newNext) {
1242       return this.map.entryHelper.copy(self(), original, newNext);
1243     }
1244 
1245     AtomicReferenceArray<E> newEntryArray(int size) {
1246       return new AtomicReferenceArray<E>(size);
1247     }
1248 
1249     void initTable(AtomicReferenceArray<E> newTable) {
1250       this.threshold = newTable.length() * 3 / 4; // 0.75
1251       if (this.threshold == maxSegmentSize) {
1252         // prevent spurious expansion before eviction
1253         this.threshold++;
1254       }
1255       this.table = newTable;
1256     }
1257 
1258     // Convenience methods for testing
1259 
1260     /**
1261      * Unsafe cast of the given entry to {@code E}, the type of the specific {@link InternalEntry}
1262      * implementation type.
1263      *
1264      * <p>This method is provided as a convenience for tests. Otherwise they'd need to be
1265      * knowledgable about all the implementation details of our type system trickery.
1266      */
1267     abstract E castForTesting(InternalEntry<K, V, ?> entry);
1268 
1269     /** Unsafely extracts the key reference queue used by this segment. */
1270     ReferenceQueue<K> getKeyReferenceQueueForTesting() {
1271       throw new AssertionError();
1272     }
1273 
1274     /** Unsafely extracts the value reference queue used by this segment. */
1275     ReferenceQueue<V> getValueReferenceQueueForTesting() {
1276       throw new AssertionError();
1277     }
1278 
1279     /** Unsafely extracts the weak value reference inside of the given {@code entry}. */
1280     WeakValueReference<K, V, E> getWeakValueReferenceForTesting(InternalEntry<K, V, ?> entry) {
1281       throw new AssertionError();
1282     }
1283 
1284     /**
1285      * Unsafely creates of a fresh {@link WeakValueReference}, referencing the given {@code value},
1286      * for the given {@code entry}
1287      */
1288     WeakValueReference<K, V, E> newWeakValueReferenceForTesting(
1289         InternalEntry<K, V, ?> entry, V value) {
1290       throw new AssertionError();
1291     }
1292 
1293     /**
1294      * Unsafely sets the weak value reference inside the given {@code entry} to be the given {@code
1295      * valueReference}
1296      */
1297     void setWeakValueReferenceForTesting(
1298         InternalEntry<K, V, ?> entry,
1299         WeakValueReference<K, V, ? extends InternalEntry<K, V, ?>> valueReference) {
1300       throw new AssertionError();
1301     }
1302 
1303     /**
1304      * Unsafely sets the given index of this segment's internal hash table to be the given entry.
1305      */
1306     void setTableEntryForTesting(int i, InternalEntry<K, V, ?> entry) {
1307       table.set(i, castForTesting(entry));
1308     }
1309 
1310     /** Unsafely returns a copy of the given entry. */
1311     E copyForTesting(InternalEntry<K, V, ?> entry, @Nullable InternalEntry<K, V, ?> newNext) {
1312       return this.map.entryHelper.copy(self(), castForTesting(entry), castForTesting(newNext));
1313     }
1314 
1315     /** Unsafely sets the value of the given entry. */
1316     void setValueForTesting(InternalEntry<K, V, ?> entry, V value) {
1317       this.map.entryHelper.setValue(self(), castForTesting(entry), value);
1318     }
1319 
1320     /** Unsafely returns a fresh entry. */
1321     E newEntryForTesting(K key, int hash, @Nullable InternalEntry<K, V, ?> next) {
1322       return this.map.entryHelper.newEntry(self(), key, hash, castForTesting(next));
1323     }
1324 
1325     /** Unsafely removes the given entry from this segment's hash table. */
1326     @CanIgnoreReturnValue
1327     boolean removeTableEntryForTesting(InternalEntry<K, V, ?> entry) {
1328       return removeEntryForTesting(castForTesting(entry));
1329     }
1330 
1331     /** Unsafely removes the given entry from the given chain in this segment's hash table. */
1332     E removeFromChainForTesting(InternalEntry<K, V, ?> first, InternalEntry<K, V, ?> entry) {
1333       return removeFromChain(castForTesting(first), castForTesting(entry));
1334     }
1335 
1336     /**
1337      * Unsafely returns the value of the given entry if it's still live, or {@code null} otherwise.
1338      */
1339     @Nullable
1340     V getLiveValueForTesting(InternalEntry<K, V, ?> entry) {
1341       return getLiveValue(castForTesting(entry));
1342     }
1343 
1344     // reference queues, for garbage collection cleanup
1345 
1346     /**
1347      * Cleanup collected entries when the lock is available.
1348      */
1349     void tryDrainReferenceQueues() {
1350       if (tryLock()) {
1351         try {
1352           maybeDrainReferenceQueues();
1353         } finally {
1354           unlock();
1355         }
1356       }
1357     }
1358 
1359     @GuardedBy("this")
1360     void drainKeyReferenceQueue(ReferenceQueue<K> keyReferenceQueue) {
1361       Reference<? extends K> ref;
1362       int i = 0;
1363       while ((ref = keyReferenceQueue.poll()) != null) {
1364         @SuppressWarnings("unchecked")
1365         E entry = (E) ref;
1366         map.reclaimKey(entry);
1367         if (++i == DRAIN_MAX) {
1368           break;
1369         }
1370       }
1371     }
1372 
1373     @GuardedBy("this")
1374     void drainValueReferenceQueue(ReferenceQueue<V> valueReferenceQueue) {
1375       Reference<? extends V> ref;
1376       int i = 0;
1377       while ((ref = valueReferenceQueue.poll()) != null) {
1378         @SuppressWarnings("unchecked")
1379         WeakValueReference<K, V, E> valueReference = (WeakValueReference<K, V, E>) ref;
1380         map.reclaimValue(valueReference);
1381         if (++i == DRAIN_MAX) {
1382           break;
1383         }
1384       }
1385     }
1386 
1387     <T> void clearReferenceQueue(ReferenceQueue<T> referenceQueue) {
1388       while (referenceQueue.poll() != null) {}
1389     }
1390 
1391     /** Returns first entry of bin for given hash. */
1392     E getFirst(int hash) {
1393       // read this volatile field only once
1394       AtomicReferenceArray<E> table = this.table;
1395       return table.get(hash & (table.length() - 1));
1396     }
1397 
1398     // Specialized implementations of map methods
1399 
1400     E getEntry(Object key, int hash) {
1401       if (count != 0) { // read-volatile
1402         for (E e = getFirst(hash); e != null; e = e.getNext()) {
1403           if (e.getHash() != hash) {
1404             continue;
1405           }
1406 
1407           K entryKey = e.getKey();
1408           if (entryKey == null) {
1409             tryDrainReferenceQueues();
1410             continue;
1411           }
1412 
1413           if (map.keyEquivalence.equivalent(key, entryKey)) {
1414             return e;
1415           }
1416         }
1417       }
1418 
1419       return null;
1420     }
1421 
1422     E getLiveEntry(Object key, int hash) {
1423       return getEntry(key, hash);
1424     }
1425 
1426     V get(Object key, int hash) {
1427       try {
1428         E e = getLiveEntry(key, hash);
1429         if (e == null) {
1430           return null;
1431         }
1432 
1433         V value = e.getValue();
1434         if (value == null) {
1435           tryDrainReferenceQueues();
1436         }
1437         return value;
1438       } finally {
1439         postReadCleanup();
1440       }
1441     }
1442 
1443     boolean containsKey(Object key, int hash) {
1444       try {
1445         if (count != 0) { // read-volatile
1446           E e = getLiveEntry(key, hash);
1447           return e != null && e.getValue() != null;
1448         }
1449 
1450         return false;
1451       } finally {
1452         postReadCleanup();
1453       }
1454     }
1455 
1456     /**
1457      * This method is a convenience for testing. Code should call {@link
1458      * MapMakerInternalMap#containsValue} directly.
1459      */
1460     @VisibleForTesting
1461     boolean containsValue(Object value) {
1462       try {
1463         if (count != 0) { // read-volatile
1464           AtomicReferenceArray<E> table = this.table;
1465           int length = table.length();
1466           for (int i = 0; i < length; ++i) {
1467             for (E e = table.get(i); e != null; e = e.getNext()) {
1468               V entryValue = getLiveValue(e);
1469               if (entryValue == null) {
1470                 continue;
1471               }
1472               if (map.valueEquivalence().equivalent(value, entryValue)) {
1473                 return true;
1474               }
1475             }
1476           }
1477         }
1478 
1479         return false;
1480       } finally {
1481         postReadCleanup();
1482       }
1483     }
1484 
1485     V put(K key, int hash, V value, boolean onlyIfAbsent) {
1486       lock();
1487       try {
1488         preWriteCleanup();
1489 
1490         int newCount = this.count + 1;
1491         if (newCount > this.threshold) { // ensure capacity
1492           expand();
1493           newCount = this.count + 1;
1494         }
1495 
1496         AtomicReferenceArray<E> table = this.table;
1497         int index = hash & (table.length() - 1);
1498         E first = table.get(index);
1499 
1500         // Look for an existing entry.
1501         for (E e = first; e != null; e = e.getNext()) {
1502           K entryKey = e.getKey();
1503           if (e.getHash() == hash
1504               && entryKey != null
1505               && map.keyEquivalence.equivalent(key, entryKey)) {
1506             // We found an existing entry.
1507 
1508             V entryValue = e.getValue();
1509 
1510             if (entryValue == null) {
1511               ++modCount;
1512               setValue(e, value);
1513               newCount = this.count; // count remains unchanged
1514               this.count = newCount; // write-volatile
1515               return null;
1516             } else if (onlyIfAbsent) {
1517               // Mimic
1518               // "if (!map.containsKey(key)) ...
1519               // else return map.get(key);
1520               return entryValue;
1521             } else {
1522               // clobber existing entry, count remains unchanged
1523               ++modCount;
1524               setValue(e, value);
1525               return entryValue;
1526             }
1527           }
1528         }
1529 
1530         // Create a new entry.
1531         ++modCount;
1532         E newEntry = map.entryHelper.newEntry(self(), key, hash, first);
1533         setValue(newEntry, value);
1534         table.set(index, newEntry);
1535         this.count = newCount; // write-volatile
1536         return null;
1537       } finally {
1538         unlock();
1539       }
1540     }
1541 
1542     /**
1543      * Expands the table if possible.
1544      */
1545     @GuardedBy("this")
1546     void expand() {
1547       AtomicReferenceArray<E> oldTable = table;
1548       int oldCapacity = oldTable.length();
1549       if (oldCapacity >= MAXIMUM_CAPACITY) {
1550         return;
1551       }
1552 
1553       /*
1554        * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the
1555        * elements from each bin must either stay at same index, or move with a power of two offset.
1556        * We eliminate unnecessary node creation by catching cases where old nodes can be reused
1557        * because their next fields won't change. Statistically, at the default threshold, only
1558        * about one-sixth of them need cloning when a table doubles. The nodes they replace will be
1559        * garbage collectable as soon as they are no longer referenced by any reader thread that may
1560        * be in the midst of traversing table right now.
1561        */
1562 
1563       int newCount = count;
1564       AtomicReferenceArray<E> newTable = newEntryArray(oldCapacity << 1);
1565       threshold = newTable.length() * 3 / 4;
1566       int newMask = newTable.length() - 1;
1567       for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) {
1568         // We need to guarantee that any existing reads of old Map can
1569         // proceed. So we cannot yet null out each bin.
1570         E head = oldTable.get(oldIndex);
1571 
1572         if (head != null) {
1573           E next = head.getNext();
1574           int headIndex = head.getHash() & newMask;
1575 
1576           // Single node on list
1577           if (next == null) {
1578             newTable.set(headIndex, head);
1579           } else {
1580             // Reuse the consecutive sequence of nodes with the same target
1581             // index from the end of the list. tail points to the first
1582             // entry in the reusable list.
1583             E tail = head;
1584             int tailIndex = headIndex;
1585             for (E e = next; e != null; e = e.getNext()) {
1586               int newIndex = e.getHash() & newMask;
1587               if (newIndex != tailIndex) {
1588                 // The index changed. We'll need to copy the previous entry.
1589                 tailIndex = newIndex;
1590                 tail = e;
1591               }
1592             }
1593             newTable.set(tailIndex, tail);
1594 
1595             // Clone nodes leading up to the tail.
1596             for (E e = head; e != tail; e = e.getNext()) {
1597               int newIndex = e.getHash() & newMask;
1598               E newNext = newTable.get(newIndex);
1599               E newFirst = copyEntry(e, newNext);
1600               if (newFirst != null) {
1601                 newTable.set(newIndex, newFirst);
1602               } else {
1603                 newCount--;
1604               }
1605             }
1606           }
1607         }
1608       }
1609       table = newTable;
1610       this.count = newCount;
1611     }
1612 
1613     boolean replace(K key, int hash, V oldValue, V newValue) {
1614       lock();
1615       try {
1616         preWriteCleanup();
1617 
1618         AtomicReferenceArray<E> table = this.table;
1619         int index = hash & (table.length() - 1);
1620         E first = table.get(index);
1621 
1622         for (E e = first; e != null; e = e.getNext()) {
1623           K entryKey = e.getKey();
1624           if (e.getHash() == hash
1625               && entryKey != null
1626               && map.keyEquivalence.equivalent(key, entryKey)) {
1627             // If the value disappeared, this entry is partially collected,
1628             // and we should pretend like it doesn't exist.
1629             V entryValue = e.getValue();
1630             if (entryValue == null) {
1631               if (isCollected(e)) {
1632                 int newCount = this.count - 1;
1633                 ++modCount;
1634                 E newFirst = removeFromChain(first, e);
1635                 newCount = this.count - 1;
1636                 table.set(index, newFirst);
1637                 this.count = newCount; // write-volatile
1638               }
1639               return false;
1640             }
1641 
1642             if (map.valueEquivalence().equivalent(oldValue, entryValue)) {
1643               ++modCount;
1644               setValue(e, newValue);
1645               return true;
1646             } else {
1647               // Mimic
1648               // "if (map.containsKey(key) && map.get(key).equals(oldValue))..."
1649               return false;
1650             }
1651           }
1652         }
1653 
1654         return false;
1655       } finally {
1656         unlock();
1657       }
1658     }
1659 
1660     V replace(K key, int hash, V newValue) {
1661       lock();
1662       try {
1663         preWriteCleanup();
1664 
1665         AtomicReferenceArray<E> table = this.table;
1666         int index = hash & (table.length() - 1);
1667         E first = table.get(index);
1668 
1669         for (E e = first; e != null; e = e.getNext()) {
1670           K entryKey = e.getKey();
1671           if (e.getHash() == hash
1672               && entryKey != null
1673               && map.keyEquivalence.equivalent(key, entryKey)) {
1674             // If the value disappeared, this entry is partially collected,
1675             // and we should pretend like it doesn't exist.
1676             V entryValue = e.getValue();
1677             if (entryValue == null) {
1678               if (isCollected(e)) {
1679                 int newCount = this.count - 1;
1680                 ++modCount;
1681                 E newFirst = removeFromChain(first, e);
1682                 newCount = this.count - 1;
1683                 table.set(index, newFirst);
1684                 this.count = newCount; // write-volatile
1685               }
1686               return null;
1687             }
1688 
1689             ++modCount;
1690             setValue(e, newValue);
1691             return entryValue;
1692           }
1693         }
1694 
1695         return null;
1696       } finally {
1697         unlock();
1698       }
1699     }
1700 
1701     @CanIgnoreReturnValue
1702     V remove(Object key, int hash) {
1703       lock();
1704       try {
1705         preWriteCleanup();
1706 
1707         int newCount = this.count - 1;
1708         AtomicReferenceArray<E> table = this.table;
1709         int index = hash & (table.length() - 1);
1710         E first = table.get(index);
1711 
1712         for (E e = first; e != null; e = e.getNext()) {
1713           K entryKey = e.getKey();
1714           if (e.getHash() == hash
1715               && entryKey != null
1716               && map.keyEquivalence.equivalent(key, entryKey)) {
1717             V entryValue = e.getValue();
1718 
1719             if (entryValue != null) {
1720               // TODO(kak): Remove this branch
1721             } else if (isCollected(e)) {
1722               // TODO(kak): Remove this branch
1723             } else {
1724               return null;
1725             }
1726 
1727             ++modCount;
1728             E newFirst = removeFromChain(first, e);
1729             newCount = this.count - 1;
1730             table.set(index, newFirst);
1731             this.count = newCount; // write-volatile
1732             return entryValue;
1733           }
1734         }
1735 
1736         return null;
1737       } finally {
1738         unlock();
1739       }
1740     }
1741 
1742     boolean remove(Object key, int hash, Object value) {
1743       lock();
1744       try {
1745         preWriteCleanup();
1746 
1747         int newCount = this.count - 1;
1748         AtomicReferenceArray<E> table = this.table;
1749         int index = hash & (table.length() - 1);
1750         E first = table.get(index);
1751 
1752         for (E e = first; e != null; e = e.getNext()) {
1753           K entryKey = e.getKey();
1754           if (e.getHash() == hash
1755               && entryKey != null
1756               && map.keyEquivalence.equivalent(key, entryKey)) {
1757             V entryValue = e.getValue();
1758 
1759             boolean explicitRemoval = false;
1760             if (map.valueEquivalence().equivalent(value, entryValue)) {
1761               explicitRemoval = true;
1762             } else if (isCollected(e)) {
1763               // TODO(kak): Remove this branch
1764             } else {
1765               return false;
1766             }
1767 
1768             ++modCount;
1769             E newFirst = removeFromChain(first, e);
1770             newCount = this.count - 1;
1771             table.set(index, newFirst);
1772             this.count = newCount; // write-volatile
1773             return explicitRemoval;
1774           }
1775         }
1776 
1777         return false;
1778       } finally {
1779         unlock();
1780       }
1781     }
1782 
1783     void clear() {
1784       if (count != 0) {
1785         lock();
1786         try {
1787           AtomicReferenceArray<E> table = this.table;
1788           for (int i = 0; i < table.length(); ++i) {
1789             table.set(i, null);
1790           }
1791           maybeClearReferenceQueues();
1792           readCount.set(0);
1793 
1794           ++modCount;
1795           count = 0; // write-volatile
1796         } finally {
1797           unlock();
1798         }
1799       }
1800     }
1801 
1802     /**
1803      * Removes an entry from within a table. All entries following the removed node can stay, but
1804      * all preceding ones need to be cloned.
1805      *
1806      * <p>This method does not decrement count for the removed entry, but does decrement count for
1807      * all partially collected entries which are skipped. As such callers which are modifying count
1808      * must re-read it after calling removeFromChain.
1809      *
1810      * @param first the first entry of the table
1811      * @param entry the entry being removed from the table
1812      * @return the new first entry for the table
1813      */
1814     @GuardedBy("this")
1815     E removeFromChain(E first, E entry) {
1816       int newCount = count;
1817       E newFirst = entry.getNext();
1818       for (E e = first; e != entry; e = e.getNext()) {
1819         E next = copyEntry(e, newFirst);
1820         if (next != null) {
1821           newFirst = next;
1822         } else {
1823           newCount--;
1824         }
1825       }
1826       this.count = newCount;
1827       return newFirst;
1828     }
1829 
1830     /** Removes an entry whose key has been garbage collected. */
1831     @CanIgnoreReturnValue
1832     boolean reclaimKey(E entry, int hash) {
1833       lock();
1834       try {
1835         int newCount = count - 1;
1836         AtomicReferenceArray<E> table = this.table;
1837         int index = hash & (table.length() - 1);
1838         E first = table.get(index);
1839 
1840         for (E e = first; e != null; e = e.getNext()) {
1841           if (e == entry) {
1842             ++modCount;
1843             E newFirst = removeFromChain(first, e);
1844             newCount = this.count - 1;
1845             table.set(index, newFirst);
1846             this.count = newCount; // write-volatile
1847             return true;
1848           }
1849         }
1850 
1851         return false;
1852       } finally {
1853         unlock();
1854       }
1855     }
1856 
1857     /** Removes an entry whose value has been garbage collected. */
1858     @CanIgnoreReturnValue
1859     boolean reclaimValue(K key, int hash, WeakValueReference<K, V, E> valueReference) {
1860       lock();
1861       try {
1862         int newCount = this.count - 1;
1863         AtomicReferenceArray<E> table = this.table;
1864         int index = hash & (table.length() - 1);
1865         E first = table.get(index);
1866 
1867         for (E e = first; e != null; e = e.getNext()) {
1868           K entryKey = e.getKey();
1869           if (e.getHash() == hash
1870               && entryKey != null
1871               && map.keyEquivalence.equivalent(key, entryKey)) {
1872             WeakValueReference<K, V, E> v = ((WeakValueEntry<K, V, E>) e).getValueReference();
1873             if (v == valueReference) {
1874               ++modCount;
1875               E newFirst = removeFromChain(first, e);
1876               newCount = this.count - 1;
1877               table.set(index, newFirst);
1878               this.count = newCount; // write-volatile
1879               return true;
1880             }
1881             return false;
1882           }
1883         }
1884 
1885         return false;
1886       } finally {
1887         unlock();
1888       }
1889     }
1890 
1891     /** Clears a value that has not yet been set, and thus does not require count to be modified. */
1892     @CanIgnoreReturnValue
1893     boolean clearValueForTesting(
1894         K key,
1895         int hash,
1896         WeakValueReference<K, V, ? extends InternalEntry<K, V, ?>> valueReference) {
1897       lock();
1898       try {
1899         AtomicReferenceArray<E> table = this.table;
1900         int index = hash & (table.length() - 1);
1901         E first = table.get(index);
1902 
1903         for (E e = first; e != null; e = e.getNext()) {
1904           K entryKey = e.getKey();
1905           if (e.getHash() == hash
1906               && entryKey != null
1907               && map.keyEquivalence.equivalent(key, entryKey)) {
1908             WeakValueReference<K, V, E> v = ((WeakValueEntry<K, V, E>) e).getValueReference();
1909             if (v == valueReference) {
1910               E newFirst = removeFromChain(first, e);
1911               table.set(index, newFirst);
1912               return true;
1913             }
1914             return false;
1915           }
1916         }
1917 
1918         return false;
1919       } finally {
1920         unlock();
1921       }
1922     }
1923 
1924     @GuardedBy("this")
1925     boolean removeEntryForTesting(E entry) {
1926       int hash = entry.getHash();
1927       int newCount = this.count - 1;
1928       AtomicReferenceArray<E> table = this.table;
1929       int index = hash & (table.length() - 1);
1930       E first = table.get(index);
1931 
1932       for (E e = first; e != null; e = e.getNext()) {
1933         if (e == entry) {
1934           ++modCount;
1935           E newFirst = removeFromChain(first, e);
1936           newCount = this.count - 1;
1937           table.set(index, newFirst);
1938           this.count = newCount; // write-volatile
1939           return true;
1940         }
1941       }
1942 
1943       return false;
1944     }
1945 
1946     /**
1947      * Returns {@code true} if the value has been partially collected, meaning that the value is
1948      * null.
1949      */
1950     static <K, V, E extends InternalEntry<K, V, E>> boolean isCollected(E entry) {
1951       return entry.getValue() == null;
1952     }
1953 
1954     /**
1955      * Gets the value from an entry. Returns {@code null} if the entry is invalid or
1956      * partially-collected.
1957      */
1958     @Nullable
1959     V getLiveValue(E entry) {
1960       if (entry.getKey() == null) {
1961         tryDrainReferenceQueues();
1962         return null;
1963       }
1964       V value = entry.getValue();
1965       if (value == null) {
1966         tryDrainReferenceQueues();
1967         return null;
1968       }
1969 
1970       return value;
1971     }
1972 
1973     /**
1974      * Performs routine cleanup following a read. Normally cleanup happens during writes, or from
1975      * the cleanupExecutor. If cleanup is not observed after a sufficient number of reads, try
1976      * cleaning up from the read thread.
1977      */
1978     void postReadCleanup() {
1979       if ((readCount.incrementAndGet() & DRAIN_THRESHOLD) == 0) {
1980         runCleanup();
1981       }
1982     }
1983 
1984     /**
1985      * Performs routine cleanup prior to executing a write. This should be called every time a
1986      * write thread acquires the segment lock, immediately after acquiring the lock.
1987      */
1988     @GuardedBy("this")
1989     void preWriteCleanup() {
1990       runLockedCleanup();
1991     }
1992 
1993     void runCleanup() {
1994       runLockedCleanup();
1995     }
1996 
1997     void runLockedCleanup() {
1998       if (tryLock()) {
1999         try {
2000           maybeDrainReferenceQueues();
2001           readCount.set(0);
2002         } finally {
2003           unlock();
2004         }
2005       }
2006     }
2007   }
2008 
2009   /** Concrete implementation of {@link Segment} for strong keys and strong values. */
2010   static final class StrongKeyStrongValueSegment<K, V>
2011       extends Segment<K, V, StrongKeyStrongValueEntry<K, V>, StrongKeyStrongValueSegment<K, V>> {
2012     StrongKeyStrongValueSegment(
2013         MapMakerInternalMap<
2014                 K, V, StrongKeyStrongValueEntry<K, V>, StrongKeyStrongValueSegment<K, V>>
2015             map,
2016         int initialCapacity,
2017         int maxSegmentSize) {
2018       super(map, initialCapacity, maxSegmentSize);
2019     }
2020 
2021     @Override
2022     StrongKeyStrongValueSegment<K, V> self() {
2023       return this;
2024     }
2025 
2026     @SuppressWarnings("unchecked")
2027     @Override
2028     public StrongKeyStrongValueEntry<K, V> castForTesting(InternalEntry<K, V, ?> entry) {
2029       return (StrongKeyStrongValueEntry<K, V>) entry;
2030     }
2031   }
2032 
2033   /** Concrete implementation of {@link Segment} for strong keys and weak values. */
2034   static final class StrongKeyWeakValueSegment<K, V>
2035       extends Segment<K, V, StrongKeyWeakValueEntry<K, V>, StrongKeyWeakValueSegment<K, V>> {
2036     private final ReferenceQueue<V> queueForValues = new ReferenceQueue<V>();
2037 
2038     StrongKeyWeakValueSegment(
2039         MapMakerInternalMap<K, V, StrongKeyWeakValueEntry<K, V>, StrongKeyWeakValueSegment<K, V>>
2040             map,
2041         int initialCapacity,
2042         int maxSegmentSize) {
2043       super(map, initialCapacity, maxSegmentSize);
2044     }
2045 
2046     @Override
2047     StrongKeyWeakValueSegment<K, V> self() {
2048       return this;
2049     }
2050 
2051     @Override
2052     ReferenceQueue<V> getValueReferenceQueueForTesting() {
2053       return queueForValues;
2054     }
2055 
2056     @SuppressWarnings("unchecked")
2057     @Override
2058     public StrongKeyWeakValueEntry<K, V> castForTesting(InternalEntry<K, V, ?> entry) {
2059       return (StrongKeyWeakValueEntry<K, V>) entry;
2060     }
2061 
2062     @Override
2063     public WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> getWeakValueReferenceForTesting(
2064         InternalEntry<K, V, ?> e) {
2065       return castForTesting(e).getValueReference();
2066     }
2067 
2068     @Override
2069     public WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> newWeakValueReferenceForTesting(
2070         InternalEntry<K, V, ?> e, V value) {
2071       return new WeakValueReferenceImpl<>(queueForValues, value, castForTesting(e));
2072     }
2073 
2074     @Override
2075     public void setWeakValueReferenceForTesting(
2076         InternalEntry<K, V, ?> e,
2077         WeakValueReference<K, V, ? extends InternalEntry<K, V, ?>> valueReference) {
2078       StrongKeyWeakValueEntry<K, V> entry = castForTesting(e);
2079       @SuppressWarnings("unchecked")
2080       WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> newValueReference =
2081           (WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>>) valueReference;
2082       WeakValueReference<K, V, StrongKeyWeakValueEntry<K, V>> previous = entry.valueReference;
2083       entry.valueReference = newValueReference;
2084       previous.clear();
2085     }
2086 
2087     @Override
2088     void maybeDrainReferenceQueues() {
2089       drainValueReferenceQueue(queueForValues);
2090     }
2091 
2092     @Override
2093     void maybeClearReferenceQueues() {
2094       clearReferenceQueue(queueForValues);
2095     }
2096   }
2097 
2098   /** Concrete implementation of {@link Segment} for strong keys and {@link Dummy} values. */
2099   static final class StrongKeyDummyValueSegment<K>
2100       extends Segment<K, Dummy, StrongKeyDummyValueEntry<K>, StrongKeyDummyValueSegment<K>> {
2101     StrongKeyDummyValueSegment(
2102         MapMakerInternalMap<K, Dummy, StrongKeyDummyValueEntry<K>, StrongKeyDummyValueSegment<K>>
2103             map,
2104         int initialCapacity,
2105         int maxSegmentSize) {
2106       super(map, initialCapacity, maxSegmentSize);
2107     }
2108 
2109     @Override
2110     StrongKeyDummyValueSegment<K> self() {
2111       return this;
2112     }
2113 
2114     @SuppressWarnings("unchecked")
2115     @Override
2116     public StrongKeyDummyValueEntry<K> castForTesting(InternalEntry<K, Dummy, ?> entry) {
2117       return (StrongKeyDummyValueEntry<K>) entry;
2118     }
2119   }
2120 
2121   /** Concrete implementation of {@link Segment} for weak keys and strong values. */
2122   static final class WeakKeyStrongValueSegment<K, V>
2123       extends Segment<K, V, WeakKeyStrongValueEntry<K, V>, WeakKeyStrongValueSegment<K, V>> {
2124     private final ReferenceQueue<K> queueForKeys = new ReferenceQueue<K>();
2125 
2126     WeakKeyStrongValueSegment(
2127         MapMakerInternalMap<K, V, WeakKeyStrongValueEntry<K, V>, WeakKeyStrongValueSegment<K, V>>
2128             map,
2129         int initialCapacity,
2130         int maxSegmentSize) {
2131       super(map, initialCapacity, maxSegmentSize);
2132     }
2133 
2134     @Override
2135     WeakKeyStrongValueSegment<K, V> self() {
2136       return this;
2137     }
2138 
2139     @Override
2140     ReferenceQueue<K> getKeyReferenceQueueForTesting() {
2141       return queueForKeys;
2142     }
2143 
2144     @SuppressWarnings("unchecked")
2145     @Override
2146     public WeakKeyStrongValueEntry<K, V> castForTesting(InternalEntry<K, V, ?> entry) {
2147       return (WeakKeyStrongValueEntry<K, V>) entry;
2148     }
2149 
2150     @Override
2151     void maybeDrainReferenceQueues() {
2152       drainKeyReferenceQueue(queueForKeys);
2153     }
2154 
2155     @Override
2156     void maybeClearReferenceQueues() {
2157       clearReferenceQueue(queueForKeys);
2158     }
2159   }
2160 
2161   /** Concrete implementation of {@link Segment} for weak keys and weak values. */
2162   static final class WeakKeyWeakValueSegment<K, V>
2163       extends Segment<K, V, WeakKeyWeakValueEntry<K, V>, WeakKeyWeakValueSegment<K, V>> {
2164     private final ReferenceQueue<K> queueForKeys = new ReferenceQueue<K>();
2165     private final ReferenceQueue<V> queueForValues = new ReferenceQueue<V>();
2166 
2167     WeakKeyWeakValueSegment(
2168         MapMakerInternalMap<K, V, WeakKeyWeakValueEntry<K, V>, WeakKeyWeakValueSegment<K, V>> map,
2169         int initialCapacity,
2170         int maxSegmentSize) {
2171       super(map, initialCapacity, maxSegmentSize);
2172     }
2173 
2174     @Override
2175     WeakKeyWeakValueSegment<K, V> self() {
2176       return this;
2177     }
2178 
2179     @Override
2180     ReferenceQueue<K> getKeyReferenceQueueForTesting() {
2181       return queueForKeys;
2182     }
2183 
2184     @Override
2185     ReferenceQueue<V> getValueReferenceQueueForTesting() {
2186       return queueForValues;
2187     }
2188 
2189     @SuppressWarnings("unchecked")
2190     @Override
2191     public WeakKeyWeakValueEntry<K, V> castForTesting(InternalEntry<K, V, ?> entry) {
2192       return (WeakKeyWeakValueEntry<K, V>) entry;
2193     }
2194 
2195     @Override
2196     public WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> getWeakValueReferenceForTesting(
2197         InternalEntry<K, V, ?> e) {
2198       return (castForTesting(e)).getValueReference();
2199     }
2200 
2201     @Override
2202     public WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> newWeakValueReferenceForTesting(
2203         InternalEntry<K, V, ?> e, V value) {
2204       return new WeakValueReferenceImpl<>(queueForValues, value, castForTesting(e));
2205     }
2206 
2207     @Override
2208     public void setWeakValueReferenceForTesting(
2209         InternalEntry<K, V, ?> e,
2210         WeakValueReference<K, V, ? extends InternalEntry<K, V, ?>> valueReference) {
2211       WeakKeyWeakValueEntry<K, V> entry = castForTesting(e);
2212       @SuppressWarnings("unchecked")
2213       WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> newValueReference =
2214           (WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>>) valueReference;
2215       WeakValueReference<K, V, WeakKeyWeakValueEntry<K, V>> previous = entry.valueReference;
2216       entry.valueReference = newValueReference;
2217       previous.clear();
2218     }
2219 
2220     @Override
2221     void maybeDrainReferenceQueues() {
2222       drainKeyReferenceQueue(queueForKeys);
2223       drainValueReferenceQueue(queueForValues);
2224     }
2225 
2226     @Override
2227     void maybeClearReferenceQueues() {
2228       clearReferenceQueue(queueForKeys);
2229     }
2230   }
2231 
2232   /** Concrete implementation of {@link Segment} for weak keys and {@link Dummy} values. */
2233   static final class WeakKeyDummyValueSegment<K>
2234       extends Segment<K, Dummy, WeakKeyDummyValueEntry<K>, WeakKeyDummyValueSegment<K>> {
2235     private final ReferenceQueue<K> queueForKeys = new ReferenceQueue<K>();
2236 
2237     WeakKeyDummyValueSegment(
2238         MapMakerInternalMap<K, Dummy, WeakKeyDummyValueEntry<K>, WeakKeyDummyValueSegment<K>> map,
2239         int initialCapacity,
2240         int maxSegmentSize) {
2241       super(map, initialCapacity, maxSegmentSize);
2242     }
2243 
2244     @Override
2245     WeakKeyDummyValueSegment<K> self() {
2246       return this;
2247     }
2248 
2249     @Override
2250     ReferenceQueue<K> getKeyReferenceQueueForTesting() {
2251       return queueForKeys;
2252     }
2253 
2254     @SuppressWarnings("unchecked")
2255     @Override
2256     public WeakKeyDummyValueEntry<K> castForTesting(InternalEntry<K, Dummy, ?> entry) {
2257       return (WeakKeyDummyValueEntry<K>) entry;
2258     }
2259 
2260     @Override
2261     void maybeDrainReferenceQueues() {
2262       drainKeyReferenceQueue(queueForKeys);
2263     }
2264 
2265     @Override
2266     void maybeClearReferenceQueues() {
2267       clearReferenceQueue(queueForKeys);
2268     }
2269   }
2270 
2271   static final class CleanupMapTask implements Runnable {
2272     final WeakReference<MapMakerInternalMap<?, ?, ?, ?>> mapReference;
2273 
2274     public CleanupMapTask(MapMakerInternalMap<?, ?, ?, ?> map) {
2275       this.mapReference = new WeakReference<MapMakerInternalMap<?, ?, ?, ?>>(map);
2276     }
2277 
2278     @Override
2279     public void run() {
2280       MapMakerInternalMap<?, ?, ?, ?> map = mapReference.get();
2281       if (map == null) {
2282         throw new CancellationException();
2283       }
2284 
2285       for (Segment<?, ?, ?, ?> segment : map.segments) {
2286         segment.runCleanup();
2287       }
2288     }
2289   }
2290 
2291   @VisibleForTesting
2292   Strength keyStrength() {
2293     return entryHelper.keyStrength();
2294   }
2295 
2296   @VisibleForTesting
2297   Strength valueStrength() {
2298     return entryHelper.valueStrength();
2299   }
2300 
2301   @VisibleForTesting
2302   Equivalence<Object> valueEquivalence() {
2303     return entryHelper.valueStrength().defaultEquivalence();
2304   }
2305 
2306   // ConcurrentMap methods
2307 
2308   @Override
2309   public boolean isEmpty() {
2310     /*
2311      * Sum per-segment modCounts to avoid mis-reporting when elements are concurrently added and
2312      * removed in one segment while checking another, in which case the table was never actually
2313      * empty at any point. (The sum ensures accuracy up through at least 1<<31 per-segment
2314      * modifications before recheck.)  Method containsValue() uses similar constructions for
2315      * stability checks.
2316      */
2317     long sum = 0L;
2318     Segment<K, V, E, S>[] segments = this.segments;
2319     for (int i = 0; i < segments.length; ++i) {
2320       if (segments[i].count != 0) {
2321         return false;
2322       }
2323       sum += segments[i].modCount;
2324     }
2325 
2326     if (sum != 0L) { // recheck unless no modifications
2327       for (int i = 0; i < segments.length; ++i) {
2328         if (segments[i].count != 0) {
2329           return false;
2330         }
2331         sum -= segments[i].modCount;
2332       }
2333       if (sum != 0L) {
2334         return false;
2335       }
2336     }
2337     return true;
2338   }
2339 
2340   @Override
2341   public int size() {
2342     Segment<K, V, E, S>[] segments = this.segments;
2343     long sum = 0;
2344     for (int i = 0; i < segments.length; ++i) {
2345       sum += segments[i].count;
2346     }
2347     return Ints.saturatedCast(sum);
2348   }
2349 
2350   @Override
2351   public V get(@Nullable Object key) {
2352     if (key == null) {
2353       return null;
2354     }
2355     int hash = hash(key);
2356     return segmentFor(hash).get(key, hash);
2357   }
2358 
2359   /**
2360    * Returns the internal entry for the specified key. The entry may be computing or partially
2361    * collected. Does not impact recency ordering.
2362    */
2363   E getEntry(@Nullable Object key) {
2364     if (key == null) {
2365       return null;
2366     }
2367     int hash = hash(key);
2368     return segmentFor(hash).getEntry(key, hash);
2369   }
2370 
2371   @Override
2372   public boolean containsKey(@Nullable Object key) {
2373     if (key == null) {
2374       return false;
2375     }
2376     int hash = hash(key);
2377     return segmentFor(hash).containsKey(key, hash);
2378   }
2379 
2380   @Override
2381   public boolean containsValue(@Nullable Object value) {
2382     if (value == null) {
2383       return false;
2384     }
2385 
2386     // This implementation is patterned after ConcurrentHashMap, but without the locking. The only
2387     // way for it to return a false negative would be for the target value to jump around in the map
2388     // such that none of the subsequent iterations observed it, despite the fact that at every point
2389     // in time it was present somewhere int the map. This becomes increasingly unlikely as
2390     // CONTAINS_VALUE_RETRIES increases, though without locking it is theoretically possible.
2391     final Segment<K, V, E, S>[] segments = this.segments;
2392     long last = -1L;
2393     for (int i = 0; i < CONTAINS_VALUE_RETRIES; i++) {
2394       long sum = 0L;
2395       for (Segment<K, V, E, S> segment : segments) {
2396         // ensure visibility of most recent completed write
2397         int unused = segment.count; // read-volatile
2398 
2399         AtomicReferenceArray<E> table = segment.table;
2400         for (int j = 0; j < table.length(); j++) {
2401           for (E e = table.get(j); e != null; e = e.getNext()) {
2402             V v = segment.getLiveValue(e);
2403             if (v != null && valueEquivalence().equivalent(value, v)) {
2404               return true;
2405             }
2406           }
2407         }
2408         sum += segment.modCount;
2409       }
2410       if (sum == last) {
2411         break;
2412       }
2413       last = sum;
2414     }
2415     return false;
2416   }
2417 
2418   @CanIgnoreReturnValue
2419   @Override
2420   public V put(K key, V value) {
2421     checkNotNull(key);
2422     checkNotNull(value);
2423     int hash = hash(key);
2424     return segmentFor(hash).put(key, hash, value, false);
2425   }
2426 
2427   @CanIgnoreReturnValue
2428   @Override
2429   public V putIfAbsent(K key, V value) {
2430     checkNotNull(key);
2431     checkNotNull(value);
2432     int hash = hash(key);
2433     return segmentFor(hash).put(key, hash, value, true);
2434   }
2435 
2436   @Override
2437   public void putAll(Map<? extends K, ? extends V> m) {
2438     for (Entry<? extends K, ? extends V> e : m.entrySet()) {
2439       put(e.getKey(), e.getValue());
2440     }
2441   }
2442 
2443   @CanIgnoreReturnValue
2444   @Override
2445   public V remove(@Nullable Object key) {
2446     if (key == null) {
2447       return null;
2448     }
2449     int hash = hash(key);
2450     return segmentFor(hash).remove(key, hash);
2451   }
2452 
2453   @CanIgnoreReturnValue
2454   @Override
2455   public boolean remove(@Nullable Object key, @Nullable Object value) {
2456     if (key == null || value == null) {
2457       return false;
2458     }
2459     int hash = hash(key);
2460     return segmentFor(hash).remove(key, hash, value);
2461   }
2462 
2463   @CanIgnoreReturnValue
2464   @Override
2465   public boolean replace(K key, @Nullable V oldValue, V newValue) {
2466     checkNotNull(key);
2467     checkNotNull(newValue);
2468     if (oldValue == null) {
2469       return false;
2470     }
2471     int hash = hash(key);
2472     return segmentFor(hash).replace(key, hash, oldValue, newValue);
2473   }
2474 
2475   @CanIgnoreReturnValue
2476   @Override
2477   public V replace(K key, V value) {
2478     checkNotNull(key);
2479     checkNotNull(value);
2480     int hash = hash(key);
2481     return segmentFor(hash).replace(key, hash, value);
2482   }
2483 
2484   @Override
2485   public void clear() {
2486     for (Segment<K, V, E, S> segment : segments) {
2487       segment.clear();
2488     }
2489   }
2490 
2491   transient Set<K> keySet;
2492 
2493   @Override
2494   public Set<K> keySet() {
2495     Set<K> ks = keySet;
2496     return (ks != null) ? ks : (keySet = new KeySet());
2497   }
2498 
2499   transient Collection<V> values;
2500 
2501   @Override
2502   public Collection<V> values() {
2503     Collection<V> vs = values;
2504     return (vs != null) ? vs : (values = new Values());
2505   }
2506 
2507   transient Set<Entry<K, V>> entrySet;
2508 
2509   @Override
2510   public Set<Entry<K, V>> entrySet() {
2511     Set<Entry<K, V>> es = entrySet;
2512     return (es != null) ? es : (entrySet = new EntrySet());
2513   }
2514 
2515   // Iterator Support
2516 
2517   abstract class HashIterator<T> implements Iterator<T> {
2518 
2519     int nextSegmentIndex;
2520     int nextTableIndex;
2521     Segment<K, V, E, S> currentSegment;
2522     AtomicReferenceArray<E> currentTable;
2523     E nextEntry;
2524     WriteThroughEntry nextExternal;
2525     WriteThroughEntry lastReturned;
2526 
2527     HashIterator() {
2528       nextSegmentIndex = segments.length - 1;
2529       nextTableIndex = -1;
2530       advance();
2531     }
2532 
2533     @Override
2534     public abstract T next();
2535 
2536     final void advance() {
2537       nextExternal = null;
2538 
2539       if (nextInChain()) {
2540         return;
2541       }
2542 
2543       if (nextInTable()) {
2544         return;
2545       }
2546 
2547       while (nextSegmentIndex >= 0) {
2548         currentSegment = segments[nextSegmentIndex--];
2549         if (currentSegment.count != 0) {
2550           currentTable = currentSegment.table;
2551           nextTableIndex = currentTable.length() - 1;
2552           if (nextInTable()) {
2553             return;
2554           }
2555         }
2556       }
2557     }
2558 
2559     /**
2560      * Finds the next entry in the current chain. Returns {@code true} if an entry was found.
2561      */
2562     boolean nextInChain() {
2563       if (nextEntry != null) {
2564         for (nextEntry = nextEntry.getNext(); nextEntry != null; nextEntry = nextEntry.getNext()) {
2565           if (advanceTo(nextEntry)) {
2566             return true;
2567           }
2568         }
2569       }
2570       return false;
2571     }
2572 
2573     /**
2574      * Finds the next entry in the current table. Returns {@code true} if an entry was found.
2575      */
2576     boolean nextInTable() {
2577       while (nextTableIndex >= 0) {
2578         if ((nextEntry = currentTable.get(nextTableIndex--)) != null) {
2579           if (advanceTo(nextEntry) || nextInChain()) {
2580             return true;
2581           }
2582         }
2583       }
2584       return false;
2585     }
2586 
2587     /**
2588      * Advances to the given entry. Returns {@code true} if the entry was valid, {@code false} if it
2589      * should be skipped.
2590      */
2591     boolean advanceTo(E entry) {
2592       try {
2593         K key = entry.getKey();
2594         V value = getLiveValue(entry);
2595         if (value != null) {
2596           nextExternal = new WriteThroughEntry(key, value);
2597           return true;
2598         } else {
2599           // Skip stale entry.
2600           return false;
2601         }
2602       } finally {
2603         currentSegment.postReadCleanup();
2604       }
2605     }
2606 
2607     @Override
2608     public boolean hasNext() {
2609       return nextExternal != null;
2610     }
2611 
2612     WriteThroughEntry nextEntry() {
2613       if (nextExternal == null) {
2614         throw new NoSuchElementException();
2615       }
2616       lastReturned = nextExternal;
2617       advance();
2618       return lastReturned;
2619     }
2620 
2621     @Override
2622     public void remove() {
2623       checkRemove(lastReturned != null);
2624       MapMakerInternalMap.this.remove(lastReturned.getKey());
2625       lastReturned = null;
2626     }
2627   }
2628 
2629   final class KeyIterator extends HashIterator<K> {
2630 
2631     @Override
2632     public K next() {
2633       return nextEntry().getKey();
2634     }
2635   }
2636 
2637   final class ValueIterator extends HashIterator<V> {
2638 
2639     @Override
2640     public V next() {
2641       return nextEntry().getValue();
2642     }
2643   }
2644 
2645   /**
2646    * Custom Entry class used by EntryIterator.next(), that relays setValue changes to the
2647    * underlying map.
2648    */
2649   final class WriteThroughEntry extends AbstractMapEntry<K, V> {
2650     final K key; // non-null
2651     V value; // non-null
2652 
2653     WriteThroughEntry(K key, V value) {
2654       this.key = key;
2655       this.value = value;
2656     }
2657 
2658     @Override
2659     public K getKey() {
2660       return key;
2661     }
2662 
2663     @Override
2664     public V getValue() {
2665       return value;
2666     }
2667 
2668     @Override
2669     public boolean equals(@Nullable Object object) {
2670       // Cannot use key and value equivalence
2671       if (object instanceof Entry) {
2672         Entry<?, ?> that = (Entry<?, ?>) object;
2673         return key.equals(that.getKey()) && value.equals(that.getValue());
2674       }
2675       return false;
2676     }
2677 
2678     @Override
2679     public int hashCode() {
2680       // Cannot use key and value equivalence
2681       return key.hashCode() ^ value.hashCode();
2682     }
2683 
2684     @Override
2685     public V setValue(V newValue) {
2686       V oldValue = put(key, newValue);
2687       value = newValue; // only if put succeeds
2688       return oldValue;
2689     }
2690   }
2691 
2692   final class EntryIterator extends HashIterator<Entry<K, V>> {
2693 
2694     @Override
2695     public Entry<K, V> next() {
2696       return nextEntry();
2697     }
2698   }
2699 
2700   @WeakOuter
2701   final class KeySet extends SafeToArraySet<K> {
2702 
2703     @Override
2704     public Iterator<K> iterator() {
2705       return new KeyIterator();
2706     }
2707 
2708     @Override
2709     public int size() {
2710       return MapMakerInternalMap.this.size();
2711     }
2712 
2713     @Override
2714     public boolean isEmpty() {
2715       return MapMakerInternalMap.this.isEmpty();
2716     }
2717 
2718     @Override
2719     public boolean contains(Object o) {
2720       return MapMakerInternalMap.this.containsKey(o);
2721     }
2722 
2723     @Override
2724     public boolean remove(Object o) {
2725       return MapMakerInternalMap.this.remove(o) != null;
2726     }
2727 
2728     @Override
2729     public void clear() {
2730       MapMakerInternalMap.this.clear();
2731     }
2732   }
2733 
2734   @WeakOuter
2735   final class Values extends AbstractCollection<V> {
2736 
2737     @Override
2738     public Iterator<V> iterator() {
2739       return new ValueIterator();
2740     }
2741 
2742     @Override
2743     public int size() {
2744       return MapMakerInternalMap.this.size();
2745     }
2746 
2747     @Override
2748     public boolean isEmpty() {
2749       return MapMakerInternalMap.this.isEmpty();
2750     }
2751 
2752     @Override
2753     public boolean contains(Object o) {
2754       return MapMakerInternalMap.this.containsValue(o);
2755     }
2756 
2757     @Override
2758     public void clear() {
2759       MapMakerInternalMap.this.clear();
2760     }
2761 
2762     // super.toArray() may misbehave if size() is inaccurate, at least on old versions of Android.
2763     // https://code.google.com/p/android/issues/detail?id=36519 / http://r.android.com/47508
2764 
2765     @Override
2766     public Object[] toArray() {
2767       return toArrayList(this).toArray();
2768     }
2769 
2770     @Override
2771     public <T> T[] toArray(T[] a) {
2772       return toArrayList(this).toArray(a);
2773     }
2774   }
2775 
2776   @WeakOuter
2777   final class EntrySet extends SafeToArraySet<Entry<K, V>> {
2778 
2779     @Override
2780     public Iterator<Entry<K, V>> iterator() {
2781       return new EntryIterator();
2782     }
2783 
2784     @Override
2785     public boolean contains(Object o) {
2786       if (!(o instanceof Entry)) {
2787         return false;
2788       }
2789       Entry<?, ?> e = (Entry<?, ?>) o;
2790       Object key = e.getKey();
2791       if (key == null) {
2792         return false;
2793       }
2794       V v = MapMakerInternalMap.this.get(key);
2795 
2796       return v != null && valueEquivalence().equivalent(e.getValue(), v);
2797     }
2798 
2799     @Override
2800     public boolean remove(Object o) {
2801       if (!(o instanceof Entry)) {
2802         return false;
2803       }
2804       Entry<?, ?> e = (Entry<?, ?>) o;
2805       Object key = e.getKey();
2806       return key != null && MapMakerInternalMap.this.remove(key, e.getValue());
2807     }
2808 
2809     @Override
2810     public int size() {
2811       return MapMakerInternalMap.this.size();
2812     }
2813 
2814     @Override
2815     public boolean isEmpty() {
2816       return MapMakerInternalMap.this.isEmpty();
2817     }
2818 
2819     @Override
2820     public void clear() {
2821       MapMakerInternalMap.this.clear();
2822     }
2823   }
2824 
2825   private abstract static class SafeToArraySet<E> extends AbstractSet<E> {
2826     // super.toArray() may misbehave if size() is inaccurate, at least on old versions of Android.
2827     // https://code.google.com/p/android/issues/detail?id=36519 / http://r.android.com/47508
2828 
2829     @Override
2830     public Object[] toArray() {
2831       return toArrayList(this).toArray();
2832     }
2833 
2834     @Override
2835     public <T> T[] toArray(T[] a) {
2836       return toArrayList(this).toArray(a);
2837     }
2838   }
2839 
2840   private static <E> ArrayList<E> toArrayList(Collection<E> c) {
2841     // Avoid calling ArrayList(Collection), which may call back into toArray.
2842     ArrayList<E> result = new ArrayList<>(c.size());
2843     Iterators.addAll(result, c.iterator());
2844     return result;
2845   }
2846 
2847   // Serialization Support
2848 
2849   private static final long serialVersionUID = 5;
2850 
2851   Object writeReplace() {
2852     return new SerializationProxy<>(
2853         entryHelper.keyStrength(),
2854         entryHelper.valueStrength(),
2855         keyEquivalence,
2856         entryHelper.valueStrength().defaultEquivalence(),
2857         concurrencyLevel,
2858         this);
2859   }
2860 
2861   /**
2862    * The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
2863    * circular dependency is present, so the proxy must be able to behave as the map itself.
2864    */
2865   abstract static class AbstractSerializationProxy<K, V> extends ForwardingConcurrentMap<K, V>
2866       implements Serializable {
2867     private static final long serialVersionUID = 3;
2868 
2869     final Strength keyStrength;
2870     final Strength valueStrength;
2871     final Equivalence<Object> keyEquivalence;
2872     final Equivalence<Object> valueEquivalence;
2873     final int concurrencyLevel;
2874 
2875     transient ConcurrentMap<K, V> delegate;
2876 
2877     AbstractSerializationProxy(
2878         Strength keyStrength,
2879         Strength valueStrength,
2880         Equivalence<Object> keyEquivalence,
2881         Equivalence<Object> valueEquivalence,
2882         int concurrencyLevel,
2883         ConcurrentMap<K, V> delegate) {
2884       this.keyStrength = keyStrength;
2885       this.valueStrength = valueStrength;
2886       this.keyEquivalence = keyEquivalence;
2887       this.valueEquivalence = valueEquivalence;
2888       this.concurrencyLevel = concurrencyLevel;
2889       this.delegate = delegate;
2890     }
2891 
2892     @Override
2893     protected ConcurrentMap<K, V> delegate() {
2894       return delegate;
2895     }
2896 
2897     void writeMapTo(ObjectOutputStream out) throws IOException {
2898       out.writeInt(delegate.size());
2899       for (Entry<K, V> entry : delegate.entrySet()) {
2900         out.writeObject(entry.getKey());
2901         out.writeObject(entry.getValue());
2902       }
2903       out.writeObject(null); // terminate entries
2904     }
2905 
2906     @SuppressWarnings("deprecation") // serialization of deprecated feature
2907     MapMaker readMapMaker(ObjectInputStream in) throws IOException {
2908       int size = in.readInt();
2909       return new MapMaker()
2910           .initialCapacity(size)
2911           .setKeyStrength(keyStrength)
2912           .setValueStrength(valueStrength)
2913           .keyEquivalence(keyEquivalence)
2914           .concurrencyLevel(concurrencyLevel);
2915     }
2916 
2917     @SuppressWarnings("unchecked")
2918     void readEntries(ObjectInputStream in) throws IOException, ClassNotFoundException {
2919       while (true) {
2920         K key = (K) in.readObject();
2921         if (key == null) {
2922           break; // terminator
2923         }
2924         V value = (V) in.readObject();
2925         delegate.put(key, value);
2926       }
2927     }
2928   }
2929 
2930   /**
2931    * The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
2932    * circular dependency is present, so the proxy must be able to behave as the map itself.
2933    */
2934   private static final class SerializationProxy<K, V> extends AbstractSerializationProxy<K, V> {
2935     private static final long serialVersionUID = 3;
2936 
2937     SerializationProxy(
2938         Strength keyStrength,
2939         Strength valueStrength,
2940         Equivalence<Object> keyEquivalence,
2941         Equivalence<Object> valueEquivalence,
2942         int concurrencyLevel,
2943         ConcurrentMap<K, V> delegate) {
2944       super(
2945           keyStrength,
2946           valueStrength,
2947           keyEquivalence,
2948           valueEquivalence,
2949           concurrencyLevel,
2950           delegate);
2951     }
2952 
2953     private void writeObject(ObjectOutputStream out) throws IOException {
2954       out.defaultWriteObject();
2955       writeMapTo(out);
2956     }
2957 
2958     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
2959       in.defaultReadObject();
2960       MapMaker mapMaker = readMapMaker(in);
2961       delegate = mapMaker.makeMap();
2962       readEntries(in);
2963     }
2964 
2965     private Object readResolve() {
2966       return delegate;
2967     }
2968   }
2969 }