diff options
| -rw-r--r-- | api/current.xml | 191 | ||||
| -rw-r--r-- | core/java/android/util/LruCache.java | 249 | ||||
| -rw-r--r-- | core/tests/coretests/src/android/util/LruCacheTest.java | 385 |
3 files changed, 824 insertions, 1 deletions
diff --git a/api/current.xml b/api/current.xml index 15463de78f3d..bd86302f9014 100644 --- a/api/current.xml +++ b/api/current.xml @@ -204632,6 +204632,195 @@ </parameter> </method> </class> +<class name="LruCache" + extends="java.lang.Object" + abstract="false" + static="false" + final="false" + deprecated="not deprecated" + visibility="public" +> +<constructor name="LruCache" + type="android.util.LruCache" + static="false" + final="false" + deprecated="not deprecated" + visibility="public" +> +<parameter name="maxSize" type="int"> +</parameter> +</constructor> +<method name="create" + return="V" + abstract="false" + native="false" + synchronized="false" + static="false" + final="false" + deprecated="not deprecated" + visibility="protected" +> +<parameter name="key" type="K"> +</parameter> +</method> +<method name="createCount" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="entryEvicted" + return="void" + abstract="false" + native="false" + synchronized="false" + static="false" + final="false" + deprecated="not deprecated" + visibility="protected" +> +<parameter name="key" type="K"> +</parameter> +<parameter name="value" type="V"> +</parameter> +</method> +<method name="evictAll" + return="void" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="evictionCount" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="get" + return="V" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +<parameter name="key" type="K"> +</parameter> +</method> +<method name="hitCount" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="missCount" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="put" + return="V" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +<parameter name="key" type="K"> +</parameter> +<parameter name="value" type="V"> +</parameter> +</method> +<method name="putCount" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="size" + return="int" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="sizeOf" + return="int" + abstract="false" + native="false" + synchronized="false" + static="false" + final="false" + deprecated="not deprecated" + visibility="protected" +> +<parameter name="key" type="K"> +</parameter> +<parameter name="value" type="V"> +</parameter> +</method> +<method name="snapshot" + return="java.util.Map<K, V>" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +<method name="toString" + return="java.lang.String" + abstract="false" + native="false" + synchronized="true" + static="false" + final="true" + deprecated="not deprecated" + visibility="public" +> +</method> +</class> <class name="MalformedJsonException" extends="java.io.IOException" abstract="false" @@ -263805,7 +263994,7 @@ deprecated="not deprecated" visibility="public" > -<parameter name="t" type="T"> +<parameter name="arg0" type="T"> </parameter> </method> </interface> diff --git a/core/java/android/util/LruCache.java b/core/java/android/util/LruCache.java new file mode 100644 index 000000000000..92912997dbb4 --- /dev/null +++ b/core/java/android/util/LruCache.java @@ -0,0 +1,249 @@ +/* + * 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.LinkedHashMap; +import java.util.Map; + +/** + * A cache that holds strong references to a limited number of values. Each time + * a value is accessed, it is moved to the head of a queue. When a value is + * added to a full cache, the value at the end of that queue is evicted and may + * become eligible for garbage collection. + * + * <p>If your cached values hold resources that need to be explicitly released, + * override {@link #entryEvicted}. This method is only invoked when values are + * evicted. Values replaced by calls to {@link #put} must be released manually. + * + * <p>If a cache miss should be computed on demand for the corresponding keys, + * override {@link #create}. This simplifies the calling code, allowing it to + * assume a value will always be returned, even when there's a cache miss. + * + * <p>By default, the cache size is measured in the number of entries. Override + * {@link #sizeOf} to size the cache in different units. For, this cache is + * limited to 4MiB of bitmaps: + * <pre> {@code + * int cacheSize = 4 * 1024 * 1024; // 4MiB + * LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { + * @Override protected int sizeOf(String key, Bitmap value) { + * return value.getByteCount(); + * } + * }}</pre> + */ +public class LruCache<K, V> { + private final LinkedHashMap<K, V> map; + + /** Size of this cache in units. Not necessarily the number of elements. */ + private int size; + private final int maxSize; + + private int putCount; + private int createCount; + private int evictionCount; + private int hitCount; + private int missCount; + + /** + * @param maxSize for caches that do not override {@link #sizeOf}, this is + * the maximum number of entries in the cache. For all other caches, + * this is the maximum sum of the sizes of the entries in this cache. + */ + public LruCache(int maxSize) { + if (maxSize <= 0) { + throw new IllegalArgumentException("maxSize <= 0"); + } + this.maxSize = maxSize; + this.map = new LinkedHashMap<K, V>(0, 0.75f, true); + } + + /** + * Returns the value for {@code key} if it exists in the cache or can be + * created by {@code #create}. If a value was returned, it is moved to the + * head of the queue. This returns null if a value is not cached and cannot + * be created. + */ + public synchronized final V get(K key) { + if (key == null) { + throw new NullPointerException(); + } + + V result = map.get(key); + if (result != null) { + hitCount++; + return result; + } + + missCount++; + + // TODO: release the lock while calling this potentially slow user code + result = create(key); + + if (result != null) { + createCount++; + size += safeSizeOf(key, result); + map.put(key, result); + trimToSize(maxSize); + } + return result; + } + + /** + * Caches {@code value} for {@code key}. The value is moved to the head of + * the queue. + * + * @return the previous value mapped by {@code key}. Although that entry is + * no longer cached, it has not been passed to {@link #entryEvicted}. + */ + public synchronized final V put(K key, V value) { + if (key == null || value == null) { + throw new NullPointerException(); + } + + putCount++; + size += safeSizeOf(key, value); + V previous = map.put(key, value); + if (previous != null) { + size -= safeSizeOf(key, previous); + } + trimToSize(maxSize); + return previous; + } + + private void trimToSize(int maxSize) { + while (size > maxSize) { + Map.Entry<K, V> toEvict = map.eldest(); + if (toEvict == null) { + break; // map is empty; if size is not 0 then throw an error below + } + + K key = toEvict.getKey(); + V value = toEvict.getValue(); + map.remove(key); + size -= safeSizeOf(key, value); + evictionCount++; + + // TODO: release the lock while calling this potentially slow user code + entryEvicted(key, value); + } + + if (size < 0 || (map.isEmpty() && size != 0)) { + throw new IllegalStateException(getClass().getName() + + ".sizeOf() is reporting inconsistent results!"); + } + } + + /** + * Called for entries that have reached the tail of the least recently used + * queue and are be removed. The default implementation does nothing. + */ + protected void entryEvicted(K key, V value) {} + + /** + * Called after a cache miss to compute a value for the corresponding key. + * Returns the computed value or null if no value can be computed. The + * default implementation returns null. + */ + protected V create(K key) { + return null; + } + + private int safeSizeOf(K key, V value) { + int result = sizeOf(key, value); + if (result < 0) { + throw new IllegalStateException("Negative size: " + key + "=" + value); + } + return result; + } + + /** + * Returns the size of the entry for {@code key} and {@code value} in + * user-defined units. The default implementation returns 1 so that size + * is the number of entries and max size is the maximum number of entries. + * + * <p>An entry's size must not change while it is in the cache. + */ + protected int sizeOf(K key, V value) { + return 1; + } + + /** + * Clear the cache, calling {@link #entryEvicted} on each removed entry. + */ + public synchronized final void evictAll() { + trimToSize(-1); // -1 will evict 0-sized elements + } + + /** + * For caches that do not override {@link #sizeOf}, this is the number of + * entries in the cache. For all other caches, this is the sum of the sizes + * of the entries in this cache. + */ + public synchronized final int size() { + return size; + } + + /** + * Returns the number of times {@link #get} returned a value. + */ + public synchronized final int hitCount() { + return hitCount; + } + + /** + * Returns the number of times {@link #get} returned null or required a new + * value to be created. + */ + public synchronized final int missCount() { + return missCount; + } + + /** + * Returns the number of times {@link #create(Object)} returned a value. + */ + public synchronized final int createCount() { + return createCount; + } + + /** + * Returns the number of times {@link #put} was called. + */ + public synchronized final int putCount() { + return putCount; + } + + /** + * Returns the number of values that have been evicted. + */ + public synchronized final int evictionCount() { + return evictionCount; + } + + /** + * Returns a copy of the current contents of the cache, ordered from least + * recently accessed to most recently accessed. + */ + public synchronized final Map<K, V> snapshot() { + return new LinkedHashMap<K, V>(map); + } + + @Override public synchronized final String toString() { + int accesses = hitCount + missCount; + int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; + return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", + maxSize, hitCount, missCount, hitPercent); + } +} diff --git a/core/tests/coretests/src/android/util/LruCacheTest.java b/core/tests/coretests/src/android/util/LruCacheTest.java new file mode 100644 index 000000000000..506315d4872d --- /dev/null +++ b/core/tests/coretests/src/android/util/LruCacheTest.java @@ -0,0 +1,385 @@ +/* + * 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.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> expectedEvictionLog = new ArrayList<String>(); + final List<String> evictionLog = new ArrayList<String>(); + LruCache<String, String> cache = new LruCache<String, String>(3) { + @Override protected void entryEvicted(String key, String value) { + evictionLog.add(key + "=" + value); + } + }; + + cache.put("a", "A"); + cache.put("b", "B"); + cache.put("c", "C"); + assertEquals(expectedEvictionLog, evictionLog); + + cache.put("d", "D"); + expectedEvictionLog.add("a=A"); + assertEquals(expectedEvictionLog, evictionLog); + } + + /** + * 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 testPutDoesNotCauseEviction() { + final List<String> evictionLog = new ArrayList<String>(); + List<String> expectedEvictionLog = new ArrayList<String>(); + LruCache<String, String> cache = new LruCache<String, String>(3) { + @Override protected void entryEvicted(String key, String value) { + evictionLog.add(key + "=" + value); + } + }; + + cache.put("a", "A"); + cache.put("b", "B"); + cache.put("c", "C"); + cache.put("b", "B2"); + assertEquals(expectedEvictionLog, evictionLog); + 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() { + final List<String> evictionLog = new ArrayList<String>(); + LruCache<String, String> cache = new LruCache<String, String>(10) { + @Override protected void entryEvicted(String key, String value) { + evictionLog.add(key + "=" + value); + } + }; + + 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"), evictionLog); + } + + 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); + } + + 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 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); + } +} |