1package com.bumptech.glide.util;
2
3import java.util.LinkedHashMap;
4import java.util.Map;
5
6/**
7 * A general purpose size limited cache that evicts items using an LRU algorithm. By default every item is assumed to
8 * have a size of one. Subclasses can override {@link #getSize(Object)}} to change the size on a per item basis.
9 *
10 * @param <T> The type of the keys.
11 * @param <Y> The type of the values.
12 */
13public class LruCache<T, Y> {
14    private final LinkedHashMap<T, Y> cache = new LinkedHashMap<T, Y>(100, 0.75f, true);
15    private int maxSize;
16    private final int initialMaxSize;
17    private int currentSize = 0;
18
19    /**
20     * Constructor for LruCache.
21     *
22     * @param size The maximum size of the cache, the units must match the units used in {@link #getSize(Object)}.
23     */
24    public LruCache(int size) {
25        this.initialMaxSize = size;
26        this.maxSize = size;
27    }
28
29    /**
30     * Sets a size multiplier that will be applied to the size provided in the constructor to set the new size of the
31     * cache. If the new size is less than the current size, entries will be evicted until the current size is less
32     * than or equal to the new size.
33     *
34     * @param multiplier The multiplier to apply.
35     */
36    public void setSizeMultiplier(float multiplier) {
37        if (multiplier < 0) {
38            throw new IllegalArgumentException("Multiplier must be >= 0");
39        }
40        maxSize = Math.round(initialMaxSize * multiplier);
41        evict();
42    }
43
44    /**
45     * Returns the size of a given item, defaulting to one. The units must match those used in the size passed in to the
46     * constructor. Subclasses can override this method to return sizes in various units, usually bytes.
47     *
48     * @param item The item to get the size of.
49     */
50    protected int getSize(Y item) {
51        return 1;
52    }
53
54    /**
55     * A callback called whenever an item is evicted from the cache. Subclasses can override.
56     *
57     * @param key The key of the evicted item.
58     * @param item The evicted item.
59     */
60    protected void onItemEvicted(T key, Y item) {
61        // optional override
62    }
63
64    /**
65     * Returns the current maximum size of the cache in bytes.
66     */
67    public int getMaxSize() {
68        return maxSize;
69    }
70
71    /**
72     * Returns the sum of the sizes of all items in the cache.
73     */
74    public int getCurrentSize() {
75        return currentSize;
76    }
77
78    /**
79     * Returns true if there is a value for the given key in the cache.
80     *
81     * @param key The key to check.
82     */
83
84    public boolean contains(T key) {
85        return cache.containsKey(key);
86    }
87
88    /**
89     * Returns the item in the cache for the given key or null if no such item exists.
90     *
91     * @param key The key to check.
92     */
93    public Y get(T key) {
94        return cache.get(key);
95    }
96
97    /**
98     * Adds the given item to the cache with the given key and returns any previous entry for the given key that may
99     * have already been in the cache.
100     *
101     * <p>
102     *     If the size of the item is larger than the total cache size, the item will not be added to the cache and
103     *     instead {@link #onItemEvicted(Object, Object)} will be called synchronously with the given key and item.
104     * </p>
105     *
106     * @param key The key to add the item at.
107     * @param item The item to add.
108     */
109    public Y put(T key, Y item) {
110        final int itemSize = getSize(item);
111        if (itemSize >= maxSize) {
112            onItemEvicted(key, item);
113            return null;
114        }
115
116        final Y result = cache.put(key, item);
117        if (item != null) {
118            currentSize += getSize(item);
119        }
120        if (result != null) {
121            // TODO: should we call onItemEvicted here?
122            currentSize -= getSize(result);
123        }
124        evict();
125
126        return result;
127    }
128
129    /**
130     * Removes the item at the given key and returns the removed item if present, and null otherwise.
131     *
132     * @param key The key to remove the item at.
133     */
134    public Y remove(T key) {
135        final Y value = cache.remove(key);
136        if (value != null) {
137            currentSize -= getSize(value);
138        }
139        return value;
140    }
141
142    /**
143     * Clears all items in the cache.
144     */
145    public void clearMemory() {
146        trimToSize(0);
147    }
148
149    /**
150     * Removes the least recently used items from the cache until the current size is less than the given size.
151     *
152     * @param size The size the cache should be less than.
153     */
154    protected void trimToSize(int size) {
155        Map.Entry<T, Y> last;
156        while (currentSize > size) {
157            last = cache.entrySet().iterator().next();
158            final Y toRemove = last.getValue();
159            currentSize -= getSize(toRemove);
160            final T key = last.getKey();
161            cache.remove(key);
162            onItemEvicted(key, toRemove);
163        }
164    }
165
166    private void evict() {
167        trimToSize(maxSize);
168    }
169}
170