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