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