1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.cache;
18
19import static com.google.common.cache.CacheBuilder.NULL_TICKER;
20import static com.google.common.cache.LocalCache.DISCARDING_QUEUE;
21import static com.google.common.cache.LocalCache.DRAIN_THRESHOLD;
22import static com.google.common.cache.LocalCache.nullEntry;
23import static com.google.common.cache.LocalCache.unset;
24import static com.google.common.cache.TestingCacheLoaders.identityLoader;
25import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener;
26import static com.google.common.cache.TestingRemovalListeners.queuingRemovalListener;
27import static com.google.common.cache.TestingWeighers.constantWeigher;
28import static com.google.common.collect.Lists.newArrayList;
29import static com.google.common.collect.Maps.immutableEntry;
30import static java.util.concurrent.TimeUnit.MINUTES;
31import static java.util.concurrent.TimeUnit.NANOSECONDS;
32import static java.util.concurrent.TimeUnit.SECONDS;
33
34import com.google.common.base.Equivalence;
35import com.google.common.base.Ticker;
36import com.google.common.cache.LocalCache.EntryFactory;
37import com.google.common.cache.LocalCache.LoadingValueReference;
38import com.google.common.cache.LocalCache.LocalLoadingCache;
39import com.google.common.cache.LocalCache.LocalManualCache;
40import com.google.common.cache.LocalCache.ReferenceEntry;
41import com.google.common.cache.LocalCache.Segment;
42import com.google.common.cache.LocalCache.Strength;
43import com.google.common.cache.LocalCache.ValueReference;
44import com.google.common.cache.TestingCacheLoaders.CountingLoader;
45import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener;
46import com.google.common.cache.TestingRemovalListeners.QueuingRemovalListener;
47import com.google.common.collect.ImmutableList;
48import com.google.common.collect.ImmutableMap;
49import com.google.common.collect.ImmutableSet;
50import com.google.common.collect.Lists;
51import com.google.common.collect.Maps;
52import com.google.common.collect.testing.MapTestSuiteBuilder;
53import com.google.common.collect.testing.TestStringMapGenerator;
54import com.google.common.collect.testing.features.CollectionFeature;
55import com.google.common.collect.testing.features.CollectionSize;
56import com.google.common.collect.testing.features.MapFeature;
57import com.google.common.testing.FakeTicker;
58import com.google.common.testing.NullPointerTester;
59import com.google.common.testing.SerializableTester;
60import com.google.common.testing.TestLogHandler;
61
62import junit.framework.Test;
63import junit.framework.TestCase;
64import junit.framework.TestSuite;
65
66import java.io.Serializable;
67import java.lang.ref.Reference;
68import java.lang.ref.ReferenceQueue;
69import java.util.Iterator;
70import java.util.LinkedHashMap;
71import java.util.List;
72import java.util.Map;
73import java.util.Map.Entry;
74import java.util.Random;
75import java.util.Set;
76import java.util.concurrent.CountDownLatch;
77import java.util.concurrent.ExecutionException;
78import java.util.concurrent.TimeUnit;
79import java.util.concurrent.atomic.AtomicReferenceArray;
80import java.util.logging.LogRecord;
81
82/**
83 * @author Charles Fry
84 */
85public class LocalCacheTest extends TestCase {
86
87  public static Test suite() {
88    TestSuite suite = new TestSuite();
89    suite.addTestSuite(LocalCacheTest.class);
90    suite.addTest(MapTestSuiteBuilder.using(new TestStringMapGenerator() {
91          @Override public Map<String, String> create(
92              Entry<String, String>[] entries) {
93            LocalCache<String, String> map = makeLocalCache(createCacheBuilder());
94            for (Entry<String, String> entry : entries) {
95              map.put(entry.getKey(), entry.getValue());
96            }
97            return map;
98          }
99
100        }).named("LocalCache with defaults")
101        .withFeatures(CollectionSize.ANY, MapFeature.GENERAL_PURPOSE,
102            CollectionFeature.SUPPORTS_ITERATOR_REMOVE)
103        .createTestSuite());
104    return suite;
105  }
106
107  static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5;
108
109  TestLogHandler logHandler;
110
111  @Override
112  public void setUp() throws Exception {
113    super.setUp();
114    logHandler = new TestLogHandler();
115    LocalCache.logger.addHandler(logHandler);
116  }
117
118  @Override
119  public void tearDown() throws Exception {
120    super.tearDown();
121    LocalCache.logger.removeHandler(logHandler);
122  }
123
124  private Throwable popLoggedThrowable() {
125    List<LogRecord> logRecords = logHandler.getStoredLogRecords();
126    assertSame(1, logRecords.size());
127    LogRecord logRecord = logRecords.get(0);
128    logHandler.clear();
129    return logRecord.getThrown();
130  }
131
132  private void checkNothingLogged() {
133    assertTrue(logHandler.getStoredLogRecords().isEmpty());
134  }
135
136  private void checkLogged(Throwable t) {
137    assertSame(t, popLoggedThrowable());
138  }
139
140  private static <K, V> LocalCache<K, V> makeLocalCache(
141      CacheBuilder<? super K, ? super V> builder) {
142    return new LocalCache<K, V>(builder, null);
143  }
144
145  private static CacheBuilder<Object, Object> createCacheBuilder() {
146    return new CacheBuilder<Object, Object>();
147  }
148
149  // constructor tests
150
151  public void testDefaults() {
152    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
153
154    assertSame(Strength.STRONG, map.keyStrength);
155    assertSame(Strength.STRONG, map.valueStrength);
156    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
157    assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
158
159    assertEquals(0, map.expireAfterAccessNanos);
160    assertEquals(0, map.expireAfterWriteNanos);
161    assertEquals(0, map.refreshNanos);
162    assertEquals(CacheBuilder.UNSET_INT, map.maxWeight);
163
164    assertSame(EntryFactory.STRONG, map.entryFactory);
165    assertSame(CacheBuilder.NullListener.INSTANCE, map.removalListener);
166    assertSame(DISCARDING_QUEUE, map.removalNotificationQueue);
167    assertSame(NULL_TICKER, map.ticker);
168
169    assertEquals(4, map.concurrencyLevel);
170
171    // concurrency level
172    assertEquals(4, map.segments.length);
173    // initial capacity / concurrency level
174    assertEquals(16 / map.segments.length, map.segments[0].table.length());
175
176    assertFalse(map.evictsBySize());
177    assertFalse(map.expires());
178    assertFalse(map.expiresAfterWrite());
179    assertFalse(map.expiresAfterAccess());
180    assertFalse(map.refreshes());
181  }
182
183  public void testSetKeyEquivalence() {
184    Equivalence<Object> testEquivalence = new Equivalence<Object>() {
185      @Override
186      protected boolean doEquivalent(Object a, Object b) {
187        return false;
188      }
189
190      @Override
191      protected int doHash(Object t) {
192        return 0;
193      }
194    };
195
196    LocalCache<Object, Object> map =
197        makeLocalCache(createCacheBuilder().keyEquivalence(testEquivalence));
198    assertSame(testEquivalence, map.keyEquivalence);
199    assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
200  }
201
202  public void testSetValueEquivalence() {
203    Equivalence<Object> testEquivalence = new Equivalence<Object>() {
204      @Override
205      protected boolean doEquivalent(Object a, Object b) {
206        return false;
207      }
208
209      @Override
210      protected int doHash(Object t) {
211        return 0;
212      }
213    };
214
215    LocalCache<Object, Object> map =
216        makeLocalCache(createCacheBuilder().valueEquivalence(testEquivalence));
217    assertSame(testEquivalence, map.valueEquivalence);
218    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
219  }
220
221  public void testSetConcurrencyLevel() {
222    // round up to nearest power of two
223
224    checkConcurrencyLevel(1, 1);
225    checkConcurrencyLevel(2, 2);
226    checkConcurrencyLevel(3, 4);
227    checkConcurrencyLevel(4, 4);
228    checkConcurrencyLevel(5, 8);
229    checkConcurrencyLevel(6, 8);
230    checkConcurrencyLevel(7, 8);
231    checkConcurrencyLevel(8, 8);
232  }
233
234  private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) {
235    LocalCache<Object, Object> map =
236        makeLocalCache(createCacheBuilder().concurrencyLevel(concurrencyLevel));
237    assertEquals(segmentCount, map.segments.length);
238  }
239
240  public void testSetInitialCapacity() {
241    // share capacity over each segment, then round up to nearest power of two
242
243    checkInitialCapacity(1, 0, 1);
244    checkInitialCapacity(1, 1, 1);
245    checkInitialCapacity(1, 2, 2);
246    checkInitialCapacity(1, 3, 4);
247    checkInitialCapacity(1, 4, 4);
248    checkInitialCapacity(1, 5, 8);
249    checkInitialCapacity(1, 6, 8);
250    checkInitialCapacity(1, 7, 8);
251    checkInitialCapacity(1, 8, 8);
252
253    checkInitialCapacity(2, 0, 1);
254    checkInitialCapacity(2, 1, 1);
255    checkInitialCapacity(2, 2, 1);
256    checkInitialCapacity(2, 3, 2);
257    checkInitialCapacity(2, 4, 2);
258    checkInitialCapacity(2, 5, 4);
259    checkInitialCapacity(2, 6, 4);
260    checkInitialCapacity(2, 7, 4);
261    checkInitialCapacity(2, 8, 4);
262
263    checkInitialCapacity(4, 0, 1);
264    checkInitialCapacity(4, 1, 1);
265    checkInitialCapacity(4, 2, 1);
266    checkInitialCapacity(4, 3, 1);
267    checkInitialCapacity(4, 4, 1);
268    checkInitialCapacity(4, 5, 2);
269    checkInitialCapacity(4, 6, 2);
270    checkInitialCapacity(4, 7, 2);
271    checkInitialCapacity(4, 8, 2);
272  }
273
274  private static void checkInitialCapacity(
275      int concurrencyLevel, int initialCapacity, int segmentSize) {
276    LocalCache<Object, Object> map = makeLocalCache(
277        createCacheBuilder().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity));
278    for (int i = 0; i < map.segments.length; i++) {
279      assertEquals(segmentSize, map.segments[i].table.length());
280    }
281  }
282
283  public void testSetMaximumSize() {
284    // vary maximumSize wrt concurrencyLevel
285
286    for (int maxSize = 1; maxSize < 100; maxSize++) {
287      checkMaximumSize(1, 8, maxSize);
288      checkMaximumSize(2, 8, maxSize);
289      checkMaximumSize(4, 8, maxSize);
290      checkMaximumSize(8, 8, maxSize);
291    }
292
293    checkMaximumSize(1, 8, Long.MAX_VALUE);
294    checkMaximumSize(2, 8, Long.MAX_VALUE);
295    checkMaximumSize(4, 8, Long.MAX_VALUE);
296    checkMaximumSize(8, 8, Long.MAX_VALUE);
297
298    // vary initial capacity wrt maximumSize
299
300    for (int capacity = 0; capacity < 8; capacity++) {
301      checkMaximumSize(1, capacity, 4);
302      checkMaximumSize(2, capacity, 4);
303      checkMaximumSize(4, capacity, 4);
304      checkMaximumSize(8, capacity, 4);
305    }
306  }
307
308  private static void checkMaximumSize(int concurrencyLevel, int initialCapacity, long maxSize) {
309    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
310        .concurrencyLevel(concurrencyLevel)
311        .initialCapacity(initialCapacity)
312        .maximumSize(maxSize));
313    long totalCapacity = 0;
314    assertTrue("segments=" + map.segments.length + ", maxSize=" + maxSize,
315        map.segments.length <= Math.max(1, maxSize / 10));
316    for (int i = 0; i < map.segments.length; i++) {
317      totalCapacity += map.segments[i].maxSegmentWeight;
318    }
319    assertTrue("totalCapacity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity == maxSize);
320
321    map = makeLocalCache(createCacheBuilder()
322        .concurrencyLevel(concurrencyLevel)
323        .initialCapacity(initialCapacity)
324        .maximumWeight(maxSize)
325        .weigher(constantWeigher(1)));
326    assertTrue("segments=" + map.segments.length + ", maxSize=" + maxSize,
327        map.segments.length <= Math.max(1, maxSize / 10));
328    totalCapacity = 0;
329    for (int i = 0; i < map.segments.length; i++) {
330      totalCapacity += map.segments[i].maxSegmentWeight;
331    }
332    assertTrue("totalCapacity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity == maxSize);
333  }
334
335  public void testSetWeigher() {
336    Weigher<Object, Object> testWeigher = new Weigher<Object, Object>() {
337      @Override
338      public int weigh(Object key, Object value) {
339        return 42;
340      }
341    };
342    LocalCache<Object, Object> map =
343        makeLocalCache(createCacheBuilder().maximumWeight(1).weigher(testWeigher));
344    assertSame(testWeigher, map.weigher);
345  }
346
347  public void testSetWeakKeys() {
348    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().weakKeys());
349    checkStrength(map, Strength.WEAK, Strength.STRONG);
350    assertSame(EntryFactory.WEAK, map.entryFactory);
351  }
352
353  public void testSetWeakValues() {
354    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().weakValues());
355    checkStrength(map, Strength.STRONG, Strength.WEAK);
356    assertSame(EntryFactory.STRONG, map.entryFactory);
357  }
358
359  public void testSetSoftValues() {
360    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().softValues());
361    checkStrength(map, Strength.STRONG, Strength.SOFT);
362    assertSame(EntryFactory.STRONG, map.entryFactory);
363  }
364
365  private static void checkStrength(
366      LocalCache<Object, Object> map, Strength keyStrength, Strength valueStrength) {
367    assertSame(keyStrength, map.keyStrength);
368    assertSame(valueStrength, map.valueStrength);
369    assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence);
370    assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence);
371  }
372
373  public void testSetExpireAfterWrite() {
374    long duration = 42;
375    TimeUnit unit = TimeUnit.SECONDS;
376    LocalCache<Object, Object> map =
377        makeLocalCache(createCacheBuilder().expireAfterWrite(duration, unit));
378    assertEquals(unit.toNanos(duration), map.expireAfterWriteNanos);
379  }
380
381  public void testSetExpireAfterAccess() {
382    long duration = 42;
383    TimeUnit unit = TimeUnit.SECONDS;
384    LocalCache<Object, Object> map =
385        makeLocalCache(createCacheBuilder().expireAfterAccess(duration, unit));
386    assertEquals(unit.toNanos(duration), map.expireAfterAccessNanos);
387  }
388
389  public void testSetRefresh() {
390    long duration = 42;
391    TimeUnit unit = TimeUnit.SECONDS;
392    LocalCache<Object, Object> map =
393        makeLocalCache(createCacheBuilder().refreshAfterWrite(duration, unit));
394    assertEquals(unit.toNanos(duration), map.refreshNanos);
395  }
396
397  public void testSetRemovalListener() {
398    RemovalListener<Object, Object> testListener = TestingRemovalListeners.nullRemovalListener();
399    LocalCache<Object, Object> map =
400        makeLocalCache(createCacheBuilder().removalListener(testListener));
401    assertSame(testListener, map.removalListener);
402  }
403
404  public void testSetTicker() {
405    Ticker testTicker = new Ticker() {
406      @Override
407      public long read() {
408        return 0;
409      }
410    };
411    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().ticker(testTicker));
412    assertSame(testTicker, map.ticker);
413  }
414
415  public void testEntryFactory() {
416    assertSame(EntryFactory.STRONG,
417        EntryFactory.getFactory(Strength.STRONG, false, false));
418    assertSame(EntryFactory.STRONG_ACCESS,
419        EntryFactory.getFactory(Strength.STRONG, true, false));
420    assertSame(EntryFactory.STRONG_WRITE,
421        EntryFactory.getFactory(Strength.STRONG, false, true));
422    assertSame(EntryFactory.STRONG_ACCESS_WRITE,
423        EntryFactory.getFactory(Strength.STRONG, true, true));
424    assertSame(EntryFactory.WEAK,
425        EntryFactory.getFactory(Strength.WEAK, false, false));
426    assertSame(EntryFactory.WEAK_ACCESS,
427        EntryFactory.getFactory(Strength.WEAK, true, false));
428    assertSame(EntryFactory.WEAK_WRITE,
429        EntryFactory.getFactory(Strength.WEAK, false, true));
430    assertSame(EntryFactory.WEAK_ACCESS_WRITE,
431        EntryFactory.getFactory(Strength.WEAK, true, true));
432  }
433
434  // computation tests
435
436  public void testCompute() throws ExecutionException {
437    CountingLoader loader = new CountingLoader();
438    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
439    assertEquals(0, loader.getCount());
440
441    Object key = new Object();
442    Object value = map.get(key, loader);
443    assertEquals(1, loader.getCount());
444    assertEquals(value, map.get(key, loader));
445    assertEquals(1, loader.getCount());
446  }
447
448  public void testRecordReadOnCompute() throws ExecutionException {
449    CountingLoader loader = new CountingLoader();
450    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
451      LocalCache<Object, Object> map =
452          makeLocalCache(builder.concurrencyLevel(1));
453      Segment<Object, Object> segment = map.segments[0];
454      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
455      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
456      for (int i = 0; i < SMALL_MAX_SIZE; i++) {
457        Object key = new Object();
458        int hash = map.hash(key);
459
460        map.get(key, loader);
461        ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
462        writeOrder.add(entry);
463        readOrder.add(entry);
464      }
465
466      checkEvictionQueues(map, segment, readOrder, writeOrder);
467      checkExpirationTimes(map);
468      assertTrue(segment.recencyQueue.isEmpty());
469
470      // access some of the elements
471      Random random = new Random();
472      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
473      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
474      while (i.hasNext()) {
475        ReferenceEntry<Object, Object> entry = i.next();
476        if (random.nextBoolean()) {
477          map.get(entry.getKey(), loader);
478          reads.add(entry);
479          i.remove();
480          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
481        }
482      }
483      int undrainedIndex = reads.size() - segment.recencyQueue.size();
484      checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
485      readOrder.addAll(reads);
486
487      checkEvictionQueues(map, segment, readOrder, writeOrder);
488      checkExpirationTimes(map);
489    }
490  }
491
492  public void testComputeExistingEntry() throws ExecutionException {
493    CountingLoader loader = new CountingLoader();
494    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
495    assertEquals(0, loader.getCount());
496
497    Object key = new Object();
498    Object value = new Object();
499    map.put(key, value);
500
501    assertEquals(value, map.get(key, loader));
502    assertEquals(0, loader.getCount());
503  }
504
505  public void testComputePartiallyCollectedKey() throws ExecutionException {
506    CacheBuilder<Object, Object> builder = createCacheBuilder().concurrencyLevel(1);
507    CountingLoader loader = new CountingLoader();
508    LocalCache<Object, Object> map = makeLocalCache(builder);
509    Segment<Object, Object> segment = map.segments[0];
510    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
511    assertEquals(0, loader.getCount());
512
513    Object key = new Object();
514    int hash = map.hash(key);
515    Object value = new Object();
516    int index = hash & (table.length() - 1);
517
518    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
519    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
520    entry.setValueReference(valueRef);
521    table.set(index, entry);
522    segment.count++;
523
524    assertSame(value, map.get(key, loader));
525    assertEquals(0, loader.getCount());
526    assertEquals(1, segment.count);
527
528    entry.clearKey();
529    assertNotSame(value, map.get(key, loader));
530    assertEquals(1, loader.getCount());
531    assertEquals(2, segment.count);
532  }
533
534  public void testComputePartiallyCollectedValue() throws ExecutionException {
535    CacheBuilder<Object, Object> builder = createCacheBuilder().concurrencyLevel(1);
536    CountingLoader loader = new CountingLoader();
537    LocalCache<Object, Object> map = makeLocalCache(builder);
538    Segment<Object, Object> segment = map.segments[0];
539    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
540    assertEquals(0, loader.getCount());
541
542    Object key = new Object();
543    int hash = map.hash(key);
544    Object value = new Object();
545    int index = hash & (table.length() - 1);
546
547    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
548    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
549    entry.setValueReference(valueRef);
550    table.set(index, entry);
551    segment.count++;
552
553    assertSame(value, map.get(key, loader));
554    assertEquals(0, loader.getCount());
555    assertEquals(1, segment.count);
556
557    valueRef.clear();
558    assertNotSame(value, map.get(key, loader));
559    assertEquals(1, loader.getCount());
560    assertEquals(1, segment.count);
561  }
562
563  public void testComputeExpiredEntry() throws ExecutionException {
564    CacheBuilder<Object, Object> builder = createCacheBuilder()
565        .expireAfterWrite(1, TimeUnit.NANOSECONDS);
566    CountingLoader loader = new CountingLoader();
567    LocalCache<Object, Object> map = makeLocalCache(builder);
568    assertEquals(0, loader.getCount());
569
570    Object key = new Object();
571    Object one = map.get(key, loader);
572    assertEquals(1, loader.getCount());
573
574    Object two = map.get(key, loader);
575    assertNotSame(one, two);
576    assertEquals(2, loader.getCount());
577  }
578
579  public void testValues() {
580    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
581    map.put("foo", "bar");
582    map.put("baz", "bar");
583    map.put("quux", "quux");
584    assertFalse(map.values() instanceof Set);
585    assertTrue(map.values().removeAll(ImmutableSet.of("bar")));
586    assertEquals(1, map.size());
587  }
588
589  public void testCopyEntry_computing() {
590    final CountDownLatch startSignal = new CountDownLatch(1);
591    final CountDownLatch computingSignal = new CountDownLatch(1);
592    final CountDownLatch doneSignal = new CountDownLatch(2);
593    final Object computedObject = new Object();
594
595    final CacheLoader<Object, Object> loader = new CacheLoader<Object, Object>() {
596      @Override
597      public Object load(Object key) throws Exception {
598        computingSignal.countDown();
599        startSignal.await();
600        return computedObject;
601      }
602    };
603
604    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
605    CacheBuilder<Object, Object> builder = createCacheBuilder()
606        .concurrencyLevel(1)
607        .removalListener(listener);
608    final LocalCache<Object, Object> map = makeLocalCache(builder);
609    Segment<Object, Object> segment = map.segments[0];
610    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
611    assertTrue(listener.isEmpty());
612
613    final Object one = new Object();
614    int hash = map.hash(one);
615    int index = hash & (table.length() - 1);
616
617    new Thread() {
618      @Override
619      public void run() {
620        try {
621          map.get(one, loader);
622        } catch (ExecutionException e) {
623          throw new RuntimeException(e);
624        }
625        doneSignal.countDown();
626      }
627    }.start();
628
629    try {
630      computingSignal.await();
631    } catch (InterruptedException e) {
632      throw new RuntimeException(e);
633    }
634
635    new Thread() {
636      @Override
637      public void run() {
638        try {
639          map.get(one, loader);
640        } catch (ExecutionException e) {
641          throw new RuntimeException(e);
642        }
643        doneSignal.countDown();
644      }
645    }.start();
646
647    ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
648    ReferenceEntry<Object, Object> newEntry = segment.copyEntry(entry, null);
649    table.set(index, newEntry);
650
651    @SuppressWarnings("unchecked")
652    LoadingValueReference<Object, Object> valueReference =
653        (LoadingValueReference) newEntry.getValueReference();
654    assertFalse(valueReference.futureValue.isDone());
655    startSignal.countDown();
656
657    try {
658      doneSignal.await();
659    } catch (InterruptedException e) {
660      throw new RuntimeException(e);
661    }
662
663    map.cleanUp(); // force notifications
664    assertTrue(listener.isEmpty());
665    assertTrue(map.containsKey(one));
666    assertEquals(1, map.size());
667    assertSame(computedObject, map.get(one));
668  }
669
670  public void testRemovalListenerCheckedException() {
671    final RuntimeException e = new RuntimeException();
672    RemovalListener<Object, Object> listener = new RemovalListener<Object, Object>() {
673      @Override
674      public void onRemoval(RemovalNotification<Object, Object> notification) {
675        throw e;
676      }
677    };
678
679    CacheBuilder<Object, Object> builder = createCacheBuilder().removalListener(listener);
680    final LocalCache<Object, Object> cache = makeLocalCache(builder);
681    Object key = new Object();
682    cache.put(key, new Object());
683    checkNothingLogged();
684
685    cache.remove(key);
686    checkLogged(e);
687  }
688
689  public void testRemovalListener_replaced_computing() {
690    final CountDownLatch startSignal = new CountDownLatch(1);
691    final CountDownLatch computingSignal = new CountDownLatch(1);
692    final CountDownLatch doneSignal = new CountDownLatch(1);
693    final Object computedObject = new Object();
694
695    final CacheLoader<Object, Object> loader = new CacheLoader<Object, Object>() {
696      @Override
697      public Object load(Object key) throws Exception {
698        computingSignal.countDown();
699        startSignal.await();
700        return computedObject;
701      }
702    };
703
704    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
705    CacheBuilder<Object, Object> builder = createCacheBuilder().removalListener(listener);
706    final LocalCache<Object, Object> map = makeLocalCache(builder);
707    assertTrue(listener.isEmpty());
708
709    final Object one = new Object();
710    final Object two = new Object();
711
712    new Thread() {
713      @Override
714      public void run() {
715        try {
716          map.get(one, loader);
717        } catch (ExecutionException e) {
718          throw new RuntimeException(e);
719        }
720        doneSignal.countDown();
721      }
722    }.start();
723
724    try {
725      computingSignal.await();
726    } catch (InterruptedException e) {
727      throw new RuntimeException(e);
728    }
729
730    map.put(one, two);
731    assertSame(two, map.get(one));
732    startSignal.countDown();
733
734    try {
735      doneSignal.await();
736    } catch (InterruptedException e) {
737      throw new RuntimeException(e);
738    }
739
740    map.cleanUp(); // force notifications
741    assertNotified(listener, one, computedObject, RemovalCause.REPLACED);
742    assertTrue(listener.isEmpty());
743  }
744
745  public void testSegmentRefresh_duplicate() throws ExecutionException {
746    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
747        .concurrencyLevel(1));
748    Segment<Object, Object> segment = map.segments[0];
749
750    Object key = new Object();
751    int hash = map.hash(key);
752    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
753    int index = hash & (table.length() - 1);
754
755    // already loading
756    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
757    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(null);
758    valueRef.setLoading(true);
759    entry.setValueReference(valueRef);
760    table.set(index, entry);
761    assertNull(segment.refresh(key, hash, identityLoader(), false));
762  }
763
764  // Removal listener tests
765
766  public void testRemovalListener_explicit() {
767    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
768    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
769        .removalListener(listener));
770    assertTrue(listener.isEmpty());
771
772    Object one = new Object();
773    Object two = new Object();
774    Object three = new Object();
775    Object four = new Object();
776    Object five = new Object();
777    Object six = new Object();
778
779    map.put(one, two);
780    map.remove(one);
781    assertNotified(listener, one, two, RemovalCause.EXPLICIT);
782
783    map.put(two, three);
784    map.remove(two, three);
785    assertNotified(listener, two, three, RemovalCause.EXPLICIT);
786
787    map.put(three, four);
788    Iterator<?> i = map.entrySet().iterator();
789    i.next();
790    i.remove();
791    assertNotified(listener, three, four, RemovalCause.EXPLICIT);
792
793    map.put(four, five);
794    i = map.keySet().iterator();
795    i.next();
796    i.remove();
797    assertNotified(listener, four, five, RemovalCause.EXPLICIT);
798
799    map.put(five, six);
800    i = map.values().iterator();
801    i.next();
802    i.remove();
803    assertNotified(listener, five, six, RemovalCause.EXPLICIT);
804
805    assertTrue(listener.isEmpty());
806  }
807
808  public void testRemovalListener_replaced() {
809    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
810    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
811        .removalListener(listener));
812    assertTrue(listener.isEmpty());
813
814    Object one = new Object();
815    Object two = new Object();
816    Object three = new Object();
817    Object four = new Object();
818    Object five = new Object();
819    Object six = new Object();
820
821    map.put(one, two);
822    map.put(one, three);
823    assertNotified(listener, one, two, RemovalCause.REPLACED);
824
825    Map<Object, Object> newMap = ImmutableMap.of(one, four);
826    map.putAll(newMap);
827    assertNotified(listener, one, three, RemovalCause.REPLACED);
828
829    map.replace(one, five);
830    assertNotified(listener, one, four, RemovalCause.REPLACED);
831
832    map.replace(one, five, six);
833    assertNotified(listener, one, five, RemovalCause.REPLACED);
834  }
835
836  public void testRemovalListener_collected() {
837    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
838    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
839        .concurrencyLevel(1)
840        .softValues()
841        .removalListener(listener));
842    Segment<Object, Object> segment = map.segments[0];
843    assertTrue(listener.isEmpty());
844
845    Object one = new Object();
846    Object two = new Object();
847    Object three = new Object();
848
849    map.put(one, two);
850    map.put(two, three);
851    assertTrue(listener.isEmpty());
852
853    int hash = map.hash(one);
854    ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
855    map.reclaimValue(entry.getValueReference());
856    assertNotified(listener, one, two, RemovalCause.COLLECTED);
857
858    assertTrue(listener.isEmpty());
859  }
860
861  public void testRemovalListener_expired() {
862    FakeTicker ticker = new FakeTicker();
863    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
864    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
865        .concurrencyLevel(1)
866        .expireAfterWrite(3, TimeUnit.NANOSECONDS)
867        .ticker(ticker)
868        .removalListener(listener));
869    assertTrue(listener.isEmpty());
870
871    Object one = new Object();
872    Object two = new Object();
873    Object three = new Object();
874    Object four = new Object();
875    Object five = new Object();
876
877    map.put(one, two);
878    ticker.advance(1);
879    map.put(two, three);
880    ticker.advance(1);
881    map.put(three, four);
882    assertTrue(listener.isEmpty());
883    ticker.advance(1);
884    map.put(four, five);
885    assertNotified(listener, one, two, RemovalCause.EXPIRED);
886
887    assertTrue(listener.isEmpty());
888  }
889
890  public void testRemovalListener_size() {
891    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
892    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
893        .concurrencyLevel(1)
894        .maximumSize(2)
895        .removalListener(listener));
896    assertTrue(listener.isEmpty());
897
898    Object one = new Object();
899    Object two = new Object();
900    Object three = new Object();
901    Object four = new Object();
902
903    map.put(one, two);
904    map.put(two, three);
905    assertTrue(listener.isEmpty());
906    map.put(three, four);
907    assertNotified(listener, one, two, RemovalCause.SIZE);
908
909    assertTrue(listener.isEmpty());
910  }
911
912  static <K, V> void assertNotified(
913      QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause) {
914    RemovalNotification<K, V> notification = listener.remove();
915    assertSame(key, notification.getKey());
916    assertSame(value, notification.getValue());
917    assertSame(cause, notification.getCause());
918  }
919
920  // Segment core tests
921
922  public void testNewEntry() {
923    for (CacheBuilder<Object, Object> builder : allEntryTypeMakers()) {
924      LocalCache<Object, Object> map = makeLocalCache(builder);
925
926      Object keyOne = new Object();
927      Object valueOne = new Object();
928      int hashOne = map.hash(keyOne);
929      ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
930      ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne, 1);
931      assertSame(valueOne, valueRefOne.get());
932      entryOne.setValueReference(valueRefOne);
933
934      assertSame(keyOne, entryOne.getKey());
935      assertEquals(hashOne, entryOne.getHash());
936      assertNull(entryOne.getNext());
937      assertSame(valueRefOne, entryOne.getValueReference());
938
939      Object keyTwo = new Object();
940      Object valueTwo = new Object();
941      int hashTwo = map.hash(keyTwo);
942      ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
943      ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo, 1);
944      assertSame(valueTwo, valueRefTwo.get());
945      entryTwo.setValueReference(valueRefTwo);
946
947      assertSame(keyTwo, entryTwo.getKey());
948      assertEquals(hashTwo, entryTwo.getHash());
949      assertSame(entryOne, entryTwo.getNext());
950      assertSame(valueRefTwo, entryTwo.getValueReference());
951    }
952  }
953
954  public void testCopyEntry() {
955    for (CacheBuilder<Object, Object> builder : allEntryTypeMakers()) {
956      LocalCache<Object, Object> map = makeLocalCache(builder);
957
958      Object keyOne = new Object();
959      Object valueOne = new Object();
960      int hashOne = map.hash(keyOne);
961      ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
962      entryOne.setValueReference(map.newValueReference(entryOne, valueOne, 1));
963
964      Object keyTwo = new Object();
965      Object valueTwo = new Object();
966      int hashTwo = map.hash(keyTwo);
967      ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
968      entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo, 1));
969      if (map.usesAccessQueue()) {
970        LocalCache.connectAccessOrder(entryOne, entryTwo);
971      }
972      if (map.usesWriteQueue()) {
973        LocalCache.connectWriteOrder(entryOne, entryTwo);
974      }
975      assertConnected(map, entryOne, entryTwo);
976
977      ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null);
978      assertSame(keyOne, entryOne.getKey());
979      assertEquals(hashOne, entryOne.getHash());
980      assertNull(entryOne.getNext());
981      assertSame(valueOne, copyOne.getValueReference().get());
982      assertConnected(map, copyOne, entryTwo);
983
984      ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne);
985      assertSame(keyTwo, copyTwo.getKey());
986      assertEquals(hashTwo, copyTwo.getHash());
987      assertSame(copyOne, copyTwo.getNext());
988      assertSame(valueTwo, copyTwo.getValueReference().get());
989      assertConnected(map, copyOne, copyTwo);
990    }
991  }
992
993  private static <K, V> void assertConnected(
994      LocalCache<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) {
995    if (map.usesWriteQueue()) {
996      assertSame(two, one.getNextInWriteQueue());
997    }
998    if (map.usesAccessQueue()) {
999      assertSame(two, one.getNextInAccessQueue());
1000    }
1001  }
1002
1003  public void testSegmentGetAndContains() {
1004    FakeTicker ticker = new FakeTicker();
1005    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1006        .concurrencyLevel(1)
1007        .ticker(ticker)
1008        .expireAfterAccess(1, TimeUnit.NANOSECONDS));
1009    Segment<Object, Object> segment = map.segments[0];
1010    // TODO(fry): check recency ordering
1011
1012    Object key = new Object();
1013    int hash = map.hash(key);
1014    Object value = new Object();
1015    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1016    int index = hash & (table.length() - 1);
1017
1018    ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null);
1019    ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
1020    entry.setValueReference(valueRef);
1021
1022    assertNull(segment.get(key, hash));
1023
1024    // count == 0
1025    table.set(index, entry);
1026    assertNull(segment.get(key, hash));
1027    assertFalse(segment.containsKey(key, hash));
1028    assertFalse(segment.containsValue(value));
1029
1030    // count == 1
1031    segment.count++;
1032    assertSame(value, segment.get(key, hash));
1033    assertTrue(segment.containsKey(key, hash));
1034    assertTrue(segment.containsValue(value));
1035    // don't see absent values now that count > 0
1036    assertNull(segment.get(new Object(), hash));
1037
1038    // null key
1039    DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry);
1040    Object nullValue = new Object();
1041    ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue, 1);
1042    nullEntry.setValueReference(nullValueRef);
1043    table.set(index, nullEntry);
1044    // skip the null key
1045    assertSame(value, segment.get(key, hash));
1046    assertTrue(segment.containsKey(key, hash));
1047    assertTrue(segment.containsValue(value));
1048    assertFalse(segment.containsValue(nullValue));
1049
1050    // hash collision
1051    DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry);
1052    Object dummyValue = new Object();
1053    ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue, 1);
1054    dummy.setValueReference(dummyValueRef);
1055    table.set(index, dummy);
1056    assertSame(value, segment.get(key, hash));
1057    assertTrue(segment.containsKey(key, hash));
1058    assertTrue(segment.containsValue(value));
1059    assertTrue(segment.containsValue(dummyValue));
1060
1061    // key collision
1062    dummy = DummyEntry.create(key, hash, entry);
1063    dummyValue = new Object();
1064    dummyValueRef = map.newValueReference(dummy, dummyValue, 1);
1065    dummy.setValueReference(dummyValueRef);
1066    table.set(index, dummy);
1067    // returns the most recent entry
1068    assertSame(dummyValue, segment.get(key, hash));
1069    assertTrue(segment.containsKey(key, hash));
1070    assertTrue(segment.containsValue(value));
1071    assertTrue(segment.containsValue(dummyValue));
1072
1073    // expired
1074    dummy.setAccessTime(ticker.read() - 2);
1075    assertNull(segment.get(key, hash));
1076    assertFalse(segment.containsKey(key, hash));
1077    assertTrue(segment.containsValue(value));
1078    assertFalse(segment.containsValue(dummyValue));
1079  }
1080
1081  public void testSegmentReplaceValue() {
1082    LocalCache<Object, Object> map =
1083        makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1084    Segment<Object, Object> segment = map.segments[0];
1085    // TODO(fry): check recency ordering
1086
1087    Object key = new Object();
1088    int hash = map.hash(key);
1089    Object oldValue = new Object();
1090    Object newValue = new Object();
1091    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1092    int index = hash & (table.length() - 1);
1093
1094    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1095    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1096    entry.setValueReference(oldValueRef);
1097
1098    // no entry
1099    assertFalse(segment.replace(key, hash, oldValue, newValue));
1100    assertEquals(0, segment.count);
1101
1102    // same value
1103    table.set(index, entry);
1104    segment.count++;
1105    assertEquals(1, segment.count);
1106    assertSame(oldValue, segment.get(key, hash));
1107    assertTrue(segment.replace(key, hash, oldValue, newValue));
1108    assertEquals(1, segment.count);
1109    assertSame(newValue, segment.get(key, hash));
1110
1111    // different value
1112    assertFalse(segment.replace(key, hash, oldValue, newValue));
1113    assertEquals(1, segment.count);
1114    assertSame(newValue, segment.get(key, hash));
1115
1116    // cleared
1117    entry.setValueReference(oldValueRef);
1118    assertSame(oldValue, segment.get(key, hash));
1119    oldValueRef.clear();
1120    assertFalse(segment.replace(key, hash, oldValue, newValue));
1121    assertEquals(0, segment.count);
1122    assertNull(segment.get(key, hash));
1123  }
1124
1125  public void testSegmentReplace() {
1126    LocalCache<Object, Object> map =
1127        makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1128    Segment<Object, Object> segment = map.segments[0];
1129    // TODO(fry): check recency ordering
1130
1131    Object key = new Object();
1132    int hash = map.hash(key);
1133    Object oldValue = new Object();
1134    Object newValue = new Object();
1135    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1136    int index = hash & (table.length() - 1);
1137
1138    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1139    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1140    entry.setValueReference(oldValueRef);
1141
1142    // no entry
1143    assertNull(segment.replace(key, hash, newValue));
1144    assertEquals(0, segment.count);
1145
1146    // same key
1147    table.set(index, entry);
1148    segment.count++;
1149    assertEquals(1, segment.count);
1150    assertSame(oldValue, segment.get(key, hash));
1151    assertSame(oldValue, segment.replace(key, hash, newValue));
1152    assertEquals(1, segment.count);
1153    assertSame(newValue, segment.get(key, hash));
1154
1155    // cleared
1156    entry.setValueReference(oldValueRef);
1157    assertSame(oldValue, segment.get(key, hash));
1158    oldValueRef.clear();
1159    assertNull(segment.replace(key, hash, newValue));
1160    assertEquals(0, segment.count);
1161    assertNull(segment.get(key, hash));
1162  }
1163
1164  public void testSegmentPut() {
1165    LocalCache<Object, Object> map =
1166        makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1167    Segment<Object, Object> segment = map.segments[0];
1168    // TODO(fry): check recency ordering
1169
1170    Object key = new Object();
1171    int hash = map.hash(key);
1172    Object oldValue = new Object();
1173    Object newValue = new Object();
1174
1175    // no entry
1176    assertEquals(0, segment.count);
1177    assertNull(segment.put(key, hash, oldValue, false));
1178    assertEquals(1, segment.count);
1179
1180    // same key
1181    assertSame(oldValue, segment.put(key, hash, newValue, false));
1182    assertEquals(1, segment.count);
1183    assertSame(newValue, segment.get(key, hash));
1184
1185    // cleared
1186    ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1187    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1188    entry.setValueReference(oldValueRef);
1189    assertSame(oldValue, segment.get(key, hash));
1190    oldValueRef.clear();
1191    assertNull(segment.put(key, hash, newValue, false));
1192    assertEquals(1, segment.count);
1193    assertSame(newValue, segment.get(key, hash));
1194  }
1195
1196  public void testSegmentPutIfAbsent() {
1197    LocalCache<Object, Object> map =
1198        makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1199    Segment<Object, Object> segment = map.segments[0];
1200    // TODO(fry): check recency ordering
1201
1202    Object key = new Object();
1203    int hash = map.hash(key);
1204    Object oldValue = new Object();
1205    Object newValue = new Object();
1206
1207    // no entry
1208    assertEquals(0, segment.count);
1209    assertNull(segment.put(key, hash, oldValue, true));
1210    assertEquals(1, segment.count);
1211
1212    // same key
1213    assertSame(oldValue, segment.put(key, hash, newValue, true));
1214    assertEquals(1, segment.count);
1215    assertSame(oldValue, segment.get(key, hash));
1216
1217    // cleared
1218    ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1219    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1220    entry.setValueReference(oldValueRef);
1221    assertSame(oldValue, segment.get(key, hash));
1222    oldValueRef.clear();
1223    assertNull(segment.put(key, hash, newValue, true));
1224    assertEquals(1, segment.count);
1225    assertSame(newValue, segment.get(key, hash));
1226  }
1227
1228  public void testSegmentPut_expand() {
1229    LocalCache<Object, Object> map =
1230        makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1231    Segment<Object, Object> segment = map.segments[0];
1232    assertEquals(1, segment.table.length());
1233
1234    int count = 1024;
1235    for (int i = 0; i < count; i++) {
1236      Object key = new Object();
1237      Object value = new Object();
1238      int hash = map.hash(key);
1239      assertNull(segment.put(key, hash, value, false));
1240      assertTrue(segment.table.length() > i);
1241    }
1242  }
1243
1244  public void testSegmentPut_evict() {
1245    int maxSize = 10;
1246    LocalCache<Object, Object> map =
1247        makeLocalCache(createCacheBuilder().concurrencyLevel(1).maximumSize(maxSize));
1248
1249    // manually add elements to avoid eviction
1250    int originalCount = 1024;
1251    LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
1252    for (int i = 0; i < originalCount; i++) {
1253      Object key = new Object();
1254      Object value = new Object();
1255      map.put(key, value);
1256      originalMap.put(key, value);
1257      if (i >= maxSize) {
1258        Iterator<Object> it = originalMap.keySet().iterator();
1259        it.next();
1260        it.remove();
1261      }
1262      assertEquals(originalMap, map);
1263    }
1264  }
1265
1266  public void testSegmentStoreComputedValue() {
1267    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
1268    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1269        .concurrencyLevel(1)
1270        .removalListener(listener));
1271    Segment<Object, Object> segment = map.segments[0];
1272
1273    Object key = new Object();
1274    int hash = map.hash(key);
1275    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1276    int index = hash & (table.length() - 1);
1277
1278    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1279    LoadingValueReference<Object, Object> valueRef = new LoadingValueReference<Object, Object>();
1280    entry.setValueReference(valueRef);
1281
1282    // absent
1283    Object value = new Object();
1284    assertTrue(listener.isEmpty());
1285    assertEquals(0, segment.count);
1286    assertNull(segment.get(key, hash));
1287    assertTrue(segment.storeLoadedValue(key, hash, valueRef, value));
1288    assertSame(value, segment.get(key, hash));
1289    assertEquals(1, segment.count);
1290    assertTrue(listener.isEmpty());
1291
1292    // clobbered
1293    Object value2 = new Object();
1294    assertFalse(segment.storeLoadedValue(key, hash, valueRef, value2));
1295    assertEquals(1, segment.count);
1296    assertSame(value, segment.get(key, hash));
1297    RemovalNotification<Object, Object> notification = listener.remove();
1298    assertEquals(immutableEntry(key, value2), notification);
1299    assertEquals(RemovalCause.REPLACED, notification.getCause());
1300    assertTrue(listener.isEmpty());
1301
1302    // inactive
1303    Object value3 = new Object();
1304    map.clear();
1305    listener.clear();
1306    assertEquals(0, segment.count);
1307    table.set(index, entry);
1308    assertTrue(segment.storeLoadedValue(key, hash, valueRef, value3));
1309    assertSame(value3, segment.get(key, hash));
1310    assertEquals(1, segment.count);
1311    assertTrue(listener.isEmpty());
1312
1313    // replaced
1314    Object value4 = new Object();
1315    DummyValueReference<Object, Object> value3Ref = DummyValueReference.create(value3);
1316    valueRef = new LoadingValueReference<Object, Object>(value3Ref);
1317    entry.setValueReference(valueRef);
1318    table.set(index, entry);
1319    assertSame(value3, segment.get(key, hash));
1320    assertEquals(1, segment.count);
1321    assertTrue(segment.storeLoadedValue(key, hash, valueRef, value4));
1322    assertSame(value4, segment.get(key, hash));
1323    assertEquals(1, segment.count);
1324    notification = listener.remove();
1325    assertEquals(immutableEntry(key, value3), notification);
1326    assertEquals(RemovalCause.REPLACED, notification.getCause());
1327    assertTrue(listener.isEmpty());
1328
1329    // collected
1330    entry.setValueReference(valueRef);
1331    table.set(index, entry);
1332    assertSame(value3, segment.get(key, hash));
1333    assertEquals(1, segment.count);
1334    value3Ref.clear();
1335    assertTrue(segment.storeLoadedValue(key, hash, valueRef, value4));
1336    assertSame(value4, segment.get(key, hash));
1337    assertEquals(1, segment.count);
1338    notification = listener.remove();
1339    assertEquals(immutableEntry(key, null), notification);
1340    assertEquals(RemovalCause.COLLECTED, notification.getCause());
1341    assertTrue(listener.isEmpty());
1342  }
1343
1344  public void testSegmentRemove() {
1345    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1346    Segment<Object, Object> segment = map.segments[0];
1347
1348    Object key = new Object();
1349    int hash = map.hash(key);
1350    Object oldValue = new Object();
1351    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1352    int index = hash & (table.length() - 1);
1353
1354    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1355    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1356    entry.setValueReference(oldValueRef);
1357
1358    // no entry
1359    assertEquals(0, segment.count);
1360    assertNull(segment.remove(key, hash));
1361    assertEquals(0, segment.count);
1362
1363    // same key
1364    table.set(index, entry);
1365    segment.count++;
1366    assertEquals(1, segment.count);
1367    assertSame(oldValue, segment.get(key, hash));
1368    assertSame(oldValue, segment.remove(key, hash));
1369    assertEquals(0, segment.count);
1370    assertNull(segment.get(key, hash));
1371
1372    // cleared
1373    table.set(index, entry);
1374    segment.count++;
1375    assertEquals(1, segment.count);
1376    assertSame(oldValue, segment.get(key, hash));
1377    oldValueRef.clear();
1378    assertNull(segment.remove(key, hash));
1379    assertEquals(0, segment.count);
1380    assertNull(segment.get(key, hash));
1381  }
1382
1383  public void testSegmentRemoveValue() {
1384    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1385    Segment<Object, Object> segment = map.segments[0];
1386
1387    Object key = new Object();
1388    int hash = map.hash(key);
1389    Object oldValue = new Object();
1390    Object newValue = new Object();
1391    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1392    int index = hash & (table.length() - 1);
1393
1394    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1395    DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1396    entry.setValueReference(oldValueRef);
1397
1398    // no entry
1399    assertEquals(0, segment.count);
1400    assertNull(segment.remove(key, hash));
1401    assertEquals(0, segment.count);
1402
1403    // same value
1404    table.set(index, entry);
1405    segment.count++;
1406    assertEquals(1, segment.count);
1407    assertSame(oldValue, segment.get(key, hash));
1408    assertTrue(segment.remove(key, hash, oldValue));
1409    assertEquals(0, segment.count);
1410    assertNull(segment.get(key, hash));
1411
1412    // different value
1413    table.set(index, entry);
1414    segment.count++;
1415    assertEquals(1, segment.count);
1416    assertSame(oldValue, segment.get(key, hash));
1417    assertFalse(segment.remove(key, hash, newValue));
1418    assertEquals(1, segment.count);
1419    assertSame(oldValue, segment.get(key, hash));
1420
1421    // cleared
1422    assertSame(oldValue, segment.get(key, hash));
1423    oldValueRef.clear();
1424    assertFalse(segment.remove(key, hash, oldValue));
1425    assertEquals(0, segment.count);
1426    assertNull(segment.get(key, hash));
1427  }
1428
1429  public void testExpand() {
1430    LocalCache<Object, Object> map =
1431        makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1432    Segment<Object, Object> segment = map.segments[0];
1433    assertEquals(1, segment.table.length());
1434
1435    // manually add elements to avoid expansion
1436    int originalCount = 1024;
1437    ReferenceEntry<Object, Object> entry = null;
1438    for (int i = 0; i < originalCount; i++) {
1439      Object key = new Object();
1440      Object value = new Object();
1441      int hash = map.hash(key);
1442      // chain all entries together as we only have a single bucket
1443      entry = map.newEntry(key, hash, entry);
1444      ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
1445      entry.setValueReference(valueRef);
1446    }
1447    segment.table.set(0, entry);
1448    segment.count = originalCount;
1449    ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
1450    assertEquals(originalCount, originalMap.size());
1451    assertEquals(originalMap, map);
1452
1453    for (int i = 1; i <= originalCount * 2; i *= 2) {
1454      if (i > 1) {
1455        segment.expand();
1456      }
1457      assertEquals(i, segment.table.length());
1458      assertEquals(originalCount, countLiveEntries(map, 0));
1459      assertEquals(originalCount, segment.count);
1460      assertEquals(originalMap, map);
1461    }
1462  }
1463
1464  public void testGetCausesExpansion() throws ExecutionException {
1465    for (int count = 1; count <= 100; count++) {
1466      LocalCache<Object, Object> map =
1467          makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1468      Segment<Object, Object> segment = map.segments[0];
1469      assertEquals(1, segment.table.length());
1470
1471      for (int i = 0; i < count; i++) {
1472        Object key = new Object();
1473        final Object value = new Object();
1474        segment.get(key, key.hashCode(), new CacheLoader<Object, Object>() {
1475          @Override
1476          public Object load(Object key) {
1477            return value;
1478          }
1479        });
1480      }
1481      assertEquals(count, segment.count);
1482      assertTrue(count <= segment.threshold);
1483      assertTrue(count <= (segment.table.length() * 3 / 4));
1484      assertTrue(count > (segment.table.length() * 3 / 8));
1485    }
1486  }
1487
1488  public void testPutCausesExpansion() {
1489    for (int count = 1; count <= 100; count++) {
1490      LocalCache<Object, Object> map =
1491          makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1492      Segment<Object, Object> segment = map.segments[0];
1493      assertEquals(1, segment.table.length());
1494
1495      for (int i = 0; i < count; i++) {
1496        Object key = new Object();
1497        Object value = new Object();
1498        segment.put(key, key.hashCode(), value, true);
1499      }
1500      assertEquals(count, segment.count);
1501      assertTrue(count <= segment.threshold);
1502      assertTrue(count <= (segment.table.length() * 3 / 4));
1503      assertTrue(count > (segment.table.length() * 3 / 8));
1504    }
1505  }
1506
1507  public void testReclaimKey() {
1508    CountingRemovalListener<Object, Object> listener = countingRemovalListener();
1509    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1510        .concurrencyLevel(1)
1511        .initialCapacity(1)
1512        .maximumSize(SMALL_MAX_SIZE)
1513        .expireAfterWrite(99999, SECONDS)
1514        .removalListener(listener));
1515    Segment<Object, Object> segment = map.segments[0];
1516    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1517    assertEquals(1, table.length());
1518
1519    // create 3 objects and chain them together
1520    Object keyOne = new Object();
1521    Object valueOne = new Object();
1522    int hashOne = map.hash(keyOne);
1523    DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
1524    Object keyTwo = new Object();
1525    Object valueTwo = new Object();
1526    int hashTwo = map.hash(keyTwo);
1527    DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
1528    Object keyThree = new Object();
1529    Object valueThree = new Object();
1530    int hashThree = map.hash(keyThree);
1531    DummyEntry<Object, Object> entryThree =
1532      createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
1533
1534    // absent
1535    assertEquals(0, listener.getCount());
1536    assertFalse(segment.reclaimKey(entryOne, hashOne));
1537    assertEquals(0, listener.getCount());
1538    table.set(0, entryOne);
1539    assertFalse(segment.reclaimKey(entryTwo, hashTwo));
1540    assertEquals(0, listener.getCount());
1541    table.set(0, entryTwo);
1542    assertFalse(segment.reclaimKey(entryThree, hashThree));
1543    assertEquals(0, listener.getCount());
1544
1545    // present
1546    table.set(0, entryOne);
1547    segment.count = 1;
1548    assertTrue(segment.reclaimKey(entryOne, hashOne));
1549    assertEquals(1, listener.getCount());
1550    assertSame(keyOne, listener.getLastEvictedKey());
1551    assertSame(valueOne, listener.getLastEvictedValue());
1552    assertTrue(map.removalNotificationQueue.isEmpty());
1553    assertFalse(segment.accessQueue.contains(entryOne));
1554    assertFalse(segment.writeQueue.contains(entryOne));
1555    assertEquals(0, segment.count);
1556    assertNull(table.get(0));
1557  }
1558
1559  public void testRemoveEntryFromChain() {
1560    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1561    Segment<Object, Object> segment = map.segments[0];
1562
1563    // create 3 objects and chain them together
1564    Object keyOne = new Object();
1565    Object valueOne = new Object();
1566    int hashOne = map.hash(keyOne);
1567    DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
1568    Object keyTwo = new Object();
1569    Object valueTwo = new Object();
1570    int hashTwo = map.hash(keyTwo);
1571    DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
1572    Object keyThree = new Object();
1573    Object valueThree = new Object();
1574    int hashThree = map.hash(keyThree);
1575    DummyEntry<Object, Object> entryThree =
1576      createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
1577
1578    // alone
1579    assertNull(segment.removeEntryFromChain(entryOne, entryOne));
1580
1581    // head
1582    assertSame(entryOne, segment.removeEntryFromChain(entryTwo, entryTwo));
1583
1584    // middle
1585    ReferenceEntry<Object, Object> newFirst = segment.removeEntryFromChain(entryThree, entryTwo);
1586    assertSame(keyThree, newFirst.getKey());
1587    assertSame(valueThree, newFirst.getValueReference().get());
1588    assertEquals(hashThree, newFirst.getHash());
1589    assertSame(entryOne, newFirst.getNext());
1590
1591    // tail (remaining entries are copied in reverse order)
1592    newFirst = segment.removeEntryFromChain(entryThree, entryOne);
1593    assertSame(keyTwo, newFirst.getKey());
1594    assertSame(valueTwo, newFirst.getValueReference().get());
1595    assertEquals(hashTwo, newFirst.getHash());
1596    newFirst = newFirst.getNext();
1597    assertSame(keyThree, newFirst.getKey());
1598    assertSame(valueThree, newFirst.getValueReference().get());
1599    assertEquals(hashThree, newFirst.getHash());
1600    assertNull(newFirst.getNext());
1601  }
1602
1603  public void testExpand_cleanup() {
1604    LocalCache<Object, Object> map =
1605        makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1606    Segment<Object, Object> segment = map.segments[0];
1607    assertEquals(1, segment.table.length());
1608
1609    // manually add elements to avoid expansion
1610    // 1/3 null keys, 1/3 null values
1611    int originalCount = 1024;
1612    ReferenceEntry<Object, Object> entry = null;
1613    for (int i = 0; i < originalCount; i++) {
1614      Object key = new Object();
1615      Object value = (i % 3 == 0) ? null : new Object();
1616      int hash = map.hash(key);
1617      if (i % 3 == 1) {
1618        key = null;
1619      }
1620      // chain all entries together as we only have a single bucket
1621      entry = DummyEntry.create(key, hash, entry);
1622      ValueReference<Object, Object> valueRef = DummyValueReference.create(value);
1623      entry.setValueReference(valueRef);
1624    }
1625    segment.table.set(0, entry);
1626    segment.count = originalCount;
1627    int liveCount = originalCount / 3;
1628    assertEquals(1, segment.table.length());
1629    assertEquals(liveCount, countLiveEntries(map, 0));
1630    ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
1631    assertEquals(liveCount, originalMap.size());
1632    // can't compare map contents until cleanup occurs
1633
1634    for (int i = 1; i <= originalCount * 2; i *= 2) {
1635      if (i > 1) {
1636        segment.expand();
1637      }
1638      assertEquals(i, segment.table.length());
1639      assertEquals(liveCount, countLiveEntries(map, 0));
1640      // expansion cleanup is sloppy, with a goal of avoiding unnecessary copies
1641      assertTrue(segment.count >= liveCount);
1642      assertTrue(segment.count <= originalCount);
1643      assertEquals(originalMap, ImmutableMap.copyOf(map));
1644    }
1645  }
1646
1647  private static <K, V> int countLiveEntries(LocalCache<K, V> map, long now) {
1648    int result = 0;
1649    for (Segment<K, V> segment : map.segments) {
1650      AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
1651      for (int i = 0; i < table.length(); i++) {
1652        for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
1653          if (map.isLive(e, now)) {
1654            result++;
1655          }
1656        }
1657      }
1658    }
1659    return result;
1660  }
1661
1662  public void testClear() {
1663    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1664        .concurrencyLevel(1)
1665        .initialCapacity(1)
1666        .maximumSize(SMALL_MAX_SIZE)
1667        .expireAfterWrite(99999, SECONDS));
1668    Segment<Object, Object> segment = map.segments[0];
1669    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1670    assertEquals(1, table.length());
1671
1672    Object key = new Object();
1673    Object value = new Object();
1674    int hash = map.hash(key);
1675    DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1676    segment.recordWrite(entry, 1, map.ticker.read());
1677    segment.table.set(0, entry);
1678    segment.readCount.incrementAndGet();
1679    segment.count = 1;
1680    segment.totalWeight = 1;
1681
1682    assertSame(entry, table.get(0));
1683    assertSame(entry, segment.accessQueue.peek());
1684    assertSame(entry, segment.writeQueue.peek());
1685
1686    segment.clear();
1687    assertNull(table.get(0));
1688    assertTrue(segment.accessQueue.isEmpty());
1689    assertTrue(segment.writeQueue.isEmpty());
1690    assertEquals(0, segment.readCount.get());
1691    assertEquals(0, segment.count);
1692    assertEquals(0, segment.totalWeight);
1693  }
1694
1695  public void testClear_notification() {
1696    QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
1697    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1698        .concurrencyLevel(1)
1699        .initialCapacity(1)
1700        .maximumSize(SMALL_MAX_SIZE)
1701        .expireAfterWrite(99999, SECONDS)
1702        .removalListener(listener));
1703    Segment<Object, Object> segment = map.segments[0];
1704    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1705    assertEquals(1, table.length());
1706
1707    Object key = new Object();
1708    Object value = new Object();
1709    int hash = map.hash(key);
1710    DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1711    segment.recordWrite(entry, 1, map.ticker.read());
1712    segment.table.set(0, entry);
1713    segment.readCount.incrementAndGet();
1714    segment.count = 1;
1715    segment.totalWeight = 1;
1716
1717    assertSame(entry, table.get(0));
1718    assertSame(entry, segment.accessQueue.peek());
1719    assertSame(entry, segment.writeQueue.peek());
1720
1721    segment.clear();
1722    assertNull(table.get(0));
1723    assertTrue(segment.accessQueue.isEmpty());
1724    assertTrue(segment.writeQueue.isEmpty());
1725    assertEquals(0, segment.readCount.get());
1726    assertEquals(0, segment.count);
1727    assertEquals(0, segment.totalWeight);
1728    assertNotified(listener, key, value, RemovalCause.EXPLICIT);
1729  }
1730
1731  public void testRemoveEntry() {
1732    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1733        .concurrencyLevel(1)
1734        .initialCapacity(1)
1735        .maximumSize(SMALL_MAX_SIZE)
1736        .expireAfterWrite(99999, SECONDS)
1737        .removalListener(countingRemovalListener()));
1738    Segment<Object, Object> segment = map.segments[0];
1739    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1740    assertEquals(1, table.length());
1741
1742    Object key = new Object();
1743    Object value = new Object();
1744    int hash = map.hash(key);
1745    DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1746
1747    // remove absent
1748    assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1749
1750    // remove live
1751    segment.recordWrite(entry, 1, map.ticker.read());
1752    table.set(0, entry);
1753    segment.count = 1;
1754    assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1755    assertNotificationEnqueued(map, key, value, hash);
1756    assertTrue(map.removalNotificationQueue.isEmpty());
1757    assertFalse(segment.accessQueue.contains(entry));
1758    assertFalse(segment.writeQueue.contains(entry));
1759    assertEquals(0, segment.count);
1760    assertNull(table.get(0));
1761  }
1762
1763  public void testReclaimValue() {
1764    CountingRemovalListener<Object, Object> listener =
1765        countingRemovalListener();
1766    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1767        .concurrencyLevel(1)
1768        .initialCapacity(1)
1769        .maximumSize(SMALL_MAX_SIZE)
1770        .expireAfterWrite(99999, SECONDS)
1771        .removalListener(listener));
1772    Segment<Object, Object> segment = map.segments[0];
1773    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1774    assertEquals(1, table.length());
1775
1776    Object key = new Object();
1777    Object value = new Object();
1778    int hash = map.hash(key);
1779    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1780    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
1781    entry.setValueReference(valueRef);
1782
1783    // reclaim absent
1784    assertFalse(segment.reclaimValue(key, hash, valueRef));
1785
1786    // reclaim live
1787    segment.recordWrite(entry, 1, map.ticker.read());
1788    table.set(0, entry);
1789    segment.count = 1;
1790    assertTrue(segment.reclaimValue(key, hash, valueRef));
1791    assertEquals(1, listener.getCount());
1792    assertSame(key, listener.getLastEvictedKey());
1793    assertSame(value, listener.getLastEvictedValue());
1794    assertTrue(map.removalNotificationQueue.isEmpty());
1795    assertFalse(segment.accessQueue.contains(entry));
1796    assertFalse(segment.writeQueue.contains(entry));
1797    assertEquals(0, segment.count);
1798    assertNull(table.get(0));
1799
1800    // reclaim wrong value reference
1801    table.set(0, entry);
1802    DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value);
1803    entry.setValueReference(otherValueRef);
1804    assertFalse(segment.reclaimValue(key, hash, valueRef));
1805    assertEquals(1, listener.getCount());
1806    assertTrue(segment.reclaimValue(key, hash, otherValueRef));
1807    assertEquals(2, listener.getCount());
1808    assertSame(key, listener.getLastEvictedKey());
1809    assertSame(value, listener.getLastEvictedValue());
1810  }
1811
1812  public void testRemoveComputingValue() {
1813    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1814        .concurrencyLevel(1)
1815        .initialCapacity(1)
1816        .maximumSize(SMALL_MAX_SIZE)
1817        .expireAfterWrite(99999, SECONDS)
1818        .removalListener(countingRemovalListener()));
1819    Segment<Object, Object> segment = map.segments[0];
1820    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1821    assertEquals(1, table.length());
1822
1823    Object key = new Object();
1824    int hash = map.hash(key);
1825    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1826    LoadingValueReference<Object, Object> valueRef = new LoadingValueReference<Object, Object>();
1827    entry.setValueReference(valueRef);
1828
1829    // absent
1830    assertFalse(segment.removeLoadingValue(key, hash, valueRef));
1831
1832    // live
1833    table.set(0, entry);
1834    // don't increment count; this is used during computation
1835    assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1836    // no notification sent with removeLoadingValue
1837    assertTrue(map.removalNotificationQueue.isEmpty());
1838    assertEquals(0, segment.count);
1839    assertNull(table.get(0));
1840
1841    // active
1842    Object value = new Object();
1843    DummyValueReference<Object, Object> previousRef = DummyValueReference.create(value);
1844    valueRef = new LoadingValueReference<Object, Object>(previousRef);
1845    entry.setValueReference(valueRef);
1846    table.set(0, entry);
1847    segment.count = 1;
1848    assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1849    assertSame(entry, table.get(0));
1850    assertSame(value, segment.get(key, hash));
1851
1852    // wrong value reference
1853    table.set(0, entry);
1854    DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value);
1855    entry.setValueReference(otherValueRef);
1856    assertFalse(segment.removeLoadingValue(key, hash, valueRef));
1857    entry.setValueReference(valueRef);
1858    assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1859  }
1860
1861  private static <K, V> void assertNotificationEnqueued(
1862      LocalCache<K, V> map, K key, V value, int hash) {
1863    RemovalNotification<K, V> notification = map.removalNotificationQueue.poll();
1864    assertSame(key, notification.getKey());
1865    assertSame(value, notification.getValue());
1866  }
1867
1868  // Segment eviction tests
1869
1870  public void testDrainRecencyQueueOnWrite() {
1871    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1872      LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1873      Segment<Object, Object> segment = map.segments[0];
1874
1875      if (segment.recencyQueue != DISCARDING_QUEUE) {
1876        Object keyOne = new Object();
1877        Object valueOne = new Object();
1878        Object keyTwo = new Object();
1879        Object valueTwo = new Object();
1880
1881        map.put(keyOne, valueOne);
1882        assertTrue(segment.recencyQueue.isEmpty());
1883
1884        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1885          map.get(keyOne);
1886        }
1887        assertFalse(segment.recencyQueue.isEmpty());
1888
1889        map.put(keyTwo, valueTwo);
1890        assertTrue(segment.recencyQueue.isEmpty());
1891      }
1892    }
1893  }
1894
1895  public void testDrainRecencyQueueOnRead() {
1896    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1897      LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1898      Segment<Object, Object> segment = map.segments[0];
1899
1900      if (segment.recencyQueue != DISCARDING_QUEUE) {
1901        Object keyOne = new Object();
1902        Object valueOne = new Object();
1903
1904        // repeated get of the same key
1905
1906        map.put(keyOne, valueOne);
1907        assertTrue(segment.recencyQueue.isEmpty());
1908
1909        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1910          map.get(keyOne);
1911        }
1912        assertFalse(segment.recencyQueue.isEmpty());
1913
1914        for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1915          map.get(keyOne);
1916          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1917        }
1918
1919        // get over many different keys
1920
1921        for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1922          map.put(new Object(), new Object());
1923        }
1924        assertTrue(segment.recencyQueue.isEmpty());
1925
1926        for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1927          map.get(keyOne);
1928        }
1929        assertFalse(segment.recencyQueue.isEmpty());
1930
1931        for (Object key : map.keySet()) {
1932          map.get(key);
1933          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1934        }
1935      }
1936    }
1937  }
1938
1939  public void testRecordRead() {
1940    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1941      LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1942      Segment<Object, Object> segment = map.segments[0];
1943      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1944      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1945      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1946        Object key = new Object();
1947        int hash = map.hash(key);
1948        Object value = new Object();
1949
1950        ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1951        // must recordRead for drainRecencyQueue to believe this entry is live
1952        segment.recordWrite(entry, 1, map.ticker.read());
1953        writeOrder.add(entry);
1954        readOrder.add(entry);
1955      }
1956
1957      checkEvictionQueues(map, segment, readOrder, writeOrder);
1958      checkExpirationTimes(map);
1959
1960      // access some of the elements
1961      Random random = new Random();
1962      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1963      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1964      while (i.hasNext()) {
1965        ReferenceEntry<Object, Object> entry = i.next();
1966        if (random.nextBoolean()) {
1967          segment.recordRead(entry, map.ticker.read());
1968          reads.add(entry);
1969          i.remove();
1970        }
1971      }
1972      checkAndDrainRecencyQueue(map, segment, reads);
1973      readOrder.addAll(reads);
1974
1975      checkEvictionQueues(map, segment, readOrder, writeOrder);
1976      checkExpirationTimes(map);
1977    }
1978  }
1979
1980  public void testRecordReadOnGet() {
1981    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1982      LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1983      Segment<Object, Object> segment = map.segments[0];
1984      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1985      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1986      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1987        Object key = new Object();
1988        int hash = map.hash(key);
1989        Object value = new Object();
1990
1991        map.put(key, value);
1992        ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1993        writeOrder.add(entry);
1994        readOrder.add(entry);
1995      }
1996
1997      checkEvictionQueues(map, segment, readOrder, writeOrder);
1998      checkExpirationTimes(map);
1999      assertTrue(segment.recencyQueue.isEmpty());
2000
2001      // access some of the elements
2002      Random random = new Random();
2003      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
2004      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
2005      while (i.hasNext()) {
2006        ReferenceEntry<Object, Object> entry = i.next();
2007        if (random.nextBoolean()) {
2008          map.get(entry.getKey());
2009          reads.add(entry);
2010          i.remove();
2011          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
2012        }
2013      }
2014      int undrainedIndex = reads.size() - segment.recencyQueue.size();
2015      checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
2016      readOrder.addAll(reads);
2017
2018      checkEvictionQueues(map, segment, readOrder, writeOrder);
2019      checkExpirationTimes(map);
2020    }
2021  }
2022
2023  public void testRecordWrite() {
2024    for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
2025      LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
2026      Segment<Object, Object> segment = map.segments[0];
2027      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
2028      for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
2029        Object key = new Object();
2030        int hash = map.hash(key);
2031        Object value = new Object();
2032
2033        ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
2034        // must recordRead for drainRecencyQueue to believe this entry is live
2035        segment.recordWrite(entry, 1, map.ticker.read());
2036        writeOrder.add(entry);
2037      }
2038
2039      checkEvictionQueues(map, segment, writeOrder, writeOrder);
2040      checkExpirationTimes(map);
2041
2042      // access some of the elements
2043      Random random = new Random();
2044      List<ReferenceEntry<Object, Object>> writes = Lists.newArrayList();
2045      Iterator<ReferenceEntry<Object, Object>> i = writeOrder.iterator();
2046      while (i.hasNext()) {
2047        ReferenceEntry<Object, Object> entry = i.next();
2048        if (random.nextBoolean()) {
2049          segment.recordWrite(entry, 1, map.ticker.read());
2050          writes.add(entry);
2051          i.remove();
2052        }
2053      }
2054      writeOrder.addAll(writes);
2055
2056      checkEvictionQueues(map, segment, writeOrder, writeOrder);
2057      checkExpirationTimes(map);
2058    }
2059  }
2060
2061  static <K, V> void checkAndDrainRecencyQueue(LocalCache<K, V> map,
2062      Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) {
2063    if (map.evictsBySize() || map.expiresAfterAccess()) {
2064      assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue));
2065    }
2066    segment.drainRecencyQueue();
2067  }
2068
2069  static <K, V> void checkEvictionQueues(LocalCache<K, V> map,
2070      Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder,
2071      List<ReferenceEntry<K, V>> writeOrder) {
2072    if (map.evictsBySize() || map.expiresAfterAccess()) {
2073      assertSameEntries(readOrder, ImmutableList.copyOf(segment.accessQueue));
2074    }
2075    if (map.expiresAfterWrite()) {
2076      assertSameEntries(writeOrder, ImmutableList.copyOf(segment.writeQueue));
2077    }
2078  }
2079
2080  private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries,
2081      List<ReferenceEntry<K, V>> actualEntries) {
2082    int size = expectedEntries.size();
2083    assertEquals(size, actualEntries.size());
2084    for (int i = 0; i < size; i++) {
2085      ReferenceEntry<K, V> expectedEntry = expectedEntries.get(i);
2086      ReferenceEntry<K, V> actualEntry = actualEntries.get(i);
2087      assertSame(expectedEntry.getKey(), actualEntry.getKey());
2088      assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get());
2089    }
2090  }
2091
2092  static <K, V> void checkExpirationTimes(LocalCache<K, V> map) {
2093    if (!map.expires()) {
2094      return;
2095    }
2096
2097    for (Segment<K, V> segment : map.segments) {
2098      long lastAccessTime = 0;
2099      long lastWriteTime = 0;
2100      for (ReferenceEntry<K, V> e : segment.recencyQueue) {
2101        long accessTime = e.getAccessTime();
2102        assertTrue(accessTime >= lastAccessTime);
2103        lastAccessTime = accessTime;
2104        long writeTime = e.getWriteTime();
2105        assertTrue(writeTime >= lastWriteTime);
2106        lastWriteTime = writeTime;
2107      }
2108
2109      lastAccessTime = 0;
2110      lastWriteTime = 0;
2111      for (ReferenceEntry<K, V> e : segment.accessQueue) {
2112        long accessTime = e.getAccessTime();
2113        assertTrue(accessTime >= lastAccessTime);
2114        lastAccessTime = accessTime;
2115      }
2116      for (ReferenceEntry<K, V> e : segment.writeQueue) {
2117        long writeTime = e.getWriteTime();
2118        assertTrue(writeTime >= lastWriteTime);
2119        lastWriteTime = writeTime;
2120      }
2121    }
2122  }
2123
2124  public void testExpireAfterWrite() {
2125    FakeTicker ticker = new FakeTicker();
2126    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
2127        .concurrencyLevel(1)
2128        .ticker(ticker)
2129        .expireAfterWrite(2, TimeUnit.NANOSECONDS));
2130    Segment<Object, Object> segment = map.segments[0];
2131
2132    Object key = new Object();
2133    Object value = new Object();
2134    map.put(key, value);
2135    ReferenceEntry<Object, Object> entry = map.getEntry(key);
2136    assertTrue(map.isLive(entry, ticker.read()));
2137
2138    segment.writeQueue.add(entry);
2139    assertSame(value, map.get(key));
2140    assertSame(entry, segment.writeQueue.peek());
2141    assertEquals(1, segment.writeQueue.size());
2142
2143    segment.recordRead(entry, ticker.read());
2144    segment.expireEntries(ticker.read());
2145    assertSame(value, map.get(key));
2146    assertSame(entry, segment.writeQueue.peek());
2147    assertEquals(1, segment.writeQueue.size());
2148
2149    ticker.advance(1);
2150    segment.recordRead(entry, ticker.read());
2151    segment.expireEntries(ticker.read());
2152    assertSame(value, map.get(key));
2153    assertSame(entry, segment.writeQueue.peek());
2154    assertEquals(1, segment.writeQueue.size());
2155
2156    ticker.advance(1);
2157    assertNull(map.get(key));
2158    segment.expireEntries(ticker.read());
2159    assertNull(map.get(key));
2160    assertTrue(segment.writeQueue.isEmpty());
2161  }
2162
2163  public void testExpireAfterAccess() {
2164    FakeTicker ticker = new FakeTicker();
2165    LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
2166        .concurrencyLevel(1)
2167        .ticker(ticker)
2168        .expireAfterAccess(2, TimeUnit.NANOSECONDS));
2169    Segment<Object, Object> segment = map.segments[0];
2170
2171    Object key = new Object();
2172    Object value = new Object();
2173    map.put(key, value);
2174    ReferenceEntry<Object, Object> entry = map.getEntry(key);
2175    assertTrue(map.isLive(entry, ticker.read()));
2176
2177    segment.accessQueue.add(entry);
2178    assertSame(value, map.get(key));
2179    assertSame(entry, segment.accessQueue.peek());
2180    assertEquals(1, segment.accessQueue.size());
2181
2182    segment.recordRead(entry, ticker.read());
2183    segment.expireEntries(ticker.read());
2184    assertTrue(map.containsKey(key));
2185    assertSame(entry, segment.accessQueue.peek());
2186    assertEquals(1, segment.accessQueue.size());
2187
2188    ticker.advance(1);
2189    segment.recordRead(entry, ticker.read());
2190    segment.expireEntries(ticker.read());
2191    assertTrue(map.containsKey(key));
2192    assertSame(entry, segment.accessQueue.peek());
2193    assertEquals(1, segment.accessQueue.size());
2194
2195    ticker.advance(1);
2196    segment.recordRead(entry, ticker.read());
2197    segment.expireEntries(ticker.read());
2198    assertTrue(map.containsKey(key));
2199    assertSame(entry, segment.accessQueue.peek());
2200    assertEquals(1, segment.accessQueue.size());
2201
2202    ticker.advance(1);
2203    segment.expireEntries(ticker.read());
2204    assertTrue(map.containsKey(key));
2205    assertSame(entry, segment.accessQueue.peek());
2206    assertEquals(1, segment.accessQueue.size());
2207
2208    ticker.advance(1);
2209    assertFalse(map.containsKey(key));
2210    assertNull(map.get(key));
2211    segment.expireEntries(ticker.read());
2212    assertFalse(map.containsKey(key));
2213    assertNull(map.get(key));
2214    assertTrue(segment.accessQueue.isEmpty());
2215  }
2216
2217  public void testEvictEntries() {
2218    int maxSize = 10;
2219    LocalCache<Object, Object> map =
2220        makeLocalCache(createCacheBuilder().concurrencyLevel(1).maximumSize(maxSize));
2221    Segment<Object, Object> segment = map.segments[0];
2222
2223    // manually add elements to avoid eviction
2224    int originalCount = 1024;
2225    ReferenceEntry<Object, Object> entry = null;
2226    LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
2227    for (int i = 0; i < originalCount; i++) {
2228      Object key = new Object();
2229      Object value = new Object();
2230      AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
2231      int hash = map.hash(key);
2232      int index = hash & (table.length() - 1);
2233      ReferenceEntry<Object, Object> first = table.get(index);
2234      entry = map.newEntry(key, hash, first);
2235      ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
2236      entry.setValueReference(valueRef);
2237      segment.recordWrite(entry, 1, map.ticker.read());
2238      table.set(index, entry);
2239      originalMap.put(key, value);
2240    }
2241    segment.count = originalCount;
2242    segment.totalWeight = originalCount;
2243    assertEquals(originalCount, map.size());
2244    assertEquals(originalMap, map);
2245
2246    Iterator<Object> it = originalMap.keySet().iterator();
2247    for (int i = 0; i < originalCount - maxSize; i++) {
2248      it.next();
2249      it.remove();
2250    }
2251    segment.evictEntries();
2252    assertEquals(maxSize, map.size());
2253    assertEquals(originalMap, map);
2254  }
2255
2256  // reference queues
2257
2258  public void testDrainKeyReferenceQueueOnWrite() {
2259    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2260      LocalCache<Object, Object> map =
2261          makeLocalCache(builder.concurrencyLevel(1));
2262      if (map.usesKeyReferences()) {
2263        Segment<Object, Object> segment = map.segments[0];
2264
2265        Object keyOne = new Object();
2266        int hashOne = map.hash(keyOne);
2267        Object valueOne = new Object();
2268        Object keyTwo = new Object();
2269        Object valueTwo = new Object();
2270
2271        map.put(keyOne, valueOne);
2272        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2273
2274        @SuppressWarnings("unchecked")
2275        Reference<Object> reference = (Reference) entry;
2276        reference.enqueue();
2277
2278        map.put(keyTwo, valueTwo);
2279        assertFalse(map.containsKey(keyOne));
2280        assertFalse(map.containsValue(valueOne));
2281        assertNull(map.get(keyOne));
2282        assertEquals(1, map.size());
2283        assertNull(segment.keyReferenceQueue.poll());
2284      }
2285    }
2286  }
2287
2288  public void testDrainValueReferenceQueueOnWrite() {
2289    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2290      LocalCache<Object, Object> map =
2291          makeLocalCache(builder.concurrencyLevel(1));
2292      if (map.usesValueReferences()) {
2293        Segment<Object, Object> segment = map.segments[0];
2294
2295        Object keyOne = new Object();
2296        int hashOne = map.hash(keyOne);
2297        Object valueOne = new Object();
2298        Object keyTwo = new Object();
2299        Object valueTwo = new Object();
2300
2301        map.put(keyOne, valueOne);
2302        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2303        ValueReference<Object, Object> valueReference = entry.getValueReference();
2304
2305        @SuppressWarnings("unchecked")
2306        Reference<Object> reference = (Reference) valueReference;
2307        reference.enqueue();
2308
2309        map.put(keyTwo, valueTwo);
2310        assertFalse(map.containsKey(keyOne));
2311        assertFalse(map.containsValue(valueOne));
2312        assertNull(map.get(keyOne));
2313        assertEquals(1, map.size());
2314        assertNull(segment.valueReferenceQueue.poll());
2315      }
2316    }
2317  }
2318
2319  public void testDrainKeyReferenceQueueOnRead() {
2320    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2321      LocalCache<Object, Object> map =
2322          makeLocalCache(builder.concurrencyLevel(1));
2323      if (map.usesKeyReferences()) {
2324        Segment<Object, Object> segment = map.segments[0];
2325
2326        Object keyOne = new Object();
2327        int hashOne = map.hash(keyOne);
2328        Object valueOne = new Object();
2329        Object keyTwo = new Object();
2330
2331        map.put(keyOne, valueOne);
2332        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2333
2334        @SuppressWarnings("unchecked")
2335        Reference<Object> reference = (Reference) entry;
2336        reference.enqueue();
2337
2338        for (int i = 0; i < SMALL_MAX_SIZE; i++) {
2339          map.get(keyTwo);
2340        }
2341        assertFalse(map.containsKey(keyOne));
2342        assertFalse(map.containsValue(valueOne));
2343        assertNull(map.get(keyOne));
2344        assertEquals(0, map.size());
2345        assertNull(segment.keyReferenceQueue.poll());
2346      }
2347    }
2348  }
2349
2350  public void testDrainValueReferenceQueueOnRead() {
2351    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2352      LocalCache<Object, Object> map =
2353          makeLocalCache(builder.concurrencyLevel(1));
2354      if (map.usesValueReferences()) {
2355        Segment<Object, Object> segment = map.segments[0];
2356
2357        Object keyOne = new Object();
2358        int hashOne = map.hash(keyOne);
2359        Object valueOne = new Object();
2360        Object keyTwo = new Object();
2361
2362        map.put(keyOne, valueOne);
2363        ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2364        ValueReference<Object, Object> valueReference = entry.getValueReference();
2365
2366        @SuppressWarnings("unchecked")
2367        Reference<Object> reference = (Reference) valueReference;
2368        reference.enqueue();
2369
2370        for (int i = 0; i < SMALL_MAX_SIZE; i++) {
2371          map.get(keyTwo);
2372        }
2373        assertFalse(map.containsKey(keyOne));
2374        assertFalse(map.containsValue(valueOne));
2375        assertNull(map.get(keyOne));
2376        assertEquals(0, map.size());
2377        assertNull(segment.valueReferenceQueue.poll());
2378      }
2379    }
2380  }
2381
2382  public void testNullParameters() throws Exception {
2383    NullPointerTester tester = new NullPointerTester();
2384    tester.testAllPublicInstanceMethods(makeLocalCache(createCacheBuilder()));
2385    CacheLoader<Object, Object> loader = identityLoader();
2386    tester.testAllPublicInstanceMethods(makeLocalCache(createCacheBuilder()));
2387  }
2388
2389  public void testSerializationProxyLoading() {
2390    CacheLoader<Object, Object> loader = new SerializableCacheLoader();
2391    RemovalListener<Object, Object> listener = new SerializableRemovalListener<Object, Object>();
2392    SerializableWeigher<Object, Object> weigher = new SerializableWeigher<Object, Object>();
2393    Ticker ticker = new SerializableTicker();
2394    @SuppressWarnings("unchecked") // createMock
2395    LocalLoadingCache<Object, Object> one = (LocalLoadingCache) CacheBuilder.newBuilder()
2396        .weakKeys()
2397        .softValues()
2398        .expireAfterAccess(123, SECONDS)
2399        .expireAfterWrite(456, MINUTES)
2400        .maximumWeight(789)
2401        .weigher(weigher)
2402        .concurrencyLevel(12)
2403        .removalListener(listener)
2404        .ticker(ticker)
2405        .build(loader);
2406    // add a non-serializable entry
2407    one.getUnchecked(new Object());
2408    assertEquals(1, one.size());
2409    assertFalse(one.asMap().isEmpty());
2410    LocalLoadingCache<Object, Object> two = SerializableTester.reserialize(one);
2411    assertEquals(0, two.size());
2412    assertTrue(two.asMap().isEmpty());
2413
2414    LocalCache<Object, Object> localCacheOne = one.localCache;
2415    LocalCache<Object, Object> localCacheTwo = two.localCache;
2416
2417    assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2418    assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2419    assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2420    assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2421    assertEquals(localCacheOne.maxWeight, localCacheTwo.maxWeight);
2422    assertEquals(localCacheOne.weigher, localCacheTwo.weigher);
2423    assertEquals(localCacheOne.expireAfterAccessNanos, localCacheTwo.expireAfterAccessNanos);
2424    assertEquals(localCacheOne.expireAfterWriteNanos, localCacheTwo.expireAfterWriteNanos);
2425    assertEquals(localCacheOne.refreshNanos, localCacheTwo.refreshNanos);
2426    assertEquals(localCacheOne.removalListener, localCacheTwo.removalListener);
2427    assertEquals(localCacheOne.ticker, localCacheTwo.ticker);
2428
2429    // serialize the reconstituted version to be sure we haven't lost the ability to reserialize
2430    LocalLoadingCache<Object, Object> three = SerializableTester.reserialize(two);
2431    LocalCache<Object, Object> localCacheThree = three.localCache;
2432
2433    assertEquals(localCacheTwo.defaultLoader, localCacheThree.defaultLoader);
2434    assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2435    assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2436    assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2437    assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2438    assertEquals(localCacheTwo.maxWeight, localCacheThree.maxWeight);
2439    assertEquals(localCacheTwo.weigher, localCacheThree.weigher);
2440    assertEquals(localCacheTwo.expireAfterAccessNanos, localCacheThree.expireAfterAccessNanos);
2441    assertEquals(localCacheTwo.expireAfterWriteNanos, localCacheThree.expireAfterWriteNanos);
2442    assertEquals(localCacheTwo.removalListener, localCacheThree.removalListener);
2443    assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
2444  }
2445
2446  public void testSerializationProxyManual() {
2447    RemovalListener<Object, Object> listener = new SerializableRemovalListener<Object, Object>();
2448    SerializableWeigher<Object, Object> weigher = new SerializableWeigher<Object, Object>();
2449    Ticker ticker = new SerializableTicker();
2450    @SuppressWarnings("unchecked") // createMock
2451    LocalManualCache<Object, Object> one = (LocalManualCache) CacheBuilder.newBuilder()
2452        .weakKeys()
2453        .softValues()
2454        .expireAfterAccess(123, NANOSECONDS)
2455        .maximumWeight(789)
2456        .weigher(weigher)
2457        .concurrencyLevel(12)
2458        .removalListener(listener)
2459        .ticker(ticker)
2460        .build();
2461    // add a non-serializable entry
2462    one.put(new Object(), new Object());
2463    assertEquals(1, one.size());
2464    assertFalse(one.asMap().isEmpty());
2465    LocalManualCache<Object, Object> two = SerializableTester.reserialize(one);
2466    assertEquals(0, two.size());
2467    assertTrue(two.asMap().isEmpty());
2468
2469    LocalCache<Object, Object> localCacheOne = one.localCache;
2470    LocalCache<Object, Object> localCacheTwo = two.localCache;
2471
2472    assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2473    assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2474    assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2475    assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2476    assertEquals(localCacheOne.maxWeight, localCacheTwo.maxWeight);
2477    assertEquals(localCacheOne.weigher, localCacheTwo.weigher);
2478    assertEquals(localCacheOne.expireAfterAccessNanos, localCacheTwo.expireAfterAccessNanos);
2479    assertEquals(localCacheOne.expireAfterWriteNanos, localCacheTwo.expireAfterWriteNanos);
2480    assertEquals(localCacheOne.removalListener, localCacheTwo.removalListener);
2481    assertEquals(localCacheOne.ticker, localCacheTwo.ticker);
2482
2483    // serialize the reconstituted version to be sure we haven't lost the ability to reserialize
2484    LocalManualCache<Object, Object> three = SerializableTester.reserialize(two);
2485    LocalCache<Object, Object> localCacheThree = three.localCache;
2486
2487    assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2488    assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2489    assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2490    assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2491    assertEquals(localCacheTwo.maxWeight, localCacheThree.maxWeight);
2492    assertEquals(localCacheTwo.weigher, localCacheThree.weigher);
2493    assertEquals(localCacheTwo.expireAfterAccessNanos, localCacheThree.expireAfterAccessNanos);
2494    assertEquals(localCacheTwo.expireAfterWriteNanos, localCacheThree.expireAfterWriteNanos);
2495    assertEquals(localCacheTwo.removalListener, localCacheThree.removalListener);
2496    assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
2497  }
2498
2499  // utility methods
2500
2501  /**
2502   * Returns an iterable containing all combinations of maximumSize, expireAfterAccess/Write,
2503   * weakKeys and weak/softValues.
2504   */
2505  @SuppressWarnings("unchecked") // varargs
2506  private static Iterable<CacheBuilder<Object, Object>> allEntryTypeMakers() {
2507    List<CacheBuilder<Object, Object>> result =
2508        newArrayList(allKeyValueStrengthMakers());
2509    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2510      result.add(builder.maximumSize(SMALL_MAX_SIZE));
2511    }
2512    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2513      result.add(builder.expireAfterAccess(99999, SECONDS));
2514    }
2515    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2516      result.add(builder.expireAfterWrite(99999, SECONDS));
2517    }
2518    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2519      result.add(builder.maximumSize(SMALL_MAX_SIZE).expireAfterAccess(99999, SECONDS));
2520    }
2521    for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2522      result.add(builder.maximumSize(SMALL_MAX_SIZE).expireAfterWrite(99999, SECONDS));
2523    }
2524    return result;
2525  }
2526
2527  /**
2528   * Returns an iterable containing all combinations of maximumSize and expireAfterAccess/Write.
2529   */
2530  @SuppressWarnings("unchecked") // varargs
2531  static Iterable<CacheBuilder<Object, Object>> allEvictingMakers() {
2532    return ImmutableList.of(createCacheBuilder().maximumSize(SMALL_MAX_SIZE),
2533        createCacheBuilder().expireAfterAccess(99999, SECONDS),
2534        createCacheBuilder().expireAfterWrite(99999, SECONDS),
2535        createCacheBuilder()
2536            .maximumSize(SMALL_MAX_SIZE)
2537            .expireAfterAccess(SMALL_MAX_SIZE, TimeUnit.SECONDS),
2538        createCacheBuilder()
2539            .maximumSize(SMALL_MAX_SIZE)
2540            .expireAfterWrite(SMALL_MAX_SIZE, TimeUnit.SECONDS));
2541  }
2542
2543  /**
2544   * Returns an iterable containing all combinations weakKeys and weak/softValues.
2545   */
2546  @SuppressWarnings("unchecked") // varargs
2547  private static Iterable<CacheBuilder<Object, Object>> allKeyValueStrengthMakers() {
2548    return ImmutableList.of(createCacheBuilder(),
2549        createCacheBuilder().weakValues(),
2550        createCacheBuilder().softValues(),
2551        createCacheBuilder().weakKeys(),
2552        createCacheBuilder().weakKeys().weakValues(),
2553        createCacheBuilder().weakKeys().softValues());
2554  }
2555
2556  // entries and values
2557
2558  private static <K, V> DummyEntry<K, V> createDummyEntry(
2559      K key, int hash, V value, ReferenceEntry<K, V> next) {
2560    DummyEntry<K, V> entry = DummyEntry.create(key, hash, next);
2561    DummyValueReference<K, V> valueRef = DummyValueReference.create(value);
2562    entry.setValueReference(valueRef);
2563    return entry;
2564  }
2565
2566  static class DummyEntry<K, V> implements ReferenceEntry<K, V> {
2567    private K key;
2568    private final int hash;
2569    private final ReferenceEntry<K, V> next;
2570
2571    public DummyEntry(K key, int hash, ReferenceEntry<K, V> next) {
2572      this.key = key;
2573      this.hash = hash;
2574      this.next = next;
2575    }
2576
2577    public static <K, V> DummyEntry<K, V> create(K key, int hash, ReferenceEntry<K, V> next) {
2578      return new DummyEntry<K, V>(key, hash, next);
2579    }
2580
2581    public void clearKey() {
2582      this.key = null;
2583    }
2584
2585    private ValueReference<K, V> valueReference = unset();
2586
2587    @Override
2588    public ValueReference<K, V> getValueReference() {
2589      return valueReference;
2590    }
2591
2592    @Override
2593    public void setValueReference(ValueReference<K, V> valueReference) {
2594      this.valueReference = valueReference;
2595    }
2596
2597    @Override
2598    public ReferenceEntry<K, V> getNext() {
2599      return next;
2600    }
2601
2602    @Override
2603    public int getHash() {
2604      return hash;
2605    }
2606
2607    @Override
2608    public K getKey() {
2609      return key;
2610    }
2611
2612    private long accessTime = Long.MAX_VALUE;
2613
2614    @Override
2615    public long getAccessTime() {
2616      return accessTime;
2617    }
2618
2619    @Override
2620    public void setAccessTime(long time) {
2621      this.accessTime = time;
2622    }
2623
2624    private ReferenceEntry<K, V> nextAccess = nullEntry();
2625
2626    @Override
2627    public ReferenceEntry<K, V> getNextInAccessQueue() {
2628      return nextAccess;
2629    }
2630
2631    @Override
2632    public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
2633      this.nextAccess = next;
2634    }
2635
2636    private ReferenceEntry<K, V> previousAccess = nullEntry();
2637
2638    @Override
2639    public ReferenceEntry<K, V> getPreviousInAccessQueue() {
2640      return previousAccess;
2641    }
2642
2643    @Override
2644    public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
2645      this.previousAccess = previous;
2646    }
2647
2648    private long writeTime = Long.MAX_VALUE;
2649
2650    @Override
2651    public long getWriteTime() {
2652      return writeTime;
2653    }
2654
2655    @Override
2656    public void setWriteTime(long time) {
2657      this.writeTime = time;
2658    }
2659
2660    private ReferenceEntry<K, V> nextWrite = nullEntry();
2661
2662    @Override
2663    public ReferenceEntry<K, V> getNextInWriteQueue() {
2664      return nextWrite;
2665    }
2666
2667    @Override
2668    public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
2669      this.nextWrite = next;
2670    }
2671
2672    private ReferenceEntry<K, V> previousWrite = nullEntry();
2673
2674    @Override
2675    public ReferenceEntry<K, V> getPreviousInWriteQueue() {
2676      return previousWrite;
2677    }
2678
2679    @Override
2680    public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
2681      this.previousWrite = previous;
2682    }
2683  }
2684
2685  static class DummyValueReference<K, V> implements ValueReference<K, V> {
2686    private V value;
2687    boolean loading = false;
2688
2689    public DummyValueReference() {
2690      this.loading = true;
2691    }
2692
2693    public DummyValueReference(V value) {
2694      this.value = value;
2695    }
2696
2697    public static <K, V> DummyValueReference<K, V> create(V value) {
2698      return new DummyValueReference<K, V>(value);
2699    }
2700
2701    public static <K, V> DummyValueReference<K, V> createLoading() {
2702      return new DummyValueReference<K, V>();
2703    }
2704
2705    @Override
2706    public V get() {
2707      return value;
2708    }
2709
2710    @Override
2711    public int getWeight() {
2712      return 1;
2713    }
2714
2715    @Override
2716    public ReferenceEntry<K, V> getEntry() {
2717      return null;
2718    }
2719
2720    @Override
2721    public ValueReference<K, V> copyFor(
2722        ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
2723      return this;
2724    }
2725
2726    public void setLoading(boolean loading) {
2727      this.loading = loading;
2728    }
2729
2730    @Override
2731    public boolean isLoading() {
2732      return loading;
2733    }
2734
2735    @Override
2736    public boolean isActive() {
2737      return !loading;
2738    }
2739
2740    @Override
2741    public V waitForValue() {
2742      return get();
2743    }
2744
2745    @Override
2746    public void notifyNewValue(V newValue) {}
2747
2748    public void clear() {
2749      value = null;
2750    }
2751  }
2752
2753  private static class SerializableCacheLoader
2754      extends CacheLoader<Object, Object> implements Serializable {
2755    @Override
2756    public Object load(Object key) {
2757      return new Object();
2758    }
2759
2760    @Override
2761    public int hashCode() {
2762      return 42;
2763    }
2764
2765    @Override
2766    public boolean equals(Object o) {
2767      return (o instanceof SerializableCacheLoader);
2768    }
2769  }
2770
2771  private static class SerializableRemovalListener<K, V>
2772      implements RemovalListener<K, V>, Serializable {
2773    @Override
2774    public void onRemoval(RemovalNotification<K, V> notification) {}
2775
2776    @Override
2777    public int hashCode() {
2778      return 42;
2779    }
2780
2781    @Override
2782    public boolean equals(Object o) {
2783      return (o instanceof SerializableRemovalListener);
2784    }
2785  }
2786
2787  private static class SerializableTicker extends Ticker implements Serializable {
2788    @Override
2789    public long read() {
2790      return 42;
2791    }
2792
2793    @Override
2794    public int hashCode() {
2795      return 42;
2796    }
2797
2798    @Override
2799    public boolean equals(Object o) {
2800      return (o instanceof SerializableTicker);
2801    }
2802  }
2803
2804  private static class SerializableWeigher<K, V> implements Weigher<K, V>, Serializable {
2805    @Override
2806    public int weigh(K key, V value) {
2807      return 42;
2808    }
2809
2810    @Override
2811    public int hashCode() {
2812      return 42;
2813    }
2814
2815    @Override
2816    public boolean equals(Object o) {
2817      return (o instanceof SerializableWeigher);
2818    }
2819  }
2820
2821}
2822