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