101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet/* 201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Copyright (C) 2011 The Android Open Source Project 301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Licensed under the Apache License, Version 2.0 (the "License"); 501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * you may not use this file except in compliance with the License. 601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * You may obtain a copy of the License at 701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * http://www.apache.org/licenses/LICENSE-2.0 901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 1001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Unless required by applicable law or agreed to in writing, software 1101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * distributed under the License is distributed on an "AS IS" BASIS, 1201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * See the License for the specific language governing permissions and 1401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * limitations under the License. 1501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 1601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 1701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohetpackage android.util; 1801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 1901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohetimport java.util.LinkedHashMap; 2001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohetimport java.util.Map; 2101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 2201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet/** 2301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * BEGIN LAYOUTLIB CHANGE 2401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * This is a custom version that doesn't use the non standard LinkedHashMap#eldest. 2501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * END LAYOUTLIB CHANGE 2601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 2701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * A cache that holds strong references to a limited number of values. Each time 2801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * a value is accessed, it is moved to the head of a queue. When a value is 2901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * added to a full cache, the value at the end of that queue is evicted and may 3001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * become eligible for garbage collection. 3101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 3201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>If your cached values hold resources that need to be explicitly released, 3301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * override {@link #entryRemoved}. 3401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 3501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>If a cache miss should be computed on demand for the corresponding keys, 3601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * override {@link #create}. This simplifies the calling code, allowing it to 3701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * assume a value will always be returned, even when there's a cache miss. 3801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 3901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>By default, the cache size is measured in the number of entries. Override 4001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * {@link #sizeOf} to size the cache in different units. For example, this cache 4101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * is limited to 4MiB of bitmaps: 4201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <pre> {@code 4301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * int cacheSize = 4 * 1024 * 1024; // 4MiB 4401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { 4501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * protected int sizeOf(String key, Bitmap value) { 4601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * return value.getByteCount(); 4701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * } 4801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * }}</pre> 4901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 5001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>This class is thread-safe. Perform multiple cache operations atomically by 5101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * synchronizing on the cache: <pre> {@code 5201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * synchronized (cache) { 5301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * if (cache.get(key) == null) { 5401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * cache.put(key, value); 5501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * } 5601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * }}</pre> 5701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 5801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>This class does not allow null to be used as a key or value. A return 5901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * value of null from {@link #get}, {@link #put} or {@link #remove} is 6001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * unambiguous: the key was not in the cache. 6101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 6201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part 6301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * of <a href="http://developer.android.com/sdk/compatibility-library.html">Android's 6401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Support Package</a> for earlier releases. 6501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 6601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohetpublic class LruCache<K, V> { 6701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private final LinkedHashMap<K, V> map; 6801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 6901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** Size of this cache in units. Not necessarily the number of elements. */ 7001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int size; 7101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int maxSize; 7201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 7301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int putCount; 7401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int createCount; 7501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int evictionCount; 7601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int hitCount; 7701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int missCount; 7801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 7901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 8001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @param maxSize for caches that do not override {@link #sizeOf}, this is 8101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * the maximum number of entries in the cache. For all other caches, 8201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * this is the maximum sum of the sizes of the entries in this cache. 8301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 8401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public LruCache(int maxSize) { 8501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (maxSize <= 0) { 8601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new IllegalArgumentException("maxSize <= 0"); 8701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 8801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet this.maxSize = maxSize; 8901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 9001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 9101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 9201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 9301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Sets the size of the cache. 9401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @param maxSize The new maximum size. 9501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 9601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @hide 9701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 9801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public void resize(int maxSize) { 9901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (maxSize <= 0) { 10001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new IllegalArgumentException("maxSize <= 0"); 10101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 10201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 10301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 10401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet this.maxSize = maxSize; 10501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 10601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet trimToSize(maxSize); 10701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 10801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 10901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 11001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the value for {@code key} if it exists in the cache or can be 11101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * created by {@code #create}. If a value was returned, it is moved to the 11201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * head of the queue. This returns null if a value is not cached and cannot 11301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * be created. 11401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 11501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public final V get(K key) { 11601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (key == null) { 11701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new NullPointerException("key == null"); 11801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 11901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 12001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet V mapValue; 12101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 12201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet mapValue = map.get(key); 12301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (mapValue != null) { 12401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet hitCount++; 12501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return mapValue; 12601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 12701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet missCount++; 12801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 12901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 13001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /* 13101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Attempt to create a value. This may take a long time, and the map 13201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * may be different when create() returns. If a conflicting value was 13301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * added to the map while create() was working, we leave that value in 13401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * the map and release the created value. 13501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 13601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 13701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet V createdValue = create(key); 13801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (createdValue == null) { 13901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return null; 14001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 14101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 14201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 14301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet createCount++; 14401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet mapValue = map.put(key, createdValue); 14501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 14601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (mapValue != null) { 14701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // There was a conflict so undo that last put 14801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet map.put(key, mapValue); 14901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } else { 15001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet size += safeSizeOf(key, createdValue); 15101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 15201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 15301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 15401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (mapValue != null) { 15501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet entryRemoved(false, key, createdValue, mapValue); 15601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return mapValue; 15701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } else { 15801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet trimToSize(maxSize); 15901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return createdValue; 16001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 16101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 16201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 16301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 16401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Caches {@code value} for {@code key}. The value is moved to the head of 16501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * the queue. 16601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 16701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @return the previous value mapped by {@code key}. 16801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 16901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public final V put(K key, V value) { 17001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (key == null || value == null) { 17101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new NullPointerException("key == null || value == null"); 17201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 17301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 17401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet V previous; 17501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 17601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet putCount++; 17701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet size += safeSizeOf(key, value); 17801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet previous = map.put(key, value); 17901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (previous != null) { 18001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet size -= safeSizeOf(key, previous); 18101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 18201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 18301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 18401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (previous != null) { 18501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet entryRemoved(false, key, previous, value); 18601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 18701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 18801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet trimToSize(maxSize); 18901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return previous; 19001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 19101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 19201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 19301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @param maxSize the maximum size of the cache before returning. May be -1 19401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * to evict even 0-sized elements. 19501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 19601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private void trimToSize(int maxSize) { 19701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet while (true) { 19801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet K key; 19901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet V value; 20001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 20101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (size < 0 || (map.isEmpty() && size != 0)) { 20201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new IllegalStateException(getClass().getName() 20301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet + ".sizeOf() is reporting inconsistent results!"); 20401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 20501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 20601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (size <= maxSize) { 20701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet break; 20801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 20901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 21001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // BEGIN LAYOUTLIB CHANGE 21101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // get the last item in the linked list. 21201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // This is not efficient, the goal here is to minimize the changes 21301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // compared to the platform version. 21401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet Map.Entry<K, V> toEvict = null; 21501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet for (Map.Entry<K, V> entry : map.entrySet()) { 21601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet toEvict = entry; 21701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 21801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet // END LAYOUTLIB CHANGE 21901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 22001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (toEvict == null) { 22101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet break; 22201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 22301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 22401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet key = toEvict.getKey(); 22501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet value = toEvict.getValue(); 22601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet map.remove(key); 22701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet size -= safeSizeOf(key, value); 22801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet evictionCount++; 22901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 23001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 23101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet entryRemoved(true, key, value, null); 23201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 23301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 23401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 23501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 23601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Removes the entry for {@code key} if it exists. 23701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 23801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @return the previous value mapped by {@code key}. 23901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 24001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public final V remove(K key) { 24101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (key == null) { 24201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new NullPointerException("key == null"); 24301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 24401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 24501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet V previous; 24601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet synchronized (this) { 24701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet previous = map.remove(key); 24801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (previous != null) { 24901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet size -= safeSizeOf(key, previous); 25001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 25101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 25201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 25301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (previous != null) { 25401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet entryRemoved(false, key, previous, null); 25501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 25601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 25701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return previous; 25801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 25901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 26001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 26101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Called for entries that have been evicted or removed. This method is 26201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * invoked when a value is evicted to make space, removed by a call to 26301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * {@link #remove}, or replaced by a call to {@link #put}. The default 26401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * implementation does nothing. 26501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 26601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>The method is called without synchronization: other threads may 26701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * access the cache while this method is executing. 26801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 26901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @param evicted true if the entry is being removed to make space, false 27001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * if the removal was caused by a {@link #put} or {@link #remove}. 27101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * @param newValue the new value for {@code key}, if it exists. If non-null, 27201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * this removal was caused by a {@link #put}. Otherwise it was caused by 27301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * an eviction or a {@link #remove}. 27401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 27501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} 27601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 27701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 27801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Called after a cache miss to compute a value for the corresponding key. 27901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the computed value or null if no value can be computed. The 28001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * default implementation returns null. 28101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 28201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>The method is called without synchronization: other threads may 28301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * access the cache while this method is executing. 28401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 28501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>If a value for {@code key} exists in the cache when this method 28601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * returns, the created value will be released with {@link #entryRemoved} 28701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * and discarded. This can occur when multiple threads request the same key 28801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * at the same time (causing multiple values to be created), or when one 28901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * thread calls {@link #put} while another is creating a value for the same 29001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * key. 29101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 29201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet protected V create(K key) { 29301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return null; 29401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 29501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 29601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet private int safeSizeOf(K key, V value) { 29701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet int result = sizeOf(key, value); 29801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet if (result < 0) { 29901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet throw new IllegalStateException("Negative size: " + key + "=" + value); 30001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 30101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return result; 30201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 30301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 30401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 30501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the size of the entry for {@code key} and {@code value} in 30601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * user-defined units. The default implementation returns 1 so that size 30701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * is the number of entries and max size is the maximum number of entries. 30801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * 30901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * <p>An entry's size must not change while it is in the cache. 31001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 31101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet protected int sizeOf(K key, V value) { 31201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return 1; 31301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 31401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 31501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 31601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Clear the cache, calling {@link #entryRemoved} on each removed entry. 31701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 31801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public final void evictAll() { 31901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet trimToSize(-1); // -1 will evict 0-sized elements 32001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 32101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 32201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 32301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * For caches that do not override {@link #sizeOf}, this returns the number 32401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * of entries in the cache. For all other caches, this returns the sum of 32501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * the sizes of the entries in this cache. 32601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 32701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int size() { 32801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return size; 32901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 33001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 33101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 33201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * For caches that do not override {@link #sizeOf}, this returns the maximum 33301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * number of entries in the cache. For all other caches, this returns the 33401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * maximum sum of the sizes of the entries in this cache. 33501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 33601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int maxSize() { 33701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return maxSize; 33801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 33901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 34001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 34101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the number of times {@link #get} returned a value that was 34201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * already present in the cache. 34301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 34401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int hitCount() { 34501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return hitCount; 34601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 34701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 34801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 34901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the number of times {@link #get} returned null or required a new 35001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * value to be created. 35101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 35201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int missCount() { 35301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return missCount; 35401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 35501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 35601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 35701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the number of times {@link #create(Object)} returned a value. 35801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 35901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int createCount() { 36001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return createCount; 36101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 36201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 36301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 36401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the number of times {@link #put} was called. 36501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 36601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int putCount() { 36701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return putCount; 36801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 36901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 37001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 37101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns the number of values that have been evicted. 37201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 37301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final int evictionCount() { 37401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return evictionCount; 37501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 37601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 37701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet /** 37801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * Returns a copy of the current contents of the cache, ordered from least 37901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet * recently accessed to most recently accessed. 38001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet */ 38101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet public synchronized final Map<K, V> snapshot() { 38201b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return new LinkedHashMap<K, V>(map); 38301b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 38401b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet 38501b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet @Override public synchronized final String toString() { 38601b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet int accesses = hitCount + missCount; 38701b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 38801b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 38901b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet maxSize, hitCount, missCount, hitPercent); 39001b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet } 39101b6c755dbcf24e71192dc44757e2eea2a426091Xavier Ducrohet} 392