LruCache.java revision e5360fbf3efe85427f7e7f59afe7bbeddb4949ac
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 /** 1897db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param maxSize the maximum size of the cache before returning. May be -1 1907db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * to evict even 0-sized elements. 1917db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 192e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private void trimToSize(int maxSize) { 1937db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson while (true) { 1947db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson K key; 1957db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V value; 1967db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1977db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size < 0 || (map.isEmpty() && size != 0)) { 1987db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson throw new IllegalStateException(getClass().getName() 1997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson + ".sizeOf() is reporting inconsistent results!"); 2007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 201e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2027db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size <= maxSize) { 2037db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2047db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 205e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2067db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson Map.Entry<K, V> toEvict = map.eldest(); 2077db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (toEvict == null) { 2087db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2097db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 210e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2117db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson key = toEvict.getKey(); 2127db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson value = toEvict.getValue(); 2137db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.remove(key); 2147db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, value); 2157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson evictionCount++; 2167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 218c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson entryRemoved(true, key, value, null); 219e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 220e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 221e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 222e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 22356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * Removes the entry for {@code key} if it exists. 22456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 225c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 22656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson */ 2277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V remove(K key) { 22856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (key == null) { 22956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 23056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 23156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 2327db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 2337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.remove(key); 2357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 2367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 2377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (previous != null) { 2417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, null); 24256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 2437db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 24456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson return previous; 24556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 24656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 24756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson /** 2487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Called for entries that have been evicted or removed. This method is 2497db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * invoked when a value is evicted to make space, removed by a call to 2507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * {@link #remove}, or replaced by a call to {@link #put}. The default 2517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * implementation does nothing. 2527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param evicted true if the entry is being removed to make space, false 2577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * if the removal was caused by a {@link #put} or {@link #remove}. 2587db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param newValue the new value for {@code key}, if it exists. If non-null, 2597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * this removal was caused by a {@link #put}. Otherwise it was caused by 2607db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * an eviction or a {@link #remove}. 261e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2627db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 263e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 264e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 265e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Called after a cache miss to compute a value for the corresponding key. 266e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the computed value or null if no value can be computed. The 267e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * default implementation returns null. 2687db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2697db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2707db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>If a value for {@code key} exists in the cache when this method 2737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * returns, the created value will be released with {@link #entryRemoved} 2747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * and discarded. This can occur when multiple threads request the same key 2757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * at the same time (causing multiple values to be created), or when one 2767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * thread calls {@link #put} while another is creating a value for the same 2777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * key. 278e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 279e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected V create(K key) { 280e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return null; 281e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 282e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 283e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int safeSizeOf(K key, V value) { 284e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int result = sizeOf(key, value); 285e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (result < 0) { 286e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalStateException("Negative size: " + key + "=" + value); 287e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 288e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return result; 289e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 290e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 291e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 292e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the size of the entry for {@code key} and {@code value} in 293e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * user-defined units. The default implementation returns 1 so that size 294e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * is the number of entries and max size is the maximum number of entries. 295e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 296e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>An entry's size must not change while it is in the cache. 297e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 298e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected int sizeOf(K key, V value) { 299e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return 1; 300e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 301e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 302e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 303c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * Clear the cache, calling {@link #entryRemoved} on each removed entry. 304e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 3057db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final void evictAll() { 306e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(-1); // -1 will evict 0-sized elements 307e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 308e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 309e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3109b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the number 3119b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * of entries in the cache. For all other caches, this returns the sum of 3129b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * the sizes of the entries in this cache. 313e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 314e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int size() { 315e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return size; 316e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 317e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 318e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3199b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the maximum 3209b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * number of entries in the cache. For all other caches, this returns the 3219b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * maximum sum of the sizes of the entries in this cache. 3229b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson */ 3239b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson public synchronized final int maxSize() { 3249b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson return maxSize; 3259b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson } 3269b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson 3279b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson /** 328a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * Returns the number of times {@link #get} returned a value that was 329a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * already present in the cache. 330e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 331e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int hitCount() { 332e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return hitCount; 333e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 334e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 335e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 336e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #get} returned null or required a new 337e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * value to be created. 338e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 339e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int missCount() { 340e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return missCount; 341e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 342e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 343e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 344e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #create(Object)} returned a value. 345e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 346e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int createCount() { 347e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return createCount; 348e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 349e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 350e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 351e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #put} was called. 352e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 353e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int putCount() { 354e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return putCount; 355e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 356e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 357e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 358e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of values that have been evicted. 359e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 360e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int evictionCount() { 361e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return evictionCount; 362e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 363e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 364e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 365e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns a copy of the current contents of the cache, ordered from least 366e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * recently accessed to most recently accessed. 367e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 368e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final Map<K, V> snapshot() { 369e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return new LinkedHashMap<K, V>(map); 370e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 371e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 372e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson @Override public synchronized final String toString() { 373e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int accesses = hitCount + missCount; 374e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 375e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 376e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson maxSize, hitCount, missCount, hitPercent); 377e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 378e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson} 379