    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.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 = Logger.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(new Integer(i), new byte[1024]);
    233        }
    234    }
    235}