LruCacheTest.java revision 7db1b40a03ff04ac8b49b3b53839b3c5d1c6f16a
1/* 2 * Copyright (C) 2011 The Android Open Source Project 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 17package android.util; 18 19import java.util.ArrayList; 20import java.util.Arrays; 21import java.util.Collections; 22import java.util.List; 23import java.util.Map; 24import junit.framework.TestCase; 25 26public final class LruCacheTest extends TestCase { 27 private int expectedCreateCount; 28 private int expectedPutCount; 29 private int expectedHitCount; 30 private int expectedMissCount; 31 private int expectedEvictionCount; 32 33 public void testStatistics() { 34 LruCache<String, String> cache = new LruCache<String, String>(3); 35 assertStatistics(cache); 36 37 assertEquals(null, cache.put("a", "A")); 38 expectedPutCount++; 39 assertStatistics(cache); 40 assertHit(cache, "a", "A"); 41 assertSnapshot(cache, "a", "A"); 42 43 assertEquals(null, cache.put("b", "B")); 44 expectedPutCount++; 45 assertStatistics(cache); 46 assertHit(cache, "a", "A"); 47 assertHit(cache, "b", "B"); 48 assertSnapshot(cache, "a", "A", "b", "B"); 49 50 assertEquals(null, cache.put("c", "C")); 51 expectedPutCount++; 52 assertStatistics(cache); 53 assertHit(cache, "a", "A"); 54 assertHit(cache, "b", "B"); 55 assertHit(cache, "c", "C"); 56 assertSnapshot(cache, "a", "A", "b", "B", "c", "C"); 57 58 assertEquals(null, cache.put("d", "D")); 59 expectedPutCount++; 60 expectedEvictionCount++; // a should have been evicted 61 assertStatistics(cache); 62 assertMiss(cache, "a"); 63 assertHit(cache, "b", "B"); 64 assertHit(cache, "c", "C"); 65 assertHit(cache, "d", "D"); 66 assertHit(cache, "b", "B"); 67 assertHit(cache, "c", "C"); 68 assertSnapshot(cache, "d", "D", "b", "B", "c", "C"); 69 70 assertEquals(null, cache.put("e", "E")); 71 expectedPutCount++; 72 expectedEvictionCount++; // d should have been evicted 73 assertStatistics(cache); 74 assertMiss(cache, "d"); 75 assertMiss(cache, "a"); 76 assertHit(cache, "e", "E"); 77 assertHit(cache, "b", "B"); 78 assertHit(cache, "c", "C"); 79 assertSnapshot(cache, "e", "E", "b", "B", "c", "C"); 80 } 81 82 public void testStatisticsWithCreate() { 83 LruCache<String, String> cache = newCreatingCache(); 84 assertStatistics(cache); 85 86 assertCreated(cache, "aa", "created-aa"); 87 assertHit(cache, "aa", "created-aa"); 88 assertSnapshot(cache, "aa", "created-aa"); 89 90 assertCreated(cache, "bb", "created-bb"); 91 assertMiss(cache, "c"); 92 assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb"); 93 94 assertCreated(cache, "cc", "created-cc"); 95 assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb", "cc", "created-cc"); 96 97 expectedEvictionCount++; // aa will be evicted 98 assertCreated(cache, "dd", "created-dd"); 99 assertSnapshot(cache, "bb", "created-bb", "cc", "created-cc", "dd", "created-dd"); 100 101 expectedEvictionCount++; // bb will be evicted 102 assertCreated(cache, "aa", "created-aa"); 103 assertSnapshot(cache, "cc", "created-cc", "dd", "created-dd", "aa", "created-aa"); 104 } 105 106 public void testCreateOnCacheMiss() { 107 LruCache<String, String> cache = newCreatingCache(); 108 String created = cache.get("aa"); 109 assertEquals("created-aa", created); 110 } 111 112 public void testNoCreateOnCacheHit() { 113 LruCache<String, String> cache = newCreatingCache(); 114 cache.put("aa", "put-aa"); 115 assertEquals("put-aa", cache.get("aa")); 116 } 117 118 public void testConstructorDoesNotAllowZeroCacheSize() { 119 try { 120 new LruCache<String, String>(0); 121 fail(); 122 } catch (IllegalArgumentException expected) { 123 } 124 } 125 126 public void testCannotPutNullKey() { 127 LruCache<String, String> cache = new LruCache<String, String>(3); 128 try { 129 cache.put(null, "A"); 130 fail(); 131 } catch (NullPointerException expected) { 132 } 133 } 134 135 public void testCannotPutNullValue() { 136 LruCache<String, String> cache = new LruCache<String, String>(3); 137 try { 138 cache.put("a", null); 139 fail(); 140 } catch (NullPointerException expected) { 141 } 142 } 143 144 public void testToString() { 145 LruCache<String, String> cache = new LruCache<String, String>(3); 146 assertEquals("LruCache[maxSize=3,hits=0,misses=0,hitRate=0%]", cache.toString()); 147 148 cache.put("a", "A"); 149 cache.put("b", "B"); 150 cache.put("c", "C"); 151 cache.put("d", "D"); 152 153 cache.get("a"); // miss 154 cache.get("b"); // hit 155 cache.get("c"); // hit 156 cache.get("d"); // hit 157 cache.get("e"); // miss 158 159 assertEquals("LruCache[maxSize=3,hits=3,misses=2,hitRate=60%]", cache.toString()); 160 } 161 162 public void testEvictionWithSingletonCache() { 163 LruCache<String, String> cache = new LruCache<String, String>(1); 164 cache.put("a", "A"); 165 cache.put("b", "B"); 166 assertSnapshot(cache, "b", "B"); 167 } 168 169 public void testEntryEvictedWhenFull() { 170 List<String> log = new ArrayList<String>(); 171 LruCache<String, String> cache = newRemovalLogCache(log); 172 173 cache.put("a", "A"); 174 cache.put("b", "B"); 175 cache.put("c", "C"); 176 assertEquals(Collections.<String>emptyList(), log); 177 178 cache.put("d", "D"); 179 assertEquals(Arrays.asList("a=A"), log); 180 } 181 182 /** 183 * Replacing the value for a key doesn't cause an eviction but it does bring 184 * the replaced entry to the front of the queue. 185 */ 186 public void testPutDoesNotCauseEviction() { 187 final List<String> evictionLog = new ArrayList<String>(); 188 List<String> expectedEvictionLog = new ArrayList<String>(); 189 LruCache<String, String> cache = new LruCache<String, String>(3) { 190 @Override protected void entryEvicted(String key, String value) { 191 evictionLog.add(key + "=" + value); 192 } 193 }; 194 195 cache.put("a", "A"); 196 cache.put("b", "B"); 197 cache.put("c", "C"); 198 cache.put("b", "B2"); 199 assertEquals(expectedEvictionLog, evictionLog); 200 assertSnapshot(cache, "a", "A", "c", "C", "b", "B2"); 201 } 202 203 public void testCustomSizesImpactsSize() { 204 LruCache<String, String> cache = new LruCache<String, String>(10) { 205 @Override protected int sizeOf(String key, String value) { 206 return key.length() + value.length(); 207 } 208 }; 209 210 assertEquals(0, cache.size()); 211 cache.put("a", "AA"); 212 assertEquals(3, cache.size()); 213 cache.put("b", "BBBB"); 214 assertEquals(8, cache.size()); 215 cache.put("a", ""); 216 assertEquals(6, cache.size()); 217 } 218 219 public void testEvictionWithCustomSizes() { 220 LruCache<String, String> cache = new LruCache<String, String>(4) { 221 @Override protected int sizeOf(String key, String value) { 222 return value.length(); 223 } 224 }; 225 226 cache.put("a", "AAAA"); 227 assertSnapshot(cache, "a", "AAAA"); 228 cache.put("b", "BBBB"); // should evict a 229 assertSnapshot(cache, "b", "BBBB"); 230 cache.put("c", "CC"); // should evict b 231 assertSnapshot(cache, "c", "CC"); 232 cache.put("d", "DD"); 233 assertSnapshot(cache, "c", "CC", "d", "DD"); 234 cache.put("e", "E"); // should evict c 235 assertSnapshot(cache, "d", "DD", "e", "E"); 236 cache.put("f", "F"); 237 assertSnapshot(cache, "d", "DD", "e", "E", "f", "F"); 238 cache.put("g", "G"); // should evict d 239 assertSnapshot(cache, "e", "E", "f", "F", "g", "G"); 240 cache.put("h", "H"); 241 assertSnapshot(cache, "e", "E", "f", "F", "g", "G", "h", "H"); 242 cache.put("i", "III"); // should evict e, f, and g 243 assertSnapshot(cache, "h", "H", "i", "III"); 244 cache.put("j", "JJJ"); // should evict h and i 245 assertSnapshot(cache, "j", "JJJ"); 246 } 247 248 public void testEvictionThrowsWhenSizesAreInconsistent() { 249 LruCache<String, int[]> cache = new LruCache<String, int[]>(4) { 250 @Override protected int sizeOf(String key, int[] value) { 251 return value[0]; 252 } 253 }; 254 255 int[] a = { 4 }; 256 cache.put("a", a); 257 258 // get the cache size out of sync 259 a[0] = 1; 260 assertEquals(4, cache.size()); 261 262 // evict something 263 try { 264 cache.put("b", new int[] { 2 }); 265 fail(); 266 } catch (IllegalStateException expected) { 267 } 268 } 269 270 public void testEvictionThrowsWhenSizesAreNegative() { 271 LruCache<String, String> cache = new LruCache<String, String>(4) { 272 @Override protected int sizeOf(String key, String value) { 273 return -1; 274 } 275 }; 276 277 try { 278 cache.put("a", "A"); 279 fail(); 280 } catch (IllegalStateException expected) { 281 } 282 } 283 284 /** 285 * Naive caches evict at most one element at a time. This is problematic 286 * because evicting a small element may be insufficient to make room for a 287 * large element. 288 */ 289 public void testDifferentElementSizes() { 290 LruCache<String, String> cache = new LruCache<String, String>(10) { 291 @Override protected int sizeOf(String key, String value) { 292 return value.length(); 293 } 294 }; 295 296 cache.put("a", "1"); 297 cache.put("b", "12345678"); 298 cache.put("c", "1"); 299 assertSnapshot(cache, "a", "1", "b", "12345678", "c", "1"); 300 cache.put("d", "12345678"); // should evict a and b 301 assertSnapshot(cache, "c", "1", "d", "12345678"); 302 cache.put("e", "12345678"); // should evict c and d 303 assertSnapshot(cache, "e", "12345678"); 304 } 305 306 public void testEvictAll() { 307 List<String> log = new ArrayList<String>(); 308 LruCache<String, String> cache = newRemovalLogCache(log); 309 cache.put("a", "A"); 310 cache.put("b", "B"); 311 cache.put("c", "C"); 312 cache.evictAll(); 313 assertEquals(0, cache.size()); 314 assertEquals(Arrays.asList("a=A", "b=B", "c=C"), log); 315 } 316 317 public void testEvictAllEvictsSizeZeroElements() { 318 LruCache<String, String> cache = new LruCache<String, String>(10) { 319 @Override protected int sizeOf(String key, String value) { 320 return 0; 321 } 322 }; 323 324 cache.put("a", "A"); 325 cache.put("b", "B"); 326 cache.evictAll(); 327 assertSnapshot(cache); 328 } 329 330 public void testRemoveWithCustomSizes() { 331 LruCache<String, String> cache = new LruCache<String, String>(10) { 332 @Override protected int sizeOf(String key, String value) { 333 return value.length(); 334 } 335 }; 336 cache.put("a", "123456"); 337 cache.put("b", "1234"); 338 cache.remove("a"); 339 assertEquals(4, cache.size()); 340 } 341 342 public void testRemoveAbsentElement() { 343 LruCache<String, String> cache = new LruCache<String, String>(10); 344 cache.put("a", "A"); 345 cache.put("b", "B"); 346 assertEquals(null, cache.remove("c")); 347 assertEquals(2, cache.size()); 348 } 349 350 public void testRemoveNullThrows() { 351 LruCache<String, String> cache = new LruCache<String, String>(10); 352 try { 353 cache.remove(null); 354 fail(); 355 } catch (NullPointerException expected) { 356 } 357 } 358 359 public void testRemoveCallsEntryRemoved() { 360 List<String> log = new ArrayList<String>(); 361 LruCache<String, String> cache = newRemovalLogCache(log); 362 cache.put("a", "A"); 363 cache.remove("a"); 364 assertEquals(Arrays.asList("a=A>null"), log); 365 } 366 367 public void testPutCallsEntryRemoved() { 368 List<String> log = new ArrayList<String>(); 369 LruCache<String, String> cache = newRemovalLogCache(log); 370 cache.put("a", "A"); 371 cache.put("a", "A2"); 372 assertEquals(Arrays.asList("a=A>A2"), log); 373 } 374 375 public void testEntryRemovedIsCalledWithoutSynchronization() { 376 LruCache<String, String> cache = new LruCache<String, String>(3) { 377 @Override protected void entryRemoved( 378 boolean evicted, String key, String oldValue, String newValue) { 379 assertFalse(Thread.holdsLock(this)); 380 } 381 }; 382 383 cache.put("a", "A"); 384 cache.put("a", "A2"); // replaced 385 cache.put("b", "B"); 386 cache.put("c", "C"); 387 cache.put("d", "D"); // single eviction 388 cache.remove("a"); // removed 389 cache.evictAll(); // multiple eviction 390 } 391 392 public void testCreateIsCalledWithoutSynchronization() { 393 LruCache<String, String> cache = new LruCache<String, String>(3) { 394 @Override protected String create(String key) { 395 assertFalse(Thread.holdsLock(this)); 396 return null; 397 } 398 }; 399 400 cache.get("a"); 401 } 402 403 /** 404 * Test what happens when a value is added to the map while create is 405 * working. The map value should be returned by get(), and the created value 406 * should be released with entryRemoved(). 407 */ 408 public void testCreateWithConcurrentPut() { 409 final List<String> log = new ArrayList<String>(); 410 LruCache<String, String> cache = new LruCache<String, String>(3) { 411 @Override protected String create(String key) { 412 put(key, "B"); 413 return "A"; 414 } 415 @Override protected void entryRemoved( 416 boolean evicted, String key, String oldValue, String newValue) { 417 log.add(key + "=" + oldValue + ">" + newValue); 418 } 419 }; 420 421 assertEquals("B", cache.get("a")); 422 assertEquals(Arrays.asList("a=A>B"), log); 423 } 424 425 /** 426 * Test what happens when two creates happen concurrently. The result from 427 * the first create to return is returned by both gets. The other created 428 * values should be released with entryRemove(). 429 */ 430 public void testCreateWithConcurrentCreate() { 431 final List<String> log = new ArrayList<String>(); 432 LruCache<String, Integer> cache = new LruCache<String, Integer>(3) { 433 int callCount = 0; 434 @Override protected Integer create(String key) { 435 if (callCount++ == 0) { 436 assertEquals(2, get(key).intValue()); 437 return 1; 438 } else { 439 return 2; 440 } 441 } 442 @Override protected void entryRemoved( 443 boolean evicted, String key, Integer oldValue, Integer newValue) { 444 log.add(key + "=" + oldValue + ">" + newValue); 445 } 446 }; 447 448 assertEquals(2, cache.get("a").intValue()); 449 assertEquals(Arrays.asList("a=1>2"), log); 450 } 451 452 private LruCache<String, String> newCreatingCache() { 453 return new LruCache<String, String>(3) { 454 @Override protected String create(String key) { 455 return (key.length() > 1) ? ("created-" + key) : null; 456 } 457 }; 458 } 459 460 private LruCache<String, String> newRemovalLogCache(final List<String> log) { 461 return new LruCache<String, String>(3) { 462 @Override protected void entryRemoved( 463 boolean evicted, String key, String oldValue, String newValue) { 464 String message = evicted 465 ? (key + "=" + oldValue) 466 : (key + "=" + oldValue + ">" + newValue); 467 log.add(message); 468 } 469 }; 470 } 471 472 private void assertHit(LruCache<String, String> cache, String key, String value) { 473 assertEquals(value, cache.get(key)); 474 expectedHitCount++; 475 assertStatistics(cache); 476 } 477 478 private void assertMiss(LruCache<String, String> cache, String key) { 479 assertEquals(null, cache.get(key)); 480 expectedMissCount++; 481 assertStatistics(cache); 482 } 483 484 private void assertCreated(LruCache<String, String> cache, String key, String value) { 485 assertEquals(value, cache.get(key)); 486 expectedMissCount++; 487 expectedCreateCount++; 488 assertStatistics(cache); 489 } 490 491 private void assertStatistics(LruCache<?, ?> cache) { 492 assertEquals("create count", expectedCreateCount, cache.createCount()); 493 assertEquals("put count", expectedPutCount, cache.putCount()); 494 assertEquals("hit count", expectedHitCount, cache.hitCount()); 495 assertEquals("miss count", expectedMissCount, cache.missCount()); 496 assertEquals("eviction count", expectedEvictionCount, cache.evictionCount()); 497 } 498 499 private <T> void assertSnapshot(LruCache<T, T> cache, T... keysAndValues) { 500 List<T> actualKeysAndValues = new ArrayList<T>(); 501 for (Map.Entry<T, T> entry : cache.snapshot().entrySet()) { 502 actualKeysAndValues.add(entry.getKey()); 503 actualKeysAndValues.add(entry.getValue()); 504 } 505 506 // assert using lists because order is important for LRUs 507 assertEquals(Arrays.asList(keysAndValues), actualKeysAndValues); 508 } 509} 510