1282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/* 2282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Copyright (C) 2011 The Android Open Source Project 3282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 4282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 5282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * you may not use this file except in compliance with the License. 6282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * You may obtain a copy of the License at 7282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 8282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 9282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 10282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Unless required by applicable law or agreed to in writing, software 11282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 12282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * See the License for the specific language governing permissions and 14282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * limitations under the License. 15282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 16282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 17282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskipackage android.util; 18282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 19282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiimport java.util.LinkedHashMap; 20282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiimport java.util.Map; 21282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 22282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/** 23282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * BEGIN LAYOUTLIB CHANGE 24282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * This is a custom version that doesn't use the non standard LinkedHashMap#eldest. 25282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * END LAYOUTLIB CHANGE 26282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 27282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * A cache that holds strong references to a limited number of values. Each time 28282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * a value is accessed, it is moved to the head of a queue. When a value is 29282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * added to a full cache, the value at the end of that queue is evicted and may 30282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * become eligible for garbage collection. 31282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 32282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>If your cached values hold resources that need to be explicitly released, 33282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * override {@link #entryRemoved}. 34282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 35282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>If a cache miss should be computed on demand for the corresponding keys, 36282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * override {@link #create}. This simplifies the calling code, allowing it to 37282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * assume a value will always be returned, even when there's a cache miss. 38282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 39282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>By default, the cache size is measured in the number of entries. Override 40282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * {@link #sizeOf} to size the cache in different units. For example, this cache 41282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * is limited to 4MiB of bitmaps: 42282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <pre> {@code 43282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * int cacheSize = 4 * 1024 * 1024; // 4MiB 44282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { 45282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * protected int sizeOf(String key, Bitmap value) { 46282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * return value.getByteCount(); 47282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * } 48282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * }}</pre> 49282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 50282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>This class is thread-safe. Perform multiple cache operations atomically by 51282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * synchronizing on the cache: <pre> {@code 52282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * synchronized (cache) { 53282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * if (cache.get(key) == null) { 54282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * cache.put(key, value); 55282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * } 56282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * }}</pre> 57282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 58282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>This class does not allow null to be used as a key or value. A return 59282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * value of null from {@link #get}, {@link #put} or {@link #remove} is 60282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * unambiguous: the key was not in the cache. 61282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 62282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part 63282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * of <a href="http://developer.android.com/sdk/compatibility-library.html">Android's 64282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Support Package</a> for earlier releases. 65282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 66282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskipublic class LruCache<K, V> { 67282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private final LinkedHashMap<K, V> map; 68282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 69282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** Size of this cache in units. Not necessarily the number of elements. */ 70282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int size; 71282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int maxSize; 72282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 73282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int putCount; 74282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int createCount; 75282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int evictionCount; 76282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int hitCount; 77282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int missCount; 78282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 79282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 80282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @param maxSize for caches that do not override {@link #sizeOf}, this is 81282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the maximum number of entries in the cache. For all other caches, 82282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * this is the maximum sum of the sizes of the entries in this cache. 83282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 84282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public LruCache(int maxSize) { 85282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (maxSize <= 0) { 86282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new IllegalArgumentException("maxSize <= 0"); 87282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 88282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski this.maxSize = maxSize; 89282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 90282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 91282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 92282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 93282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Sets the size of the cache. 94282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @param maxSize The new maximum size. 95282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 96282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @hide 97282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 98282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public void resize(int maxSize) { 99282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (maxSize <= 0) { 100282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new IllegalArgumentException("maxSize <= 0"); 101282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 102282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 103282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 104282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski this.maxSize = maxSize; 105282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 106282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski trimToSize(maxSize); 107282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 108282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 109282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 110282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the value for {@code key} if it exists in the cache or can be 111282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * created by {@code #create}. If a value was returned, it is moved to the 112282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * head of the queue. This returns null if a value is not cached and cannot 113282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * be created. 114282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 115282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public final V get(K key) { 116282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (key == null) { 117282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new NullPointerException("key == null"); 118282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 119282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 120282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski V mapValue; 121282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 122282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mapValue = map.get(key); 123282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mapValue != null) { 124282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski hitCount++; 125282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return mapValue; 126282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 127282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski missCount++; 128282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 129282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 130282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /* 131282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Attempt to create a value. This may take a long time, and the map 132282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * may be different when create() returns. If a conflicting value was 133282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * added to the map while create() was working, we leave that value in 134282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the map and release the created value. 135282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 136282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 137282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski V createdValue = create(key); 138282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (createdValue == null) { 139282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return null; 140282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 141282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 142282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 143282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski createCount++; 144282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mapValue = map.put(key, createdValue); 145282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 146282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mapValue != null) { 147282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // There was a conflict so undo that last put 148282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski map.put(key, mapValue); 149282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 150282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski size += safeSizeOf(key, createdValue); 151282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 152282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 153282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 154282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mapValue != null) { 155282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski entryRemoved(false, key, createdValue, mapValue); 156282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return mapValue; 157282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 158282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski trimToSize(maxSize); 159282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return createdValue; 160282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 161282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 162282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 163282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 164282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Caches {@code value} for {@code key}. The value is moved to the head of 165282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the queue. 166282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 167282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @return the previous value mapped by {@code key}. 168282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 169282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public final V put(K key, V value) { 170282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (key == null || value == null) { 171282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new NullPointerException("key == null || value == null"); 172282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 173282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 174282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski V previous; 175282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 176282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski putCount++; 177282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski size += safeSizeOf(key, value); 178282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski previous = map.put(key, value); 179282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (previous != null) { 180282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski size -= safeSizeOf(key, previous); 181282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 182282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 183282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 184282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (previous != null) { 185282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski entryRemoved(false, key, previous, value); 186282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 187282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 188282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski trimToSize(maxSize); 189282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return previous; 190282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 191282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 192282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 193282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @param maxSize the maximum size of the cache before returning. May be -1 194282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * to evict even 0-sized elements. 195282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 196282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private void trimToSize(int maxSize) { 197282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (true) { 198282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski K key; 199282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski V value; 200282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 201282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (size < 0 || (map.isEmpty() && size != 0)) { 202282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new IllegalStateException(getClass().getName() 203282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski + ".sizeOf() is reporting inconsistent results!"); 204282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 205282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 206282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (size <= maxSize) { 207282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski break; 208282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 209282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 210282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // BEGIN LAYOUTLIB CHANGE 211282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // get the last item in the linked list. 212282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // This is not efficient, the goal here is to minimize the changes 213282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // compared to the platform version. 214282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski Map.Entry<K, V> toEvict = null; 215282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (Map.Entry<K, V> entry : map.entrySet()) { 216282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski toEvict = entry; 217282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 218282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // END LAYOUTLIB CHANGE 219282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 220282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (toEvict == null) { 221282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski break; 222282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 223282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 224282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski key = toEvict.getKey(); 225282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski value = toEvict.getValue(); 226282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski map.remove(key); 227282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski size -= safeSizeOf(key, value); 228282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski evictionCount++; 229282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 230282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 231282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski entryRemoved(true, key, value, null); 232282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 233282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 234282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 235282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 236282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Removes the entry for {@code key} if it exists. 237282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 238282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @return the previous value mapped by {@code key}. 239282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 240282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public final V remove(K key) { 241282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (key == null) { 242282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new NullPointerException("key == null"); 243282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 244282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 245282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski V previous; 246282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski synchronized (this) { 247282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski previous = map.remove(key); 248282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (previous != null) { 249282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski size -= safeSizeOf(key, previous); 250282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 251282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 252282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 253282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (previous != null) { 254282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski entryRemoved(false, key, previous, null); 255282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 256282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 257282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return previous; 258282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 259282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 260282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 261282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Called for entries that have been evicted or removed. This method is 262282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * invoked when a value is evicted to make space, removed by a call to 263282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * {@link #remove}, or replaced by a call to {@link #put}. The default 264282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * implementation does nothing. 265282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 266282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>The method is called without synchronization: other threads may 267282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * access the cache while this method is executing. 268282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 269282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @param evicted true if the entry is being removed to make space, false 270282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * if the removal was caused by a {@link #put} or {@link #remove}. 271282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * @param newValue the new value for {@code key}, if it exists. If non-null, 272282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * this removal was caused by a {@link #put}. Otherwise it was caused by 273282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * an eviction or a {@link #remove}. 274282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 275282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 276282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 277282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 278282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Called after a cache miss to compute a value for the corresponding key. 279282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the computed value or null if no value can be computed. The 280282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * default implementation returns null. 281282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 282282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>The method is called without synchronization: other threads may 283282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * access the cache while this method is executing. 284282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 285282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>If a value for {@code key} exists in the cache when this method 286282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * returns, the created value will be released with {@link #entryRemoved} 287282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * and discarded. This can occur when multiple threads request the same key 288282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * at the same time (causing multiple values to be created), or when one 289282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * thread calls {@link #put} while another is creating a value for the same 290282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * key. 291282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 292282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski protected V create(K key) { 293282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return null; 294282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 295282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 296282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int safeSizeOf(K key, V value) { 297282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int result = sizeOf(key, value); 298282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (result < 0) { 299282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski throw new IllegalStateException("Negative size: " + key + "=" + value); 300282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 301282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return result; 302282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 303282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 304282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 305282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the size of the entry for {@code key} and {@code value} in 306282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * user-defined units. The default implementation returns 1 so that size 307282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * is the number of entries and max size is the maximum number of entries. 308282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 309282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * <p>An entry's size must not change while it is in the cache. 310282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 311282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski protected int sizeOf(K key, V value) { 312282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return 1; 313282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 314282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 315282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 316282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Clear the cache, calling {@link #entryRemoved} on each removed entry. 317282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 318282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public final void evictAll() { 319282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski trimToSize(-1); // -1 will evict 0-sized elements 320282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 321282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 322282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 323282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * For caches that do not override {@link #sizeOf}, this returns the number 324282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * of entries in the cache. For all other caches, this returns the sum of 325282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the sizes of the entries in this cache. 326282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 327282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int size() { 328282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return size; 329282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 330282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 331282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 332282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * For caches that do not override {@link #sizeOf}, this returns the maximum 333282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * number of entries in the cache. For all other caches, this returns the 334282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * maximum sum of the sizes of the entries in this cache. 335282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 336282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int maxSize() { 337282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return maxSize; 338282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 339282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 340282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 341282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of times {@link #get} returned a value that was 342282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * already present in the cache. 343282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 344282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int hitCount() { 345282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return hitCount; 346282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 347282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 348282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 349282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of times {@link #get} returned null or required a new 350282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * value to be created. 351282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 352282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int missCount() { 353282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return missCount; 354282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 355282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 356282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 357282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of times {@link #create(Object)} returned a value. 358282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 359282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int createCount() { 360282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return createCount; 361282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 362282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 363282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 364282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of times {@link #put} was called. 365282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 366282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int putCount() { 367282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return putCount; 368282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 369282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 370282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 371282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of values that have been evicted. 372282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 373282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final int evictionCount() { 374282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return evictionCount; 375282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 376282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 377282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 378282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns a copy of the current contents of the cache, ordered from least 379282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * recently accessed to most recently accessed. 380282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 381282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public synchronized final Map<K, V> snapshot() { 382282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return new LinkedHashMap<K, V>(map); 383282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 384282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 385282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski @Override public synchronized final String toString() { 386282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int accesses = hitCount + missCount; 387282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 388282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 389282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski maxSize, hitCount, missCount, hitPercent); 390282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 391282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 392