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