LruCache.java revision 795b97d901e1793dac5c3e67d43c96a758fec388
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.support.v4.util; 18 19import java.util.LinkedHashMap; 20import java.util.Map; 21 22// STOPSHIP replace "Honeycomb MR1" with numbered release 2x below 23 24/** 25 * Static library version of {@link android.util.LruCache}. Used to write apps 26 * that run on platforms prior to Android Honeycomb MR1. When running on 27 * Honeycomb MR1 or above, this implementation is still used; it does not try to 28 * switch to the framework's implementation. See the framework SDK 29 * documentation for a class overview. 30 */ 31public class LruCache<K, V> { 32 private final LinkedHashMap<K, V> map; 33 34 /** Size of this cache in units. Not necessarily the number of elements. */ 35 private int size; 36 private int maxSize; 37 38 private int putCount; 39 private int createCount; 40 private int evictionCount; 41 private int hitCount; 42 private int missCount; 43 44 /** 45 * @param maxSize for caches that do not override {@link #sizeOf}, this is 46 * the maximum number of entries in the cache. For all other caches, 47 * this is the maximum sum of the sizes of the entries in this cache. 48 */ 49 public LruCache(int maxSize) { 50 if (maxSize <= 0) { 51 throw new IllegalArgumentException("maxSize <= 0"); 52 } 53 this.maxSize = maxSize; 54 this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 55 } 56 57 /** 58 * Returns the value for {@code key} if it exists in the cache or can be 59 * created by {@code #create}. If a value was returned, it is moved to the 60 * head of the queue. This returns null if a value is not cached and cannot 61 * be created. 62 */ 63 public synchronized final V get(K key) { 64 if (key == null) { 65 throw new NullPointerException("key == null"); 66 } 67 68 V result = map.get(key); 69 if (result != null) { 70 hitCount++; 71 return result; 72 } 73 74 missCount++; 75 76 // TODO: release the lock while calling this potentially slow user code 77 result = create(key); 78 79 if (result != null) { 80 createCount++; 81 size += safeSizeOf(key, result); 82 map.put(key, result); 83 trimToSize(maxSize); 84 } 85 return result; 86 } 87 88 /** 89 * Caches {@code value} for {@code key}. The value is moved to the head of 90 * the queue. 91 * 92 * @return the previous value mapped by {@code key}. Although that entry is 93 * no longer cached, it has not been passed to {@link #entryEvicted}. 94 */ 95 public synchronized final V put(K key, V value) { 96 if (key == null || value == null) { 97 throw new NullPointerException("key == null || value == null"); 98 } 99 100 putCount++; 101 size += safeSizeOf(key, value); 102 V previous = map.put(key, value); 103 if (previous != null) { 104 size -= safeSizeOf(key, previous); 105 } 106 trimToSize(maxSize); 107 return previous; 108 } 109 110 private void trimToSize(int maxSize) { 111 while (size > maxSize && !map.isEmpty()) { 112 Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); 113 if (toEvict == null) { 114 break; // map is empty; if size is not 0 then throw an error below 115 } 116 117 K key = toEvict.getKey(); 118 V value = toEvict.getValue(); 119 map.remove(key); 120 size -= safeSizeOf(key, value); 121 evictionCount++; 122 123 // TODO: release the lock while calling this potentially slow user code 124 entryEvicted(key, value); 125 } 126 127 if (size < 0 || (map.isEmpty() && size != 0)) { 128 throw new IllegalStateException(getClass().getName() 129 + ".sizeOf() is reporting inconsistent results!"); 130 } 131 } 132 133 /** 134 * Removes the entry for {@code key} if it exists. 135 * 136 * @return the previous value mapped by {@code key}. Although that entry is 137 * no longer cached, it has not been passed to {@link #entryEvicted}. 138 */ 139 public synchronized final V remove(K key) { 140 if (key == null) { 141 throw new NullPointerException("key == null"); 142 } 143 144 V previous = map.remove(key); 145 if (previous != null) { 146 size -= safeSizeOf(key, previous); 147 } 148 return previous; 149 } 150 151 /** 152 * Called for entries that have reached the tail of the least recently used 153 * queue and are be removed. The default implementation does nothing. 154 */ 155 protected void entryEvicted(K key, V value) {} 156 157 /** 158 * Called after a cache miss to compute a value for the corresponding key. 159 * Returns the computed value or null if no value can be computed. The 160 * default implementation returns null. 161 */ 162 protected V create(K key) { 163 return null; 164 } 165 166 private int safeSizeOf(K key, V value) { 167 int result = sizeOf(key, value); 168 if (result < 0) { 169 throw new IllegalStateException("Negative size: " + key + "=" + value); 170 } 171 return result; 172 } 173 174 /** 175 * Returns the size of the entry for {@code key} and {@code value} in 176 * user-defined units. The default implementation returns 1 so that size 177 * is the number of entries and max size is the maximum number of entries. 178 * 179 * <p>An entry's size must not change while it is in the cache. 180 */ 181 protected int sizeOf(K key, V value) { 182 return 1; 183 } 184 185 /** 186 * Clear the cache, calling {@link #entryEvicted} on each removed entry. 187 */ 188 public synchronized final void evictAll() { 189 trimToSize(-1); // -1 will evict 0-sized elements 190 } 191 192 /** 193 * For caches that do not override {@link #sizeOf}, this returns the number 194 * of entries in the cache. For all other caches, this returns the sum of 195 * the sizes of the entries in this cache. 196 */ 197 public synchronized final int size() { 198 return size; 199 } 200 201 /** 202 * For caches that do not override {@link #sizeOf}, this returns the maximum 203 * number of entries in the cache. For all other caches, this returns the 204 * maximum sum of the sizes of the entries in this cache. 205 */ 206 public synchronized final int maxSize() { 207 return maxSize; 208 } 209 210 /** 211 * Returns the number of times {@link #get} returned a value. 212 */ 213 public synchronized final int hitCount() { 214 return hitCount; 215 } 216 217 /** 218 * Returns the number of times {@link #get} returned null or required a new 219 * value to be created. 220 */ 221 public synchronized final int missCount() { 222 return missCount; 223 } 224 225 /** 226 * Returns the number of times {@link #create(Object)} returned a value. 227 */ 228 public synchronized final int createCount() { 229 return createCount; 230 } 231 232 /** 233 * Returns the number of times {@link #put} was called. 234 */ 235 public synchronized final int putCount() { 236 return putCount; 237 } 238 239 /** 240 * Returns the number of values that have been evicted. 241 */ 242 public synchronized final int evictionCount() { 243 return evictionCount; 244 } 245 246 /** 247 * Returns a copy of the current contents of the cache, ordered from least 248 * recently accessed to most recently accessed. 249 */ 250 public synchronized final Map<K, V> snapshot() { 251 return new LinkedHashMap<K, V>(map); 252 } 253 254 @Override public synchronized final String toString() { 255 int accesses = hitCount + missCount; 256 int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 257 return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 258 maxSize, hitCount, missCount, hitPercent); 259 } 260} 261