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