diff options
author | Jesse Wilson <jessewilson@google.com> | 2011-02-03 15:10:55 -0800 |
---|---|---|
committer | Android (Google) Code Review <android-gerrit@google.com> | 2011-02-03 15:10:55 -0800 |
commit | adf31bd1326e32ba299fddc531672a4dd6c73448 (patch) | |
tree | a7a3b5ced63a682ede21f034f7bb7fe250b66fb8 /luni/src | |
parent | 4155a2498a57fb09e92815f8993a70c216ddc5ec (diff) | |
parent | b3f2b1082275ed9f95153a077a45bafde6c2a55c (diff) | |
download | libcore-adf31bd1326e32ba299fddc531672a4dd6c73448.zip libcore-adf31bd1326e32ba299fddc531672a4dd6c73448.tar.gz libcore-adf31bd1326e32ba299fddc531672a4dd6c73448.tar.bz2 |
Merge "Permit cache elements to have non-symmetric sizes."
Diffstat (limited to 'luni/src')
-rw-r--r-- | luni/src/main/java/java/util/LinkedHashMap.java | 9 | ||||
-rw-r--r-- | luni/src/main/java/libcore/base/LruCache.java | 99 | ||||
-rw-r--r-- | luni/src/test/java/libcore/base/LruCacheTest.java | 106 |
3 files changed, 194 insertions, 20 deletions
diff --git a/luni/src/main/java/java/util/LinkedHashMap.java b/luni/src/main/java/java/util/LinkedHashMap.java index 47d532f..5db8eb6 100644 --- a/luni/src/main/java/java/util/LinkedHashMap.java +++ b/luni/src/main/java/java/util/LinkedHashMap.java @@ -165,6 +165,15 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> { } /** + * Returns the eldest entry in the map, or {@code null} if the map is empty. + * @hide + */ + public Entry<K, V> eldest() { + LinkedEntry<K, V> eldest = header.nxt; + return eldest != header ? eldest : null; + } + + /** * Evicts eldest entry if instructed, creates a new entry and links it in * as head of linked list. This method should call constructorNewEntry * (instead of duplicating code) if the performance of your VM permits. diff --git a/luni/src/main/java/libcore/base/LruCache.java b/luni/src/main/java/libcore/base/LruCache.java index bcdb070..24a224e 100644 --- a/luni/src/main/java/libcore/base/LruCache.java +++ b/luni/src/main/java/libcore/base/LruCache.java @@ -32,9 +32,23 @@ import java.util.Map; * <p>If cache values 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 Map<K, V> map; + 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; @@ -43,25 +57,17 @@ public class LruCache<K, V> { private int hitCount; private int missCount; - public LruCache(final int maxSize) { + /** + * @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) { - @Override protected boolean removeEldestEntry(Entry<K, V> eldest) { - // LinkedHashMap evicts after put, so size is always off by one - if (size() != maxSize + 1) { - return false; - } - - evictionCount++; - - // TODO: release the lock while calling this potentially slow user code - entryEvicted(eldest.getKey(), eldest.getValue()); - return true; - } - }; + this.map = new LinkedHashMap<K, V>(0, 0.75f, true); } /** @@ -88,7 +94,9 @@ public class LruCache<K, V> { if (result != null) { createCount++; + size += safeSizeOf(key, result); map.put(key, result); + trimToSize(); } return result; } @@ -106,7 +114,36 @@ public class LruCache<K, V> { } putCount++; - return map.put(key, value); + size += safeSizeOf(key, value); + V previous = map.put(key, value); + if (previous != null) { + size -= safeSizeOf(key, previous); + } + trimToSize(); + return previous; + } + + private void trimToSize() { + while (size > maxSize) { + Map.Entry<K, V> toEvict = map.eldest(); + if (toEvict == null) { + break; // map is empty so size should be 0! 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!"); + } } /** @@ -124,6 +161,34 @@ public class LruCache<K, V> { 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; + } + + /** + * 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. */ diff --git a/luni/src/test/java/libcore/base/LruCacheTest.java b/luni/src/test/java/libcore/base/LruCacheTest.java index b66d75a..c94c1ce 100644 --- a/luni/src/test/java/libcore/base/LruCacheTest.java +++ b/luni/src/test/java/libcore/base/LruCacheTest.java @@ -23,7 +23,6 @@ import java.util.Map; import junit.framework.TestCase; public final class LruCacheTest extends TestCase { - private int expectedCreateCount; private int expectedPutCount; private int expectedHitCount; @@ -105,14 +104,12 @@ public final class LruCacheTest extends TestCase { 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")); } @@ -208,6 +205,109 @@ public final class LruCacheTest extends TestCase { 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"); + } + private LruCache<String, String> newCreatingCache() { return new LruCache<String, String>(3) { @Override protected String create(String key) { |