001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License. You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied. See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019 package org.apache.shiro.util;
020
021 import java.lang.ref.ReferenceQueue;
022 import java.lang.ref.SoftReference;
023 import java.util.*;
024 import java.util.concurrent.ConcurrentHashMap;
025 import java.util.concurrent.ConcurrentLinkedQueue;
026 import java.util.concurrent.locks.ReentrantLock;
027
028
029 /**
030 * A <code><em>Soft</em>HashMap</code> is a memory-constrained map that stores its <em>values</em> in
031 * {@link SoftReference SoftReference}s. (Contrast this with the JDK's
032 * {@link WeakHashMap WeakHashMap}, which uses weak references for its <em>keys</em>, which is of little value if you
033 * want the cache to auto-resize itself based on memory constraints).
034 * <p/>
035 * Having the values wrapped by soft references allows the cache to automatically reduce its size based on memory
036 * limitations and garbage collection. This ensures that the cache will not cause memory leaks by holding strong
037 * references to all of its values.
038 * <p/>
039 * This class is a generics-enabled Map based on initial ideas from Heinz Kabutz's and Sydney Redelinghuys's
040 * <a href="http://www.javaspecialists.eu/archive/Issue015.html">publicly posted version (with their approval)</a>, with
041 * continued modifications.
042 * <p/>
043 * This implementation is thread-safe and usable in concurrent environments.
044 *
045 * @since 1.0
046 */
047 public class SoftHashMap<K, V> implements Map<K, V> {
048
049 /**
050 * The default value of the RETENTION_SIZE attribute, equal to 100.
051 */
052 private static final int DEFAULT_RETENTION_SIZE = 100;
053
054 /**
055 * The internal HashMap that will hold the SoftReference.
056 */
057 private final Map<K, SoftValue<V, K>> map;
058
059 /**
060 * The number of strong references to hold internally, that is, the number of instances to prevent
061 * from being garbage collected automatically (unlike other soft references).
062 */
063 private final int RETENTION_SIZE;
064
065 /**
066 * The FIFO list of strong references (not to be garbage collected), order of last access.
067 */
068 private final Queue<V> strongReferences; //guarded by 'strongReferencesLock'
069 private final ReentrantLock strongReferencesLock;
070
071 /**
072 * Reference queue for cleared SoftReference objects.
073 */
074 private final ReferenceQueue<? super V> queue;
075
076 /**
077 * Creates a new SoftHashMap with a default retention size size of
078 * {@link #DEFAULT_RETENTION_SIZE DEFAULT_RETENTION_SIZE} (100 entries).
079 *
080 * @see #SoftHashMap(int)
081 */
082 public SoftHashMap() {
083 this(DEFAULT_RETENTION_SIZE);
084 }
085
086 /**
087 * Creates a new SoftHashMap with the specified retention size.
088 * <p/>
089 * The retention size (n) is the total number of most recent entries in the map that will be strongly referenced
090 * (ie 'retained') to prevent them from being eagerly garbage collected. That is, the point of a SoftHashMap is to
091 * allow the garbage collector to remove as many entries from this map as it desires, but there will always be (n)
092 * elements retained after a GC due to the strong references.
093 * <p/>
094 * Note that in a highly concurrent environments the exact total number of strong references may differ slightly
095 * than the actual <code>retentionSize</code> value. This number is intended to be a best-effort retention low
096 * water mark.
097 *
098 * @param retentionSize the total number of most recent entries in the map that will be strongly referenced
099 * (retained), preventing them from being eagerly garbage collected by the JVM.
100 */
101 @SuppressWarnings({"unchecked"})
102 public SoftHashMap(int retentionSize) {
103 super();
104 RETENTION_SIZE = Math.max(0, retentionSize);
105 queue = new ReferenceQueue<V>();
106 strongReferencesLock = new ReentrantLock();
107 map = new ConcurrentHashMap<K, SoftValue<V, K>>();
108 strongReferences = new ConcurrentLinkedQueue<V>();
109 }
110
111 /**
112 * Creates a {@code SoftHashMap} backed by the specified {@code source}, with a default retention
113 * size of {@link #DEFAULT_RETENTION_SIZE DEFAULT_RETENTION_SIZE} (100 entries).
114 *
115 * @param source the backing map to populate this {@code SoftHashMap}
116 * @see #SoftHashMap(Map,int)
117 */
118 public SoftHashMap(Map<K, V> source) {
119 this(DEFAULT_RETENTION_SIZE);
120 putAll(source);
121 }
122
123 /**
124 * Creates a {@code SoftHashMap} backed by the specified {@code source}, with the specified retention size.
125 * <p/>
126 * The retention size (n) is the total number of most recent entries in the map that will be strongly referenced
127 * (ie 'retained') to prevent them from being eagerly garbage collected. That is, the point of a SoftHashMap is to
128 * allow the garbage collector to remove as many entries from this map as it desires, but there will always be (n)
129 * elements retained after a GC due to the strong references.
130 * <p/>
131 * Note that in a highly concurrent environments the exact total number of strong references may differ slightly
132 * than the actual <code>retentionSize</code> value. This number is intended to be a best-effort retention low
133 * water mark.
134 *
135 * @param source the backing map to populate this {@code SoftHashMap}
136 * @param retentionSize the total number of most recent entries in the map that will be strongly referenced
137 * (retained), preventing them from being eagerly garbage collected by the JVM.
138 */
139 public SoftHashMap(Map<K, V> source, int retentionSize) {
140 this(retentionSize);
141 putAll(source);
142 }
143
144 public V get(Object key) {
145 processQueue();
146
147 V result = null;
148 SoftValue<V, K> value = map.get(key);
149
150 if (value != null) {
151 //unwrap the 'real' value from the SoftReference
152 result = value.get();
153 if (result == null) {
154 //The wrapped value was garbage collected, so remove this entry from the backing map:
155 //noinspection SuspiciousMethodCalls
156 map.remove(key);
157 } else {
158 //Add this value to the beginning of the strong reference queue (FIFO).
159 addToStrongReferences(result);
160 }
161 }
162 return result;
163 }
164
165 private void addToStrongReferences(V result) {
166 strongReferencesLock.lock();
167 try {
168 strongReferences.add(result);
169 trimStrongReferencesIfNecessary();
170 } finally {
171 strongReferencesLock.unlock();
172 }
173
174 }
175
176 //Guarded by the strongReferencesLock in the addToStrongReferences method
177
178 private void trimStrongReferencesIfNecessary() {
179 //trim the strong ref queue if necessary:
180 while (strongReferences.size() > RETENTION_SIZE) {
181 strongReferences.poll();
182 }
183 }
184
185 /**
186 * Traverses the ReferenceQueue and removes garbage-collected SoftValue objects from the backing map
187 * by looking them up using the SoftValue.key data member.
188 */
189 private void processQueue() {
190 SoftValue sv;
191 while ((sv = (SoftValue) queue.poll()) != null) {
192 //noinspection SuspiciousMethodCalls
193 map.remove(sv.key); // we can access private data!
194 }
195 }
196
197 public boolean isEmpty() {
198 processQueue();
199 return map.isEmpty();
200 }
201
202 public boolean containsKey(Object key) {
203 processQueue();
204 return map.containsKey(key);
205 }
206
207 public boolean containsValue(Object value) {
208 processQueue();
209 Collection values = values();
210 return values != null && values.contains(value);
211 }
212
213 public void putAll(Map<? extends K, ? extends V> m) {
214 if (m == null || m.isEmpty()) {
215 processQueue();
216 return;
217 }
218 for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
219 put(entry.getKey(), entry.getValue());
220 }
221 }
222
223 public Set<K> keySet() {
224 processQueue();
225 return map.keySet();
226 }
227
228 public Collection<V> values() {
229 processQueue();
230 Collection<K> keys = map.keySet();
231 if (keys.isEmpty()) {
232 //noinspection unchecked
233 return Collections.EMPTY_SET;
234 }
235 Collection<V> values = new ArrayList<V>(keys.size());
236 for (K key : keys) {
237 V v = get(key);
238 if (v != null) {
239 values.add(v);
240 }
241 }
242 return values;
243 }
244
245 /**
246 * Creates a new entry, but wraps the value in a SoftValue instance to enable auto garbage collection.
247 */
248 public V put(K key, V value) {
249 processQueue(); // throw out garbage collected values first
250 SoftValue<V, K> sv = new SoftValue<V, K>(value, key, queue);
251 SoftValue<V, K> previous = map.put(key, sv);
252 addToStrongReferences(value);
253 return previous != null ? previous.get() : null;
254 }
255
256 public V remove(Object key) {
257 processQueue(); // throw out garbage collected values first
258 SoftValue<V, K> raw = map.remove(key);
259 return raw != null ? raw.get() : null;
260 }
261
262 public void clear() {
263 strongReferencesLock.lock();
264 try {
265 strongReferences.clear();
266 } finally {
267 strongReferencesLock.unlock();
268 }
269 processQueue(); // throw out garbage collected values
270 map.clear();
271 }
272
273 public int size() {
274 processQueue(); // throw out garbage collected values first
275 return map.size();
276 }
277
278 public Set<Map.Entry<K, V>> entrySet() {
279 processQueue(); // throw out garbage collected values first
280 Collection<K> keys = map.keySet();
281 if (keys.isEmpty()) {
282 //noinspection unchecked
283 return Collections.EMPTY_SET;
284 }
285
286 Map<K, V> kvPairs = new HashMap<K, V>(keys.size());
287 for (K key : keys) {
288 V v = get(key);
289 if (v != null) {
290 kvPairs.put(key, v);
291 }
292 }
293 return kvPairs.entrySet();
294 }
295
296 /**
297 * We define our own subclass of SoftReference which contains
298 * not only the value but also the key to make it easier to find
299 * the entry in the HashMap after it's been garbage collected.
300 */
301 private static class SoftValue<V, K> extends SoftReference<V> {
302
303 private final K key;
304
305 /**
306 * Constructs a new instance, wrapping the value, key, and queue, as
307 * required by the superclass.
308 *
309 * @param value the map value
310 * @param key the map key
311 * @param queue the soft reference queue to poll to determine if the entry had been reaped by the GC.
312 */
313 private SoftValue(V value, K key, ReferenceQueue<? super V> queue) {
314 super(value, queue);
315 this.key = key;
316 }
317
318 }
319 }