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