LruCache.java revision d96b585f5c40ee0d1232630ac0124d4610341577
1e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson/* 2e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Copyright (C) 2011 The Android Open Source Project 3e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 4e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * you may not use this file except in compliance with the License. 6e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * You may obtain a copy of the License at 7e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 8e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 10e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * See the License for the specific language governing permissions and 14e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * limitations under the License. 15e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 16e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 17e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilsonpackage android.util; 18e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 19e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilsonimport java.util.LinkedHashMap; 20e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilsonimport java.util.Map; 21e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 22e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson/** 23e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * A cache that holds strong references to a limited number of values. Each time 24e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * a value is accessed, it is moved to the head of a queue. When a value is 25e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * added to a full cache, the value at the end of that queue is evicted and may 26e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * become eligible for garbage collection. 27e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 28e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>If your cached values hold resources that need to be explicitly released, 297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * override {@link #entryRemoved}. 30e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 31e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>If a cache miss should be computed on demand for the corresponding keys, 32e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * override {@link #create}. This simplifies the calling code, allowing it to 33e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * assume a value will always be returned, even when there's a cache miss. 34e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 35e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>By default, the cache size is measured in the number of entries. Override 3634895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * {@link #sizeOf} to size the cache in different units. For example, this cache 3734895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * is limited to 4MiB of bitmaps: 38e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <pre> {@code 3934895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * int cacheSize = 4 * 1024 * 1024; // 4MiB 4034895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { 4134895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * protected int sizeOf(String key, Bitmap value) { 4234895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * return value.getByteCount(); 4334895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * } 4434895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * }}</pre> 4534895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * 4634895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * <p>This class is thread-safe. Perform multiple cache operations atomically by 4734895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * synchronizing on the cache: <pre> {@code 4834895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * synchronized (cache) { 4934895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * if (cache.get(key) == null) { 5034895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * cache.put(key, value); 51e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * } 5234895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * }}</pre> 5356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 5456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * <p>This class does not allow null to be used as a key or value. A return 5556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * value of null from {@link #get}, {@link #put} or {@link #remove} is 5656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * unambiguous: the key was not in the cache. 5702db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * 5802db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part 5902db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * of <a href="http://developer.android.com/sdk/compatibility-library.html">Android's 6002db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * Support Package</a> for earlier releases. 61e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 62e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilsonpublic class LruCache<K, V> { 63e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private final LinkedHashMap<K, V> map; 64e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 65e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** Size of this cache in units. Not necessarily the number of elements. */ 66e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int size; 679b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson private int maxSize; 68e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 69e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int putCount; 70e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int createCount; 71e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int evictionCount; 72e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int hitCount; 73e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int missCount; 74e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 75e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 76e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * @param maxSize for caches that do not override {@link #sizeOf}, this is 77e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the maximum number of entries in the cache. For all other caches, 78e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * this is the maximum sum of the sizes of the entries in this cache. 79e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 80e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public LruCache(int maxSize) { 81e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (maxSize <= 0) { 82e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalArgumentException("maxSize <= 0"); 83e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 84e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson this.maxSize = maxSize; 85e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 86e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 87e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 88e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 89e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * Sets the size of the cache. 90e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * @param maxSize The new maximum size. 91e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * 92e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * @hide 93e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown */ 94e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown public void resize(int maxSize) { 95e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown if (maxSize <= 0) { 96e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown throw new IllegalArgumentException("maxSize <= 0"); 97e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 98e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 99e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown synchronized (this) { 100e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown this.maxSize = maxSize; 101e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 102e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown trimToSize(maxSize); 103e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 104e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 105e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown /** 106e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the value for {@code key} if it exists in the cache or can be 107e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * created by {@code #create}. If a value was returned, it is moved to the 108e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * head of the queue. This returns null if a value is not cached and cannot 109e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * be created. 110e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1117db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V get(K key) { 112e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null) { 11356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 114e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 115e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V mapValue; 1177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.get(key); 1197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson hitCount++; 1217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1227db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1237db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson missCount++; 124e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 125e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /* 1277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Attempt to create a value. This may take a long time, and the map 1287db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * may be different when create() returns. If a conflicting value was 1297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * added to the map while create() was working, we leave that value in 1307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * the map and release the created value. 1317db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 132e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V createdValue = create(key); 1347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (createdValue == null) { 1357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return null; 1367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 137e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 139e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson createCount++; 1407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.put(key, createdValue); 1417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1427db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1437db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson // There was a conflict so undo that last put 1447db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.put(key, mapValue); 1457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 1467db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, createdValue); 1477db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1497db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, createdValue, mapValue); 1527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 154e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 1557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return createdValue; 156e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 157e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 158e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 159e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 160e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Caches {@code value} for {@code key}. The value is moved to the head of 161e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the queue. 162e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 163c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 164e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1657db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V put(K key, V value) { 166e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null || value == null) { 16756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null || value == null"); 168e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 169e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1707db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 1717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson putCount++; 1737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, value); 1747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.put(key, value); 1757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 1767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 1777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1797db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 180e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (previous != null) { 1817db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, value); 182e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 1837db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 184e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 185e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return previous; 186e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 187e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1887db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /** 189d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * Remove the eldest entries until the total of remaining entries is at or 190d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * below the requested size. 191d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * 1927db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param maxSize the maximum size of the cache before returning. May be -1 193d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * to evict even 0-sized elements. 1947db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 195d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey public void trimToSize(int maxSize) { 1967db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson while (true) { 1977db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson K key; 1987db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V value; 1997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size < 0 || (map.isEmpty() && size != 0)) { 2017db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson throw new IllegalStateException(getClass().getName() 2027db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson + ".sizeOf() is reporting inconsistent results!"); 2037db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 204e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2057db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size <= maxSize) { 2067db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2077db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 208e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2097db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson Map.Entry<K, V> toEvict = map.eldest(); 2107db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (toEvict == null) { 2117db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2127db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 213e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2147db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson key = toEvict.getKey(); 2157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson value = toEvict.getValue(); 2167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.remove(key); 2177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, value); 2187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson evictionCount++; 2197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 221c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson entryRemoved(true, key, value, null); 222e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 223e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 224e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 225e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 22656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * Removes the entry for {@code key} if it exists. 22756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 228c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 22956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson */ 2307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V remove(K key) { 23156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (key == null) { 23256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 23356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 23456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 2357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 2367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.remove(key); 2387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 2397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 2407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2427db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (previous != null) { 2447db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, null); 24556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 2467db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson return previous; 24856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 24956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 25056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson /** 2517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Called for entries that have been evicted or removed. This method is 2527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * invoked when a value is evicted to make space, removed by a call to 2537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * {@link #remove}, or replaced by a call to {@link #put}. The default 2547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * implementation does nothing. 2557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2587db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param evicted true if the entry is being removed to make space, false 2607db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * if the removal was caused by a {@link #put} or {@link #remove}. 2617db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param newValue the new value for {@code key}, if it exists. If non-null, 2627db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * this removal was caused by a {@link #put}. Otherwise it was caused by 2637db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * an eviction or a {@link #remove}. 264e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2657db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 266e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 267e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 268e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Called after a cache miss to compute a value for the corresponding key. 269e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the computed value or null if no value can be computed. The 270e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * default implementation returns null. 2717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>If a value for {@code key} exists in the cache when this method 2767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * returns, the created value will be released with {@link #entryRemoved} 2777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * and discarded. This can occur when multiple threads request the same key 2787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * at the same time (causing multiple values to be created), or when one 2797db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * thread calls {@link #put} while another is creating a value for the same 2807db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * key. 281e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 282e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected V create(K key) { 283e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return null; 284e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 285e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 286e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int safeSizeOf(K key, V value) { 287e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int result = sizeOf(key, value); 288e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (result < 0) { 289e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalStateException("Negative size: " + key + "=" + value); 290e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 291e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return result; 292e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 293e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 294e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 295e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the size of the entry for {@code key} and {@code value} in 296e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * user-defined units. The default implementation returns 1 so that size 297e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * is the number of entries and max size is the maximum number of entries. 298e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 299e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>An entry's size must not change while it is in the cache. 300e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 301e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected int sizeOf(K key, V value) { 302e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return 1; 303e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 304e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 305e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 306c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * Clear the cache, calling {@link #entryRemoved} on each removed entry. 307e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 3087db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final void evictAll() { 309e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(-1); // -1 will evict 0-sized elements 310e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 311e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 312e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3139b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the number 3149b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * of entries in the cache. For all other caches, this returns the sum of 3159b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * the sizes of the entries in this cache. 316e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 317e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int size() { 318e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return size; 319e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 320e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 321e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3229b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the maximum 3239b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * number of entries in the cache. For all other caches, this returns the 3249b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * maximum sum of the sizes of the entries in this cache. 3259b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson */ 3269b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson public synchronized final int maxSize() { 3279b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson return maxSize; 3289b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson } 3299b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson 3309b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson /** 331a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * Returns the number of times {@link #get} returned a value that was 332a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * already present in the cache. 333e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 334e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int hitCount() { 335e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return hitCount; 336e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 337e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 338e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 339e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #get} returned null or required a new 340e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * value to be created. 341e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 342e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int missCount() { 343e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return missCount; 344e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 345e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 346e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 347e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #create(Object)} returned a value. 348e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 349e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int createCount() { 350e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return createCount; 351e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 352e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 353e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 354e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #put} was called. 355e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 356e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int putCount() { 357e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return putCount; 358e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 359e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 360e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 361e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of values that have been evicted. 362e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 363e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int evictionCount() { 364e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return evictionCount; 365e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 366e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 367e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 368e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns a copy of the current contents of the cache, ordered from least 369e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * recently accessed to most recently accessed. 370e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 371e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final Map<K, V> snapshot() { 372e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return new LinkedHashMap<K, V>(map); 373e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 374e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 375e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson @Override public synchronized final String toString() { 376e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int accesses = hitCount + missCount; 377e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 378e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 379e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson maxSize, hitCount, missCount, hitPercent); 380e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 381e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson} 382