1/*
2 * The MIT License (MIT)
3 *
4 * Copyright (c) 2014-2016 Christian Schudt
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24
25package rocks.xmpp.util.cache;
26
27import java.util.Collection;
28import java.util.Map;
29import java.util.Queue;
30import java.util.Set;
31import java.util.concurrent.ConcurrentHashMap;
32import java.util.concurrent.ConcurrentLinkedDeque;
33import java.util.function.BiFunction;
34import java.util.function.Function;
35
36/**
37 * A simple concurrent implementation of a least-recently-used cache.
38 * <p>
39 * This cache is keeps a maximal number of items in memory and removes the least-recently-used item, when new items are added.
40 *
41 * @param <K> The key.
42 * @param <V> The value.
43 * @author Christian Schudt
44 * @see <a href="http://javadecodedquestions.blogspot.de/2013/02/java-cache-static-data-loading.html">http://javadecodedquestions.blogspot.de/2013/02/java-cache-static-data-loading.html</a>
45 * @see <a href="http://stackoverflow.com/a/22891780">http://stackoverflow.com/a/22891780</a>
46 */
47public final class LruCache<K, V> implements Map<K, V> {
48 private final int maxEntries;
49
50 private final Map<K, V> map;
51
52 final Queue<K> queue;
53
54 public LruCache(final int maxEntries) {
55 this.maxEntries = maxEntries;
56 this.map = new ConcurrentHashMap<>(maxEntries);
57 // Don't use a ConcurrentLinkedQueue here.
58 // There's a JDK bug, leading to OutOfMemoryError and high CPU usage:
59 // https://bugs.openjdk.java.net/browse/JDK-8054446
60 this.queue = new ConcurrentLinkedDeque<>();
61 }
62
63 @Override
64 public final int size() {
65 return map.size();
66 }
67
68 @Override
69 public final boolean isEmpty() {
70 return map.isEmpty();
71 }
72
73 @Override
74 public final boolean containsKey(final Object key) {
75 return map.containsKey(key);
76 }
77
78 @Override
79 public final boolean containsValue(final Object value) {
80 return map.containsValue(value);
81 }
82
83 @SuppressWarnings("unchecked")
84 @Override
85 public final V get(final Object key) {
86 final V v = map.get(key);
87 if (v != null) {
88 // Remove the key from the queue and re-add it to the tail. It is now the most recently used key.
89 keyUsed((K) key);
90 }
91 return v;
92 }
93
94
95 @Override
96 public final V put(final K key, final V value) {
97 V v = map.put(key, value);
98 keyUsed(key);
99 limit();
100 return v;
101 }
102
103 @Override
104 public final V remove(final Object key) {
105 queue.remove(key);
106 return map.remove(key);
107 }
108
109
110 @Override
111 public final void putAll(final Map<? extends K, ? extends V> m) {
112 for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
113 put(entry.getKey(), entry.getValue());
114 }
115 }
116
117 @Override
118 public final void clear() {
119 queue.clear();
120 map.clear();
121 }
122
123 @Override
124 public final Set<K> keySet() {
125 return map.keySet();
126 }
127
128 @Override
129 public final Collection<V> values() {
130 return map.values();
131 }
132
133 @Override
134 public final Set<Entry<K, V>> entrySet() {
135 return map.entrySet();
136 }
137
138
139 // Default methods
140
141 @Override
142 public final V putIfAbsent(final K key, final V value) {
143 final V v = map.putIfAbsent(key, value);
144 if (v == null) {
145 keyUsed(key);
146 }
147 limit();
148 return v;
149 }
150
151 @Override
152 public final boolean remove(final Object key, final Object value) {
153 final boolean removed = map.remove(key, value);
154 if (removed) {
155 queue.remove(key);
156 }
157 return removed;
158 }
159
160 @Override
161 public final boolean replace(final K key, final V oldValue, final V newValue) {
162 final boolean replaced = map.replace(key, oldValue, newValue);
163 if (replaced) {
164 keyUsed(key);
165 }
166 return replaced;
167 }
168
169 @Override
170 public final V replace(final K key, final V value) {
171 final V v = map.replace(key, value);
172 if (v != null) {
173 keyUsed(key);
174 }
175 return v;
176 }
177
178 @Override
179 public final V computeIfAbsent(final K key, final Function<? super K, ? extends V> mappingFunction) {
180 return map.computeIfAbsent(key, mappingFunction.<V>andThen(v -> {
181 keyUsed(key);
182 limit();
183 return v;
184 }));
185 }
186
187 @Override
188 public final V computeIfPresent(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
189 return map.computeIfPresent(key, remappingFunction.<V>andThen(v -> {
190 keyUsed(key);
191 limit();
192 return v;
193 }));
194 }
195
196 @Override
197 public final V compute(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
198 return map.compute(key, remappingFunction.<V>andThen(v -> {
199 keyUsed(key);
200 limit();
201 return v;
202 }));
203 }
204
205 @Override
206 public final V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
207 return map.merge(key, value, remappingFunction.<V>andThen(v -> {
208 keyUsed(key);
209 limit();
210 return v;
211 }));
212 }
213
214 private void limit() {
215 while (queue.size() > maxEntries) {
216 final K oldestKey = queue.poll();
217 if (oldestKey != null) {
218 map.remove(oldestKey);
219 }
220 }
221 }
222
223 private void keyUsed(final K key) {
224 // remove it from the queue and re-add it, to make it the most recently used key.
225 queue.remove(key);
226 queue.offer(key);
227 }
228}