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