001package net.sf.cpsolver.ifs.util;
002
003import java.lang.ref.Reference;
004import java.lang.ref.ReferenceQueue;
005import java.lang.ref.SoftReference;
006import java.lang.ref.WeakReference;
007import java.util.ArrayList;
008import java.util.Collection;
009import java.util.HashSet;
010import java.util.HashMap;
011import java.util.Iterator;
012import java.util.List;
013import java.util.Map;
014import java.util.Set;
015
016import 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 Tomáš Müller<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
041public 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}