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 17 package android.util; 18 19 import java.util.ArrayList; 20 import java.util.Arrays; 21 import java.util.Collections; 22 import java.util.List; 23 import java.util.Map; 24 import junit.framework.TestCase; 25 26 public 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 testPutCauseEviction() { 187 List<String> log = new ArrayList<String>(); 188 LruCache<String, String> cache = newRemovalLogCache(log); 189 190 cache.put("a", "A"); 191 cache.put("b", "B"); 192 cache.put("c", "C"); 193 cache.put("b", "B2"); 194 assertEquals(Arrays.asList("b=B>B2"), log); 195 assertSnapshot(cache, "a", "A", "c", "C", "b", "B2"); 196 } 197 198 public void testCustomSizesImpactsSize() { 199 LruCache<String, String> cache = new LruCache<String, String>(10) { 200 @Override protected int sizeOf(String key, String value) { 201 return key.length() + value.length(); 202 } 203 }; 204 205 assertEquals(0, cache.size()); 206 cache.put("a", "AA"); 207 assertEquals(3, cache.size()); 208 cache.put("b", "BBBB"); 209 assertEquals(8, cache.size()); 210 cache.put("a", ""); 211 assertEquals(6, cache.size()); 212 } 213 214 public void testEvictionWithCustomSizes() { 215 LruCache<String, String> cache = new LruCache<String, String>(4) { 216 @Override protected int sizeOf(String key, String value) { 217 return value.length(); 218 } 219 }; 220 221 cache.put("a", "AAAA"); 222 assertSnapshot(cache, "a", "AAAA"); 223 cache.put("b", "BBBB"); // should evict a 224 assertSnapshot(cache, "b", "BBBB"); 225 cache.put("c", "CC"); // should evict b 226 assertSnapshot(cache, "c", "CC"); 227 cache.put("d", "DD"); 228 assertSnapshot(cache, "c", "CC", "d", "DD"); 229 cache.put("e", "E"); // should evict c 230 assertSnapshot(cache, "d", "DD", "e", "E"); 231 cache.put("f", "F"); 232 assertSnapshot(cache, "d", "DD", "e", "E", "f", "F"); 233 cache.put("g", "G"); // should evict d 234 assertSnapshot(cache, "e", "E", "f", "F", "g", "G"); 235 cache.put("h", "H"); 236 assertSnapshot(cache, "e", "E", "f", "F", "g", "G", "h", "H"); 237 cache.put("i", "III"); // should evict e, f, and g 238 assertSnapshot(cache, "h", "H", "i", "III"); 239 cache.put("j", "JJJ"); // should evict h and i 240 assertSnapshot(cache, "j", "JJJ"); 241 } 242 243 public void testEvictionThrowsWhenSizesAreInconsistent() { 244 LruCache<String, int[]> cache = new LruCache<String, int[]>(4) { 245 @Override protected int sizeOf(String key, int[] value) { 246 return value[0]; 247 } 248 }; 249 250 int[] a = { 4 }; 251 cache.put("a", a); 252 253 // get the cache size out of sync 254 a[0] = 1; 255 assertEquals(4, cache.size()); 256 257 // evict something 258 try { 259 cache.put("b", new int[] { 2 }); 260 fail(); 261 } catch (IllegalStateException expected) { 262 } 263 } 264 265 public void testEvictionThrowsWhenSizesAreNegative() { 266 LruCache<String, String> cache = new LruCache<String, String>(4) { 267 @Override protected int sizeOf(String key, String value) { 268 return -1; 269 } 270 }; 271 272 try { 273 cache.put("a", "A"); 274 fail(); 275 } catch (IllegalStateException expected) { 276 } 277 } 278 279 /** 280 * Naive caches evict at most one element at a time. This is problematic 281 * because evicting a small element may be insufficient to make room for a 282 * large element. 283 */ 284 public void testDifferentElementSizes() { 285 LruCache<String, String> cache = new LruCache<String, String>(10) { 286 @Override protected int sizeOf(String key, String value) { 287 return value.length(); 288 } 289 }; 290 291 cache.put("a", "1"); 292 cache.put("b", "12345678"); 293 cache.put("c", "1"); 294 assertSnapshot(cache, "a", "1", "b", "12345678", "c", "1"); 295 cache.put("d", "12345678"); // should evict a and b 296 assertSnapshot(cache, "c", "1", "d", "12345678"); 297 cache.put("e", "12345678"); // should evict c and d 298 assertSnapshot(cache, "e", "12345678"); 299 } 300 301 public void testEvictAll() { 302 List<String> log = new ArrayList<String>(); 303 LruCache<String, String> cache = newRemovalLogCache(log); 304 cache.put("a", "A"); 305 cache.put("b", "B"); 306 cache.put("c", "C"); 307 cache.evictAll(); 308 assertEquals(0, cache.size()); 309 assertEquals(Arrays.asList("a=A", "b=B", "c=C"), log); 310 } 311 312 public void testEvictAllEvictsSizeZeroElements() { 313 LruCache<String, String> cache = new LruCache<String, String>(10) { 314 @Override protected int sizeOf(String key, String value) { 315 return 0; 316 } 317 }; 318 319 cache.put("a", "A"); 320 cache.put("b", "B"); 321 cache.evictAll(); 322 assertSnapshot(cache); 323 } 324 325 public void testRemoveWithCustomSizes() { 326 LruCache<String, String> cache = new LruCache<String, String>(10) { 327 @Override protected int sizeOf(String key, String value) { 328 return value.length(); 329 } 330 }; 331 cache.put("a", "123456"); 332 cache.put("b", "1234"); 333 cache.remove("a"); 334 assertEquals(4, cache.size()); 335 } 336 337 public void testRemoveAbsentElement() { 338 LruCache<String, String> cache = new LruCache<String, String>(10); 339 cache.put("a", "A"); 340 cache.put("b", "B"); 341 assertEquals(null, cache.remove("c")); 342 assertEquals(2, cache.size()); 343 } 344 345 public void testRemoveNullThrows() { 346 LruCache<String, String> cache = new LruCache<String, String>(10); 347 try { 348 cache.remove(null); 349 fail(); 350 } catch (NullPointerException expected) { 351 } 352 } 353 354 public void testRemoveCallsEntryRemoved() { 355 List<String> log = new ArrayList<String>(); 356 LruCache<String, String> cache = newRemovalLogCache(log); 357 cache.put("a", "A"); 358 cache.remove("a"); 359 assertEquals(Arrays.asList("a=A>null"), log); 360 } 361 362 public void testPutCallsEntryRemoved() { 363 List<String> log = new ArrayList<String>(); 364 LruCache<String, String> cache = newRemovalLogCache(log); 365 cache.put("a", "A"); 366 cache.put("a", "A2"); 367 assertEquals(Arrays.asList("a=A>A2"), log); 368 } 369 370 public void testEntryRemovedIsCalledWithoutSynchronization() { 371 LruCache<String, String> cache = new LruCache<String, String>(3) { 372 @Override protected void entryRemoved( 373 boolean evicted, String key, String oldValue, String newValue) { 374 assertFalse(Thread.holdsLock(this)); 375 } 376 }; 377 378 cache.put("a", "A"); 379 cache.put("a", "A2"); // replaced 380 cache.put("b", "B"); 381 cache.put("c", "C"); 382 cache.put("d", "D"); // single eviction 383 cache.remove("a"); // removed 384 cache.evictAll(); // multiple eviction 385 } 386 387 public void testCreateIsCalledWithoutSynchronization() { 388 LruCache<String, String> cache = new LruCache<String, String>(3) { 389 @Override protected String create(String key) { 390 assertFalse(Thread.holdsLock(this)); 391 return null; 392 } 393 }; 394 395 cache.get("a"); 396 } 397 398 /** 399 * Test what happens when a value is added to the map while create is 400 * working. The map value should be returned by get(), and the created value 401 * should be released with entryRemoved(). 402 */ 403 public void testCreateWithConcurrentPut() { 404 final List<String> log = new ArrayList<String>(); 405 LruCache<String, String> cache = new LruCache<String, String>(3) { 406 @Override protected String create(String key) { 407 put(key, "B"); 408 return "A"; 409 } 410 @Override protected void entryRemoved( 411 boolean evicted, String key, String oldValue, String newValue) { 412 log.add(key + "=" + oldValue + ">" + newValue); 413 } 414 }; 415 416 assertEquals("B", cache.get("a")); 417 assertEquals(Arrays.asList("a=A>B"), log); 418 } 419 420 /** 421 * Test what happens when two creates happen concurrently. The result from 422 * the first create to return is returned by both gets. The other created 423 * values should be released with entryRemove(). 424 */ 425 public void testCreateWithConcurrentCreate() { 426 final List<String> log = new ArrayList<String>(); 427 LruCache<String, Integer> cache = new LruCache<String, Integer>(3) { 428 int callCount = 0; 429 @Override protected Integer create(String key) { 430 if (callCount++ == 0) { 431 assertEquals(2, get(key).intValue()); 432 return 1; 433 } else { 434 return 2; 435 } 436 } 437 @Override protected void entryRemoved( 438 boolean evicted, String key, Integer oldValue, Integer newValue) { 439 log.add(key + "=" + oldValue + ">" + newValue); 440 } 441 }; 442 443 assertEquals(2, cache.get("a").intValue()); 444 assertEquals(Arrays.asList("a=1>2"), log); 445 } 446 447 private LruCache<String, String> newCreatingCache() { 448 return new LruCache<String, String>(3) { 449 @Override protected String create(String key) { 450 return (key.length() > 1) ? ("created-" + key) : null; 451 } 452 }; 453 } 454 455 private LruCache<String, String> newRemovalLogCache(final List<String> log) { 456 return new LruCache<String, String>(3) { 457 @Override protected void entryRemoved( 458 boolean evicted, String key, String oldValue, String newValue) { 459 String message = evicted 460 ? (key + "=" + oldValue) 461 : (key + "=" + oldValue + ">" + newValue); 462 log.add(message); 463 } 464 }; 465 } 466 467 private void assertHit(LruCache<String, String> cache, String key, String value) { 468 assertEquals(value, cache.get(key)); 469 expectedHitCount++; 470 assertStatistics(cache); 471 } 472 473 private void assertMiss(LruCache<String, String> cache, String key) { 474 assertEquals(null, cache.get(key)); 475 expectedMissCount++; 476 assertStatistics(cache); 477 } 478 479 private void assertCreated(LruCache<String, String> cache, String key, String value) { 480 assertEquals(value, cache.get(key)); 481 expectedMissCount++; 482 expectedCreateCount++; 483 assertStatistics(cache); 484 } 485 486 private void assertStatistics(LruCache<?, ?> cache) { 487 assertEquals("create count", expectedCreateCount, cache.createCount()); 488 assertEquals("put count", expectedPutCount, cache.putCount()); 489 assertEquals("hit count", expectedHitCount, cache.hitCount()); 490 assertEquals("miss count", expectedMissCount, cache.missCount()); 491 assertEquals("eviction count", expectedEvictionCount, cache.evictionCount()); 492 } 493 494 private <T> void assertSnapshot(LruCache<T, T> cache, T... keysAndValues) { 495 List<T> actualKeysAndValues = new ArrayList<T>(); 496 for (Map.Entry<T, T> entry : cache.snapshot().entrySet()) { 497 actualKeysAndValues.add(entry.getKey()); 498 actualKeysAndValues.add(entry.getValue()); 499 } 500 501 // assert using lists because order is important for LRUs 502 assertEquals(Arrays.asList(keysAndValues), actualKeysAndValues); 503 } 504 } 505