Home | History | Annotate | Download | only in collect 
      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 
     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