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 
17 package libcore.util;
18 
19 import java.util.LinkedHashMap;
20 import java.util.Map;
21 
22 /**
23  * A minimal least-recently-used cache for libcore. Prefer {@code
24  * android.util.LruCache} where that is available.
25  */
26 public class BasicLruCache<K, V> {
27     private final LinkedHashMap<K, V> map;
28     private final int maxSize;
29 
BasicLruCache(int maxSize)30     public BasicLruCache(int maxSize) {
31         if (maxSize <= 0) {
32             throw new IllegalArgumentException("maxSize <= 0");
33         }
34         this.maxSize = maxSize;
35         this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
36     }
37 
38     /**
39      * Returns the value for {@code key} if it exists in the cache or can be
40      * created by {@code #create}. If a value was returned, it is moved to the
41      * head of the queue. This returns null if a value is not cached and cannot
42      * be created.
43      */
get(K key)44     public final V get(K key) {
45         if (key == null) {
46             throw new NullPointerException("key == null");
47         }
48 
49         V result;
50         synchronized (this) {
51             result = map.get(key);
52             if (result != null) {
53                 return result;
54             }
55         }
56 
57         // Don't hold any locks while calling create.
58         result = create(key);
59 
60         synchronized (this) {
61             // NOTE: Another thread might have already inserted a value for |key| into the map.
62             // This shouldn't be an observable change as long as create creates equal values for
63             // equal keys. We will however attempt to trim the map twice, but that shouldn't be
64             // a big deal since uses of this class aren't heavily contended (and this class
65             // isn't design for such usage anyway).
66             if (result != null) {
67                 map.put(key, result);
68                 trimToSize(maxSize);
69             }
70         }
71 
72         return result;
73     }
74 
75     /**
76      * Caches {@code value} for {@code key}. The value is moved to the head of
77      * the queue.
78      *
79      * @return the previous value mapped by {@code key}. Although that entry is
80      *     no longer cached, it has not been passed to {@link #entryEvicted}.
81      */
put(K key, V value)82     public synchronized final V put(K key, V value) {
83         if (key == null) {
84             throw new NullPointerException("key == null");
85         } else if (value == null) {
86             throw new NullPointerException("value == null");
87         }
88 
89         V previous = map.put(key, value);
90         trimToSize(maxSize);
91         return previous;
92     }
93 
trimToSize(int maxSize)94     private void trimToSize(int maxSize) {
95         while (map.size() > maxSize) {
96             Map.Entry<K, V> toEvict = map.eldest();
97 
98             K key = toEvict.getKey();
99             V value = toEvict.getValue();
100             map.remove(key);
101 
102             entryEvicted(key, value);
103         }
104     }
105 
106     /**
107      * Called for entries that have reached the tail of the least recently used
108      * queue and are be removed. The default implementation does nothing.
109      */
entryEvicted(K key, V value)110     protected void entryEvicted(K key, V value) {}
111 
112     /**
113      * Called after a cache miss to compute a value for the corresponding key.
114      * Returns the computed value or null if no value can be computed. The
115      * default implementation returns null.
116      */
create(K key)117     protected V create(K key) {
118         return null;
119     }
120 
121     /**
122      * Returns a copy of the current contents of the cache, ordered from least
123      * recently accessed to most recently accessed.
124      */
snapshot()125     public synchronized final Map<K, V> snapshot() {
126         return new LinkedHashMap<K, V>(map);
127     }
128 
129     /**
130      * Clear the cache, calling {@link #entryEvicted} on each removed entry.
131      */
evictAll()132     public synchronized final void evictAll() {
133         trimToSize(0);
134     }
135 }
136