001: /**
002: * Based on JDK 1.3.1 WeakHashMap
003: */package clime.messadmin.providers;
004:
005: import java.lang.ref.ReferenceQueue;
006: import java.lang.ref.SoftReference;
007:
008: import java.util.AbstractMap;
009: import java.util.AbstractSet;
010: import java.util.HashMap;
011: import java.util.Iterator;
012: import java.util.Map;
013: import java.util.NoSuchElementException;
014: import java.util.Set;
015:
016: /**
017: * A hashtable-based <code>Map</code> implementation with <em>soft keys</em>.
018: * An entry in a <code>SoftHashMap</code> will automatically be removed when
019: * its key is no longer in ordinary use. More precisely, the presence of a
020: * mapping for a given key will not prevent the key from being discarded by the
021: * garbage collector, that is, made finalizable, finalized, and then reclaimed.
022: * When a key has been discarded its entry is effectively removed from the map,
023: * so this class behaves somewhat differently than other <code>Map</code>
024: * implementations.
025: *
026: * <p> Both null values and the null key are supported. This class has
027: * performance characteristics similar to those of the <code>HashMap</code>
028: * class, and has the same efficiency parameters of <em>initial capacity</em>
029: * and <em>load factor</em>.
030: *
031: * <p> Like most collection classes, this class is not synchronized. A
032: * synchronized <code>SoftHashMap</code> may be constructed using the
033: * <code>Collections.synchronizedMap</code> method.
034: *
035: * <p> This class is intended primarily for use with key objects whose
036: * <code>equals</code> methods test for object identity using the
037: * <code>==</code> operator. Once such a key is discarded it can never be
038: * recreated, so it is impossible to do a lookup of that key in a
039: * <code>SoftHashMap</code> at some later time and be surprised that its entry
040: * has been removed. This class will work perfectly well with key objects
041: * whose <code>equals</code> methods are not based upon object identity, such
042: * as <code>String</code> instances. With such recreatable key objects,
043: * however, the automatic removal of <code>SoftHashMap</code> entries whose
044: * keys have been discarded may prove to be confusing.
045: *
046: * <p> The behavior of the <code>SoftHashMap</code> class depends in part upon
047: * the actions of the garbage collector, so several familiar (though not
048: * required) <code>Map</code> invariants do not hold for this class. Because
049: * the garbage collector may discard keys at any time, a
050: * <code>SoftHashMap</code> may behave as though an unknown thread is silently
051: * removing entries. In particular, even if you synchronize on a
052: * <code>SoftHashMap</code> instance and invoke none of its mutator methods, it
053: * is possible for the <code>size</code> method to return smaller values over
054: * time, for the <code>isEmpty</code> method to return <code>false</code> and
055: * then <code>true</code>, for the <code>containsKey</code> method to return
056: * <code>true</code> and later <code>false</code> for a given key, for the
057: * <code>get</code> method to return a value for a given key but later return
058: * <code>null</code>, for the <code>put</code> method to return
059: * <code>null</code> and the <code>remove</code> method to return
060: * <code>false</code> for a key that previously appeared to be in the map, and
061: * for successive examinations of the key set, the value set, and the entry set
062: * to yield successively smaller numbers of elements.
063: *
064: * <p> Each key object in a <code>SoftHashMap</code> is stored indirectly as
065: * the referent of a soft reference. Therefore a key will automatically be
066: * removed only after the soft references to it, both inside and outside of the
067: * map, have been cleared by the garbage collector.
068: *
069: * <p> <strong>Implementation note:</strong> The value objects in a
070: * <code>SoftHashMap</code> are held by ordinary strong references. Thus care
071: * should be taken to ensure that value objects do not strongly refer to their
072: * own keys, either directly or indirectly, since that will prevent the keys
073: * from being discarded. Note that a value object may refer indirectly to its
074: * key via the <code>SoftHashMap</code> itself; that is, a value object may
075: * strongly refer to some other key object whose associated value object, in
076: * turn, strongly refers to the key of the first value object. One way
077: * to deal with this is to wrap values themselves within
078: * <tt>SoftReferences</tt> before
079: * inserting, as in: <tt>m.put(key, new SoftReference(value))</tt>,
080: * and then unwrapping upon each <tt>get</tt>.
081: *
082: * @version 1.13, 02/06/02
083: * @author Mark Reinhold, Cédrik LIME
084: * @see java.util.HashMap
085: * @see java.lang.ref.SoftReference
086: */
087: class SoftHashMap extends AbstractMap implements Map {
088:
089: /*
090: * A SoftHashMap is implemented as a HashMap that maps SoftKeys to values.
091: * Because we don't have access to the innards of the HashMap, the various
092: * query methods must create a temporary SoftKey every time a lookup is
093: * done. Fortunately these are small, short-lived objects, so the added
094: * allocation overhead is tolerable.
095: */
096:
097: static private class SoftKey extends SoftReference {
098: /*
099: * Hashcode of key, stored here since the key may be tossed by the GC
100: */
101: private int hash;
102:
103: private SoftKey(Object k) {
104: super (k);
105: hash = k.hashCode();
106: }
107:
108: protected/*private*/static SoftKey create(Object k) {
109: if (k == null)
110: return null;
111: else
112: return new SoftKey(k);
113: }
114:
115: private SoftKey(Object k, ReferenceQueue q) {
116: super (k, q);
117: hash = k.hashCode();
118: }
119:
120: protected/*private*/static SoftKey create(Object k,
121: ReferenceQueue q) {
122: if (k == null)
123: return null;
124: else
125: return new SoftKey(k, q);
126: }
127:
128: /*
129: * A SoftKey is equal to another SoftKey iff they both refer to objects
130: * that are, in turn, equal according to their own equals methods
131: */
132: public boolean equals(Object o) {
133: if (this == o)
134: return true;
135: if (!(o instanceof SoftKey))
136: return false;
137: Object t = this .get();
138: Object u = ((SoftKey) o).get();
139: if ((t == null) || (u == null))
140: return false;
141: if (t == u)
142: return true;
143: return t.equals(u);
144: }
145:
146: public int hashCode() {
147: return hash;
148: }
149: }
150:
151: /* Hash table mapping SoftKeys to values */
152: protected/*private*/Map hash;
153:
154: /* Reference queue for cleared SoftKeys */
155: private ReferenceQueue queue = new ReferenceQueue();
156:
157: /*
158: * Remove all invalidated entries from the map, that is, remove all entries
159: * whose keys have been discarded. This method should be invoked once by
160: * each public mutator in this class. We don't invoke this method in public
161: * accessors because that can lead to surprising
162: * ConcurrentModificationExceptions.
163: */
164: protected/*private*/void processQueue() {
165: SoftKey sk;
166: while ((sk = (SoftKey) queue.poll()) != null) {
167: hash.remove(sk);
168: }
169: }
170:
171: /* -- Constructors -- */
172:
173: /**
174: * Constructs a new, empty <code>SoftHashMap</code> with the given
175: * initial capacity and the given load factor.
176: *
177: * @param initialCapacity
178: * The initial capacity of the <code>SoftHashMap</code>
179: *
180: * @param loadFactor
181: * The load factor of the <code>SoftHashMap</code>
182: *
183: * @throws IllegalArgumentException
184: * If the initial capacity is less than zero, or if the load
185: * factor is nonpositive
186: */
187: public SoftHashMap(int initialCapacity, float loadFactor) {
188: hash = new HashMap(initialCapacity, loadFactor);
189: }
190:
191: /**
192: * Constructs a new, empty <code>SoftHashMap</code> with the given initial
193: * capacity and the default load factor, which is <code>0.75</code>.
194: *
195: * @param initialCapacity
196: * The initial capacity of the <code>SoftHashMap</code>
197: *
198: * @throws IllegalArgumentException
199: * If the initial capacity is less than zero
200: */
201: public SoftHashMap(int initialCapacity) {
202: hash = new HashMap(initialCapacity);
203: }
204:
205: /**
206: * Constructs a new, empty <code>SoftHashMap</code> with the default
207: * initial capacity and the default load factor, which is <code>0.75</code>.
208: */
209: public SoftHashMap() {
210: hash = new HashMap();
211: }
212:
213: /**
214: * Constructs a new <code>SoftHashMap</code> with the same mappings as the
215: * specified <tt>Map</tt>. The <code>SoftHashMap</code> is created with an
216: * initial capacity of twice the number of mappings in the specified map
217: * or 11 (whichever is greater), and a default load factor, which is
218: * <tt>0.75</tt>.
219: *
220: * @param t
221: * the map whose mappings are to be placed in this map.
222: * @since 1.3
223: */
224: public SoftHashMap(Map t) {
225: this (Math.max(2 * t.size(), 11), 0.75f);
226: putAll(t);
227: }
228:
229: /* -- Simple queries -- */
230:
231: /**
232: * Returns the number of key-value mappings in this map.
233: * <strong>Note:</strong> <em>In contrast with most implementations of the
234: * <code>Map</code> interface, the time required by this operation is
235: * linear in the size of the map.</em>
236: */
237: public int size() {
238: return entrySet().size();
239: }
240:
241: /**
242: * Returns <code>true</code> if this map contains no key-value mappings.
243: */
244: public boolean isEmpty() {
245: return entrySet().isEmpty();
246: }
247:
248: /**
249: * Returns <code>true</code> if this map contains a mapping for the
250: * specified key.
251: *
252: * @param key
253: * The key whose presence in this map is to be tested
254: */
255: public boolean containsKey(Object key) {
256: return hash.containsKey(SoftKey.create(key));
257: }
258:
259: /* -- Lookup and modification operations -- */
260:
261: /**
262: * Returns the value to which this map maps the specified <code>key</code>.
263: * If this map does not contain a value for this key, then return
264: * <code>null</code>.
265: *
266: * @param key
267: * The key whose associated value, if any, is to be returned
268: */
269: public Object get(Object key) {
270: return hash.get(SoftKey.create(key));
271: }
272:
273: /**
274: * Updates this map so that the given <code>key</code> maps to the given
275: * <code>value</code>. If the map previously contained a mapping for
276: * <code>key</code> then that mapping is replaced and the previous value
277: * is returned.
278: *
279: * @param key
280: * The key that is to be mapped to the given <code>value</code>
281: * @param value
282: * The value to which the given <code>key</code> is to be
283: * mapped
284: *
285: * @return The previous value to which this key was mapped, or
286: * <code>null</code> if if there was no mapping for the key
287: */
288: public Object put(Object key, Object value) {
289: processQueue();
290: return hash.put(SoftKey.create(key, queue), value);
291: }
292:
293: /**
294: * Removes the mapping for the given <code>key</code> from this map, if
295: * present.
296: *
297: * @param key
298: * The key whose mapping is to be removed
299: *
300: * @return The value to which this key was mapped, or <code>null</code> if
301: * there was no mapping for the key
302: */
303: public Object remove(Object key) {
304: processQueue();
305: return hash.remove(SoftKey.create(key));
306: }
307:
308: /**
309: * Removes all mappings from this map.
310: */
311: public void clear() {
312: processQueue();
313: hash.clear();
314: }
315:
316: /* -- Views -- */
317:
318: /* Internal class for entries */
319: static private class Entry implements Map.Entry {
320: private Map.Entry ent;
321: /*
322: * Strong reference to key, so that the GC will
323: * leave it alone as long as this Entry exists
324: */
325: private Object key;
326:
327: Entry(Map.Entry ent, Object key) {
328: this .ent = ent;
329: this .key = key;
330: }
331:
332: public Object getKey() {
333: return key;
334: }
335:
336: public Object getValue() {
337: return ent.getValue();
338: }
339:
340: public Object setValue(Object value) {
341: return ent.setValue(value);
342: }
343:
344: private static boolean valEquals(Object o1, Object o2) {
345: return (o1 == null) ? (o2 == null) : o1.equals(o2);
346: }
347:
348: public boolean equals(Object o) {
349: if (!(o instanceof Map.Entry))
350: return false;
351: Map.Entry e = (Map.Entry) o;
352: return valEquals(key, e.getKey())
353: && valEquals(getValue(), e.getValue());
354: }
355:
356: public int hashCode() {
357: Object v;
358: return (((key == null) ? 0 : key.hashCode()) ^ (((v = getValue()) == null) ? 0
359: : v.hashCode()));
360: }
361: }
362:
363: /* Internal class for entry sets */
364: private class EntrySet extends AbstractSet {
365: Set hashEntrySet = hash.entrySet();
366:
367: public Iterator iterator() {
368: return new Iterator() {
369: Iterator hashIterator = hashEntrySet.iterator();
370: Entry next = null;
371:
372: public boolean hasNext() {
373: while (hashIterator.hasNext()) {
374: Map.Entry ent = (Map.Entry) hashIterator.next();
375: SoftKey sk = (SoftKey) ent.getKey();
376: Object k = null;
377: if ((sk != null) && ((k = sk.get()) == null)) {
378: /* Soft key has been cleared by GC */
379: continue;
380: }
381: next = new Entry(ent, k);
382: return true;
383: }
384: return false;
385: }
386:
387: public Object next() {
388: if ((next == null) && !hasNext())
389: throw new NoSuchElementException();
390: Entry e = next;
391: next = null;
392: return e;
393: }
394:
395: public void remove() {
396: hashIterator.remove();
397: }
398: };
399: }
400:
401: public boolean isEmpty() {
402: return !(iterator().hasNext());
403: }
404:
405: public int size() {
406: int j = 0;
407: for (Iterator i = iterator(); i.hasNext(); i.next())
408: ++j;
409: return j;
410: }
411:
412: public boolean remove(Object o) {
413: processQueue();
414: if (!(o instanceof Map.Entry))
415: return false;
416: Map.Entry e = (Map.Entry) o;
417: Object ev = e.getValue();
418: SoftKey wk = SoftKey.create(e.getKey());
419: Object hv = hash.get(wk);
420: if ((hv == null) ? ((ev == null) && hash.containsKey(wk))
421: : hv.equals(ev)) {
422: hash.remove(wk);
423: return true;
424: }
425: return false;
426: }
427:
428: public int hashCode() {
429: int h = 0;
430: for (Iterator i = hashEntrySet.iterator(); i.hasNext();) {
431: Map.Entry ent = (Map.Entry) i.next();
432: SoftKey wk = (SoftKey) ent.getKey();
433: Object v;
434: if (wk == null)
435: continue;
436: h += (wk.hashCode() ^ (((v = ent.getValue()) == null) ? 0
437: : v.hashCode()));
438: }
439: return h;
440: }
441: }
442:
443: private Set entrySet = null;
444:
445: /**
446: * Returns a <code>Set</code> view of the mappings in this map.
447: */
448: public Set entrySet() {
449: if (entrySet == null)
450: entrySet = new EntrySet();
451: return entrySet;
452: }
453:
454: }
|