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