LruCache.java revision 02db1b6c0081fe442534c8955c0c927c9ddccd46
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 /** 89e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the value for {@code key} if it exists in the cache or can be 90e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * created by {@code #create}. If a value was returned, it is moved to the 91e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * head of the queue. This returns null if a value is not cached and cannot 92e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * be created. 93e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 947db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V get(K key) { 95e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null) { 9656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 97e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 98e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V mapValue; 1007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1017db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.get(key); 1027db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1037db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson hitCount++; 1047db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1057db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1067db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson missCount++; 107e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 108e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1097db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /* 1107db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Attempt to create a value. This may take a long time, and the map 1117db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * may be different when create() returns. If a conflicting value was 1127db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * added to the map while create() was working, we leave that value in 1137db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * the map and release the created value. 1147db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 115e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V createdValue = create(key); 1177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (createdValue == null) { 1187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return null; 1197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 120e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 122e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson createCount++; 1237db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.put(key, createdValue); 1247db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1257db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson // There was a conflict so undo that last put 1277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.put(key, mapValue); 1287db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 1297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, createdValue); 1307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1317db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1327db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, createdValue, mapValue); 1357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 137e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 1387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return createdValue; 139e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 140e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 141e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 142e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 143e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Caches {@code value} for {@code key}. The value is moved to the head of 144e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the queue. 145e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 146c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 147e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V put(K key, V value) { 149e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null || value == null) { 15056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null || value == null"); 151e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 152e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 1547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson putCount++; 1567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, value); 1577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.put(key, value); 1587db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 1597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 1607db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1617db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1627db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 163e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (previous != null) { 1647db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, value); 165e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 1667db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 167e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 168e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return previous; 169e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 170e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /** 1727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param maxSize the maximum size of the cache before returning. May be -1 1737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * to evict even 0-sized elements. 1747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 175e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private void trimToSize(int maxSize) { 1767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson while (true) { 1777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson K key; 1787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V value; 1797db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1807db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size < 0 || (map.isEmpty() && size != 0)) { 1817db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson throw new IllegalStateException(getClass().getName() 1827db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson + ".sizeOf() is reporting inconsistent results!"); 1837db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 184e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1857db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size <= maxSize) { 1867db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 1877db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 188e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1897db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson Map.Entry<K, V> toEvict = map.eldest(); 1907db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (toEvict == null) { 1917db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 1927db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 193e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1947db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson key = toEvict.getKey(); 1957db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson value = toEvict.getValue(); 1967db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.remove(key); 1977db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, value); 1987db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson evictionCount++; 1997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 201c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson entryRemoved(true, key, value, null); 202e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 203e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 204e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 205e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 20656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * Removes the entry for {@code key} if it exists. 20756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 208c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 20956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson */ 2107db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V remove(K key) { 21156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (key == null) { 21256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 21356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 21456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 2157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 2167db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2177db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.remove(key); 2187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 2197db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 2207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2227db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 22356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (previous != null) { 2247db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, null); 22556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 2267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 22756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson return previous; 22856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 22956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 23056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson /** 2317db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Called for entries that have been evicted or removed. This method is 2327db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * invoked when a value is evicted to make space, removed by a call to 2337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * {@link #remove}, or replaced by a call to {@link #put}. The default 2347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * implementation does nothing. 2357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2367db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param evicted true if the entry is being removed to make space, false 2407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * if the removal was caused by a {@link #put} or {@link #remove}. 2417db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param newValue the new value for {@code key}, if it exists. If non-null, 2427db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * this removal was caused by a {@link #put}. Otherwise it was caused by 2437db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * an eviction or a {@link #remove}. 244e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 246e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 247e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 248e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Called after a cache miss to compute a value for the corresponding key. 249e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the computed value or null if no value can be computed. The 250e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * default implementation returns null. 2517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>If a value for {@code key} exists in the cache when this method 2567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * returns, the created value will be released with {@link #entryRemoved} 2577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * and discarded. This can occur when multiple threads request the same key 2587db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * at the same time (causing multiple values to be created), or when one 2597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * thread calls {@link #put} while another is creating a value for the same 2607db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * key. 261e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 262e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected V create(K key) { 263e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return null; 264e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 265e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 266e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int safeSizeOf(K key, V value) { 267e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int result = sizeOf(key, value); 268e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (result < 0) { 269e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalStateException("Negative size: " + key + "=" + value); 270e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 271e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return result; 272e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 273e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 274e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 275e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the size of the entry for {@code key} and {@code value} in 276e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * user-defined units. The default implementation returns 1 so that size 277e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * is the number of entries and max size is the maximum number of entries. 278e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 279e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>An entry's size must not change while it is in the cache. 280e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 281e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected int sizeOf(K key, V value) { 282e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return 1; 283e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 284e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 285e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 286c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * Clear the cache, calling {@link #entryRemoved} on each removed entry. 287e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2887db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final void evictAll() { 289e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(-1); // -1 will evict 0-sized elements 290e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 291e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 292e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 2939b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the number 2949b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * of entries in the cache. For all other caches, this returns the sum of 2959b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * the sizes of the entries in this cache. 296e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 297e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int size() { 298e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return size; 299e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 300e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 301e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3029b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the maximum 3039b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * number of entries in the cache. For all other caches, this returns the 3049b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * maximum sum of the sizes of the entries in this cache. 3059b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson */ 3069b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson public synchronized final int maxSize() { 3079b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson return maxSize; 3089b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson } 3099b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson 3109b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson /** 311a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * Returns the number of times {@link #get} returned a value that was 312a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * already present in the cache. 313e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 314e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int hitCount() { 315e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return hitCount; 316e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 317e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 318e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 319e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #get} returned null or required a new 320e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * value to be created. 321e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 322e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int missCount() { 323e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return missCount; 324e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 325e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 326e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 327e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #create(Object)} returned a value. 328e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 329e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int createCount() { 330e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return createCount; 331e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 332e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 333e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 334e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #put} was called. 335e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 336e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int putCount() { 337e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return putCount; 338e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 339e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 340e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 341e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of values that have been evicted. 342e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 343e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int evictionCount() { 344e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return evictionCount; 345e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 346e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 347e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 348e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns a copy of the current contents of the cache, ordered from least 349e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * recently accessed to most recently accessed. 350e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 351e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final Map<K, V> snapshot() { 352e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return new LinkedHashMap<K, V>(map); 353e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 354e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 355e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson @Override public synchronized final String toString() { 356e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int accesses = hitCount + missCount; 357e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 358e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 359e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson maxSize, hitCount, missCount, hitPercent); 360e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 361e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson} 362