1 package android.util;  
  2   
  3 import java.util.LinkedHashMap;  
  4 import java.util.Map;  
  5   
  6 /** 
  7  * A cache that holds strong references to a limited number of values. Each time 
  8  * a value is accessed, it is moved to the head of a queue. When a value is 
  9  * added to a full cache, the value at the end of that queue is evicted and may 
 10  * become eligible for garbage collection. 
 11  * Cache保存一个强引用来限制内容数量，每当Item被访问的时候，此Item就会移动到队列的头部。
 12  * 当cache已满的时候加入新的item时，在队列尾部的item会被回收。
 13  * <p>If your cached values hold resources that need to be explicitly released, 
 14  * override {@link #entryRemoved}. 
 15  * 如果你cache的某个值需要明确释放，重写entryRemoved()
 16  * <p>If a cache miss should be computed on demand for the corresponding keys, 
 17  * override {@link #create}. This simplifies the calling code, allowing it to 
 18  * assume a value will always be returned, even when there‘s a cache miss. 
 19  * 如果key相对应的item丢掉啦，重写create().这简化了调用代码，即使丢失了也总会返回。
 20  * <p>By default, the cache size is measured in the number of entries. Override 
 21  * {@link #sizeOf} to size the cache in different units. For example, this cache 
 22  * is limited to 4MiB of bitmaps: 默认cache大小是测量的item的数量，重写sizeof计算不同item的
 23  *  大小。
 24  * <pre>   {@code 
 25  *   int cacheSize = 4 * 1024 * 1024; // 4MiB 
 26  *   LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) { 
 27  *       protected int sizeOf(String key, Bitmap value) { 
 28  *           return value.getByteCount(); 
 29  *       } 
 30  *   }}</pre> 
 31  * 
 32  * <p>This class is thread-safe. Perform multiple cache operations atomically by 
 33  * synchronizing on the cache: <pre>   {@code 
 34  *   synchronized (cache) { 
 35  *     if (cache.get(key) == null) { 
 36  *         cache.put(key, value); 
 37  *     } 
 38  *   }}</pre> 
 39  * 
 40  * <p>This class does not allow null to be used as a key or value. A return 
 41  * value of null from {@link #get}, {@link #put} or {@link #remove} is 
 42  * unambiguous: the key was not in the cache.
 43  * 不允许key或者value为null
 44  *  当get（），put（），remove（）返回值为null时，key相应的项不在cache中
 45  */  
 46 public class LruCache<K, V> {  
 47     private final LinkedHashMap<K, V> map;  
 48   
 49     /** Size of this cache in units. Not necessarily the number of elements. */  
 50     private int size; //已经存储的大小
 51     private int maxSize; //规定的最大存储空间
 52   
 53     private int putCount;  //put的次数
 54     private int createCount;  //create的次数
 55     private int evictionCount;  //回收的次数
 56     private int hitCount;  //命中的次数
 57     private int missCount;  //丢失的次数
 58   
 59     /** 
 60      * @param maxSize for caches that do not override {@link #sizeOf}, this is 
 61      *     the maximum number of entries in the cache. For all other caches, 
 62      *     this is the maximum sum of the sizes of the entries in this cache. 
 63      */  
 64     public LruCache(int maxSize) {  
 65         if (maxSize <= 0) {  
 66             throw new IllegalArgumentException("maxSize <= 0");  
 67         }  
 68         this.maxSize = maxSize;  
 69         this.map = new LinkedHashMap<K, V>(0, 0.75f, true);  
 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. 通过key返回相应的item，或者创建返回相应的item。相应的item会移动到队列的头部，
 77      * 如果item的value没有被cache或者不能被创建，则返回null。
 78      */  
 79     public final V get(K key) {  
 80         if (key == null) {  
 81             throw new NullPointerException("key == null");  
 82         }  
 83   
 84         V mapValue;  
 85         synchronized (this) {  
 86             mapValue = map.get(key);  
 87             if (mapValue != null) {  
 88                 hitCount++;  //命中
 89                 return mapValue;  
 90             }  
 91             missCount++;  //丢失
 92         }  
 93   
 94         /* 
 95          * Attempt to create a value. This may take a long time, and the map 
 96          * may be different when create() returns. If a conflicting value was 
 97          * added to the map while create() was working, we leave that value in 
 98          * the map and release the created value. 
 99          * 如果丢失了就试图创建一个item
100          */  
101   
102         V createdValue = create(key);  
103         if (createdValue == null) {  
104             return null;  
105         }  
106   
107         synchronized (this) {  
108             createCount++;//创建++  
109             mapValue = map.put(key, createdValue);  
110   
111             if (mapValue != null) {  
112                 // There was a conflict so undo that last put  
113                 //如果前面存在oldValue，那么撤销put（） 
114                 map.put(key, mapValue);  
115             } else {  
116                 size += safeSizeOf(key, createdValue);  
117             }  
118         }  
119   
120         if (mapValue != null) {  
121             entryRemoved(false, key, createdValue, mapValue);  
122             return mapValue;  
123         } else {  
124             trimToSize(maxSize);  
125             return createdValue;  
126         }  
127     }  
128   
129     /** 
130      * Caches {@code value} for {@code key}. The value is moved to the head of 
131      * the queue. 
132      * 
133      * @return the previous value mapped by {@code key}. 
134      */  
135     public final V put(K key, V value) {  
136         if (key == null || value == null) {  
137             throw new NullPointerException("key == null || value == null");  
138         }  
139   
140         V previous;  
141         synchronized (this) {  
142             putCount++;  
143             size += safeSizeOf(key, value);  
144             previous = map.put(key, value);  
145             if (previous != null) {  //返回的先前的value值
146                 size -= safeSizeOf(key, previous);  
147             }  
148         }  
149   
150         if (previous != null) {  
151             entryRemoved(false, key, previous, value);  
152         }  
153   
154         trimToSize(maxSize);  
155         return previous;  
156     }  
157   
158     /** 
159      * @param maxSize the maximum size of the cache before returning. May be -1 
160      *     to evict even 0-sized elements. 
161      *  清空cache空间
162      */  
163     private void trimToSize(int maxSize) {  
164         while (true) {  
165             K key;  
166             V value;  
167             synchronized (this) {  
168                 if (size < 0 || (map.isEmpty() && size != 0)) {  
169                     throw new IllegalStateException(getClass().getName()  
170                             + ".sizeOf() is reporting inconsistent results!");  
171                 }  
172   
173                 if (size <= maxSize) {  
174                     break;  
175                 }  
176   
177                 Map.Entry<K, V> toEvict = map.eldest();  
178                 if (toEvict == null) {  
179                     break;  
180                 }  
181   
182                 key = toEvict.getKey();  
183                 value = toEvict.getValue();  
184                 map.remove(key);  
185                 size -= safeSizeOf(key, value);  
186                 evictionCount++;  
187             }  
188   
189             entryRemoved(true, key, value, null);  
190         }  
191     }  
192   
193     /** 
194      * Removes the entry for {@code key} if it exists. 
195      * 删除key相应的cache项，返回相应的value
196      * @return the previous value mapped by {@code key}. 
197      */  
198     public final V remove(K key) {  
199         if (key == null) {  
200             throw new NullPointerException("key == null");  
201         }  
202   
203         V previous;  
204         synchronized (this) {  
205             previous = map.remove(key);  
206             if (previous != null) {  
207                 size -= safeSizeOf(key, previous);  
208             }  
209         }  
210   
211         if (previous != null) {  
212             entryRemoved(false, key, previous, null);  
213         }  
214   
215         return previous;  
216     }  
217   
218     /** 
219      * Called for entries that have been evicted or removed. This method is 
220      * invoked when a value is evicted to make space, removed by a call to 
221      * {@link #remove}, or replaced by a call to {@link #put}. The default 
222      * implementation does nothing. 
223      * 当item被回收或者删掉时调用。改方法当value被回收释放存储空间时被remove调用，
224      * 或者替换item值时put调用，默认实现什么都没做。
225      * <p>The method is called without synchronization: other threads may 
226      * access the cache while this method is executing. 
227      * 
228      * @param evicted true if the entry is being removed to make space, false 
229      *     if the removal was caused by a {@link #put} or {@link #remove}. 
230      * true---为释放空间被删除；false---put或remove导致
231      * @param newValue the new value for {@code key}, if it exists. If non-null, 
232      *     this removal was caused by a {@link #put}. Otherwise it was caused by 
233      *     an eviction or a {@link #remove}. 
234      */  
235     protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}  
236   
237     /** 
238      * Called after a cache miss to compute a value for the corresponding key. 
239      * Returns the computed value or null if no value can be computed. The 
240      * default implementation returns null. 
241      * 当某Item丢失时会调用到，返回计算的相应的value或者null
242      * <p>The method is called without synchronization: other threads may 
243      * access the cache while this method is executing. 
244      * 
245      * <p>If a value for {@code key} exists in the cache when this method 
246      * returns, the created value will be released with {@link #entryRemoved} 
247      * and discarded. This can occur when multiple threads request the same key 
248      * at the same time (causing multiple values to be created), or when one 
249      * thread calls {@link #put} while another is creating a value for the same 
250      * key. 
251      */  
252     protected V create(K key) {  
253         return null;  
254     }  
255   
256     private int safeSizeOf(K key, V value) {  
257         int result = sizeOf(key, value);  
258         if (result < 0) {  
259             throw new IllegalStateException("Negative size: " + key + "=" + value);  
260         }  
261         return result;  
262     }  
263   
264     /** 
265      * Returns the size of the entry for {@code key} and {@code value} in 
266      * user-defined units.  The default implementation returns 1 so that size 
267      * is the number of entries and max size is the maximum number of entries. 
268      * 返回用户定义的item的大小，默认返回1代表item的数量，最大size就是最大item值
269      * <p>An entry‘s size must not change while it is in the cache. 
270      */  
271     protected int sizeOf(K key, V value) {  
272         return 1;  
273     }  
274   
275     /** 
276      * Clear the cache, calling {@link #entryRemoved} on each removed entry. 
277      * 清空cacke
278      */  
279     public final void evictAll() {  
280         trimToSize(-1); // -1 will evict 0-sized elements  
281     }  
282   
283     /** 
284      * For caches that do not override {@link #sizeOf}, this returns the number 
285      * of entries in the cache. For all other caches, this returns the sum of 
286      * the sizes of the entries in this cache. 
287      */  
288     public synchronized final int size() {  
289         return size;  
290     }  
291   
292     /** 
293      * For caches that do not override {@link #sizeOf}, this returns the maximum 
294      * number of entries in the cache. For all other caches, this returns the 
295      * maximum sum of the sizes of the entries in this cache. 
296      */  
297     public synchronized final int maxSize() {  
298         return maxSize;  
299     }  
300   
301     /** 
302      * Returns the number of times {@link #get} returned a value that was 
303      * already present in the cache. 
304      */  
305     public synchronized final int hitCount() {  
306         return hitCount;  
307     }  
308   
309     /** 
310      * Returns the number of times {@link #get} returned null or required a new 
311      * value to be created. 
312      */  
313     public synchronized final int missCount() {  
314         return missCount;  
315     }  
316   
317     /** 
318      * Returns the number of times {@link #create(Object)} returned a value. 
319      */  
320     public synchronized final int createCount() {  
321         return createCount;  
322     }  
323   
324     /** 
325      * Returns the number of times {@link #put} was called. 
326      */  
327     public synchronized final int putCount() {  
328         return putCount;  
329     }  
330   
331     /** 
332      * Returns the number of values that have been evicted. 
333      * 返回被回收的数量
334      */  
335     public synchronized final int evictionCount() {  
336         return evictionCount;  
337     }  
338   
339     /** 
340      * Returns a copy of the current contents of the cache, ordered from least 
341      * recently accessed to most recently accessed. 返回当前cache的副本，从最近最少访问到最多访问
342      */  
343     public synchronized final Map<K, V> snapshot() {  
344         return new LinkedHashMap<K, V>(map);  
345     }  
346   
347     @Override public synchronized final String toString() {  
348         int accesses = hitCount + missCount;  
349         int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;  
350         return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",  
351                 maxSize, hitCount, missCount, hitPercent);  
352     }  
353 }