001package org.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.logging.log4j.Logger;
017
018/**
019 * Simple table cache (key, value) using java soft references.
020 * 
021 * @version IFS 1.3 (Iterative Forward Search)<br>
022 *          Copyright (C) 2006 - 2014 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 * @param <K> key
041 * @param <V> value
042 */
043
044public class SoftCache<K, V> implements Map<K, V> {
045    private static Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(SoftCache.class);
046    private HashMap<K, Reference<V>> iCache = new HashMap<K, Reference<V>>();
047    private ReferenceQueue<V> iQueue = new ReferenceQueue<V>();
048
049    public SoftCache() {
050        new SoftCacheCleanupThread().start();
051    }
052
053    @Override
054    public synchronized boolean isEmpty() {
055        return iCache.isEmpty();
056    }
057
058    @Override
059    public synchronized void clear() {
060        iCache.clear();
061    }
062
063    @Override
064    public synchronized boolean containsKey(Object key) {
065        return iCache.containsKey(key);
066    }
067
068    @Override
069    public synchronized boolean containsValue(Object value) {
070        for (Iterator<Reference<V>> i = iCache.values().iterator(); i.hasNext();) {
071            Reference<V> ref = i.next();
072            if (value.equals(ref.get()))
073                return true;
074        }
075        return false;
076    }
077
078    @Override
079    public synchronized V get(Object key) {
080        Reference<V> ref = iCache.get(key);
081        return (ref == null ? null : ref.get());
082    }
083
084    @Override
085    public synchronized V remove(Object key) {
086        Reference<V> ref = iCache.remove(key);
087        return (ref == null ? null : ref.get());
088    }
089
090    @Override
091    public V put(K key, V value) {
092        return putReference(key, new SoftReference<V>(value, iQueue));
093    }
094
095    public Object putSoft(K key, V value) {
096        return putReference(key, new SoftReference<V>(value, iQueue));
097    }
098
099    public Object putWeak(K key, V value) {
100        return putReference(key, new WeakReference<V>(value, iQueue));
101    }
102
103    private synchronized V putReference(K key, Reference<V> ref) {
104        Reference<V> old = iCache.put(key, ref);
105        return (old == null ? null : old.get());
106    }
107
108    @Override
109    public void putAll(Map<? extends K, ? extends V> map) {
110        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
111            put(entry.getKey(), entry.getValue());
112        }
113    }
114
115    @Override
116    public synchronized int size() {
117        return iCache.size();
118    }
119
120    @Override
121    public synchronized Set<K> keySet() {
122        return iCache.keySet();
123    }
124
125    @Override
126    public synchronized Collection<V> values() {
127        List<V> ret = new ArrayList<V>(iCache.size());
128        for (Reference<V> ref : iCache.values()) {
129            V value = ref.get();
130            if (value != null)
131                ret.add(value);
132        }
133        return ret;
134    }
135
136    @Override
137    public synchronized Set<Map.Entry<K, V>> entrySet() {
138        Set<Map.Entry<K, V>> ret = new HashSet<Map.Entry<K, V>>(iCache.size());
139        for (Map.Entry<K, Reference<V>> entry : iCache.entrySet()) {
140            if (entry.getValue().get() != null)
141                ret.add(new Entry<K, V>(entry.getKey(), entry.getValue().get()));
142
143        }
144        return ret;
145    }
146
147    public synchronized void cleanDeallocated() {
148        int nrCleaned = 0;
149        for (Iterator<Map.Entry<K, Reference<V>>> i = iCache.entrySet().iterator(); i.hasNext();) {
150            Map.Entry<K, Reference<V>> entry = i.next();
151            if (entry.getValue().get() == null) {
152                i.remove();
153                nrCleaned++;
154            }
155        }
156        sLogger.debug("cleaned " + nrCleaned + " of " + (iCache.size() + nrCleaned) + " items.");
157    }
158
159    private ReferenceQueue<V> getQueue() {
160        return iQueue;
161    }
162
163    private class SoftCacheCleanupThread extends Thread {
164        private SoftCacheCleanupThread() {
165            setDaemon(true);
166            setName("SoftCacheCleanup");
167        }
168
169        @Override
170        public void run() {
171            try {
172                while (true) {
173                    ReferenceQueue<V> q = getQueue();
174                    if (q == null)
175                        break; // soft cache deallocated -- stop the thread
176                    if (q.remove(10000) == null)
177                        continue; // was there something deallocated?
178                    while (q.poll() != null) {
179                    } // pull all the deallocated references from the queue
180                    cleanDeallocated(); // clean the cache
181                }
182                sLogger.debug("cache terminated");
183            } catch (Exception e) {
184                sLogger.error("cleanup thread failed, reason:" + e.getMessage(), e);
185            }
186        }
187    }
188
189    private static class Entry<K, V> implements Map.Entry<K, V> {
190        private K iKey = null;
191        private V iValue = null;
192
193        private Entry(K key, V value) {
194            iKey = key;
195            iValue = value;
196        }
197
198        @Override
199        public boolean equals(Object o) {
200            if (o == null || !(o instanceof Map.Entry<?, ?>))
201                return false;
202            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
203            return (getKey() == null ? e.getKey() == null : getKey().equals(e.getKey()))
204                    && (getValue() == null ? e.getValue() == null : getValue().equals(e.getValue()));
205        }
206
207        @Override
208        public int hashCode() {
209            return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode());
210        }
211
212        @Override
213        public K getKey() {
214            return iKey;
215        }
216
217        @Override
218        public V getValue() {
219            return iValue;
220        }
221
222        @Override
223        public V setValue(V value) throws UnsupportedOperationException {
224            throw new UnsupportedOperationException();
225        }
226    }
227
228    public static void test() {
229        for (int t = 0; t < 10; t++) {
230            SoftCache<Integer, byte[]> x = new SoftCache<Integer, byte[]>();
231            for (int i = 0; i < 1000000; i++)
232                x.put(Integer.valueOf(i), new byte[1024]);
233        }
234    }
235}