View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.shiro.util;
20  
21  import java.lang.ref.ReferenceQueue;
22  import java.lang.ref.SoftReference;
23  import java.util.*;
24  import java.util.concurrent.ConcurrentHashMap;
25  import java.util.concurrent.ConcurrentLinkedQueue;
26  import java.util.concurrent.locks.ReentrantLock;
27  
28  
29  /**
30   * A <code><em>Soft</em>HashMap</code> is a memory-constrained map that stores its <em>values</em> in
31   * {@link SoftReference SoftReference}s.  (Contrast this with the JDK's
32   * {@link WeakHashMap WeakHashMap}, which uses weak references for its <em>keys</em>, which is of little value if you
33   * want the cache to auto-resize itself based on memory constraints).
34   * <p/>
35   * Having the values wrapped by soft references allows the cache to automatically reduce its size based on memory
36   * limitations and garbage collection.  This ensures that the cache will not cause memory leaks by holding strong
37   * references to all of its values.
38   * <p/>
39   * This class is a generics-enabled Map based on initial ideas from Heinz Kabutz's and Sydney Redelinghuys's
40   * <a href="http://www.javaspecialists.eu/archive/Issue015.html">publicly posted version (with their approval)</a>, with
41   * continued modifications.
42   * <p/>
43   * This implementation is thread-safe and usable in concurrent environments.
44   *
45   * @since 1.0
46   */
47  public class SoftHashMap<K, V> implements Map<K, V> {
48  
49      /**
50       * The default value of the RETENTION_SIZE attribute, equal to 100.
51       */
52      private static final int DEFAULT_RETENTION_SIZE = 100;
53  
54      /**
55       * The internal HashMap that will hold the SoftReference.
56       */
57      private final Map<K, SoftValue<V, K>> map;
58  
59      /**
60       * The number of strong references to hold internally, that is, the number of instances to prevent
61       * from being garbage collected automatically (unlike other soft references).
62       */
63      private final int RETENTION_SIZE;
64  
65      /**
66       * The FIFO list of strong references (not to be garbage collected), order of last access.
67       */
68      private final Queue<V> strongReferences; //guarded by 'strongReferencesLock'
69      private final ReentrantLock strongReferencesLock;
70  
71      /**
72       * Reference queue for cleared SoftReference objects.
73       */
74      private final ReferenceQueue<? super V> queue;
75  
76      /**
77       * Creates a new SoftHashMap with a default retention size size of
78       * {@link #DEFAULT_RETENTION_SIZE DEFAULT_RETENTION_SIZE} (100 entries).
79       *
80       * @see #SoftHashMap(int)
81       */
82      public SoftHashMap() {
83          this(DEFAULT_RETENTION_SIZE);
84      }
85  
86      /**
87       * Creates a new SoftHashMap with the specified retention size.
88       * <p/>
89       * The retention size (n) is the total number of most recent entries in the map that will be strongly referenced
90       * (ie 'retained') to prevent them from being eagerly garbage collected.  That is, the point of a SoftHashMap is to
91       * allow the garbage collector to remove as many entries from this map as it desires, but there will always be (n)
92       * elements retained after a GC due to the strong references.
93       * <p/>
94       * Note that in a highly concurrent environments the exact total number of strong references may differ slightly
95       * than the actual <code>retentionSize</code> value.  This number is intended to be a best-effort retention low
96       * water mark.
97       *
98       * @param retentionSize the total number of most recent entries in the map that will be strongly referenced
99       *                      (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 }