    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}