001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2006, Geotools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2.1 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.util;
017:
018: // J2SE dependencies
019: import java.lang.ref.SoftReference;
020: import java.util.AbstractMap;
021: import java.util.AbstractSet;
022: import java.util.Collection;
023: import java.util.HashMap;
024: import java.util.Iterator;
025: import java.util.LinkedList;
026: import java.util.Map;
027: import java.util.Set;
028: import java.util.NoSuchElementException;
029: import java.util.ConcurrentModificationException;
030:
031: // Geotools dependencies
032: import org.geotools.resources.i18n.Errors;
033: import org.geotools.resources.i18n.ErrorKeys;
034:
035: /**
036: * A hash map implementation that uses {@linkplain SoftReference soft references}, leaving memory
037: * when an entry is not used anymore and memory is low.
038: * <p>
039: * This map implementation actually maintains some of the first entries as hard references.
040: * Only oldest entries are retained by soft references, in order to avoid too aggressive garbage
041: * collection. The amount of entries to retain by hard reference is specified at {@linkplain
042: * #SoftValueHashMap(int) construction time}.
043: * <p>
044: * This map is thread-safe. It accepts the null key, but doesn't accepts null values. Usage
045: * of {@linkplain #values value}, {@linkplain #keySet key} or {@linkplain #entrySet entry}
046: * collections are supported except for direct usage of their iterators, which may throw
047: * {@link ConcurrentModificationException} randomly depending on the garbage collector activity.
048: *
049: * @since 2.3
050: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/SoftValueHashMap.java $
051: * @version $Id: SoftValueHashMap.java 22443 2006-10-27 20:47:22Z desruisseaux $
052: * @author Simone Giannecchini
053: * @author Martin Desruisseaux
054: */
055: public class SoftValueHashMap/*<K,V>*/extends AbstractMap/*<K,V>*/{
056: /**
057: * The default value for {@link #hardReferencesCount}.
058: */
059: private static final int DEFAULT_HARD_REFERENCE_COUNT = 20;
060:
061: /**
062: * The map of hard or soft references. Values are either direct reference to the objects,
063: * or wrapped in a {@code Reference} object.
064: */
065: private final Map/*<K,Object>*/hash = new HashMap/*<K,Object>*/();
066:
067: /**
068: * The FIFO list of keys to hard references. Newest elements are first, and latest elements
069: * are last. This list should never be longer than {@link #hardReferencesCount}.
070: */
071: private final LinkedList/*<K>*/hardCache = new LinkedList/*<K>*/();
072:
073: /**
074: * The number of hard references to hold internally.
075: */
076: private final int hardReferencesCount;
077:
078: /**
079: * The entries to be returned by {@link #entrySet()}, or {@code null} if not yet created.
080: */
081: private transient Set entries;
082:
083: /**
084: * Creates a map with the default hard references count.
085: */
086: public SoftValueHashMap() {
087: hardReferencesCount = DEFAULT_HARD_REFERENCE_COUNT;
088: }
089:
090: /**
091: * Creates a map with the specified hard references count.
092: */
093: public SoftValueHashMap(final int hardReferencesCount) {
094: this .hardReferencesCount = hardReferencesCount;
095: }
096:
097: /**
098: * Ensures that the specified value is non-null.
099: */
100: private static void ensureNotNull(final Object/*V*/value)
101: throws IllegalArgumentException {
102: if (value == null) {
103: throw new IllegalArgumentException(Errors.format(
104: ErrorKeys.NULL_ARGUMENT_$1, "value"));
105: }
106: }
107:
108: /**
109: * Performs a consistency check on this map. This method is used for tests and
110: * assertions only.
111: */
112: final boolean isValid() {
113: int count = 0, size = 0;
114: synchronized (hash) {
115: for (final Iterator it = hash.entrySet().iterator(); it
116: .hasNext();) {
117: final Map.Entry entry = (Map.Entry) it.next();
118: if (entry.getValue() instanceof Reference) {
119: count++;
120: } else {
121: assert hardCache.contains(entry.getKey());
122: }
123: size++;
124: }
125: assert size == hash.size();
126: assert hardCache.size() == Math.min(size,
127: hardReferencesCount);
128: }
129: return count == Math.max(size - hardReferencesCount, 0);
130: }
131:
132: /**
133: * Returns the number of entries in this map.
134: */
135: public int size() {
136: synchronized (hash) {
137: return hash.size();
138: }
139: }
140:
141: /**
142: * Returns {@code true} if this map contains a mapping for the specified key.
143: */
144: public boolean containsKey(final Object key) {
145: synchronized (hash) {
146: return hash.containsKey(key);
147: }
148: }
149:
150: /**
151: * Returns {@code true} if this map maps one or more keys to this value.
152: */
153: public boolean containsValue(final Object value) {
154: ensureNotNull(value);
155: synchronized (hash) {
156: /*
157: * We must rely on the super-class default implementation, not on HashMap
158: * implementation, because some references are wrapped into SoftReferences.
159: */
160: return super .containsValue(value);
161: }
162: }
163:
164: /**
165: * Returns the value to which this map maps the specified key. Returns {@code null} if
166: * the map contains no mapping for this key, or the value has been garbage collected.
167: *
168: * @param key key whose associated value is to be returned.
169: * @return the value to which this map maps the specified key, or {@code null} if none.
170: */
171: public/*V*/Object get(final Object key) {
172: synchronized (hash) {
173: Object value = hash.get(key);
174: if (value instanceof Reference) {
175: /*
176: * The value is a soft reference only if it was not used for a while and the map
177: * contains more than 'hardReferenceCount' entries. Otherwise, it is an ordinary
178: * reference and is returned directly. See the 'retainStrongly' method.
179: *
180: * If the value is a soft reference, get the referent and clear it immediately
181: * for avoiding the reference to be enqueded. We abandon the soft reference and
182: * reinject the referent as a strong reference in the hash map, since we try to
183: * keep the last entries by strong references.
184: */
185: value = ((Reference) value).getAndClear();
186: if (value != null) {
187: // Transforms the soft reference into a hard one.
188: hash.put(key, value);
189: retainStrongly(key);
190: } else {
191: // The value has already been garbage collected.
192: hash.remove(key);
193: }
194: }
195: return value;
196: }
197: }
198:
199: /**
200: * Declares that the value for the specified key must be retained by hard reference.
201: * If there is already {@link #hardReferencesCount} hard references, then this method
202: * replaces the oldest hard reference by a soft one.
203: */
204: private void retainStrongly(final/*K*/Object key) {
205: assert Thread.holdsLock(hash);
206: assert !hardCache.contains(key) : key;
207: hardCache.addFirst(key);
208: if (hardCache.size() > hardReferencesCount) {
209: // Remove the last entry if list longer than hardReferencesCount
210: final/*K*/Object toRemove = hardCache.removeLast();
211: final Object value = hash.get(toRemove);
212: assert value != null && !(value instanceof Reference) : toRemove;
213: hash.put(toRemove, new Reference(hash, toRemove, value));
214: assert hardCache.size() == hardReferencesCount;
215: }
216: assert isValid();
217: }
218:
219: /**
220: * Associates the specified value with the specified key in this map.
221: *
222: * @param key Key with which the specified value is to be associated.
223: * @param value Value to be associated with the specified key. The value can't be null.
224: *
225: * @return Previous value associated with specified key, or {@code null}
226: * if there was no mapping for key.
227: */
228: public Object put(final Object key, final Object value) {
229: ensureNotNull(value);
230: synchronized (hash) {
231: Object oldValue = hash.put(key, value);
232: if (oldValue instanceof Reference) {
233: oldValue = ((Reference) oldValue).getAndClear();
234: } else if (oldValue != null) {
235: /*
236: * The value was retained by hard reference, which implies that the key must be in
237: * the hard-cache list. Removes the key from the list, since we want to reinsert it
238: * at the begining of the list in order to mark the value as the most recently used.
239: * This method performs a linear search, which may be quite ineficient. But it still
240: * efficient enough if the key was recently used, in which case it appears near the
241: * begining of the list. We assume that this is a common case. We may revisit later
242: * if profiling show that this is a performance issue.
243: */
244: if (!hardCache.remove(key)) {
245: throw new AssertionError(key);
246: }
247: }
248: retainStrongly(key);
249: return oldValue;
250: }
251: }
252:
253: /**
254: * Copies all of the mappings from the specified map to this map.
255: */
256: public void putAll(Map/*<? extends K, ? extends V>*/map) {
257: synchronized (hash) {
258: super .putAll(map);
259: }
260: }
261:
262: /**
263: * Removes the mapping for this key from this map if present.
264: *
265: * @param key Key whose mapping is to be removed from the map.
266: * @return previous value associated with specified key, or {@code null}
267: * if there was no entry for key.
268: */
269: public Object remove(final Object key) {
270: synchronized (hash) {
271: Object oldValue = hash.remove(key);
272: if (oldValue instanceof Reference) {
273: oldValue = ((Reference) oldValue).getAndClear();
274: } else if (oldValue != null) {
275: /*
276: * See the comment in the 'put' method.
277: */
278: if (!hardCache.remove(key)) {
279: throw new AssertionError(key);
280: }
281: }
282: return oldValue;
283: }
284: }
285:
286: /**
287: * Removes all mappings from this map.
288: */
289: public void clear() {
290: synchronized (hash) {
291: for (final Iterator it = hash.values().iterator(); it
292: .hasNext();) {
293: final Object value = it.next();
294: if (value instanceof Reference) {
295: ((Reference) value).getAndClear();
296: }
297: }
298: hash.clear();
299: hardCache.clear();
300: }
301: }
302:
303: /**
304: * Returns a set view of the mappings contained in this map.
305: */
306: public Set entrySet() {
307: synchronized (hash) {
308: if (entries == null) {
309: entries = new Entries();
310: }
311: return entries;
312: }
313: }
314:
315: /**
316: * Compares the specified object with this map for equality.
317: */
318: public boolean equals(final Object object) {
319: synchronized (hash) {
320: return super .equals(object);
321: }
322: }
323:
324: /**
325: * Returns the hash code value for this map.
326: */
327: public int hashCode() {
328: synchronized (hash) {
329: return super .hashCode();
330: }
331: }
332:
333: /**
334: * Returns a string representation of this map.
335: */
336: public String toString() {
337: synchronized (hash) {
338: return super .toString();
339: }
340: }
341:
342: /**
343: * Implementation of the entries set to be returned by {@link #entrySet()}.
344: */
345: private final class Entries extends AbstractSet {
346: /**
347: * Returns an iterator over the elements contained in this collection.
348: */
349: public Iterator iterator() {
350: synchronized (hash) {
351: return new Iter(hash);
352: }
353: }
354:
355: /**
356: * Returns the number of elements in this collection.
357: */
358: public int size() {
359: return SoftValueHashMap.this .size();
360: }
361:
362: /**
363: * Returns {@code true} if this collection contains the specified element.
364: */
365: public boolean contains(final Object entry) {
366: synchronized (hash) {
367: return super .contains(entry);
368: }
369: }
370:
371: /**
372: * Returns an array containing all of the elements in this collection.
373: */
374: public Object[] toArray() {
375: synchronized (hash) {
376: return super .toArray();
377: }
378: }
379:
380: /**
381: * Returns an array containing all of the elements in this collection.
382: */
383: public/*<T> T[]*/Object[] toArray(final/*T[]*/Object[] array) {
384: synchronized (hash) {
385: return super .toArray(array);
386: }
387: }
388:
389: /**
390: * Removes a single instance of the specified element from this collection,
391: * if it is present.
392: */
393: public boolean remove(final Object entry) {
394: synchronized (hash) {
395: return super .remove(entry);
396: }
397: }
398:
399: /**
400: * Returns {@code true} if this collection contains all of the elements
401: * in the specified collection.
402: */
403: public boolean containsAll(final Collection/*<?>*/collection) {
404: synchronized (hash) {
405: return super .containsAll(collection);
406: }
407: }
408:
409: /**
410: * Adds all of the elements in the specified collection to this collection.
411: */
412: public boolean addAll(
413: final Collection/*<? extends E>*/collection) {
414: synchronized (hash) {
415: return super .addAll(collection);
416: }
417: }
418:
419: /**
420: * Removes from this collection all of its elements that are contained in
421: * the specified collection.
422: */
423: public boolean removeAll(final Collection/*<?>*/collection) {
424: synchronized (hash) {
425: return super .removeAll(collection);
426: }
427: }
428:
429: /**
430: * Retains only the elements in this collection that are contained in the
431: * specified collection.
432: */
433: public boolean retainAll(final Collection/*<?>*/collection) {
434: synchronized (hash) {
435: return super .retainAll(collection);
436: }
437: }
438:
439: /**
440: * Removes all of the elements from this collection.
441: */
442: public void clear() {
443: SoftValueHashMap.this .clear();
444: }
445:
446: /**
447: * Returns a string representation of this collection.
448: */
449: public String toString() {
450: synchronized (hash) {
451: return super .toString();
452: }
453: }
454: }
455:
456: /**
457: * The iterator to be returned by {@link Entries}.
458: */
459: private static final class Iter implements Iterator {
460: /**
461: * A copy of the {@link SoftValueHashMap#hash} field.
462: */
463: private final Map hash;
464:
465: /**
466: * The iterator over the {@link #hash} entries.
467: */
468: private final Iterator iterator;
469:
470: /**
471: * The next entry to be returned by the {@link #next} method, or {@code null}
472: * if not yet computed of if the iteration is finished.
473: */
474: private transient Map.Entry entry;
475:
476: /**
477: * Creates an iterator for the specified {@link SoftValueHashMap#hash} field.
478: */
479: Iter(final Map hash) {
480: this .hash = hash;
481: this .iterator = hash.entrySet().iterator();
482: }
483:
484: /**
485: * Set {@link #entry} to the next entry to iterate. Returns {@code true} if
486: * an entry has been found, or {@code false} if the iteration is finished.
487: */
488: private boolean findNext() {
489: assert Thread.holdsLock(hash);
490: while (iterator.hasNext()) {
491: final Map.Entry candidate = (Map.Entry) iterator.next();
492: Object value = candidate.getValue();
493: if (value instanceof Reference) {
494: value = ((Reference) value).get();
495: entry = new MapEntry(candidate.getKey(), value);
496: return true;
497: }
498: if (value != null) {
499: entry = candidate;
500: return true;
501: }
502: }
503: return false;
504: }
505:
506: /**
507: * Returns {@code true} if this iterator can return more value.
508: */
509: public boolean hasNext() {
510: synchronized (hash) {
511: return entry != null || findNext();
512: }
513: }
514:
515: /**
516: * Returns the next value. If some value were garbage collected after the
517: * iterator was created, they will not be returned. Note however that a
518: * {@link ConcurrentModificationException} may be throw if the iteration
519: * is not synchronized on {@link #hash}.
520: */
521: public Object/*Map.Entry*/next() {
522: synchronized (hash) {
523: if (entry == null && !findNext()) {
524: throw new NoSuchElementException();
525: }
526: final Map.Entry next = entry;
527: entry = null; // Flag that a new entry will need to be lazily fetched.
528: return next;
529: }
530: }
531:
532: /**
533: * Removes the last entry.
534: */
535: public void remove() {
536: synchronized (hash) {
537: iterator.remove();
538: }
539: }
540: }
541:
542: /**
543: * A soft reference to a map entry. Soft references are created only when the map contains
544: * more than {@link #hardReferencesCount}, in order to avoid to put more pressure on the
545: * garbage collector.
546: */
547: private static final class Reference/*<K,V>*/extends SoftReference/*<V>*/{
548: /**
549: * A reference to the {@link SoftValueHashMap#hash} entries. We keep this reference instead
550: * than a reference to {@link SoftValueHashMap} itself in order to avoid indirect retention
551: * of {@link SoftValueHashMap#hardCache}, which is not needed for this reference.
552: */
553: private final Map/*<K,V>*/hash;
554:
555: /**
556: * The key for the entry to be removed when the soft reference is cleared.
557: */
558: private final/*K*/Object key;
559:
560: /**
561: * Creates a soft reference for the specified key-value pair.
562: */
563: Reference(final Map/*<K,V>*/hash, final/*K*/Object key,
564: final/*V*/Object value) {
565: super (value, WeakCollectionCleaner.DEFAULT.referenceQueue);
566: this .hash = hash;
567: this .key = key;
568: }
569:
570: /**
571: * Gets and clear this reference object. This method performs no additional operation.
572: * More specifically:
573: * <ul>
574: * <li>It does not enqueue the reference.</li>
575: * <li>It does not remove the reference from the hash map.</li>
576: * </ul>
577: * This is because this method is invoked when the entry should have already be removed,
578: * or is about to be removed.</li>
579: */
580: final Object getAndClear() {
581: assert Thread.holdsLock(hash);
582: final Object value = get();
583: super .clear();
584: return value;
585: }
586:
587: /**
588: * Removes the entries from the backing hash map. This method need to
589: * override the {@link SoftReference#clear} method because it is invoked
590: * by {@link WeakCollectionCleaner}.
591: */
592: public void clear() {
593: super .clear();
594: synchronized (hash) {
595: final Object old = hash.remove(key);
596: /*
597: * If the entry was used for an other value, then put back the old value. This
598: * case may occurs if a new value was set in the hash map before the old value
599: * was garbage collected.
600: */
601: if (old != this && old != null) {
602: hash.put(key, old);
603: }
604: }
605: }
606: }
607: }
|