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    }