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