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