| /* |
| * Copyright (C) 2011 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package android.util; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.List; |
| import java.util.Map; |
| import junit.framework.TestCase; |
| |
| public final class LruCacheTest extends TestCase { |
| private int expectedCreateCount; |
| private int expectedPutCount; |
| private int expectedHitCount; |
| private int expectedMissCount; |
| private int expectedEvictionCount; |
| |
| public void testStatistics() { |
| LruCache<String, String> cache = new LruCache<String, String>(3); |
| assertStatistics(cache); |
| |
| assertEquals(null, cache.put("a", "A")); |
| expectedPutCount++; |
| assertStatistics(cache); |
| assertHit(cache, "a", "A"); |
| assertSnapshot(cache, "a", "A"); |
| |
| assertEquals(null, cache.put("b", "B")); |
| expectedPutCount++; |
| assertStatistics(cache); |
| assertHit(cache, "a", "A"); |
| assertHit(cache, "b", "B"); |
| assertSnapshot(cache, "a", "A", "b", "B"); |
| |
| assertEquals(null, cache.put("c", "C")); |
| expectedPutCount++; |
| assertStatistics(cache); |
| assertHit(cache, "a", "A"); |
| assertHit(cache, "b", "B"); |
| assertHit(cache, "c", "C"); |
| assertSnapshot(cache, "a", "A", "b", "B", "c", "C"); |
| |
| assertEquals(null, cache.put("d", "D")); |
| expectedPutCount++; |
| expectedEvictionCount++; // a should have been evicted |
| assertStatistics(cache); |
| assertMiss(cache, "a"); |
| assertHit(cache, "b", "B"); |
| assertHit(cache, "c", "C"); |
| assertHit(cache, "d", "D"); |
| assertHit(cache, "b", "B"); |
| assertHit(cache, "c", "C"); |
| assertSnapshot(cache, "d", "D", "b", "B", "c", "C"); |
| |
| assertEquals(null, cache.put("e", "E")); |
| expectedPutCount++; |
| expectedEvictionCount++; // d should have been evicted |
| assertStatistics(cache); |
| assertMiss(cache, "d"); |
| assertMiss(cache, "a"); |
| assertHit(cache, "e", "E"); |
| assertHit(cache, "b", "B"); |
| assertHit(cache, "c", "C"); |
| assertSnapshot(cache, "e", "E", "b", "B", "c", "C"); |
| } |
| |
| public void testStatisticsWithCreate() { |
| LruCache<String, String> cache = newCreatingCache(); |
| assertStatistics(cache); |
| |
| assertCreated(cache, "aa", "created-aa"); |
| assertHit(cache, "aa", "created-aa"); |
| assertSnapshot(cache, "aa", "created-aa"); |
| |
| assertCreated(cache, "bb", "created-bb"); |
| assertMiss(cache, "c"); |
| assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb"); |
| |
| assertCreated(cache, "cc", "created-cc"); |
| assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb", "cc", "created-cc"); |
| |
| expectedEvictionCount++; // aa will be evicted |
| assertCreated(cache, "dd", "created-dd"); |
| assertSnapshot(cache, "bb", "created-bb", "cc", "created-cc", "dd", "created-dd"); |
| |
| expectedEvictionCount++; // bb will be evicted |
| assertCreated(cache, "aa", "created-aa"); |
| assertSnapshot(cache, "cc", "created-cc", "dd", "created-dd", "aa", "created-aa"); |
| } |
| |
| public void testCreateOnCacheMiss() { |
| LruCache<String, String> cache = newCreatingCache(); |
| String created = cache.get("aa"); |
| assertEquals("created-aa", created); |
| } |
| |
| public void testNoCreateOnCacheHit() { |
| LruCache<String, String> cache = newCreatingCache(); |
| cache.put("aa", "put-aa"); |
| assertEquals("put-aa", cache.get("aa")); |
| } |
| |
| public void testConstructorDoesNotAllowZeroCacheSize() { |
| try { |
| new LruCache<String, String>(0); |
| fail(); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| public void testCannotPutNullKey() { |
| LruCache<String, String> cache = new LruCache<String, String>(3); |
| try { |
| cache.put(null, "A"); |
| fail(); |
| } catch (NullPointerException expected) { |
| } |
| } |
| |
| public void testCannotPutNullValue() { |
| LruCache<String, String> cache = new LruCache<String, String>(3); |
| try { |
| cache.put("a", null); |
| fail(); |
| } catch (NullPointerException expected) { |
| } |
| } |
| |
| public void testToString() { |
| LruCache<String, String> cache = new LruCache<String, String>(3); |
| assertEquals("LruCache[maxSize=3,hits=0,misses=0,hitRate=0%]", cache.toString()); |
| |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| cache.put("c", "C"); |
| cache.put("d", "D"); |
| |
| cache.get("a"); // miss |
| cache.get("b"); // hit |
| cache.get("c"); // hit |
| cache.get("d"); // hit |
| cache.get("e"); // miss |
| |
| assertEquals("LruCache[maxSize=3,hits=3,misses=2,hitRate=60%]", cache.toString()); |
| } |
| |
| public void testEvictionWithSingletonCache() { |
| LruCache<String, String> cache = new LruCache<String, String>(1); |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| assertSnapshot(cache, "b", "B"); |
| } |
| |
| public void testEntryEvictedWhenFull() { |
| List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = newRemovalLogCache(log); |
| |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| cache.put("c", "C"); |
| assertEquals(Collections.<String>emptyList(), log); |
| |
| cache.put("d", "D"); |
| assertEquals(Arrays.asList("a=A"), log); |
| } |
| |
| /** |
| * Replacing the value for a key doesn't cause an eviction but it does bring |
| * the replaced entry to the front of the queue. |
| */ |
| public void testPutCauseEviction() { |
| List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = newRemovalLogCache(log); |
| |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| cache.put("c", "C"); |
| cache.put("b", "B2"); |
| assertEquals(Arrays.asList("b=B>B2"), log); |
| assertSnapshot(cache, "a", "A", "c", "C", "b", "B2"); |
| } |
| |
| public void testCustomSizesImpactsSize() { |
| LruCache<String, String> cache = new LruCache<String, String>(10) { |
| @Override protected int sizeOf(String key, String value) { |
| return key.length() + value.length(); |
| } |
| }; |
| |
| assertEquals(0, cache.size()); |
| cache.put("a", "AA"); |
| assertEquals(3, cache.size()); |
| cache.put("b", "BBBB"); |
| assertEquals(8, cache.size()); |
| cache.put("a", ""); |
| assertEquals(6, cache.size()); |
| } |
| |
| public void testEvictionWithCustomSizes() { |
| LruCache<String, String> cache = new LruCache<String, String>(4) { |
| @Override protected int sizeOf(String key, String value) { |
| return value.length(); |
| } |
| }; |
| |
| cache.put("a", "AAAA"); |
| assertSnapshot(cache, "a", "AAAA"); |
| cache.put("b", "BBBB"); // should evict a |
| assertSnapshot(cache, "b", "BBBB"); |
| cache.put("c", "CC"); // should evict b |
| assertSnapshot(cache, "c", "CC"); |
| cache.put("d", "DD"); |
| assertSnapshot(cache, "c", "CC", "d", "DD"); |
| cache.put("e", "E"); // should evict c |
| assertSnapshot(cache, "d", "DD", "e", "E"); |
| cache.put("f", "F"); |
| assertSnapshot(cache, "d", "DD", "e", "E", "f", "F"); |
| cache.put("g", "G"); // should evict d |
| assertSnapshot(cache, "e", "E", "f", "F", "g", "G"); |
| cache.put("h", "H"); |
| assertSnapshot(cache, "e", "E", "f", "F", "g", "G", "h", "H"); |
| cache.put("i", "III"); // should evict e, f, and g |
| assertSnapshot(cache, "h", "H", "i", "III"); |
| cache.put("j", "JJJ"); // should evict h and i |
| assertSnapshot(cache, "j", "JJJ"); |
| } |
| |
| public void testEvictionThrowsWhenSizesAreInconsistent() { |
| LruCache<String, int[]> cache = new LruCache<String, int[]>(4) { |
| @Override protected int sizeOf(String key, int[] value) { |
| return value[0]; |
| } |
| }; |
| |
| int[] a = { 4 }; |
| cache.put("a", a); |
| |
| // get the cache size out of sync |
| a[0] = 1; |
| assertEquals(4, cache.size()); |
| |
| // evict something |
| try { |
| cache.put("b", new int[] { 2 }); |
| fail(); |
| } catch (IllegalStateException expected) { |
| } |
| } |
| |
| public void testEvictionThrowsWhenSizesAreNegative() { |
| LruCache<String, String> cache = new LruCache<String, String>(4) { |
| @Override protected int sizeOf(String key, String value) { |
| return -1; |
| } |
| }; |
| |
| try { |
| cache.put("a", "A"); |
| fail(); |
| } catch (IllegalStateException expected) { |
| } |
| } |
| |
| /** |
| * Naive caches evict at most one element at a time. This is problematic |
| * because evicting a small element may be insufficient to make room for a |
| * large element. |
| */ |
| public void testDifferentElementSizes() { |
| LruCache<String, String> cache = new LruCache<String, String>(10) { |
| @Override protected int sizeOf(String key, String value) { |
| return value.length(); |
| } |
| }; |
| |
| cache.put("a", "1"); |
| cache.put("b", "12345678"); |
| cache.put("c", "1"); |
| assertSnapshot(cache, "a", "1", "b", "12345678", "c", "1"); |
| cache.put("d", "12345678"); // should evict a and b |
| assertSnapshot(cache, "c", "1", "d", "12345678"); |
| cache.put("e", "12345678"); // should evict c and d |
| assertSnapshot(cache, "e", "12345678"); |
| } |
| |
| public void testEvictAll() { |
| List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = newRemovalLogCache(log); |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| cache.put("c", "C"); |
| cache.evictAll(); |
| assertEquals(0, cache.size()); |
| assertEquals(Arrays.asList("a=A", "b=B", "c=C"), log); |
| } |
| |
| public void testEvictAllEvictsSizeZeroElements() { |
| LruCache<String, String> cache = new LruCache<String, String>(10) { |
| @Override protected int sizeOf(String key, String value) { |
| return 0; |
| } |
| }; |
| |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| cache.evictAll(); |
| assertSnapshot(cache); |
| } |
| |
| public void testRemoveWithCustomSizes() { |
| LruCache<String, String> cache = new LruCache<String, String>(10) { |
| @Override protected int sizeOf(String key, String value) { |
| return value.length(); |
| } |
| }; |
| cache.put("a", "123456"); |
| cache.put("b", "1234"); |
| cache.remove("a"); |
| assertEquals(4, cache.size()); |
| } |
| |
| public void testRemoveAbsentElement() { |
| LruCache<String, String> cache = new LruCache<String, String>(10); |
| cache.put("a", "A"); |
| cache.put("b", "B"); |
| assertEquals(null, cache.remove("c")); |
| assertEquals(2, cache.size()); |
| } |
| |
| public void testRemoveNullThrows() { |
| LruCache<String, String> cache = new LruCache<String, String>(10); |
| try { |
| cache.remove(null); |
| fail(); |
| } catch (NullPointerException expected) { |
| } |
| } |
| |
| public void testRemoveCallsEntryRemoved() { |
| List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = newRemovalLogCache(log); |
| cache.put("a", "A"); |
| cache.remove("a"); |
| assertEquals(Arrays.asList("a=A>null"), log); |
| } |
| |
| public void testPutCallsEntryRemoved() { |
| List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = newRemovalLogCache(log); |
| cache.put("a", "A"); |
| cache.put("a", "A2"); |
| assertEquals(Arrays.asList("a=A>A2"), log); |
| } |
| |
| public void testEntryRemovedIsCalledWithoutSynchronization() { |
| LruCache<String, String> cache = new LruCache<String, String>(3) { |
| @Override protected void entryRemoved( |
| boolean evicted, String key, String oldValue, String newValue) { |
| assertFalse(Thread.holdsLock(this)); |
| } |
| }; |
| |
| cache.put("a", "A"); |
| cache.put("a", "A2"); // replaced |
| cache.put("b", "B"); |
| cache.put("c", "C"); |
| cache.put("d", "D"); // single eviction |
| cache.remove("a"); // removed |
| cache.evictAll(); // multiple eviction |
| } |
| |
| public void testCreateIsCalledWithoutSynchronization() { |
| LruCache<String, String> cache = new LruCache<String, String>(3) { |
| @Override protected String create(String key) { |
| assertFalse(Thread.holdsLock(this)); |
| return null; |
| } |
| }; |
| |
| cache.get("a"); |
| } |
| |
| /** |
| * Test what happens when a value is added to the map while create is |
| * working. The map value should be returned by get(), and the created value |
| * should be released with entryRemoved(). |
| */ |
| public void testCreateWithConcurrentPut() { |
| final List<String> log = new ArrayList<String>(); |
| LruCache<String, String> cache = new LruCache<String, String>(3) { |
| @Override protected String create(String key) { |
| put(key, "B"); |
| return "A"; |
| } |
| @Override protected void entryRemoved( |
| boolean evicted, String key, String oldValue, String newValue) { |
| log.add(key + "=" + oldValue + ">" + newValue); |
| } |
| }; |
| |
| assertEquals("B", cache.get("a")); |
| assertEquals(Arrays.asList("a=A>B"), log); |
| } |
| |
| /** |
| * Test what happens when two creates happen concurrently. The result from |
| * the first create to return is returned by both gets. The other created |
| * values should be released with entryRemove(). |
| */ |
| public void testCreateWithConcurrentCreate() { |
| final List<String> log = new ArrayList<String>(); |
| LruCache<String, Integer> cache = new LruCache<String, Integer>(3) { |
| int callCount = 0; |
| @Override protected Integer create(String key) { |
| if (callCount++ == 0) { |
| assertEquals(2, get(key).intValue()); |
| return 1; |
| } else { |
| return 2; |
| } |
| } |
| @Override protected void entryRemoved( |
| boolean evicted, String key, Integer oldValue, Integer newValue) { |
| log.add(key + "=" + oldValue + ">" + newValue); |
| } |
| }; |
| |
| assertEquals(2, cache.get("a").intValue()); |
| assertEquals(Arrays.asList("a=1>2"), log); |
| } |
| |
| private LruCache<String, String> newCreatingCache() { |
| return new LruCache<String, String>(3) { |
| @Override protected String create(String key) { |
| return (key.length() > 1) ? ("created-" + key) : null; |
| } |
| }; |
| } |
| |
| private LruCache<String, String> newRemovalLogCache(final List<String> log) { |
| return new LruCache<String, String>(3) { |
| @Override protected void entryRemoved( |
| boolean evicted, String key, String oldValue, String newValue) { |
| String message = evicted |
| ? (key + "=" + oldValue) |
| : (key + "=" + oldValue + ">" + newValue); |
| log.add(message); |
| } |
| }; |
| } |
| |
| private void assertHit(LruCache<String, String> cache, String key, String value) { |
| assertEquals(value, cache.get(key)); |
| expectedHitCount++; |
| assertStatistics(cache); |
| } |
| |
| private void assertMiss(LruCache<String, String> cache, String key) { |
| assertEquals(null, cache.get(key)); |
| expectedMissCount++; |
| assertStatistics(cache); |
| } |
| |
| private void assertCreated(LruCache<String, String> cache, String key, String value) { |
| assertEquals(value, cache.get(key)); |
| expectedMissCount++; |
| expectedCreateCount++; |
| assertStatistics(cache); |
| } |
| |
| private void assertStatistics(LruCache<?, ?> cache) { |
| assertEquals("create count", expectedCreateCount, cache.createCount()); |
| assertEquals("put count", expectedPutCount, cache.putCount()); |
| assertEquals("hit count", expectedHitCount, cache.hitCount()); |
| assertEquals("miss count", expectedMissCount, cache.missCount()); |
| assertEquals("eviction count", expectedEvictionCount, cache.evictionCount()); |
| } |
| |
| private <T> void assertSnapshot(LruCache<T, T> cache, T... keysAndValues) { |
| List<T> actualKeysAndValues = new ArrayList<T>(); |
| for (Map.Entry<T, T> entry : cache.snapshot().entrySet()) { |
| actualKeysAndValues.add(entry.getKey()); |
| actualKeysAndValues.add(entry.getValue()); |
| } |
| |
| // assert using lists because order is important for LRUs |
| assertEquals(Arrays.asList(keysAndValues), actualKeysAndValues); |
| } |
| } |