2 * Copyright (C) 2011 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package android.support.v2.util;
19 import java.util.LinkedHashMap;
23 * Static library version of {@code 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
29 public class LruCache<K, V> {
30 private final LinkedHashMap<K, V> map;
32 /** Size of this cache in units. Not necessarily the number of elements. */
37 private int createCount;
38 private int evictionCount;
40 private int missCount;
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.
47 public LruCache(int maxSize) {
49 throw new IllegalArgumentException("maxSize <= 0");
51 this.maxSize = maxSize;
52 this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
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
61 public final V get(K key) {
63 throw new NullPointerException("key == null");
68 mapValue = map.get(key);
69 if (mapValue != null) {
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.
83 V createdValue = create(key);
84 if (createdValue == null) {
90 mapValue = map.put(key, createdValue);
92 if (mapValue != null) {
93 // There was a conflict so undo that last put
94 map.put(key, mapValue);
96 size += safeSizeOf(key, createdValue);
100 if (mapValue != null) {
101 entryRemoved(false, key, createdValue, mapValue);
110 * Caches {@code value} for {@code key}. The value is moved to the head of
113 * @return the previous value mapped by {@code key}.
115 public final V put(K key, V value) {
116 if (key == null || value == null) {
117 throw new NullPointerException("key == null || value == null");
121 synchronized (this) {
123 size += safeSizeOf(key, value);
124 previous = map.put(key, value);
125 if (previous != null) {
126 size -= safeSizeOf(key, previous);
130 if (previous != null) {
131 entryRemoved(false, key, previous, value);
139 * @param maxSize the maximum size of the cache before returning. May be -1
140 * to evict even 0-sized elements.
142 private void trimToSize(int maxSize) {
146 synchronized (this) {
147 if (size < 0 || (map.isEmpty() && size != 0)) {
148 throw new IllegalStateException(getClass().getName()
149 + ".sizeOf() is reporting inconsistent results!");
152 if (size <= maxSize || map.isEmpty()) {
156 Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
157 key = toEvict.getKey();
158 value = toEvict.getValue();
160 size -= safeSizeOf(key, value);
164 entryRemoved(true, key, value, null);
169 * Removes the entry for {@code key} if it exists.
171 * @return the previous value mapped by {@code key}.
173 public final V remove(K key) {
175 throw new NullPointerException("key == null");
179 synchronized (this) {
180 previous = map.remove(key);
181 if (previous != null) {
182 size -= safeSizeOf(key, previous);
186 if (previous != null) {
187 entryRemoved(false, key, previous, null);
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.
199 * <p>The method is called without synchronization: other threads may
200 * access the cache while this method is executing.
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}.
208 protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
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.
215 * <p>The method is called without synchronization: other threads may
216 * access the cache while this method is executing.
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
225 protected V create(K key) {
229 private int safeSizeOf(K key, V value) {
230 int result = sizeOf(key, value);
232 throw new IllegalStateException("Negative size: " + key + "=" + value);
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.
242 * <p>An entry's size must not change while it is in the cache.
244 protected int sizeOf(K key, V value) {
249 * Clear the cache, calling {@link #entryRemoved} on each removed entry.
251 public final void evictAll() {
252 trimToSize(-1); // -1 will evict 0-sized elements
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.
260 public synchronized final int size() {
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.
269 public synchronized final int maxSize() {
274 * Returns the number of times {@link #get} returned a value.
276 public synchronized final int hitCount() {
281 * Returns the number of times {@link #get} returned null or required a new
282 * value to be created.
284 public synchronized final int missCount() {
289 * Returns the number of times {@link #create(Object)} returned a value.
291 public synchronized final int createCount() {
296 * Returns the number of times {@link #put} was called.
298 public synchronized final int putCount() {
303 * Returns the number of values that have been evicted.
305 public synchronized final int evictionCount() {
306 return evictionCount;
310 * Returns a copy of the current contents of the cache, ordered from least
311 * recently accessed to most recently accessed.
313 public synchronized final Map<K, V> snapshot() {
314 return new LinkedHashMap<K, V>(map);
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);