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