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 * 91a1226a7a8a9923fb230ca5657c249aa4f7fdbe43Narayan Kamath * @param maxSize The new maximum size. 92e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown */ 93e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown public void resize(int maxSize) { 94e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown if (maxSize <= 0) { 95e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown throw new IllegalArgumentException("maxSize <= 0"); 96e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 97e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 98e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown synchronized (this) { 99e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown this.maxSize = maxSize; 100e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 101e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown trimToSize(maxSize); 102e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 103e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 104e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown /** 105e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the value for {@code key} if it exists in the cache or can be 106e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * created by {@code #create}. If a value was returned, it is moved to the 107e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * head of the queue. This returns null if a value is not cached and cannot 108e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * be created. 109e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1107db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V get(K key) { 111e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null) { 11256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 113e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 114e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V mapValue; 1167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.get(key); 1187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson hitCount++; 1207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1227db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson missCount++; 123e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 124e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1257db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /* 1267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Attempt to create a value. This may take a long time, and the map 1277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * may be different when create() returns. If a conflicting value was 1287db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * added to the map while create() was working, we leave that value in 1297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * the map and release the created value. 1307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 131e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1327db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V createdValue = create(key); 1337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (createdValue == null) { 1347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return null; 1357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 136e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 138e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson createCount++; 1397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.put(key, createdValue); 1407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1427db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson // There was a conflict so undo that last put 1437db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.put(key, mapValue); 1447db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 1457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, createdValue); 1467db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1477db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1497db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, createdValue, mapValue); 1517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 153e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 1547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return createdValue; 155e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 156e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 157e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 158e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 159e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Caches {@code value} for {@code key}. The value is moved to the head of 160e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the queue. 161e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 162c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 163e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1647db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V put(K key, V value) { 165e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null || value == null) { 16656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null || value == null"); 167e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 168e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1697db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 1707db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson putCount++; 1727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, value); 1737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.put(key, value); 1747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 1757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 1767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 179e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (previous != null) { 1807db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, value); 181e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 1827db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 183e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 184e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return previous; 185e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 186e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1877db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /** 188d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * Remove the eldest entries until the total of remaining entries is at or 189d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * below the requested size. 190d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * 1917db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param maxSize the maximum size of the cache before returning. May be -1 192d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey * to evict even 0-sized elements. 1937db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 194d96b585f5c40ee0d1232630ac0124d4610341577Jeff Sharkey public void trimToSize(int maxSize) { 1957db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson while (true) { 1967db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson K key; 1977db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V value; 1987db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size < 0 || (map.isEmpty() && size != 0)) { 2007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson throw new IllegalStateException(getClass().getName() 2017db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson + ".sizeOf() is reporting inconsistent results!"); 2027db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 203e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2047db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size <= maxSize) { 2057db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2067db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 207e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2087db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson Map.Entry<K, V> toEvict = map.eldest(); 2097db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (toEvict == null) { 2107db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2117db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 212e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2137db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson key = toEvict.getKey(); 2147db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson value = toEvict.getValue(); 2157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.remove(key); 2167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, value); 2177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson evictionCount++; 2187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 220c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson entryRemoved(true, key, value, null); 221e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 222e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 223e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 224e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 22556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * Removes the entry for {@code key} if it exists. 22656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 227c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 22856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson */ 2297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V remove(K key) { 23056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (key == null) { 23156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 23256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 23356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 2347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 2357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.remove(key); 2377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 2387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 2397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (previous != null) { 2437db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, null); 24456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 2457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson return previous; 24756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 24856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 24956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson /** 2507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Called for entries that have been evicted or removed. This method is 2517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * invoked when a value is evicted to make space, removed by a call to 2527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * {@link #remove}, or replaced by a call to {@link #put}. The default 2537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * implementation does nothing. 2547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2587db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param evicted true if the entry is being removed to make space, false 2597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * if the removal was caused by a {@link #put} or {@link #remove}. 2607db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param newValue the new value for {@code key}, if it exists. If non-null, 2617db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * this removal was caused by a {@link #put}. Otherwise it was caused by 2627db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * an eviction or a {@link #remove}. 263e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2647db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 265e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 266e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 267e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Called after a cache miss to compute a value for the corresponding key. 268e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the computed value or null if no value can be computed. The 269e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * default implementation returns null. 2707db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>If a value for {@code key} exists in the cache when this method 2757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * returns, the created value will be released with {@link #entryRemoved} 2767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * and discarded. This can occur when multiple threads request the same key 2777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * at the same time (causing multiple values to be created), or when one 2787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * thread calls {@link #put} while another is creating a value for the same 2797db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * key. 280e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 281e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected V create(K key) { 282e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return null; 283e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 284e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 285e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int safeSizeOf(K key, V value) { 286e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int result = sizeOf(key, value); 287e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (result < 0) { 288e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalStateException("Negative size: " + key + "=" + value); 289e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 290e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return result; 291e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 292e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 293e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 294e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the size of the entry for {@code key} and {@code value} in 295e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * user-defined units. The default implementation returns 1 so that size 296e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * is the number of entries and max size is the maximum number of entries. 297e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 298e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>An entry's size must not change while it is in the cache. 299e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 300e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected int sizeOf(K key, V value) { 301e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return 1; 302e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 303e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 304e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 305c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * Clear the cache, calling {@link #entryRemoved} on each removed entry. 306e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 3077db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final void evictAll() { 308e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(-1); // -1 will evict 0-sized elements 309e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 310e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 311e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3129b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the number 3139b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * of entries in the cache. For all other caches, this returns the sum of 3149b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * the sizes of the entries in this cache. 315e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 316e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int size() { 317e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return size; 318e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 319e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 320e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3219b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the maximum 3229b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * number of entries in the cache. For all other caches, this returns the 3239b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * maximum sum of the sizes of the entries in this cache. 3249b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson */ 3259b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson public synchronized final int maxSize() { 3269b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson return maxSize; 3279b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson } 3289b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson 3299b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson /** 330a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * Returns the number of times {@link #get} returned a value that was 331a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * already present in the cache. 332e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 333e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int hitCount() { 334e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return hitCount; 335e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 336e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 337e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 338e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #get} returned null or required a new 339e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * value to be created. 340e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 341e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int missCount() { 342e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return missCount; 343e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 344e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 345e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 346e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #create(Object)} returned a value. 347e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 348e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int createCount() { 349e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return createCount; 350e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 351e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 352e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 353e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #put} was called. 354e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 355e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int putCount() { 356e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return putCount; 357e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 358e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 359e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 360e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of values that have been evicted. 361e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 362e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int evictionCount() { 363e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return evictionCount; 364e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 365e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 366e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 367e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns a copy of the current contents of the cache, ordered from least 368e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * recently accessed to most recently accessed. 369e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 370e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final Map<K, V> snapshot() { 371e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return new LinkedHashMap<K, V>(map); 372e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 373e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 374e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson @Override public synchronized final String toString() { 375e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int accesses = hitCount + missCount; 376e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 377e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 378e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson maxSize, hitCount, missCount, hitPercent); 379e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 380e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson} 381