summaryrefslogtreecommitdiffstats
path: root/luni/src
diff options
context:
space:
mode:
authorJesse Wilson <jessewilson@google.com>2011-02-03 15:10:55 -0800
committerAndroid (Google) Code Review <android-gerrit@google.com>2011-02-03 15:10:55 -0800
commitadf31bd1326e32ba299fddc531672a4dd6c73448 (patch)
treea7a3b5ced63a682ede21f034f7bb7fe250b66fb8 /luni/src
parent4155a2498a57fb09e92815f8993a70c216ddc5ec (diff)
parentb3f2b1082275ed9f95153a077a45bafde6c2a55c (diff)
downloadlibcore-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.java9
-rw-r--r--luni/src/main/java/libcore/base/LruCache.java99
-rw-r--r--luni/src/test/java/libcore/base/LruCacheTest.java106
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) {