001    package net.sf.cpsolver.ifs.util;
002    
003    import java.lang.ref.Reference;
004    import java.lang.ref.ReferenceQueue;
005    import java.lang.ref.SoftReference;
006    import java.lang.ref.WeakReference;
007    import java.util.ArrayList;
008    import java.util.Collection;
009    import java.util.HashSet;
010    import java.util.HashMap;
011    import java.util.Iterator;
012    import java.util.List;
013    import java.util.Map;
014    import java.util.Set;
015    
016    import org.apache.log4j.Logger;
017    
018    /**
019     * Simple table cache (key, value) using java soft references.
020     * 
021     * @version IFS 1.2 (Iterative Forward Search)<br>
022     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
023     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
024     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
025     * <br>
026     *          This library is free software; you can redistribute it and/or modify
027     *          it under the terms of the GNU Lesser General Public License as
028     *          published by the Free Software Foundation; either version 3 of the
029     *          License, or (at your option) any later version. <br>
030     * <br>
031     *          This library is distributed in the hope that it will be useful, but
032     *          WITHOUT ANY WARRANTY; without even the implied warranty of
033     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
034     *          Lesser General Public License for more details. <br>
035     * <br>
036     *          You should have received a copy of the GNU Lesser General Public
037     *          License along with this library; if not see
038     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
039     */
040    
041    public class SoftCache<K, V> implements Map<K, V> {
042        private static Logger sLogger = Logger.getLogger(SoftCache.class);
043        private HashMap<K, Reference<V>> iCache = new HashMap<K, Reference<V>>();
044        private ReferenceQueue<V> iQueue = new ReferenceQueue<V>();
045    
046        public SoftCache() {
047            new SoftCacheCleanupThread().start();
048        }
049    
050        @Override
051        public synchronized boolean isEmpty() {
052            return iCache.isEmpty();
053        }
054    
055        @Override
056        public synchronized void clear() {
057            iCache.clear();
058        }
059    
060        @Override
061        public synchronized boolean containsKey(Object key) {
062            return iCache.containsKey(key);
063        }
064    
065        @Override
066        public synchronized boolean containsValue(Object value) {
067            for (Iterator<Reference<V>> i = iCache.values().iterator(); i.hasNext();) {
068                Reference<V> ref = i.next();
069                if (value.equals(ref.get()))
070                    return true;
071            }
072            return false;
073        }
074    
075        @Override
076        public synchronized V get(Object key) {
077            Reference<V> ref = iCache.get(key);
078            return (ref == null ? null : ref.get());
079        }
080    
081        @Override
082        public synchronized V remove(Object key) {
083            Reference<V> ref = iCache.remove(key);
084            return (ref == null ? null : ref.get());
085        }
086    
087        @Override
088        public V put(K key, V value) {
089            return putReference(key, new SoftReference<V>(value, iQueue));
090        }
091    
092        public Object putSoft(K key, V value) {
093            return putReference(key, new SoftReference<V>(value, iQueue));
094        }
095    
096        public Object putWeak(K key, V value) {
097            return putReference(key, new WeakReference<V>(value, iQueue));
098        }
099    
100        private synchronized V putReference(K key, Reference<V> ref) {
101            Reference<V> old = iCache.put(key, ref);
102            return (old == null ? null : old.get());
103        }
104    
105        @Override
106        public void putAll(Map<? extends K, ? extends V> map) {
107            for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
108                put(entry.getKey(), entry.getValue());
109            }
110        }
111    
112        @Override
113        public synchronized int size() {
114            return iCache.size();
115        }
116    
117        @Override
118        public synchronized Set<K> keySet() {
119            return iCache.keySet();
120        }
121    
122        @Override
123        public synchronized Collection<V> values() {
124            List<V> ret = new ArrayList<V>(iCache.size());
125            for (Reference<V> ref : iCache.values()) {
126                V value = ref.get();
127                if (value != null)
128                    ret.add(value);
129            }
130            return ret;
131        }
132    
133        @Override
134        public synchronized Set<Map.Entry<K, V>> entrySet() {
135            Set<Map.Entry<K, V>> ret = new HashSet<Map.Entry<K, V>>(iCache.size());
136            for (Map.Entry<K, Reference<V>> entry : iCache.entrySet()) {
137                if (entry.getValue().get() != null)
138                    ret.add(new Entry<K, V>(entry.getKey(), entry.getValue().get()));
139    
140            }
141            return ret;
142        }
143    
144        public synchronized void cleanDeallocated() {
145            int nrCleaned = 0;
146            for (Iterator<Map.Entry<K, Reference<V>>> i = iCache.entrySet().iterator(); i.hasNext();) {
147                Map.Entry<K, Reference<V>> entry = i.next();
148                if (entry.getValue().get() == null) {
149                    i.remove();
150                    nrCleaned++;
151                }
152            }
153            sLogger.debug("cleaned " + nrCleaned + " of " + (iCache.size() + nrCleaned) + " items.");
154        }
155    
156        private ReferenceQueue<V> getQueue() {
157            return iQueue;
158        }
159    
160        private class SoftCacheCleanupThread extends Thread {
161            private SoftCacheCleanupThread() {
162                setDaemon(true);
163                setName("SoftCacheCleanup");
164            }
165    
166            @Override
167            public void run() {
168                try {
169                    while (true) {
170                        ReferenceQueue<V> q = getQueue();
171                        if (q == null)
172                            break; // soft cache deallocated -- stop the thread
173                        if (q.remove(10000) == null)
174                            continue; // was there something deallocated?
175                        while (q.poll() != null) {
176                        } // pull all the deallocated references from the queue
177                        cleanDeallocated(); // clean the cache
178                    }
179                    sLogger.debug("cache terminated");
180                } catch (Exception e) {
181                    sLogger.error("cleanup thread failed, reason:" + e.getMessage(), e);
182                }
183            }
184        }
185    
186        private static class Entry<K, V> implements Map.Entry<K, V> {
187            private K iKey = null;
188            private V iValue = null;
189    
190            private Entry(K key, V value) {
191                iKey = key;
192                iValue = value;
193            }
194    
195            @Override
196            public boolean equals(Object o) {
197                if (o == null || !(o instanceof Map.Entry<?, ?>))
198                    return false;
199                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
200                return (getKey() == null ? e.getKey() == null : getKey().equals(e.getKey()))
201                        && (getValue() == null ? e.getValue() == null : getValue().equals(e.getValue()));
202            }
203    
204            @Override
205            public int hashCode() {
206                return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode());
207            }
208    
209            @Override
210            public K getKey() {
211                return iKey;
212            }
213    
214            @Override
215            public V getValue() {
216                return iValue;
217            }
218    
219            @Override
220            public V setValue(V value) throws UnsupportedOperationException {
221                throw new UnsupportedOperationException();
222            }
223        }
224    
225        public static void test() {
226            for (int t = 0; t < 10; t++) {
227                SoftCache<Integer, byte[]> x = new SoftCache<Integer, byte[]>();
228                for (int i = 0; i < 1000000; i++)
229                    x.put(new Integer(i), new byte[1024]);
230            }
231        }
232    }