LruCache.java revision a87be984a409450f8e697bd5009d2aa9ccebbea6
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 final V get(K key) { 64 if (key == null) { 65 throw new NullPointerException("key == null"); 66 } 67 68 V mapValue; 69 synchronized (this) { 70 mapValue = map.get(key); 71 if (mapValue != null) { 72 hitCount++; 73 return mapValue; 74 } 75 missCount++; 76 } 77 78 /* 79 * Attempt to create a value. This may take a long time, and the map 80 * may be different when create() returns. If a conflicting value was 81 * added to the map while create() was working, we leave that value in 82 * the map and release the created value. 83 */ 84 85 V createdValue = create(key); 86 if (createdValue == null) { 87 return null; 88 } 89 90 synchronized (this) { 91 createCount++; 92 mapValue = map.put(key, createdValue); 93 94 if (mapValue != null) { 95 // There was a conflict so undo that last put 96 map.put(key, mapValue); 97 } else { 98 size += safeSizeOf(key, createdValue); 99 } 100 } 101 102 if (mapValue != null) { 103 entryRemoved(false, key, createdValue, mapValue); 104 return mapValue; 105 } else { 106 trimToSize(maxSize); 107 return createdValue; 108 } 109 } 110 111 /** 112 * Caches {@code value} for {@code key}. The value is moved to the head of 113 * the queue. 114 * 115 * @return the previous value mapped by {@code key}. 116 */ 117 public final V put(K key, V value) { 118 if (key == null || value == null) { 119 throw new NullPointerException("key == null || value == null"); 120 } 121 122 V previous; 123 synchronized (this) { 124 putCount++; 125 size += safeSizeOf(key, value); 126 previous = map.put(key, value); 127 if (previous != null) { 128 size -= safeSizeOf(key, previous); 129 } 130 } 131 132 if (previous != null) { 133 entryRemoved(false, key, previous, value); 134 } 135 136 trimToSize(maxSize); 137 return previous; 138 } 139 140 /** 141 * @param maxSize the maximum size of the cache before returning. May be -1 142 * to evict even 0-sized elements. 143 */ 144 private void trimToSize(int maxSize) { 145 while (true) { 146 K key; 147 V value; 148 synchronized (this) { 149 if (size < 0 || (map.isEmpty() && size != 0)) { 150 throw new IllegalStateException(getClass().getName() 151 + ".sizeOf() is reporting inconsistent results!"); 152 } 153 154 if (size <= maxSize) { 155 break; 156 } 157 158 Map.Entry<K, V> toEvict = map.eldest(); 159 if (toEvict == null) { 160 break; 161 } 162 163 key = toEvict.getKey(); 164 value = toEvict.getValue(); 165 map.remove(key); 166 size -= safeSizeOf(key, value); 167 evictionCount++; 168 } 169 170 entryRemoved(true, key, value, null); 171 } 172 } 173 174 /** 175 * Removes the entry for {@code key} if it exists. 176 * 177 * @return the previous value mapped by {@code key}. 178 */ 179 public final V remove(K key) { 180 if (key == null) { 181 throw new NullPointerException("key == null"); 182 } 183 184 V previous; 185 synchronized (this) { 186 previous = map.remove(key); 187 if (previous != null) { 188 size -= safeSizeOf(key, previous); 189 } 190 } 191 192 if (previous != null) { 193 entryRemoved(false, key, previous, null); 194 } 195 196 return previous; 197 } 198 199 /** 200 * Called for entries that have been evicted or removed. This method is 201 * invoked when a value is evicted to make space, removed by a call to 202 * {@link #remove}, or replaced by a call to {@link #put}. The default 203 * implementation does nothing. 204 * 205 * <p>The method is called without synchronization: other threads may 206 * access the cache while this method is executing. 207 * 208 * @param evicted true if the entry is being removed to make space, false 209 * if the removal was caused by a {@link #put} or {@link #remove}. 210 * @param newValue the new value for {@code key}, if it exists. If non-null, 211 * this removal was caused by a {@link #put}. Otherwise it was caused by 212 * an eviction or a {@link #remove}. 213 */ 214 protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 215 216 /** 217 * Called after a cache miss to compute a value for the corresponding key. 218 * Returns the computed value or null if no value can be computed. The 219 * default implementation returns null. 220 * 221 * <p>The method is called without synchronization: other threads may 222 * access the cache while this method is executing. 223 * 224 * <p>If a value for {@code key} exists in the cache when this method 225 * returns, the created value will be released with {@link #entryRemoved} 226 * and discarded. This can occur when multiple threads request the same key 227 * at the same time (causing multiple values to be created), or when one 228 * thread calls {@link #put} while another is creating a value for the same 229 * key. 230 */ 231 protected V create(K key) { 232 return null; 233 } 234 235 private int safeSizeOf(K key, V value) { 236 int result = sizeOf(key, value); 237 if (result < 0) { 238 throw new IllegalStateException("Negative size: " + key + "=" + value); 239 } 240 return result; 241 } 242 243 /** 244 * Returns the size of the entry for {@code key} and {@code value} in 245 * user-defined units. The default implementation returns 1 so that size 246 * is the number of entries and max size is the maximum number of entries. 247 * 248 * <p>An entry's size must not change while it is in the cache. 249 */ 250 protected int sizeOf(K key, V value) { 251 return 1; 252 } 253 254 /** 255 * Clear the cache, calling {@link #entryRemoved} on each removed entry. 256 */ 257 public final void evictAll() { 258 trimToSize(-1); // -1 will evict 0-sized elements 259 } 260 261 /** 262 * For caches that do not override {@link #sizeOf}, this returns the number 263 * of entries in the cache. For all other caches, this returns the sum of 264 * the sizes of the entries in this cache. 265 */ 266 public synchronized final int size() { 267 return size; 268 } 269 270 /** 271 * For caches that do not override {@link #sizeOf}, this returns the maximum 272 * number of entries in the cache. For all other caches, this returns the 273 * maximum sum of the sizes of the entries in this cache. 274 */ 275 public synchronized final int maxSize() { 276 return maxSize; 277 } 278 279 /** 280 * Returns the number of times {@link #get} returned a value. 281 */ 282 public synchronized final int hitCount() { 283 return hitCount; 284 } 285 286 /** 287 * Returns the number of times {@link #get} returned null or required a new 288 * value to be created. 289 */ 290 public synchronized final int missCount() { 291 return missCount; 292 } 293 294 /** 295 * Returns the number of times {@link #create(Object)} returned a value. 296 */ 297 public synchronized final int createCount() { 298 return createCount; 299 } 300 301 /** 302 * Returns the number of times {@link #put} was called. 303 */ 304 public synchronized final int putCount() { 305 return putCount; 306 } 307 308 /** 309 * Returns the number of values that have been evicted. 310 */ 311 public synchronized final int evictionCount() { 312 return evictionCount; 313 } 314 315 /** 316 * Returns a copy of the current contents of the cache, ordered from least 317 * recently accessed to most recently accessed. 318 */ 319 public synchronized final Map<K, V> snapshot() { 320 return new LinkedHashMap<K, V>(map); 321 } 322 323 @Override public synchronized final String toString() { 324 int accesses = hitCount + missCount; 325 int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 326 return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 327 maxSize, hitCount, missCount, hitPercent); 328 } 329} 330