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