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/** 23ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski * BEGIN LAYOUTLIB CHANGE 24ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski * This is a custom version that doesn't use the non standard LinkedHashMap#eldest. 25ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski * END LAYOUTLIB CHANGE 26ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski * 27e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * A cache that holds strong references to a limited number of values. Each time 28e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * a value is accessed, it is moved to the head of a queue. When a value is 29e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * added to a full cache, the value at the end of that queue is evicted and may 30e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * become eligible for garbage collection. 31e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 32e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>If your cached values hold resources that need to be explicitly released, 337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * override {@link #entryRemoved}. 34e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 35e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>If a cache miss should be computed on demand for the corresponding keys, 36e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * override {@link #create}. This simplifies the calling code, allowing it to 37e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * assume a value will always be returned, even when there's a cache miss. 38e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 39e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>By default, the cache size is measured in the number of entries. Override 4034895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * {@link #sizeOf} to size the cache in different units. For example, this cache 4134895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * is limited to 4MiB of bitmaps: 42e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <pre> {@code 4334895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * int cacheSize = 4 * 1024 * 1024; // 4MiB 4434895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { 4534895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * protected int sizeOf(String key, Bitmap value) { 4634895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * return value.getByteCount(); 4734895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * } 4834895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * }}</pre> 4934895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * 5034895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * <p>This class is thread-safe. Perform multiple cache operations atomically by 5134895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * synchronizing on the cache: <pre> {@code 5234895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * synchronized (cache) { 5334895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * if (cache.get(key) == null) { 5434895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * cache.put(key, value); 55e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * } 5634895b09db3679c7d4e80d21198847d316e6b0c3Jesse Wilson * }}</pre> 5756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 5856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * <p>This class does not allow null to be used as a key or value. A return 5956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * value of null from {@link #get}, {@link #put} or {@link #remove} is 6056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * unambiguous: the key was not in the cache. 6102db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * 6202db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part 6302db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * of <a href="http://developer.android.com/sdk/compatibility-library.html">Android's 6402db1b6c0081fe442534c8955c0c927c9ddccd46Jesse Wilson * Support Package</a> for earlier releases. 65e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 66e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilsonpublic class LruCache<K, V> { 67e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private final LinkedHashMap<K, V> map; 68e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 69e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** Size of this cache in units. Not necessarily the number of elements. */ 70e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int size; 719b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson private int maxSize; 72e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 73e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int putCount; 74e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int createCount; 75e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int evictionCount; 76e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int hitCount; 77e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int missCount; 78e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 79e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 80e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * @param maxSize for caches that do not override {@link #sizeOf}, this is 81e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the maximum number of entries in the cache. For all other caches, 82e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * this is the maximum sum of the sizes of the entries in this cache. 83e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 84e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public LruCache(int maxSize) { 85e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (maxSize <= 0) { 86e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalArgumentException("maxSize <= 0"); 87e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 88e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson this.maxSize = maxSize; 89e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 90e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 91e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 92e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 93e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * Sets the size of the cache. 94e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * @param maxSize The new maximum size. 95e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * 96e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown * @hide 97e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown */ 98e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown public void resize(int maxSize) { 99e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown if (maxSize <= 0) { 100e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown throw new IllegalArgumentException("maxSize <= 0"); 101e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 102e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 103e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown synchronized (this) { 104e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown this.maxSize = maxSize; 105e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 106e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown trimToSize(maxSize); 107e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown } 108e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown 109e5360fbf3efe85427f7e7f59afe7bbeddb4949acJeff Brown /** 110e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the value for {@code key} if it exists in the cache or can be 111e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * created by {@code #create}. If a value was returned, it is moved to the 112e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * head of the queue. This returns null if a value is not cached and cannot 113e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * be created. 114e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1157db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V get(K key) { 116e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null) { 11756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 118e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 119e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V mapValue; 1217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1227db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.get(key); 1237db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1247db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson hitCount++; 1257db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson missCount++; 128e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 129e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /* 1317db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Attempt to create a value. This may take a long time, and the map 1327db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * may be different when create() returns. If a conflicting value was 1337db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * added to the map while create() was working, we leave that value in 1347db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * the map and release the created value. 1357db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 136e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1377db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V createdValue = create(key); 1387db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (createdValue == null) { 1397db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return null; 1407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 141e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1427db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 143e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson createCount++; 1447db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson mapValue = map.put(key, createdValue); 1457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1467db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1477db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson // There was a conflict so undo that last put 1487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.put(key, mapValue); 1497db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 1507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, createdValue); 1517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1537db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 1547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (mapValue != null) { 1557db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, createdValue, mapValue); 1567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return mapValue; 1577db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } else { 158e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 1597db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson return createdValue; 160e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 161e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 162e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 163e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 164e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Caches {@code value} for {@code key}. The value is moved to the head of 165e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * the queue. 166e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 167c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 168e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 1697db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V put(K key, V value) { 170e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (key == null || value == null) { 17156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null || value == null"); 172e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 173e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1747db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 1757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 1767db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson putCount++; 1777db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size += safeSizeOf(key, value); 1787db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.put(key, value); 1797db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 1807db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 1817db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1827db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 1837db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 184e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (previous != null) { 1857db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, value); 186e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 1877db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 188e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(maxSize); 189e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return previous; 190e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 191e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 1927db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson /** 1937db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param maxSize the maximum size of the cache before returning. May be -1 194ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski * to evict even 0-sized elements. 1957db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson */ 196ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski private void trimToSize(int maxSize) { 1977db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson while (true) { 1987db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson K key; 1997db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V value; 2007db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2017db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size < 0 || (map.isEmpty() && size != 0)) { 2027db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson throw new IllegalStateException(getClass().getName() 2037db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson + ".sizeOf() is reporting inconsistent results!"); 2047db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 205e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2067db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (size <= maxSize) { 2077db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2087db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 209e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 210ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski // BEGIN LAYOUTLIB CHANGE 211ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski // get the last item in the linked list. 212ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski // This is not efficient, the goal here is to minimize the changes 213ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski // compared to the platform version. 214ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski Map.Entry<K, V> toEvict = null; 215ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski for (Map.Entry<K, V> entry : map.entrySet()) { 216ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski toEvict = entry; 217ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski } 218ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski // END LAYOUTLIB CHANGE 219ab775ecdd189b32e35b0d3f4a821502f88b03a4bAdam Lesinski 2207db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (toEvict == null) { 2217db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson break; 2227db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 223e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 2247db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson key = toEvict.getKey(); 2257db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson value = toEvict.getValue(); 2267db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson map.remove(key); 2277db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, value); 2287db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson evictionCount++; 2297db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2307db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 231c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson entryRemoved(true, key, value, null); 232e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 233e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 234e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 235e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 23656b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * Removes the entry for {@code key} if it exists. 23756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson * 238c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * @return the previous value mapped by {@code key}. 23956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson */ 2407db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final V remove(K key) { 24156b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (key == null) { 24256b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson throw new NullPointerException("key == null"); 24356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 24456b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 2457db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson V previous; 2467db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson synchronized (this) { 2477db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson previous = map.remove(key); 2487db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson if (previous != null) { 2497db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson size -= safeSizeOf(key, previous); 2507db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2517db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson } 2527db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 25356b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson if (previous != null) { 2547db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson entryRemoved(false, key, previous, null); 25556b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 2567db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson 25756b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson return previous; 25856b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson } 25956b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson 26056b6ad3e28f9f86fb3186c96ddd8754e190afdf0Jesse Wilson /** 2617db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * Called for entries that have been evicted or removed. This method is 2627db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * invoked when a value is evicted to make space, removed by a call to 2637db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * {@link #remove}, or replaced by a call to {@link #put}. The default 2647db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * implementation does nothing. 2657db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2667db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2677db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2687db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2697db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param evicted true if the entry is being removed to make space, false 2707db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * if the removal was caused by a {@link #put} or {@link #remove}. 2717db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * @param newValue the new value for {@code key}, if it exists. If non-null, 2727db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * this removal was caused by a {@link #put}. Otherwise it was caused by 2737db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * an eviction or a {@link #remove}. 274e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 2757db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 276e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 277e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 278e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Called after a cache miss to compute a value for the corresponding key. 279e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the computed value or null if no value can be computed. The 280e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * default implementation returns null. 2817db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2827db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>The method is called without synchronization: other threads may 2837db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * access the cache while this method is executing. 2847db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * 2857db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * <p>If a value for {@code key} exists in the cache when this method 2867db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * returns, the created value will be released with {@link #entryRemoved} 2877db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * and discarded. This can occur when multiple threads request the same key 2887db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * at the same time (causing multiple values to be created), or when one 2897db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * thread calls {@link #put} while another is creating a value for the same 2907db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson * key. 291e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 292e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected V create(K key) { 293e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return null; 294e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 295e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 296e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson private int safeSizeOf(K key, V value) { 297e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int result = sizeOf(key, value); 298e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson if (result < 0) { 299e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson throw new IllegalStateException("Negative size: " + key + "=" + value); 300e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 301e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return result; 302e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 303e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 304e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 305e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the size of the entry for {@code key} and {@code value} in 306e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * user-defined units. The default implementation returns 1 so that size 307e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * is the number of entries and max size is the maximum number of entries. 308e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * 309e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * <p>An entry's size must not change while it is in the cache. 310e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 311e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson protected int sizeOf(K key, V value) { 312e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return 1; 313e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 314e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 315e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 316c4e6209c5294da5cbca75eafd0ba5d4c3ed9a5b1Jesse Wilson * Clear the cache, calling {@link #entryRemoved} on each removed entry. 317e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 3187db1b40a03ff04ac8b49b3b53839b3c5d1c6f16aJesse Wilson public final void evictAll() { 319e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson trimToSize(-1); // -1 will evict 0-sized elements 320e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 321e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 322e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3239b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the number 3249b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * of entries in the cache. For all other caches, this returns the sum of 3259b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * the sizes of the entries in this cache. 326e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 327e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int size() { 328e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return size; 329e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 330e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 331e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 3329b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * For caches that do not override {@link #sizeOf}, this returns the maximum 3339b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * number of entries in the cache. For all other caches, this returns the 3349b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson * maximum sum of the sizes of the entries in this cache. 3359b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson */ 3369b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson public synchronized final int maxSize() { 3379b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson return maxSize; 3389b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson } 3399b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson 3409b5a93550f3853b229ae9cfb5f6cf33091478023Jesse Wilson /** 341a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * Returns the number of times {@link #get} returned a value that was 342a460c1871e594b8fc68f41f2694c04dd619032c5Jesse Wilson * already present in the cache. 343e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 344e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int hitCount() { 345e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return hitCount; 346e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 347e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 348e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 349e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #get} returned null or required a new 350e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * value to be created. 351e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 352e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int missCount() { 353e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return missCount; 354e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 355e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 356e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 357e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #create(Object)} returned a value. 358e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 359e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int createCount() { 360e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return createCount; 361e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 362e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 363e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 364e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of times {@link #put} was called. 365e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 366e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int putCount() { 367e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return putCount; 368e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 369e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 370e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 371e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns the number of values that have been evicted. 372e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 373e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final int evictionCount() { 374e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return evictionCount; 375e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 376e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 377e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson /** 378e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * Returns a copy of the current contents of the cache, ordered from least 379e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson * recently accessed to most recently accessed. 380e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson */ 381e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson public synchronized final Map<K, V> snapshot() { 382e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return new LinkedHashMap<K, V>(map); 383e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 384e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson 385e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson @Override public synchronized final String toString() { 386e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int accesses = hitCount + missCount; 387e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 388e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 389e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson maxSize, hitCount, missCount, hitPercent); 390e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson } 391e2c1f4a0ee026e7a2a15d198dc3be4529896e9f6Jesse Wilson} 392