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}