1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.cache; 16 17 import static com.google.common.cache.CacheTesting.checkEmpty; 18 import static com.google.common.cache.CacheTesting.checkValidState; 19 import static com.google.common.cache.TestingCacheLoaders.identityLoader; 20 import static java.util.Arrays.asList; 21 import static java.util.concurrent.TimeUnit.DAYS; 22 import static java.util.concurrent.TimeUnit.MILLISECONDS; 23 import static java.util.concurrent.TimeUnit.SECONDS; 24 import static org.junit.contrib.truth.Truth.ASSERT; 25 26 import com.google.common.base.Function; 27 import com.google.common.cache.CacheBuilderFactory.DurationSpec; 28 import com.google.common.cache.LocalCache.Strength; 29 import com.google.common.collect.ImmutableMap; 30 import com.google.common.collect.ImmutableSet; 31 import com.google.common.collect.Iterables; 32 import com.google.common.collect.Iterators; 33 import com.google.common.collect.Lists; 34 import com.google.common.collect.Maps; 35 import com.google.common.testing.EqualsTester; 36 37 import junit.framework.TestCase; 38 39 import java.util.Collection; 40 import java.util.List; 41 import java.util.Map; 42 import java.util.Map.Entry; 43 import java.util.Set; 44 45 /** 46 * {@link LoadingCache} tests that deal with caches that actually contain some key-value mappings. 47 * 48 * @author mike nonemacher 49 */ 50 public class PopulatedCachesTest extends TestCase { 51 // we use integers as keys; make sure the range covers some values that ARE cached by 52 // Integer.valueOf(int), and some that are not cached. (127 is the highest cached value.) 53 static final int WARMUP_MIN = 120; 54 static final int WARMUP_MAX = 135; 55 static final int WARMUP_SIZE = WARMUP_MAX - WARMUP_MIN; 56 testSize_populated()57 public void testSize_populated() { 58 for (LoadingCache<Object, Object> cache : caches()) { 59 // don't let the entries get GCed 60 List<Entry<Object, Object>> warmed = warmUp(cache); 61 assertEquals(WARMUP_SIZE, cache.size()); 62 assertMapSize(cache.asMap(), WARMUP_SIZE); 63 checkValidState(cache); 64 } 65 } 66 testContainsKey_found()67 public void testContainsKey_found() { 68 for (LoadingCache<Object, Object> cache : caches()) { 69 // don't let the entries get GCed 70 List<Entry<Object, Object>> warmed = warmUp(cache); 71 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 72 Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN); 73 assertTrue(cache.asMap().containsKey(entry.getKey())); 74 assertTrue(cache.asMap().containsValue(entry.getValue())); 75 // this getUnchecked() call shouldn't be a cache miss; verified below 76 assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey())); 77 } 78 assertEquals(WARMUP_SIZE, cache.stats().missCount()); 79 checkValidState(cache); 80 } 81 } 82 testPut_populated()83 public void testPut_populated() { 84 for (LoadingCache<Object, Object> cache : caches()) { 85 // don't let the entries get GCed 86 List<Entry<Object, Object>> warmed = warmUp(cache); 87 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 88 Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN); 89 Object newValue = new Object(); 90 assertSame(entry.getValue(), cache.asMap().put(entry.getKey(), newValue)); 91 // don't let the new entry get GCed 92 warmed.add(entryOf(entry.getKey(), newValue)); 93 Object newKey = new Object(); 94 assertNull(cache.asMap().put(newKey, entry.getValue())); 95 // this getUnchecked() call shouldn't be a cache miss; verified below 96 assertEquals(newValue, cache.getUnchecked(entry.getKey())); 97 assertEquals(entry.getValue(), cache.getUnchecked(newKey)); 98 // don't let the new entry get GCed 99 warmed.add(entryOf(newKey, entry.getValue())); 100 } 101 assertEquals(WARMUP_SIZE, cache.stats().missCount()); 102 checkValidState(cache); 103 } 104 } 105 testPutIfAbsent_populated()106 public void testPutIfAbsent_populated() { 107 for (LoadingCache<Object, Object> cache : caches()) { 108 // don't let the entries get GCed 109 List<Entry<Object, Object>> warmed = warmUp(cache); 110 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 111 Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN); 112 Object newValue = new Object(); 113 assertSame(entry.getValue(), cache.asMap().putIfAbsent(entry.getKey(), newValue)); 114 Object newKey = new Object(); 115 assertNull(cache.asMap().putIfAbsent(newKey, entry.getValue())); 116 // this getUnchecked() call shouldn't be a cache miss; verified below 117 assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey())); 118 assertEquals(entry.getValue(), cache.getUnchecked(newKey)); 119 // don't let the new entry get GCed 120 warmed.add(entryOf(newKey, entry.getValue())); 121 } 122 assertEquals(WARMUP_SIZE, cache.stats().missCount()); 123 checkValidState(cache); 124 } 125 } 126 testPutAll_populated()127 public void testPutAll_populated() { 128 for (LoadingCache<Object, Object> cache : caches()) { 129 // don't let the entries get GCed 130 List<Entry<Object, Object>> warmed = warmUp(cache); 131 Object newKey = new Object(); 132 Object newValue = new Object(); 133 cache.asMap().putAll(ImmutableMap.of(newKey, newValue)); 134 // this getUnchecked() call shouldn't be a cache miss; verified below 135 assertEquals(newValue, cache.getUnchecked(newKey)); 136 assertEquals(WARMUP_SIZE, cache.stats().missCount()); 137 checkValidState(cache); 138 } 139 } 140 testReplace_populated()141 public void testReplace_populated() { 142 for (LoadingCache<Object, Object> cache : caches()) { 143 // don't let the entries get GCed 144 List<Entry<Object, Object>> warmed = warmUp(cache); 145 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 146 Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN); 147 Object newValue = new Object(); 148 assertSame(entry.getValue(), cache.asMap().replace(entry.getKey(), newValue)); 149 assertTrue(cache.asMap().replace(entry.getKey(), newValue, entry.getValue())); 150 Object newKey = new Object(); 151 assertNull(cache.asMap().replace(newKey, entry.getValue())); 152 assertFalse(cache.asMap().replace(newKey, entry.getValue(), newValue)); 153 // this getUnchecked() call shouldn't be a cache miss; verified below 154 assertEquals(entry.getValue(), cache.getUnchecked(entry.getKey())); 155 assertFalse(cache.asMap().containsKey(newKey)); 156 } 157 assertEquals(WARMUP_SIZE, cache.stats().missCount()); 158 checkValidState(cache); 159 } 160 } 161 testRemove_byKey()162 public void testRemove_byKey() { 163 for (LoadingCache<Object, Object> cache : caches()) { 164 // don't let the entries get GCed 165 List<Entry<Object, Object>> warmed = warmUp(cache); 166 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 167 Entry<Object, Object> entry = warmed.get(i - WARMUP_MIN); 168 Object key = entry.getKey(); 169 assertEquals(entry.getValue(), cache.asMap().remove(key)); 170 assertNull(cache.asMap().remove(key)); 171 assertFalse(cache.asMap().containsKey(key)); 172 } 173 checkEmpty(cache); 174 } 175 } 176 testRemove_byKeyAndValue()177 public void testRemove_byKeyAndValue() { 178 for (LoadingCache<Object, Object> cache : caches()) { 179 // don't let the entries get GCed 180 List<Entry<Object, Object>> warmed = warmUp(cache); 181 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 182 Object key = warmed.get(i - WARMUP_MIN).getKey(); 183 Object value = warmed.get(i - WARMUP_MIN).getValue(); 184 assertFalse(cache.asMap().remove(key, -1)); 185 assertTrue(cache.asMap().remove(key, value)); 186 assertFalse(cache.asMap().remove(key, -1)); 187 assertFalse(cache.asMap().containsKey(key)); 188 } 189 checkEmpty(cache); 190 } 191 } 192 testKeySet_populated()193 public void testKeySet_populated() { 194 for (LoadingCache<Object, Object> cache : caches()) { 195 Set<Object> keys = cache.asMap().keySet(); 196 List<Entry<Object, Object>> warmed = warmUp(cache); 197 198 Object[] expectedArray = Maps.newHashMap(cache.asMap()).keySet().toArray(new Object[0]); 199 ASSERT.that(keys).hasContentsAnyOrder(expectedArray); 200 ASSERT.that(asList(keys.toArray())).hasContentsAnyOrder(expectedArray); 201 ASSERT.that(asList(keys.toArray(new Object[(int) cache.size()]))) 202 .hasContentsAnyOrder(expectedArray); 203 204 new EqualsTester() 205 .addEqualityGroup(cache.asMap().keySet(), keys) 206 .addEqualityGroup(ImmutableSet.of()) 207 .testEquals(); 208 assertEquals(WARMUP_SIZE, keys.size()); 209 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 210 Object key = warmed.get(i - WARMUP_MIN).getKey(); 211 assertTrue(keys.contains(key)); 212 assertTrue(keys.remove(key)); 213 assertFalse(keys.remove(key)); 214 assertFalse(keys.contains(key)); 215 } 216 checkEmpty(keys); 217 checkEmpty(cache); 218 } 219 } 220 testValues_populated()221 public void testValues_populated() { 222 for (LoadingCache<Object, Object> cache : caches()) { 223 Collection<Object> values = cache.asMap().values(); 224 List<Entry<Object, Object>> warmed = warmUp(cache); 225 226 Object[] expectedArray = Maps.newHashMap(cache.asMap()).values().toArray(new Object[0]); 227 ASSERT.that(values).hasContentsAnyOrder(expectedArray); 228 ASSERT.that(asList(values.toArray())).hasContentsAnyOrder(expectedArray); 229 ASSERT.that(asList(values.toArray(new Object[(int) cache.size()]))) 230 .hasContentsAnyOrder(expectedArray); 231 232 assertEquals(WARMUP_SIZE, values.size()); 233 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 234 Object value = warmed.get(i - WARMUP_MIN).getValue(); 235 assertTrue(values.contains(value)); 236 assertTrue(values.remove(value)); 237 assertFalse(values.remove(value)); 238 assertFalse(values.contains(value)); 239 } 240 checkEmpty(values); 241 checkEmpty(cache); 242 } 243 } 244 245 @SuppressWarnings("unchecked") // generic array creation testEntrySet_populated()246 public void testEntrySet_populated() { 247 for (LoadingCache<Object, Object> cache : caches()) { 248 Set<Entry<Object, Object>> entries = cache.asMap().entrySet(); 249 List<Entry<Object, Object>> warmed = warmUp(cache, WARMUP_MIN, WARMUP_MAX); 250 251 Set<Entry<Object, Object>> entrySet = Maps.newHashMap(cache.asMap()).entrySet(); 252 ASSERT.that(entries).is(entrySet); 253 ASSERT.that(entries.toArray()).hasContentsAnyOrder(entrySet.toArray()); 254 ASSERT.that(entries.toArray(new Entry[0])) 255 .hasContentsAnyOrder(entrySet.toArray(new Entry[0])); 256 257 new EqualsTester() 258 .addEqualityGroup(cache.asMap().entrySet(), entries) 259 .addEqualityGroup(ImmutableSet.of()) 260 .testEquals(); 261 assertEquals(WARMUP_SIZE, entries.size()); 262 for (int i = WARMUP_MIN; i < WARMUP_MAX; i++) { 263 Entry<Object, Object> newEntry = warmed.get(i - WARMUP_MIN); 264 assertTrue(entries.contains(newEntry)); 265 assertTrue(entries.remove(newEntry)); 266 assertFalse(entries.remove(newEntry)); 267 assertFalse(entries.contains(newEntry)); 268 } 269 checkEmpty(entries); 270 checkEmpty(cache); 271 } 272 } 273 testWriteThroughEntry()274 public void testWriteThroughEntry() { 275 for (LoadingCache<Object, Object> cache : caches()) { 276 cache.getUnchecked(1); 277 Entry<Object, Object> entry = Iterables.getOnlyElement(cache.asMap().entrySet()); 278 try { 279 entry.setValue(3); 280 fail("expected entry.setValue to throw UnsupportedOperationException"); 281 } catch (UnsupportedOperationException expected) { 282 } 283 try { 284 entry.setValue(null); 285 fail("expected entry.setValue(null) to throw UnsupportedOperationException"); 286 } catch (UnsupportedOperationException expected) { 287 } 288 checkValidState(cache); 289 } 290 } 291 292 /* ---------------- Local utilities -------------- */ 293 294 /** 295 * Most of the tests in this class run against every one of these caches. 296 */ caches()297 private Iterable<LoadingCache<Object, Object>> caches() { 298 // lots of different ways to configure a LoadingCache 299 CacheBuilderFactory factory = cacheFactory(); 300 return Iterables.transform(factory.buildAllPermutations(), 301 new Function<CacheBuilder<Object, Object>, LoadingCache<Object, Object>>() { 302 @Override public LoadingCache<Object, Object> apply( 303 CacheBuilder<Object, Object> builder) { 304 return builder.build(identityLoader()); 305 } 306 }); 307 } 308 309 private CacheBuilderFactory cacheFactory() { 310 // This is trickier than expected. We plan to put 15 values in each of these (WARMUP_MIN to 311 // WARMUP_MAX), but the tests assume no values get evicted. Even with a maximumSize of 100, one 312 // of the values gets evicted. With weak keys, we use identity equality, which means using 313 // System.identityHashCode, which means the assignment of keys to segments is nondeterministic, 314 // so more than (maximumSize / #segments) keys could get assigned to the same segment, which 315 // would cause one to be evicted. 316 return new CacheBuilderFactory() 317 .withKeyStrengths(ImmutableSet.of(Strength.STRONG, Strength.WEAK)) 318 .withValueStrengths(ImmutableSet.copyOf(Strength.values())) 319 .withConcurrencyLevels(ImmutableSet.of(1, 4, 16, 64)) 320 .withMaximumSizes(ImmutableSet.of(400, 1000)) 321 .withInitialCapacities(ImmutableSet.of(0, 1, 10, 100, 1000)) 322 .withExpireAfterWrites(ImmutableSet.of( 323 // DurationSpec.of(500, MILLISECONDS), 324 DurationSpec.of(1, SECONDS), 325 DurationSpec.of(1, DAYS))) 326 .withExpireAfterAccesses(ImmutableSet.of( 327 // DurationSpec.of(500, MILLISECONDS), 328 DurationSpec.of(1, SECONDS), 329 DurationSpec.of(1, DAYS))) 330 .withRefreshes(ImmutableSet.of( 331 // DurationSpec.of(500, MILLISECONDS), 332 DurationSpec.of(1, SECONDS), 333 DurationSpec.of(1, DAYS))); 334 } 335 336 private List<Map.Entry<Object, Object>> warmUp(LoadingCache<Object, Object> cache) { 337 return warmUp(cache, WARMUP_MIN, WARMUP_MAX); 338 } 339 340 /** 341 * Returns the entries that were added to the map, so they won't fall out of a map with weak or 342 * soft references until the caller drops the reference to the returned entries. 343 */ 344 private List<Map.Entry<Object, Object>> warmUp( 345 LoadingCache<Object, Object> cache, int minimum, int maximum) { 346 347 List<Map.Entry<Object, Object>> entries = Lists.newArrayList(); 348 for (int i = minimum; i < maximum; i++) { 349 Object key = i; 350 Object value = cache.getUnchecked(key); 351 entries.add(entryOf(key, value)); 352 } 353 return entries; 354 } 355 356 private Entry<Object, Object> entryOf(Object key, Object value) { 357 return Maps.immutableEntry(key, value); 358 } 359 360 private void assertMapSize(Map<?, ?> map, int size) { 361 assertEquals(size, map.size()); 362 if (size > 0) { 363 assertFalse(map.isEmpty()); 364 } else { 365 assertTrue(map.isEmpty()); 366 } 367 assertCollectionSize(map.keySet(), size); 368 assertCollectionSize(map.entrySet(), size); 369 assertCollectionSize(map.values(), size); 370 } 371 372 private void assertCollectionSize(Collection<?> collection, int size) { 373 assertEquals(size, collection.size()); 374 if (size > 0) { 375 assertFalse(collection.isEmpty()); 376 } else { 377 assertTrue(collection.isEmpty()); 378 } 379 assertEquals(size, Iterables.size(collection)); 380 assertEquals(size, Iterators.size(collection.iterator())); 381 } 382 } 383