1/**
2 * Copyright (c) 2011, Google Inc.
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 com.android.mail.utils;
18
19import java.util.LinkedHashMap;
20import java.util.Map;
21
22/**
23 * A simple in-memory LRU cache, which is trivial to implement on top
24 * of JDK's {@link LinkedHashMap}.
25 *
26 * LRU policy is ensured by the underlying LinkedHashMap functionality.
27 */
28public final class LruCache<K, V> extends LinkedHashMap<K, V> {
29    private static final long serialVersionUID = 1L;
30    private final int maxCapacity;
31
32    /**
33     * Creates an instance of LRUCache, with given capacity.
34     *
35     * @param capacity maximum number of elements in the cache. This is also
36     * used as initialCapacity i.e. memory is allocated upfront.
37     */
38    public LruCache(int capacity) {
39        this(capacity, capacity);
40    }
41
42    /**
43     * Creates an instance of LRUCache, with given capacity.
44     *
45     * @param initialCapacity initial capacity of the cache.
46     * @param maxCapacity maximum number of elements in the cache.
47     */
48    private LruCache(int initialCapacity, int maxCapacity) {
49        super(initialCapacity, (float) 0.75, true);
50        this.maxCapacity = maxCapacity;
51    }
52
53    // These methods are needed because the default implementation of LinkedHashMap is *not*
54    // synchronized.
55    /**
56     * Gets an element from the cache, returning the element if found, or null if not
57     * @param key
58     * @return
59     */
60    public synchronized V getElement(K key) {
61        return get(key);
62    }
63
64    /**
65     * Puts an element into the cache.
66     * @param key
67     * @param value, a non-null value.
68     */
69    public synchronized void putElement(K key, V value) {
70        put(key, value);
71    }
72
73    /**
74     * Removes an element from the cache. Returns the removed element, or null if no such element
75     * existed in the cache.
76     * @param key
77     * @return
78     */
79    public synchronized V removeElement(K key) {
80        return remove(key);
81    }
82
83    /**
84     * {@inheritDoc}
85     * <p>
86     * Necessary to override because HashMap increases the capacity of the
87     * hashtable before inserting the elements. However, here we call put() which
88     * checks if we can remove the eldest element before increasing the capacity.
89     */
90    @Override
91    public synchronized void putAll(Map<? extends K, ? extends V> m) {
92        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
93            put(e.getKey(), e.getValue());
94        }
95    }
96
97    /**
98     * This method is called by LinkedHashMap to check whether the eldest entry
99     * should be removed.
100     *
101     * @param eldest
102     * @return true if element should be removed.
103     */
104    @Override
105    protected synchronized boolean removeEldestEntry(Map.Entry<K, V> eldest) {
106        return size() > maxCapacity;
107    }
108}
109