001 package net.sf.cpsolver.ifs.util;
002
003 import java.lang.ref.Reference;
004 import java.lang.ref.ReferenceQueue;
005 import java.lang.ref.SoftReference;
006 import java.lang.ref.WeakReference;
007 import java.util.ArrayList;
008 import java.util.Collection;
009 import java.util.HashSet;
010 import java.util.HashMap;
011 import java.util.Iterator;
012 import java.util.List;
013 import java.util.Map;
014 import java.util.Set;
015
016 import 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 Tomas Muller<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
041 public 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 }