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