1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.collect.Lists.newArrayList;
20import static com.google.common.collect.MapMakerInternalMap.DISCARDING_QUEUE;
21import static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD;
22import static com.google.common.collect.MapMakerInternalMap.nullEntry;
23import static com.google.common.collect.MapMakerInternalMap.unset;
24import static java.util.concurrent.TimeUnit.SECONDS;
25
26import com.google.common.base.Equivalence;
27import com.google.common.base.Ticker;
28import com.google.common.collect.MapMaker.RemovalCause;
29import com.google.common.collect.MapMaker.RemovalListener;
30import com.google.common.collect.MapMaker.RemovalNotification;
31import com.google.common.collect.MapMakerInternalMap.EntryFactory;
32import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
33import com.google.common.collect.MapMakerInternalMap.Segment;
34import com.google.common.collect.MapMakerInternalMap.Strength;
35import com.google.common.collect.MapMakerInternalMap.ValueReference;
36import com.google.common.testing.NullPointerTester;
37
38import junit.framework.TestCase;
39
40import java.lang.ref.Reference;
41import java.lang.ref.ReferenceQueue;
42import java.util.Iterator;
43import java.util.LinkedHashMap;
44import java.util.List;
45import java.util.Map;
46import java.util.Random;
47import java.util.concurrent.ConcurrentLinkedQueue;
48import java.util.concurrent.TimeUnit;
49import java.util.concurrent.atomic.AtomicInteger;
50import java.util.concurrent.atomic.AtomicReferenceArray;
51
52/**
53 * @author Charles Fry
54 */
55@SuppressWarnings("deprecation") // many tests of deprecated methods
56public class MapMakerInternalMapTest extends TestCase {
57
58  static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5;
59
60  private static <K, V> MapMakerInternalMap<K, V> makeMap(GenericMapMaker<K, V> maker) {
61    return new MapMakerInternalMap<K, V>((MapMaker) maker);
62  }
63
64  private static <K, V> MapMakerInternalMap<K, V> makeMap(MapMaker maker) {
65    return new MapMakerInternalMap<K, V>(maker);
66  }
67
68  private static MapMaker createMapMaker() {
69    MapMaker maker = new MapMaker();
70    maker.useCustomMap = true;
71    return maker;
72  }
73
74  // constructor tests
75
76  public void testDefaults() {
77    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker());
78
79    assertSame(Strength.STRONG, map.keyStrength);
80    assertSame(Strength.STRONG, map.valueStrength);
81    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
82    assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
83
84    assertEquals(0, map.expireAfterAccessNanos);
85    assertEquals(0, map.expireAfterWriteNanos);
86    assertEquals(MapMaker.UNSET_INT, map.maximumSize);
87
88    assertSame(EntryFactory.STRONG, map.entryFactory);
89    assertSame(MapMaker.NullListener.INSTANCE, map.removalListener);
90    assertSame(DISCARDING_QUEUE, map.removalNotificationQueue);
91    assertSame(Ticker.systemTicker(), map.ticker);
92
93    assertEquals(4, map.concurrencyLevel);
94
95    // concurrency level
96    assertEquals(4, map.segments.length);
97    // initial capacity / concurrency level
98    assertEquals(16 / map.segments.length, map.segments[0].table.length());
99
100    assertFalse(map.evictsBySize());
101    assertFalse(map.expires());
102    assertFalse(map.expiresAfterWrite());
103    assertFalse(map.expiresAfterAccess());
104  }
105
106  public void testSetKeyEquivalence() {
107    Equivalence<Object> testEquivalence = new Equivalence<Object>() {
108      @Override
109      protected boolean doEquivalent(Object a, Object b) {
110        return false;
111      }
112
113      @Override
114      protected int doHash(Object t) {
115        return 0;
116      }
117    };
118
119    MapMakerInternalMap<Object, Object> map =
120        makeMap(createMapMaker().keyEquivalence(testEquivalence));
121    assertSame(testEquivalence, map.keyEquivalence);
122    assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
123  }
124
125  public void testSetValueEquivalence() {
126    Equivalence<Object> testEquivalence = new Equivalence<Object>() {
127      @Override
128      protected boolean doEquivalent(Object a, Object b) {
129        return false;
130      }
131
132      @Override
133      protected int doHash(Object t) {
134        return 0;
135      }
136    };
137
138    MapMakerInternalMap<Object, Object> map =
139        makeMap(createMapMaker().valueEquivalence(testEquivalence));
140    assertSame(testEquivalence, map.valueEquivalence);
141    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
142  }
143
144  public void testSetConcurrencyLevel() {
145    // round up to nearest power of two
146
147    checkConcurrencyLevel(1, 1);
148    checkConcurrencyLevel(2, 2);
149    checkConcurrencyLevel(3, 4);
150    checkConcurrencyLevel(4, 4);
151    checkConcurrencyLevel(5, 8);
152    checkConcurrencyLevel(6, 8);
153    checkConcurrencyLevel(7, 8);
154    checkConcurrencyLevel(8, 8);
155  }
156
157  private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) {
158    MapMakerInternalMap<Object, Object> map =
159        makeMap(createMapMaker().concurrencyLevel(concurrencyLevel));
160    assertEquals(segmentCount, map.segments.length);
161  }
162
163  public void testSetInitialCapacity() {
164    // share capacity over each segment, then round up to nearest power of two
165
166    checkInitialCapacity(1, 0, 1);
167    checkInitialCapacity(1, 1, 1);
168    checkInitialCapacity(1, 2, 2);
169    checkInitialCapacity(1, 3, 4);
170    checkInitialCapacity(1, 4, 4);
171    checkInitialCapacity(1, 5, 8);
172    checkInitialCapacity(1, 6, 8);
173    checkInitialCapacity(1, 7, 8);
174    checkInitialCapacity(1, 8, 8);
175
176    checkInitialCapacity(2, 0, 1);
177    checkInitialCapacity(2, 1, 1);
178    checkInitialCapacity(2, 2, 1);
179    checkInitialCapacity(2, 3, 2);
180    checkInitialCapacity(2, 4, 2);
181    checkInitialCapacity(2, 5, 4);
182    checkInitialCapacity(2, 6, 4);
183    checkInitialCapacity(2, 7, 4);
184    checkInitialCapacity(2, 8, 4);
185
186    checkInitialCapacity(4, 0, 1);
187    checkInitialCapacity(4, 1, 1);
188    checkInitialCapacity(4, 2, 1);
189    checkInitialCapacity(4, 3, 1);
190    checkInitialCapacity(4, 4, 1);
191    checkInitialCapacity(4, 5, 2);
192    checkInitialCapacity(4, 6, 2);
193    checkInitialCapacity(4, 7, 2);
194    checkInitialCapacity(4, 8, 2);
195  }
196
197  private static void checkInitialCapacity(
198      int concurrencyLevel, int initialCapacity, int segmentSize) {
199    MapMakerInternalMap<Object, Object> map = makeMap(
200        createMapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity));
201    for (int i = 0; i < map.segments.length; i++) {
202      assertEquals(segmentSize, map.segments[i].table.length());
203    }
204  }
205
206  public void testSetMaximumSize() {
207    // vary maximumSize wrt concurrencyLevel
208
209    for (int maxSize = 1; maxSize < 8; maxSize++) {
210      checkMaximumSize(1, 8, maxSize);
211      checkMaximumSize(2, 8, maxSize);
212      checkMaximumSize(4, 8, maxSize);
213      checkMaximumSize(8, 8, maxSize);
214    }
215
216    checkMaximumSize(1, 8, Integer.MAX_VALUE);
217    checkMaximumSize(2, 8, Integer.MAX_VALUE);
218    checkMaximumSize(4, 8, Integer.MAX_VALUE);
219    checkMaximumSize(8, 8, Integer.MAX_VALUE);
220
221    // vary initial capacity wrt maximumSize
222
223    for (int capacity = 0; capacity < 8; capacity++) {
224      checkMaximumSize(1, capacity, 4);
225      checkMaximumSize(2, capacity, 4);
226      checkMaximumSize(4, capacity, 4);
227      checkMaximumSize(8, capacity, 4);
228    }
229  }
230
231  private static void checkMaximumSize(int concurrencyLevel, int initialCapacity, int maxSize) {
232    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
233        .concurrencyLevel(concurrencyLevel)
234        .initialCapacity(initialCapacity)
235        .maximumSize(maxSize));
236    int totalCapacity = 0;
237    for (int i = 0; i < map.segments.length; i++) {
238      totalCapacity += map.segments[i].maxSegmentSize;
239    }
240    assertTrue("totalCapcity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity <= maxSize);
241  }
242
243  public void testSetWeakKeys() {
244    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakKeys());
245    checkStrength(map, Strength.WEAK, Strength.STRONG);
246    assertSame(EntryFactory.WEAK, map.entryFactory);
247  }
248
249  @SuppressWarnings("deprecation")
250  public void testSetSoftKeys() {
251    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().softKeys());
252    checkStrength(map, Strength.SOFT, Strength.STRONG);
253    assertSame(EntryFactory.SOFT, map.entryFactory);
254  }
255
256  public void testSetWeakValues() {
257    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakValues());
258    checkStrength(map, Strength.STRONG, Strength.WEAK);
259    assertSame(EntryFactory.STRONG, map.entryFactory);
260  }
261
262  public void testSetSoftValues() {
263    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().softValues());
264    checkStrength(map, Strength.STRONG, Strength.SOFT);
265    assertSame(EntryFactory.STRONG, map.entryFactory);
266  }
267
268  private static void checkStrength(
269      MapMakerInternalMap<Object, Object> map, Strength keyStrength, Strength valueStrength) {
270    assertSame(keyStrength, map.keyStrength);
271    assertSame(valueStrength, map.valueStrength);
272    assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence);
273    assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence);
274  }
275
276  public void testSetExpireAfterWrite() {
277    long duration = 42;
278    TimeUnit unit = SECONDS;
279    MapMakerInternalMap<Object, Object> map =
280        makeMap(createMapMaker().expireAfterWrite(duration, unit));
281    assertEquals(unit.toNanos(duration), map.expireAfterWriteNanos);
282  }
283
284  public void testSetExpireAfterAccess() {
285    long duration = 42;
286    TimeUnit unit = SECONDS;
287    MapMakerInternalMap<Object, Object> map =
288        makeMap(createMapMaker().expireAfterAccess(duration, unit));
289    assertEquals(unit.toNanos(duration), map.expireAfterAccessNanos);
290  }
291
292  public void testSetRemovalListener() {
293    RemovalListener<Object, Object> testListener = new RemovalListener<Object, Object>() {
294      @Override
295      public void onRemoval(RemovalNotification<Object, Object> notification) {}
296    };
297    MapMakerInternalMap<Object, Object> map =
298        makeMap(createMapMaker().removalListener(testListener));
299    assertSame(testListener, map.removalListener);
300  }
301
302  // Removal listener tests
303
304  public void testRemovalListener_explicit() {
305    QueuingRemovalListener<Object, Object> listener =
306        new QueuingRemovalListener<Object, Object>();
307    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
308        .removalListener(listener));
309    assertTrue(listener.isEmpty());
310
311    Object one = new Object();
312    Object two = new Object();
313    Object three = new Object();
314    Object four = new Object();
315    Object five = new Object();
316    Object six = new Object();
317
318    map.put(one, two);
319    map.remove(one);
320    assertNotified(listener, one, two, RemovalCause.EXPLICIT);
321
322    map.put(two, three);
323    map.remove(two, three);
324    assertNotified(listener, two, three, RemovalCause.EXPLICIT);
325
326    map.put(three, four);
327    Iterator<?> i = map.entrySet().iterator();
328    i.next();
329    i.remove();
330    assertNotified(listener, three, four, RemovalCause.EXPLICIT);
331
332    map.put(four, five);
333    i = map.keySet().iterator();
334    i.next();
335    i.remove();
336    assertNotified(listener, four, five, RemovalCause.EXPLICIT);
337
338    map.put(five, six);
339    i = map.values().iterator();
340    i.next();
341    i.remove();
342    assertNotified(listener, five, six, RemovalCause.EXPLICIT);
343
344    assertTrue(listener.isEmpty());
345  }
346
347  public void testRemovalListener_replaced() {
348    QueuingRemovalListener<Object, Object> listener =
349        new QueuingRemovalListener<Object, Object>();
350    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
351        .removalListener(listener));
352    assertTrue(listener.isEmpty());
353
354    Object one = new Object();
355    Object two = new Object();
356    Object three = new Object();
357    Object four = new Object();
358    Object five = new Object();
359    Object six = new Object();
360
361    map.put(one, two);
362    map.put(one, three);
363    assertNotified(listener, one, two, RemovalCause.REPLACED);
364
365    Map<Object, Object> newMap = ImmutableMap.of(one, four);
366    map.putAll(newMap);
367    assertNotified(listener, one, three, RemovalCause.REPLACED);
368
369    map.replace(one, five);
370    assertNotified(listener, one, four, RemovalCause.REPLACED);
371
372    map.replace(one, five, six);
373    assertNotified(listener, one, five, RemovalCause.REPLACED);
374  }
375
376  public void testRemovalListener_collected() {
377    QueuingRemovalListener<Object, Object> listener =
378        new QueuingRemovalListener<Object, Object>();
379    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
380        .concurrencyLevel(1)
381        .softValues()
382        .removalListener(listener));
383    Segment<Object, Object> segment = map.segments[0];
384    assertTrue(listener.isEmpty());
385
386    Object one = new Object();
387    Object two = new Object();
388    Object three = new Object();
389
390    map.put(one, two);
391    map.put(two, three);
392    assertTrue(listener.isEmpty());
393
394    int hash = map.hash(one);
395    ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
396    map.reclaimValue(entry.getValueReference());
397    assertNotified(listener, one, two, RemovalCause.COLLECTED);
398
399    assertTrue(listener.isEmpty());
400  }
401
402  public void testRemovalListener_size() {
403    QueuingRemovalListener<Object, Object> listener =
404        new QueuingRemovalListener<Object, Object>();
405    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
406        .concurrencyLevel(1)
407        .maximumSize(2)
408        .removalListener(listener));
409    assertTrue(listener.isEmpty());
410
411    Object one = new Object();
412    Object two = new Object();
413    Object three = new Object();
414    Object four = new Object();
415
416    map.put(one, two);
417    map.put(two, three);
418    assertTrue(listener.isEmpty());
419    map.put(three, four);
420    assertNotified(listener, one, two, RemovalCause.SIZE);
421
422    assertTrue(listener.isEmpty());
423  }
424
425  static <K, V> void assertNotified(
426      QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause) {
427    RemovalNotification<K, V> notification = listener.remove();
428    assertSame(key, notification.getKey());
429    assertSame(value, notification.getValue());
430    assertSame(cause, notification.getCause());
431  }
432
433  // Segment core tests
434
435  public void testNewEntry() {
436    for (MapMaker maker : allEntryTypeMakers()) {
437      MapMakerInternalMap<Object, Object> map = makeMap(maker);
438
439      Object keyOne = new Object();
440      Object valueOne = new Object();
441      int hashOne = map.hash(keyOne);
442      ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
443      ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne);
444      assertSame(valueOne, valueRefOne.get());
445      entryOne.setValueReference(valueRefOne);
446
447      assertSame(keyOne, entryOne.getKey());
448      assertEquals(hashOne, entryOne.getHash());
449      assertNull(entryOne.getNext());
450      assertSame(valueRefOne, entryOne.getValueReference());
451
452      Object keyTwo = new Object();
453      Object valueTwo = new Object();
454      int hashTwo = map.hash(keyTwo);
455      ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
456      ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo);
457      assertSame(valueTwo, valueRefTwo.get());
458      entryTwo.setValueReference(valueRefTwo);
459
460      assertSame(keyTwo, entryTwo.getKey());
461      assertEquals(hashTwo, entryTwo.getHash());
462      assertSame(entryOne, entryTwo.getNext());
463      assertSame(valueRefTwo, entryTwo.getValueReference());
464    }
465  }
466
467  public void testCopyEntry() {
468    for (MapMaker maker : allEntryTypeMakers()) {
469      MapMakerInternalMap<Object, Object> map = makeMap(maker);
470
471      Object keyOne = new Object();
472      Object valueOne = new Object();
473      int hashOne = map.hash(keyOne);
474      ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
475      entryOne.setValueReference(map.newValueReference(entryOne, valueOne));
476
477      Object keyTwo = new Object();
478      Object valueTwo = new Object();
479      int hashTwo = map.hash(keyTwo);
480      ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
481      entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo));
482      if (map.evictsBySize()) {
483        MapMakerInternalMap.connectEvictables(entryOne, entryTwo);
484      }
485      if (map.expires()) {
486        MapMakerInternalMap.connectExpirables(entryOne, entryTwo);
487      }
488      assertConnected(map, entryOne, entryTwo);
489
490      ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null);
491      assertSame(keyOne, entryOne.getKey());
492      assertEquals(hashOne, entryOne.getHash());
493      assertNull(entryOne.getNext());
494      assertSame(valueOne, copyOne.getValueReference().get());
495      assertConnected(map, copyOne, entryTwo);
496
497      ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne);
498      assertSame(keyTwo, copyTwo.getKey());
499      assertEquals(hashTwo, copyTwo.getHash());
500      assertSame(copyOne, copyTwo.getNext());
501      assertSame(valueTwo, copyTwo.getValueReference().get());
502      assertConnected(map, copyOne, copyTwo);
503    }
504  }
505
506  private static <K, V> void assertConnected(
507      MapMakerInternalMap<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) {
508    if (map.evictsBySize()) {
509      assertSame(two, one.getNextEvictable());
510    }
511    if (map.expires()) {
512      assertSame(two, one.getNextExpirable());
513    }
514  }
515
516  public void testSegmentGetAndContains() {
517    MapMakerInternalMap<Object, Object> map =
518        makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
519    Segment<Object, Object> segment = map.segments[0];
520    // TODO(fry): check recency ordering
521
522    Object key = new Object();
523    int hash = map.hash(key);
524    Object value = new Object();
525    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
526    int index = hash & (table.length() - 1);
527
528    ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null);
529    ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
530    entry.setValueReference(valueRef);
531
532    assertNull(segment.get(key, hash));
533
534    // count == 0
535    table.set(index, entry);
536    assertNull(segment.get(key, hash));
537    assertFalse(segment.containsKey(key, hash));
538    assertFalse(segment.containsValue(value));
539
540    // count == 1
541    segment.count++;
542    assertSame(value, segment.get(key, hash));
543    assertTrue(segment.containsKey(key, hash));
544    assertTrue(segment.containsValue(value));
545    // don't see absent values now that count > 0
546    assertNull(segment.get(new Object(), hash));
547
548    // null key
549    DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry);
550    Object nullValue = new Object();
551    ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue);
552    nullEntry.setValueReference(nullValueRef);
553    table.set(index, nullEntry);
554    // skip the null key
555    assertSame(value, segment.get(key, hash));
556    assertTrue(segment.containsKey(key, hash));
557    assertTrue(segment.containsValue(value));
558    assertFalse(segment.containsValue(nullValue));
559
560    // hash collision
561    DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry);
562    Object dummyValue = new Object();
563    ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue);
564    dummy.setValueReference(dummyValueRef);
565    table.set(index, dummy);
566    assertSame(value, segment.get(key, hash));
567    assertTrue(segment.containsKey(key, hash));
568    assertTrue(segment.containsValue(value));
569    assertTrue(segment.containsValue(dummyValue));
570
571    // key collision
572    dummy = DummyEntry.create(key, hash, entry);
573    dummyValue = new Object();
574    dummyValueRef = map.newValueReference(dummy, dummyValue);
575    dummy.setValueReference(dummyValueRef);
576    table.set(index, dummy);
577    // returns the most recent entry
578    assertSame(dummyValue, segment.get(key, hash));
579    assertTrue(segment.containsKey(key, hash));
580    assertTrue(segment.containsValue(value));
581    assertTrue(segment.containsValue(dummyValue));
582
583    // expired
584    dummy.setExpirationTime(0);
585    assertNull(segment.get(key, hash));
586    assertFalse(segment.containsKey(key, hash));
587    assertTrue(segment.containsValue(value));
588    assertFalse(segment.containsValue(dummyValue));
589  }
590
591  public void testSegmentReplaceValue() {
592    MapMakerInternalMap<Object, Object> map =
593        makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
594    Segment<Object, Object> segment = map.segments[0];
595    // TODO(fry): check recency ordering
596
597    Object key = new Object();
598    int hash = map.hash(key);
599    Object oldValue = new Object();
600    Object newValue = new Object();
601    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
602    int index = hash & (table.length() - 1);
603
604    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
605    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
606    entry.setValueReference(oldValueRef);
607
608    // no entry
609    assertFalse(segment.replace(key, hash, oldValue, newValue));
610    assertEquals(0, segment.count);
611
612    // same value
613    table.set(index, entry);
614    segment.count++;
615    assertEquals(1, segment.count);
616    assertSame(oldValue, segment.get(key, hash));
617    assertTrue(segment.replace(key, hash, oldValue, newValue));
618    assertEquals(1, segment.count);
619    assertSame(newValue, segment.get(key, hash));
620
621    // different value
622    assertFalse(segment.replace(key, hash, oldValue, newValue));
623    assertEquals(1, segment.count);
624    assertSame(newValue, segment.get(key, hash));
625
626    // cleared
627    entry.setValueReference(oldValueRef);
628    assertSame(oldValue, segment.get(key, hash));
629    oldValueRef.clear(null);
630    assertFalse(segment.replace(key, hash, oldValue, newValue));
631    assertEquals(0, segment.count);
632    assertNull(segment.get(key, hash));
633  }
634
635  public void testSegmentReplace() {
636    MapMakerInternalMap<Object, Object> map =
637        makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
638    Segment<Object, Object> segment = map.segments[0];
639    // TODO(fry): check recency ordering
640
641    Object key = new Object();
642    int hash = map.hash(key);
643    Object oldValue = new Object();
644    Object newValue = new Object();
645    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
646    int index = hash & (table.length() - 1);
647
648    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
649    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
650    entry.setValueReference(oldValueRef);
651
652    // no entry
653    assertNull(segment.replace(key, hash, newValue));
654    assertEquals(0, segment.count);
655
656    // same key
657    table.set(index, entry);
658    segment.count++;
659    assertEquals(1, segment.count);
660    assertSame(oldValue, segment.get(key, hash));
661    assertSame(oldValue, segment.replace(key, hash, newValue));
662    assertEquals(1, segment.count);
663    assertSame(newValue, segment.get(key, hash));
664
665    // cleared
666    entry.setValueReference(oldValueRef);
667    assertSame(oldValue, segment.get(key, hash));
668    oldValueRef.clear(null);
669    assertNull(segment.replace(key, hash, newValue));
670    assertEquals(0, segment.count);
671    assertNull(segment.get(key, hash));
672  }
673
674  public void testSegmentPut() {
675    MapMakerInternalMap<Object, Object> map =
676        makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
677    Segment<Object, Object> segment = map.segments[0];
678    // TODO(fry): check recency ordering
679
680    Object key = new Object();
681    int hash = map.hash(key);
682    Object oldValue = new Object();
683    Object newValue = new Object();
684
685    // no entry
686    assertEquals(0, segment.count);
687    assertNull(segment.put(key, hash, oldValue, false));
688    assertEquals(1, segment.count);
689
690    // same key
691    assertSame(oldValue, segment.put(key, hash, newValue, false));
692    assertEquals(1, segment.count);
693    assertSame(newValue, segment.get(key, hash));
694
695    // cleared
696    ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
697    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
698    entry.setValueReference(oldValueRef);
699    assertSame(oldValue, segment.get(key, hash));
700    oldValueRef.clear(null);
701    assertNull(segment.put(key, hash, newValue, false));
702    assertEquals(1, segment.count);
703    assertSame(newValue, segment.get(key, hash));
704  }
705
706  public void testSegmentPutIfAbsent() {
707    MapMakerInternalMap<Object, Object> map =
708        makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
709    Segment<Object, Object> segment = map.segments[0];
710    // TODO(fry): check recency ordering
711
712    Object key = new Object();
713    int hash = map.hash(key);
714    Object oldValue = new Object();
715    Object newValue = new Object();
716
717    // no entry
718    assertEquals(0, segment.count);
719    assertNull(segment.put(key, hash, oldValue, true));
720    assertEquals(1, segment.count);
721
722    // same key
723    assertSame(oldValue, segment.put(key, hash, newValue, true));
724    assertEquals(1, segment.count);
725    assertSame(oldValue, segment.get(key, hash));
726
727    // cleared
728    ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
729    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
730    entry.setValueReference(oldValueRef);
731    assertSame(oldValue, segment.get(key, hash));
732    oldValueRef.clear(null);
733    assertNull(segment.put(key, hash, newValue, true));
734    assertEquals(1, segment.count);
735    assertSame(newValue, segment.get(key, hash));
736  }
737
738  public void testSegmentPut_expand() {
739    MapMakerInternalMap<Object, Object> map =
740        makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
741    Segment<Object, Object> segment = map.segments[0];
742    assertEquals(1, segment.table.length());
743
744    int count = 1024;
745    for (int i = 0; i < count; i++) {
746      Object key = new Object();
747      Object value = new Object();
748      int hash = map.hash(key);
749      assertNull(segment.put(key, hash, value, false));
750      assertTrue(segment.table.length() > i);
751    }
752  }
753
754  public void testSegmentPut_evict() {
755    int maxSize = 10;
756    MapMakerInternalMap<Object, Object> map =
757        makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize));
758
759    // manually add elements to avoid eviction
760    int originalCount = 1024;
761    LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
762    for (int i = 0; i < originalCount; i++) {
763      Object key = new Object();
764      Object value = new Object();
765      map.put(key, value);
766      originalMap.put(key, value);
767      if (i >= maxSize) {
768        Iterator<Object> it = originalMap.keySet().iterator();
769        it.next();
770        it.remove();
771      }
772      assertEquals(originalMap, map);
773    }
774  }
775
776  public void testSegmentRemove() {
777    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
778    Segment<Object, Object> segment = map.segments[0];
779
780    Object key = new Object();
781    int hash = map.hash(key);
782    Object oldValue = new Object();
783    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
784    int index = hash & (table.length() - 1);
785
786    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
787    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
788    entry.setValueReference(oldValueRef);
789
790    // no entry
791    assertEquals(0, segment.count);
792    assertNull(segment.remove(key, hash));
793    assertEquals(0, segment.count);
794
795    // same key
796    table.set(index, entry);
797    segment.count++;
798    assertEquals(1, segment.count);
799    assertSame(oldValue, segment.get(key, hash));
800    assertSame(oldValue, segment.remove(key, hash));
801    assertEquals(0, segment.count);
802    assertNull(segment.get(key, hash));
803
804    // cleared
805    table.set(index, entry);
806    segment.count++;
807    assertEquals(1, segment.count);
808    assertSame(oldValue, segment.get(key, hash));
809    oldValueRef.clear(null);
810    assertNull(segment.remove(key, hash));
811    assertEquals(0, segment.count);
812    assertNull(segment.get(key, hash));
813  }
814
815  public void testSegmentRemoveValue() {
816    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
817    Segment<Object, Object> segment = map.segments[0];
818
819    Object key = new Object();
820    int hash = map.hash(key);
821    Object oldValue = new Object();
822    Object newValue = new Object();
823    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
824    int index = hash & (table.length() - 1);
825
826    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
827    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
828    entry.setValueReference(oldValueRef);
829
830    // no entry
831    assertEquals(0, segment.count);
832    assertNull(segment.remove(key, hash));
833    assertEquals(0, segment.count);
834
835    // same value
836    table.set(index, entry);
837    segment.count++;
838    assertEquals(1, segment.count);
839    assertSame(oldValue, segment.get(key, hash));
840    assertTrue(segment.remove(key, hash, oldValue));
841    assertEquals(0, segment.count);
842    assertNull(segment.get(key, hash));
843
844    // different value
845    table.set(index, entry);
846    segment.count++;
847    assertEquals(1, segment.count);
848    assertSame(oldValue, segment.get(key, hash));
849    assertFalse(segment.remove(key, hash, newValue));
850    assertEquals(1, segment.count);
851    assertSame(oldValue, segment.get(key, hash));
852
853    // cleared
854    assertSame(oldValue, segment.get(key, hash));
855    oldValueRef.clear(null);
856    assertFalse(segment.remove(key, hash, oldValue));
857    assertEquals(0, segment.count);
858    assertNull(segment.get(key, hash));
859  }
860
861  public void testExpand() {
862    MapMakerInternalMap<Object, Object> map =
863        makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
864    Segment<Object, Object> segment = map.segments[0];
865    assertEquals(1, segment.table.length());
866
867    // manually add elements to avoid expansion
868    int originalCount = 1024;
869    ReferenceEntry<Object, Object> entry = null;
870    for (int i = 0; i < originalCount; i++) {
871      Object key = new Object();
872      Object value = new Object();
873      int hash = map.hash(key);
874      // chain all entries together as we only have a single bucket
875      entry = map.newEntry(key, hash, entry);
876      ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
877      entry.setValueReference(valueRef);
878    }
879    segment.table.set(0, entry);
880    segment.count = originalCount;
881    ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
882    assertEquals(originalCount, originalMap.size());
883    assertEquals(originalMap, map);
884
885    for (int i = 1; i <= originalCount * 2; i *= 2) {
886      if (i > 1) {
887        segment.expand();
888      }
889      assertEquals(i, segment.table.length());
890      assertEquals(originalCount, countLiveEntries(map));
891      assertEquals(originalCount, segment.count);
892      assertEquals(originalMap, map);
893    }
894  }
895
896  public void testReclaimKey() {
897    CountingRemovalListener<Object, Object> listener =
898        new CountingRemovalListener<Object, Object>();
899    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
900        .concurrencyLevel(1)
901        .initialCapacity(1)
902        .maximumSize(SMALL_MAX_SIZE)
903        .expireAfterWrite(99999, SECONDS)
904        .removalListener(listener));
905    Segment<Object, Object> segment = map.segments[0];
906    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
907    assertEquals(1, table.length());
908
909    // create 3 objects and chain them together
910    Object keyOne = new Object();
911    Object valueOne = new Object();
912    int hashOne = map.hash(keyOne);
913    DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
914    Object keyTwo = new Object();
915    Object valueTwo = new Object();
916    int hashTwo = map.hash(keyTwo);
917    DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
918    Object keyThree = new Object();
919    Object valueThree = new Object();
920    int hashThree = map.hash(keyThree);
921    DummyEntry<Object, Object> entryThree =
922        createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
923
924    // absent
925    assertEquals(0, listener.getCount());
926    assertFalse(segment.reclaimKey(entryOne, hashOne));
927    assertEquals(0, listener.getCount());
928    table.set(0, entryOne);
929    assertFalse(segment.reclaimKey(entryTwo, hashTwo));
930    assertEquals(0, listener.getCount());
931    table.set(0, entryTwo);
932    assertFalse(segment.reclaimKey(entryThree, hashThree));
933    assertEquals(0, listener.getCount());
934
935    // present
936    table.set(0, entryOne);
937    segment.count = 1;
938    assertTrue(segment.reclaimKey(entryOne, hashOne));
939    assertEquals(1, listener.getCount());
940    assertSame(keyOne, listener.getLastEvictedKey());
941    assertSame(valueOne, listener.getLastEvictedValue());
942    assertTrue(map.removalNotificationQueue.isEmpty());
943    assertFalse(segment.evictionQueue.contains(entryOne));
944    assertFalse(segment.expirationQueue.contains(entryOne));
945    assertEquals(0, segment.count);
946    assertNull(table.get(0));
947  }
948
949  public void testRemoveFromChain() {
950    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
951    Segment<Object, Object> segment = map.segments[0];
952
953    // create 3 objects and chain them together
954    Object keyOne = new Object();
955    Object valueOne = new Object();
956    int hashOne = map.hash(keyOne);
957    DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
958    Object keyTwo = new Object();
959    Object valueTwo = new Object();
960    int hashTwo = map.hash(keyTwo);
961    DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
962    Object keyThree = new Object();
963    Object valueThree = new Object();
964    int hashThree = map.hash(keyThree);
965    DummyEntry<Object, Object> entryThree =
966        createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
967
968    // alone
969    assertNull(segment.removeFromChain(entryOne, entryOne));
970
971    // head
972    assertSame(entryOne, segment.removeFromChain(entryTwo, entryTwo));
973
974    // middle
975    ReferenceEntry<Object, Object> newFirst = segment.removeFromChain(entryThree, entryTwo);
976    assertSame(keyThree, newFirst.getKey());
977    assertSame(valueThree, newFirst.getValueReference().get());
978    assertEquals(hashThree, newFirst.getHash());
979    assertSame(entryOne, newFirst.getNext());
980
981    // tail (remaining entries are copied in reverse order)
982    newFirst = segment.removeFromChain(entryThree, entryOne);
983    assertSame(keyTwo, newFirst.getKey());
984    assertSame(valueTwo, newFirst.getValueReference().get());
985    assertEquals(hashTwo, newFirst.getHash());
986    newFirst = newFirst.getNext();
987    assertSame(keyThree, newFirst.getKey());
988    assertSame(valueThree, newFirst.getValueReference().get());
989    assertEquals(hashThree, newFirst.getHash());
990    assertNull(newFirst.getNext());
991  }
992
993  public void testExpand_cleanup() {
994    MapMakerInternalMap<Object, Object> map =
995        makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
996    Segment<Object, Object> segment = map.segments[0];
997    assertEquals(1, segment.table.length());
998
999    // manually add elements to avoid expansion
1000    // 1/3 null keys, 1/3 null values
1001    int originalCount = 1024;
1002    ReferenceEntry<Object, Object> entry = null;
1003    for (int i = 0; i < originalCount; i++) {
1004      Object key = new Object();
1005      Object value = (i % 3 == 0) ? null : new Object();
1006      int hash = map.hash(key);
1007      if (i % 3 == 1) {
1008        key = null;
1009      }
1010      // chain all entries together as we only have a single bucket
1011      entry = DummyEntry.create(key, hash, entry);
1012      ValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
1013      entry.setValueReference(valueRef);
1014    }
1015    segment.table.set(0, entry);
1016    segment.count = originalCount;
1017    int liveCount = originalCount / 3;
1018    assertEquals(1, segment.table.length());
1019    assertEquals(liveCount, countLiveEntries(map));
1020    ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
1021    assertEquals(liveCount, originalMap.size());
1022    // can't compare map contents until cleanup occurs
1023
1024    for (int i = 1; i <= originalCount * 2; i *= 2) {
1025      if (i > 1) {
1026        segment.expand();
1027      }
1028      assertEquals(i, segment.table.length());
1029      assertEquals(liveCount, countLiveEntries(map));
1030      // expansion cleanup is sloppy, with a goal of avoiding unnecessary copies
1031      assertTrue(segment.count >= liveCount);
1032      assertTrue(segment.count <= originalCount);
1033      assertEquals(originalMap, ImmutableMap.copyOf(map));
1034    }
1035  }
1036
1037  private static <K, V> int countLiveEntries(MapMakerInternalMap<K, V> map) {
1038    int result = 0;
1039    for (Segment<K, V> segment : map.segments) {
1040      AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
1041      for (int i = 0; i < table.length(); i++) {
1042        for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
1043          if (map.isLive(e)) {
1044            result++;
1045          }
1046        }
1047      }
1048    }
1049    return result;
1050  }
1051
1052  public void testClear() {
1053    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1054        .concurrencyLevel(1)
1055        .initialCapacity(1)
1056        .maximumSize(SMALL_MAX_SIZE)
1057        .expireAfterWrite(99999, SECONDS));
1058    Segment<Object, Object> segment = map.segments[0];
1059    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1060    assertEquals(1, table.length());
1061
1062    Object key = new Object();
1063    Object value = new Object();
1064    int hash = map.hash(key);
1065    DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1066    segment.recordWrite(entry);
1067    segment.table.set(0, entry);
1068    segment.readCount.incrementAndGet();
1069    segment.count = 1;
1070
1071    assertSame(entry, table.get(0));
1072    assertSame(entry, segment.evictionQueue.peek());
1073    assertSame(entry, segment.expirationQueue.peek());
1074
1075    segment.clear();
1076    assertNull(table.get(0));
1077    assertTrue(segment.evictionQueue.isEmpty());
1078    assertTrue(segment.expirationQueue.isEmpty());
1079    assertEquals(0, segment.readCount.get());
1080    assertEquals(0, segment.count);
1081  }
1082
1083  public void testRemoveEntry() {
1084    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1085        .concurrencyLevel(1)
1086        .initialCapacity(1)
1087        .maximumSize(SMALL_MAX_SIZE)
1088        .expireAfterWrite(99999, SECONDS)
1089        .removalListener(new CountingRemovalListener<Object, Object>()));
1090    Segment<Object, Object> segment = map.segments[0];
1091    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1092    assertEquals(1, table.length());
1093
1094    Object key = new Object();
1095    Object value = new Object();
1096    int hash = map.hash(key);
1097    DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1098
1099    // remove absent
1100    assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1101
1102    // remove live
1103    segment.recordWrite(entry);
1104    table.set(0, entry);
1105    segment.count = 1;
1106    assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1107    assertNotificationEnqueued(map, key, value, hash);
1108    assertTrue(map.removalNotificationQueue.isEmpty());
1109    assertFalse(segment.evictionQueue.contains(entry));
1110    assertFalse(segment.expirationQueue.contains(entry));
1111    assertEquals(0, segment.count);
1112    assertNull(table.get(0));
1113  }
1114
1115  public void testReclaimValue() {
1116    CountingRemovalListener<Object, Object> listener =
1117        new CountingRemovalListener<Object, Object>();
1118    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1119        .concurrencyLevel(1)
1120        .initialCapacity(1)
1121        .maximumSize(SMALL_MAX_SIZE)
1122        .expireAfterWrite(99999, SECONDS)
1123        .removalListener(listener));
1124    Segment<Object, Object> segment = map.segments[0];
1125    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1126    assertEquals(1, table.length());
1127
1128    Object key = new Object();
1129    Object value = new Object();
1130    int hash = map.hash(key);
1131    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1132    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
1133    entry.setValueReference(valueRef);
1134
1135    // reclaim absent
1136    assertFalse(segment.reclaimValue(key, hash, valueRef));
1137
1138    // reclaim live
1139    segment.recordWrite(entry);
1140    table.set(0, entry);
1141    segment.count = 1;
1142    assertTrue(segment.reclaimValue(key, hash, valueRef));
1143    assertEquals(1, listener.getCount());
1144    assertSame(key, listener.getLastEvictedKey());
1145    assertSame(value, listener.getLastEvictedValue());
1146    assertTrue(map.removalNotificationQueue.isEmpty());
1147    assertFalse(segment.evictionQueue.contains(entry));
1148    assertFalse(segment.expirationQueue.contains(entry));
1149    assertEquals(0, segment.count);
1150    assertNull(table.get(0));
1151
1152    // reclaim wrong value reference
1153    table.set(0, entry);
1154    DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry);
1155    entry.setValueReference(otherValueRef);
1156    assertFalse(segment.reclaimValue(key, hash, valueRef));
1157    assertEquals(1, listener.getCount());
1158    assertTrue(segment.reclaimValue(key, hash, otherValueRef));
1159    assertEquals(2, listener.getCount());
1160    assertSame(key, listener.getLastEvictedKey());
1161    assertSame(value, listener.getLastEvictedValue());
1162  }
1163
1164  public void testClearValue() {
1165    MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1166        .concurrencyLevel(1)
1167        .initialCapacity(1)
1168        .maximumSize(SMALL_MAX_SIZE)
1169        .expireAfterWrite(99999, SECONDS)
1170        .removalListener(new CountingRemovalListener<Object, Object>()));
1171    Segment<Object, Object> segment = map.segments[0];
1172    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1173    assertEquals(1, table.length());
1174
1175    Object key = new Object();
1176    Object value = new Object();
1177    int hash = map.hash(key);
1178    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1179    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
1180    entry.setValueReference(valueRef);
1181
1182    // clear absent
1183    assertFalse(segment.clearValue(key, hash, valueRef));
1184
1185    // clear live
1186    segment.recordWrite(entry);
1187    table.set(0, entry);
1188    // don't increment count; this is used during computation
1189    assertTrue(segment.clearValue(key, hash, valueRef));
1190    // no notification sent with clearValue
1191    assertTrue(map.removalNotificationQueue.isEmpty());
1192    assertFalse(segment.evictionQueue.contains(entry));
1193    assertFalse(segment.expirationQueue.contains(entry));
1194    assertEquals(0, segment.count);
1195    assertNull(table.get(0));
1196
1197    // clear wrong value reference
1198    table.set(0, entry);
1199    DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry);
1200    entry.setValueReference(otherValueRef);
1201    assertFalse(segment.clearValue(key, hash, valueRef));
1202    entry.setValueReference(valueRef);
1203    assertTrue(segment.clearValue(key, hash, valueRef));
1204  }
1205
1206  private static <K, V> void assertNotificationEnqueued(
1207      MapMakerInternalMap<K, V> map, K key, V value, int hash) {
1208    RemovalNotification<K, V> notification = map.removalNotificationQueue.poll();
1209    assertSame(key, notification.getKey());
1210    assertSame(value, notification.getValue());
1211  }
1212
1213  // Segment eviction tests
1214
1215  public void testDrainRecencyQueueOnWrite() {
1216    for (MapMaker maker : allEvictingMakers()) {
1217      MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1218      Segment<Object, Object> segment = map.segments[0];
1219
1220      if (segment.recencyQueue != DISCARDING_QUEUE) {
1221        Object keyOne = new Object();
1222        Object valueOne = new Object();
1223        Object keyTwo = new Object();
1224        Object valueTwo = new Object();
1225
1226        map.put(keyOne, valueOne);
1227        assertTrue(segment.recencyQueue.isEmpty());
1228
1229        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1230          map.get(keyOne);
1231        }
1232        assertFalse(segment.recencyQueue.isEmpty());
1233
1234        map.put(keyTwo, valueTwo);
1235        assertTrue(segment.recencyQueue.isEmpty());
1236      }
1237    }
1238  }
1239
1240  public void testDrainRecencyQueueOnRead() {
1241    for (MapMaker maker : allEvictingMakers()) {
1242      MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1243      Segment<Object, Object> segment = map.segments[0];
1244
1245      if (segment.recencyQueue != DISCARDING_QUEUE) {
1246        Object keyOne = new Object();
1247        Object valueOne = new Object();
1248
1249        // repeated get of the same key
1250
1251        map.put(keyOne, valueOne);
1252        assertTrue(segment.recencyQueue.isEmpty());
1253
1254        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1255          map.get(keyOne);
1256        }
1257        assertFalse(segment.recencyQueue.isEmpty());
1258
1259        for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1260          map.get(keyOne);
1261          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1262        }
1263
1264        // get over many different keys
1265
1266        for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1267          map.put(new Object(), new Object());
1268        }
1269        assertTrue(segment.recencyQueue.isEmpty());
1270
1271        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1272          map.get(keyOne);
1273        }
1274        assertFalse(segment.recencyQueue.isEmpty());
1275
1276        for (Object key : map.keySet()) {
1277          map.get(key);
1278          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1279        }
1280      }
1281    }
1282  }
1283
1284  public void testRecordRead() {
1285    for (MapMaker maker : allEvictingMakers()) {
1286      MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1287      Segment<Object, Object> segment = map.segments[0];
1288      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1289      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1290      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1291        Object key = new Object();
1292        int hash = map.hash(key);
1293        Object value = new Object();
1294
1295        ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1296        // must recordRead for drainRecencyQueue to believe this entry is live
1297        segment.recordWrite(entry);
1298        writeOrder.add(entry);
1299        readOrder.add(entry);
1300      }
1301
1302      checkEvictionQueues(map, segment, readOrder, writeOrder);
1303      checkExpirationTimes(map);
1304
1305      // access some of the elements
1306      Random random = new Random();
1307      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1308      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1309      while (i.hasNext()) {
1310        ReferenceEntry<Object, Object> entry = i.next();
1311        if (random.nextBoolean()) {
1312          segment.recordRead(entry);
1313          reads.add(entry);
1314          i.remove();
1315        }
1316      }
1317      checkAndDrainRecencyQueue(map, segment, reads);
1318      readOrder.addAll(reads);
1319
1320      checkEvictionQueues(map, segment, readOrder, writeOrder);
1321      checkExpirationTimes(map);
1322    }
1323  }
1324
1325  public void testRecordReadOnGet() {
1326    for (MapMaker maker : allEvictingMakers()) {
1327      MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1328      Segment<Object, Object> segment = map.segments[0];
1329      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1330      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1331      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1332        Object key = new Object();
1333        int hash = map.hash(key);
1334        Object value = new Object();
1335
1336        map.put(key, value);
1337        ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1338        writeOrder.add(entry);
1339        readOrder.add(entry);
1340      }
1341
1342      checkEvictionQueues(map, segment, readOrder, writeOrder);
1343      checkExpirationTimes(map);
1344      assertTrue(segment.recencyQueue.isEmpty());
1345
1346      // access some of the elements
1347      Random random = new Random();
1348      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1349      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1350      while (i.hasNext()) {
1351        ReferenceEntry<Object, Object> entry = i.next();
1352        if (random.nextBoolean()) {
1353          map.get(entry.getKey());
1354          reads.add(entry);
1355          i.remove();
1356          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1357        }
1358      }
1359      int undrainedIndex = reads.size() - segment.recencyQueue.size();
1360      checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
1361      readOrder.addAll(reads);
1362
1363      checkEvictionQueues(map, segment, readOrder, writeOrder);
1364      checkExpirationTimes(map);
1365    }
1366  }
1367
1368  public void testRecordWrite() {
1369    for (MapMaker maker : allEvictingMakers()) {
1370      MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1371      Segment<Object, Object> segment = map.segments[0];
1372      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1373      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1374        Object key = new Object();
1375        int hash = map.hash(key);
1376        Object value = new Object();
1377
1378        ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1379        // must recordRead for drainRecencyQueue to believe this entry is live
1380        segment.recordWrite(entry);
1381        writeOrder.add(entry);
1382      }
1383
1384      checkEvictionQueues(map, segment, writeOrder, writeOrder);
1385      checkExpirationTimes(map);
1386
1387      // access some of the elements
1388      Random random = new Random();
1389      List<ReferenceEntry<Object, Object>> writes = Lists.newArrayList();
1390      Iterator<ReferenceEntry<Object, Object>> i = writeOrder.iterator();
1391      while (i.hasNext()) {
1392        ReferenceEntry<Object, Object> entry = i.next();
1393        if (random.nextBoolean()) {
1394          segment.recordWrite(entry);
1395          writes.add(entry);
1396          i.remove();
1397        }
1398      }
1399      writeOrder.addAll(writes);
1400
1401      checkEvictionQueues(map, segment, writeOrder, writeOrder);
1402      checkExpirationTimes(map);
1403    }
1404  }
1405
1406  static <K, V> void checkAndDrainRecencyQueue(MapMakerInternalMap<K, V> map,
1407      Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) {
1408    if (map.evictsBySize() || map.expiresAfterAccess()) {
1409      assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue));
1410    }
1411    segment.drainRecencyQueue();
1412  }
1413
1414  static <K, V> void checkEvictionQueues(MapMakerInternalMap<K, V> map,
1415      Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder,
1416      List<ReferenceEntry<K, V>> writeOrder) {
1417    if (map.evictsBySize()) {
1418      assertSameEntries(readOrder, ImmutableList.copyOf(segment.evictionQueue));
1419    }
1420    if (map.expiresAfterAccess()) {
1421      assertSameEntries(readOrder, ImmutableList.copyOf(segment.expirationQueue));
1422    }
1423    if (map.expiresAfterWrite()) {
1424      assertSameEntries(writeOrder, ImmutableList.copyOf(segment.expirationQueue));
1425    }
1426  }
1427
1428  private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries,
1429      List<ReferenceEntry<K, V>> actualEntries) {
1430    int size = expectedEntries.size();
1431    assertEquals(size, actualEntries.size());
1432    for (int i = 0; i < size; i++) {
1433      ReferenceEntry<K, V> expectedEntry = expectedEntries.get(0);
1434      ReferenceEntry<K, V> actualEntry = actualEntries.get(0);
1435      assertSame(expectedEntry.getKey(), actualEntry.getKey());
1436      assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get());
1437    }
1438  }
1439
1440  static <K, V> void checkExpirationTimes(MapMakerInternalMap<K, V> map) {
1441    if (!map.expires()) {
1442      return;
1443    }
1444
1445    for (Segment<K, V> segment : map.segments) {
1446      long lastExpirationTime = 0;
1447      for (ReferenceEntry<K, V> e : segment.recencyQueue) {
1448        long expirationTime = e.getExpirationTime();
1449        assertTrue(expirationTime >= lastExpirationTime);
1450        lastExpirationTime = expirationTime;
1451      }
1452
1453      lastExpirationTime = 0;
1454      for (ReferenceEntry<K, V> e : segment.expirationQueue) {
1455        long expirationTime = e.getExpirationTime();
1456        assertTrue(expirationTime >= lastExpirationTime);
1457        lastExpirationTime = expirationTime;
1458      }
1459    }
1460  }
1461
1462  public void testEvictEntries() {
1463    int maxSize = 10;
1464    MapMakerInternalMap<Object, Object> map =
1465        makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize));
1466    Segment<Object, Object> segment = map.segments[0];
1467
1468    // manually add elements to avoid eviction
1469    int originalCount = 1024;
1470    ReferenceEntry<Object, Object> entry = null;
1471    LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
1472    for (int i = 0; i < originalCount; i++) {
1473      Object key = new Object();
1474      Object value = new Object();
1475      AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1476      int hash = map.hash(key);
1477      int index = hash & (table.length() - 1);
1478      ReferenceEntry<Object, Object> first = table.get(index);
1479      entry = map.newEntry(key, hash, first);
1480      ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
1481      entry.setValueReference(valueRef);
1482      segment.recordWrite(entry);
1483      table.set(index, entry);
1484      originalMap.put(key, value);
1485    }
1486    segment.count = originalCount;
1487    assertEquals(originalCount, originalMap.size());
1488    assertEquals(originalMap, map);
1489
1490    for (int i = maxSize - 1; i < originalCount; i++) {
1491      assertTrue(segment.evictEntries());
1492      Iterator<Object> it = originalMap.keySet().iterator();
1493      it.next();
1494      it.remove();
1495      assertEquals(originalMap, map);
1496    }
1497    assertFalse(segment.evictEntries());
1498  }
1499
1500  // reference queues
1501
1502  public void testDrainKeyReferenceQueueOnWrite() {
1503    for (MapMaker maker : allKeyValueStrengthMakers()) {
1504      MapMakerInternalMap<Object, Object> map =
1505          makeMap(maker.concurrencyLevel(1));
1506      if (map.usesKeyReferences()) {
1507        Segment<Object, Object> segment = map.segments[0];
1508
1509        Object keyOne = new Object();
1510        int hashOne = map.hash(keyOne);
1511        Object valueOne = new Object();
1512        Object keyTwo = new Object();
1513        Object valueTwo = new Object();
1514
1515        map.put(keyOne, valueOne);
1516        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1517
1518        @SuppressWarnings("unchecked")
1519        Reference<Object> reference = (Reference) entry;
1520        reference.enqueue();
1521
1522        map.put(keyTwo, valueTwo);
1523        assertFalse(map.containsKey(keyOne));
1524        assertFalse(map.containsValue(valueOne));
1525        assertNull(map.get(keyOne));
1526        assertEquals(1, map.size());
1527        assertNull(segment.keyReferenceQueue.poll());
1528      }
1529    }
1530  }
1531
1532  public void testDrainValueReferenceQueueOnWrite() {
1533    for (MapMaker maker : allKeyValueStrengthMakers()) {
1534      MapMakerInternalMap<Object, Object> map =
1535          makeMap(maker.concurrencyLevel(1));
1536      if (map.usesValueReferences()) {
1537        Segment<Object, Object> segment = map.segments[0];
1538
1539        Object keyOne = new Object();
1540        int hashOne = map.hash(keyOne);
1541        Object valueOne = new Object();
1542        Object keyTwo = new Object();
1543        Object valueTwo = new Object();
1544
1545        map.put(keyOne, valueOne);
1546        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1547        ValueReference<Object, Object> valueReference = entry.getValueReference();
1548
1549        @SuppressWarnings("unchecked")
1550        Reference<Object> reference = (Reference) valueReference;
1551        reference.enqueue();
1552
1553        map.put(keyTwo, valueTwo);
1554        assertFalse(map.containsKey(keyOne));
1555        assertFalse(map.containsValue(valueOne));
1556        assertNull(map.get(keyOne));
1557        assertEquals(1, map.size());
1558        assertNull(segment.valueReferenceQueue.poll());
1559      }
1560    }
1561  }
1562
1563  public void testDrainKeyReferenceQueueOnRead() {
1564    for (MapMaker maker : allKeyValueStrengthMakers()) {
1565      MapMakerInternalMap<Object, Object> map =
1566          makeMap(maker.concurrencyLevel(1));
1567      if (map.usesKeyReferences()) {
1568        Segment<Object, Object> segment = map.segments[0];
1569
1570        Object keyOne = new Object();
1571        int hashOne = map.hash(keyOne);
1572        Object valueOne = new Object();
1573        Object keyTwo = new Object();
1574
1575        map.put(keyOne, valueOne);
1576        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1577
1578        @SuppressWarnings("unchecked")
1579        Reference<Object> reference = (Reference) entry;
1580        reference.enqueue();
1581
1582        for (int i = 0; i < SMALL_MAX_SIZE; i++) {
1583          map.get(keyTwo);
1584        }
1585        assertFalse(map.containsKey(keyOne));
1586        assertFalse(map.containsValue(valueOne));
1587        assertNull(map.get(keyOne));
1588        assertEquals(0, map.size());
1589        assertNull(segment.keyReferenceQueue.poll());
1590      }
1591    }
1592  }
1593
1594  public void testDrainValueReferenceQueueOnRead() {
1595    for (MapMaker maker : allKeyValueStrengthMakers()) {
1596      MapMakerInternalMap<Object, Object> map =
1597          makeMap(maker.concurrencyLevel(1));
1598      if (map.usesValueReferences()) {
1599        Segment<Object, Object> segment = map.segments[0];
1600
1601        Object keyOne = new Object();
1602        int hashOne = map.hash(keyOne);
1603        Object valueOne = new Object();
1604        Object keyTwo = new Object();
1605
1606        map.put(keyOne, valueOne);
1607        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1608        ValueReference<Object, Object> valueReference = entry.getValueReference();
1609
1610        @SuppressWarnings("unchecked")
1611        Reference<Object> reference = (Reference) valueReference;
1612        reference.enqueue();
1613
1614        for (int i = 0; i < SMALL_MAX_SIZE; i++) {
1615          map.get(keyTwo);
1616        }
1617        assertFalse(map.containsKey(keyOne));
1618        assertFalse(map.containsValue(valueOne));
1619        assertNull(map.get(keyOne));
1620        assertEquals(0, map.size());
1621        assertNull(segment.valueReferenceQueue.poll());
1622      }
1623    }
1624  }
1625
1626  // utility methods
1627
1628  /**
1629   * Returns an iterable containing all combinations of maximumSize, expireAfterAccess/Write,
1630   * weak/softKeys and weak/softValues.
1631   */
1632  private static Iterable<MapMaker> allEntryTypeMakers() {
1633    List<MapMaker> result = newArrayList(allKeyValueStrengthMakers());
1634    for (MapMaker maker : allKeyValueStrengthMakers()) {
1635      result.add(maker.maximumSize(SMALL_MAX_SIZE));
1636    }
1637    for (MapMaker maker : allKeyValueStrengthMakers()) {
1638      result.add(maker.expireAfterAccess(99999, SECONDS));
1639    }
1640    for (MapMaker maker : allKeyValueStrengthMakers()) {
1641      result.add(maker.expireAfterWrite(99999, SECONDS));
1642    }
1643    for (MapMaker maker : allKeyValueStrengthMakers()) {
1644      result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterAccess(99999, SECONDS));
1645    }
1646    for (MapMaker maker : allKeyValueStrengthMakers()) {
1647      result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterWrite(99999, SECONDS));
1648    }
1649    return result;
1650  }
1651
1652  /**
1653   * Returns an iterable containing all combinations of maximumSize and expireAfterAccess/Write.
1654   */
1655  static Iterable<MapMaker> allEvictingMakers() {
1656    return ImmutableList.of(createMapMaker().maximumSize(SMALL_MAX_SIZE),
1657        createMapMaker().expireAfterAccess(99999, SECONDS),
1658        createMapMaker().expireAfterWrite(99999, SECONDS),
1659        createMapMaker()
1660            .maximumSize(SMALL_MAX_SIZE)
1661            .expireAfterAccess(SMALL_MAX_SIZE, TimeUnit.SECONDS),
1662        createMapMaker()
1663            .maximumSize(SMALL_MAX_SIZE)
1664            .expireAfterWrite(SMALL_MAX_SIZE, TimeUnit.SECONDS));
1665  }
1666
1667  /**
1668   * Returns an iterable containing all combinations weak/softKeys and weak/softValues.
1669   */
1670  @SuppressWarnings("deprecation")
1671  private static Iterable<MapMaker> allKeyValueStrengthMakers() {
1672    return ImmutableList.of(createMapMaker(),
1673        createMapMaker().weakValues(),
1674        createMapMaker().softValues(),
1675        createMapMaker().weakKeys(),
1676        createMapMaker().weakKeys().weakValues(),
1677        createMapMaker().weakKeys().softValues(),
1678        createMapMaker().softKeys(),
1679        createMapMaker().softKeys().weakValues(),
1680        createMapMaker().softKeys().softValues());
1681  }
1682
1683  // listeners
1684
1685  private static class CountingRemovalListener<K, V> implements RemovalListener<K, V> {
1686    private final AtomicInteger count = new AtomicInteger();
1687    private K lastKey;
1688    private V lastValue;
1689
1690    @Override
1691    public void onRemoval(RemovalNotification<K, V> notification) {
1692      count.incrementAndGet();
1693      lastKey = notification.getKey();
1694      lastValue = notification.getValue();
1695    }
1696
1697    public int getCount() {
1698      return count.get();
1699    }
1700
1701    public K getLastEvictedKey() {
1702      return lastKey;
1703    }
1704
1705    public V getLastEvictedValue() {
1706      return lastValue;
1707    }
1708  }
1709
1710  static class QueuingRemovalListener<K, V>
1711      extends ConcurrentLinkedQueue<RemovalNotification<K, V>> implements RemovalListener<K, V> {
1712    @Override
1713    public void onRemoval(RemovalNotification<K, V> notification) {
1714      add(notification);
1715    }
1716  }
1717
1718  // entries and values
1719
1720  private static <K, V> DummyEntry<K, V> createDummyEntry(
1721      K key, int hash, V value, ReferenceEntry<K, V> next) {
1722    DummyEntry<K, V> entry = DummyEntry.create(key, hash, next);
1723    DummyValueReference<K, V> valueRef = DummyValueReference.create(value, entry);
1724    entry.setValueReference(valueRef);
1725    return entry;
1726  }
1727
1728  static class DummyEntry<K, V> implements ReferenceEntry<K, V> {
1729    private K key;
1730    private final int hash;
1731    private final ReferenceEntry<K, V> next;
1732
1733    public DummyEntry(K key, int hash, ReferenceEntry<K, V> next) {
1734      this.key = key;
1735      this.hash = hash;
1736      this.next = next;
1737    }
1738
1739    public static <K, V> DummyEntry<K, V> create(K key, int hash, ReferenceEntry<K, V> next) {
1740      return new DummyEntry<K, V>(key, hash, next);
1741    }
1742
1743    public void clearKey() {
1744      this.key = null;
1745    }
1746
1747    private ValueReference<K, V> valueReference = unset();
1748
1749    @Override
1750    public ValueReference<K, V> getValueReference() {
1751      return valueReference;
1752    }
1753
1754    @Override
1755    public void setValueReference(ValueReference<K, V> valueReference) {
1756      this.valueReference = valueReference;
1757    }
1758
1759    @Override
1760    public ReferenceEntry<K, V> getNext() {
1761      return next;
1762    }
1763
1764    @Override
1765    public int getHash() {
1766      return hash;
1767    }
1768
1769    @Override
1770    public K getKey() {
1771      return key;
1772    }
1773
1774    private long expirationTime = Long.MAX_VALUE;
1775
1776    @Override
1777    public long getExpirationTime() {
1778      return expirationTime;
1779    }
1780
1781    @Override
1782    public void setExpirationTime(long time) {
1783      this.expirationTime = time;
1784    }
1785
1786    private ReferenceEntry<K, V> nextExpirable = nullEntry();
1787
1788    @Override
1789    public ReferenceEntry<K, V> getNextExpirable() {
1790      return nextExpirable;
1791    }
1792
1793    @Override
1794    public void setNextExpirable(ReferenceEntry<K, V> next) {
1795      this.nextExpirable = next;
1796    }
1797
1798    private ReferenceEntry<K, V> previousExpirable = nullEntry();
1799
1800    @Override
1801    public ReferenceEntry<K, V> getPreviousExpirable() {
1802      return previousExpirable;
1803    }
1804
1805    @Override
1806    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
1807      this.previousExpirable = previous;
1808    }
1809
1810    private ReferenceEntry<K, V> nextEvictable = nullEntry();
1811
1812    @Override
1813    public ReferenceEntry<K, V> getNextEvictable() {
1814      return nextEvictable;
1815    }
1816
1817    @Override
1818    public void setNextEvictable(ReferenceEntry<K, V> next) {
1819      this.nextEvictable = next;
1820    }
1821
1822    private ReferenceEntry<K, V> previousEvictable = nullEntry();
1823
1824    @Override
1825    public ReferenceEntry<K, V> getPreviousEvictable() {
1826      return previousEvictable;
1827    }
1828
1829    @Override
1830    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
1831      this.previousEvictable = previous;
1832    }
1833  }
1834
1835  static class DummyValueReference<K, V> implements ValueReference<K, V> {
1836    final ReferenceEntry<K, V> entry;
1837    private V value;
1838
1839    public DummyValueReference(V value, ReferenceEntry<K, V> entry) {
1840      this.value = value;
1841      this.entry = entry;
1842    }
1843
1844    public static <K, V> DummyValueReference<K, V> create(V value, ReferenceEntry<K, V> entry) {
1845      return new DummyValueReference<K, V>(value, entry);
1846    }
1847
1848    @Override
1849    public V get() {
1850      return value;
1851    }
1852
1853    @Override
1854    public ReferenceEntry<K, V> getEntry() {
1855      return entry;
1856    }
1857
1858    @Override
1859    public ValueReference<K, V> copyFor(ReferenceQueue<V> queue, ReferenceEntry<K, V> entry) {
1860      return new DummyValueReference<K, V>(value, entry);
1861    }
1862
1863    boolean computing = false;
1864
1865    public void setComputing(boolean computing) {
1866      this.computing = computing;
1867    }
1868
1869    @Override
1870    public boolean isComputingReference() {
1871      return computing;
1872    }
1873
1874    @Override
1875    public V waitForValue() {
1876      return get();
1877    }
1878
1879    @Override
1880    public void clear(ValueReference<K, V> newValue) {
1881      value = null;
1882    }
1883  }
1884
1885  public void testNullParameters() throws Exception {
1886    NullPointerTester tester = new NullPointerTester();
1887    tester.testAllPublicInstanceMethods(makeMap(createMapMaker()));
1888  }
1889
1890}
1891