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
17package libcore.util;
18
19import java.util.LinkedHashMap;
20import 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 */
26public class BasicLruCache<K, V> {
27    private final LinkedHashMap<K, V> map;
28    private final int maxSize;
29
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     */
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     */
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
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     */
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     */
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     */
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     */
132    public synchronized final void evictAll() {
133        trimToSize(0);
134    }
135}
136