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 synchronized final V get(K key) {
45        if (key == null) {
46            throw new NullPointerException();
47        }
48
49        V result = map.get(key);
50        if (result != null) {
51            return result;
52        }
53
54        result = create(key);
55
56        if (result != null) {
57            map.put(key, result);
58            trimToSize(maxSize);
59        }
60        return result;
61    }
62
63    /**
64     * Caches {@code value} for {@code key}. The value is moved to the head of
65     * the queue.
66     *
67     * @return the previous value mapped by {@code key}. Although that entry is
68     *     no longer cached, it has not been passed to {@link #entryEvicted}.
69     */
70    public synchronized final V put(K key, V value) {
71        if (key == null || value == null) {
72            throw new NullPointerException();
73        }
74
75        V previous = map.put(key, value);
76        trimToSize(maxSize);
77        return previous;
78    }
79
80    private void trimToSize(int maxSize) {
81        while (map.size() > maxSize) {
82            Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
83
84            K key = toEvict.getKey();
85            V value = toEvict.getValue();
86            map.remove(key);
87
88            entryEvicted(key, value);
89        }
90    }
91
92    /**
93     * Called for entries that have reached the tail of the least recently used
94     * queue and are be removed. The default implementation does nothing.
95     */
96    protected void entryEvicted(K key, V value) {
97    }
98
99    /**
100     * Called after a cache miss to compute a value for the corresponding key.
101     * Returns the computed value or null if no value can be computed. The
102     * default implementation returns null.
103     */
104    protected V create(K key) {
105        return null;
106    }
107
108    /**
109     * Returns a copy of the current contents of the cache, ordered from least
110     * recently accessed to most recently accessed.
111     */
112    public synchronized final Map<K, V> snapshot() {
113        return new LinkedHashMap<K, V>(map);
114    }
115
116    /**
117     * Clear the cache, calling {@link #entryEvicted} on each removed entry.
118     */
119    public synchronized final void evictAll() {
120        trimToSize(0);
121    }
122}
123