001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2003-2006, Geotools Project Managment Committee (PMC)
005: * (C) 2001, Institut de Recherche pour le Développement
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation; either
010: * version 2.1 of the License, or (at your option) any later version.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.util;
018:
019: // Collections and references
020: import java.lang.ref.WeakReference;
021: import java.util.AbstractMap;
022: import java.util.Arrays;
023: import java.util.Map;
024: import java.util.Set;
025: import java.util.WeakHashMap;
026: import java.util.logging.Level;
027: import java.util.logging.LogRecord;
028: import java.util.logging.Logger;
029:
030: // Geotools dependencies
031: import org.geotools.resources.Utilities;
032: import org.geotools.util.logging.Logging;
033:
034: /**
035: * A hashtable-based {@link Map} implementation with <em>weak values</em>. An entry in a
036: * {@code WeakValueHashMap} will automatically be removed when its value is no longer
037: * in ordinary use. This class is similar to the standard {@link WeakHashMap} class provided
038: * is J2SE, except that weak references are hold on values instead of keys.
039: * <p>
040: * The {@code WeakValueHashMap} class is thread-safe.
041: *
042: * @since 2.0
043: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/WeakValueHashMap.java $
044: * @version $Id: WeakValueHashMap.java 27862 2007-11-12 19:51:19Z desruisseaux $
045: * @author Martin Desruisseaux
046: *
047: * @see WeakHashMap
048: * @see WeakHashSet
049: */
050: public class WeakValueHashMap extends AbstractMap {
051: /**
052: * Minimal capacity for {@link #table}.
053: */
054: private static final int MIN_CAPACITY = 7;
055:
056: /**
057: * Load factor. Control the moment
058: * where {@link #table} must be rebuild.
059: */
060: private static final float LOAD_FACTOR = 0.75f;
061:
062: /**
063: * An entry in the {@link WeakValueHashMap}. This is a weak reference
064: * to a value together with a strong reference to a key.
065: */
066: private final class Entry extends WeakReference implements
067: Map.Entry {
068: /**
069: * The key.
070: */
071: Object key;
072:
073: /**
074: * The next entry, or {@code null} if there is none.
075: */
076: Entry next;
077:
078: /**
079: * Index for this element in {@link #table}. This index
080: * must be updated at every {@link #rehash} call.
081: */
082: int index;
083:
084: /**
085: * Constructs a new weak reference.
086: */
087: Entry(final Object key, final Object value, final Entry next,
088: final int index) {
089: super (value, WeakCollectionCleaner.DEFAULT.referenceQueue);
090: this .key = key;
091: this .next = next;
092: this .index = index;
093: }
094:
095: /**
096: * Returns the key corresponding to this entry.
097: */
098: public Object getKey() {
099: return key;
100: }
101:
102: /**
103: * Returns the value corresponding to this entry.
104: */
105: public Object getValue() {
106: return get();
107: }
108:
109: /**
110: * Replaces the value corresponding to this entry with the specified value.
111: */
112: public Object setValue(final Object value) {
113: if (value != null) {
114: throw new UnsupportedOperationException();
115: }
116: Object old = get();
117: clear();
118: return old;
119: }
120:
121: /**
122: * Clear the reference. The {@link WeakCollectionCleaner} requires that this method is
123: * overridden in order to remove this entry from the enclosing hash map.
124: */
125: public void clear() {
126: super .clear();
127: removeEntry(this );
128: key = null;
129: }
130:
131: /**
132: * Compares the specified object with this entry for equality.
133: */
134: public boolean equals(final Object other) {
135: if (other instanceof Map.Entry) {
136: final Map.Entry that = (Map.Entry) other;
137: return Utilities.equals(this .getKey(), that.getKey())
138: && Utilities.equals(this .getValue(), that
139: .getValue());
140: }
141: return false;
142: }
143:
144: /**
145: * Returns the hash code value for this map entry.
146: */
147: public int hashCode() {
148: final Object val = get();
149: return (key == null ? 0 : key.hashCode())
150: ^ (val == null ? 0 : val.hashCode());
151: }
152: }
153:
154: /**
155: * Table of weak references.
156: */
157: private Entry[] table;
158:
159: /**
160: * Number of non-nul elements in {@link #table}.
161: */
162: private int count;
163:
164: /**
165: * The next size value at which to resize. This value should
166: * be <code>{@link #table}.length*{@link #loadFactor}</code>.
167: */
168: private int threshold;
169:
170: /**
171: * The timestamp when {@link #table} was last rehashed. This information
172: * is used to avoid too early table reduction. When the garbage collector
173: * collected a lot of elements, we will wait at least 20 seconds before
174: * rehashing {@link #table}. Too early table reduction leads to many cycles
175: * like "reduce", "expand", "reduce", "expand", etc.
176: */
177: private long lastRehashTime;
178:
179: /**
180: * Number of millisecond to wait before to rehash
181: * the table for reducing its size.
182: */
183: private static final long HOLD_TIME = 20 * 1000L;
184:
185: /**
186: * Construct a {@code WeakValueHashMap}.
187: */
188: public WeakValueHashMap() {
189: table = new Entry[MIN_CAPACITY];
190: threshold = Math.round(table.length * LOAD_FACTOR);
191: lastRehashTime = System.currentTimeMillis();
192: }
193:
194: /**
195: * Create a {@link WeakValueHashMap} of the requested size.
196: * @param initialSize
197: */
198: public WeakValueHashMap(int initialSize) {
199: table = new Entry[initialSize];
200: threshold = Math.round(table.length * LOAD_FACTOR);
201: lastRehashTime = System.currentTimeMillis();
202: }
203:
204: /**
205: * Create a new WeakValueHashMap populated with the contents of the provied map.
206: *
207: * @param map Initial contents of the WeakValueHashMap
208: */
209: public WeakValueHashMap(Map map) {
210: this ();
211: putAll(map);
212: }
213:
214: /**
215: * Invoked by {@link Entry} when an element has been collected
216: * by the garbage collector. This method will remove the weak reference
217: * from {@link #table}.
218: */
219: private synchronized void removeEntry(final Entry toRemove) {
220: assert valid() : count;
221: final int i = toRemove.index;
222: // Index 'i' may not be valid if the reference 'toRemove'
223: // has been already removed in a previous rehash.
224: if (i < table.length) {
225: Entry prev = null;
226: Entry e = table[i];
227: while (e != null) {
228: if (e == toRemove) {
229: if (prev != null) {
230: prev.next = e.next;
231: } else {
232: table[i] = e.next;
233: }
234: count--;
235: assert valid();
236:
237: // If the number of elements has dimunished
238: // significatively, rehash the table.
239: if (count <= threshold / 4) {
240: rehash(false);
241: }
242: // We must not continue the loop, since
243: // variable 'e' is no longer valid.
244: return;
245: }
246: prev = e;
247: e = e.next;
248: }
249: }
250: assert valid();
251: /*
252: * If we reach this point, its mean that reference 'toRemove' has not
253: * been found. This situation may occurs if 'toRemove' has already been
254: * removed in a previous run of {@link #rehash}.
255: */
256: }
257:
258: /**
259: * Rehash {@link #table}.
260: *
261: * @param augmentation {@code true} if this method is invoked
262: * for augmenting {@link #table}, or {@code false} if
263: * it is invoked for making the table smaller.
264: */
265: private void rehash(final boolean augmentation) {
266: assert Thread.holdsLock(this );
267: assert valid();
268: final long currentTime = System.currentTimeMillis();
269: final int capacity = Math.max(Math.round(count
270: / (LOAD_FACTOR / 2)), count + MIN_CAPACITY);
271: if (augmentation ? (capacity <= table.length)
272: : (capacity >= table.length || currentTime
273: - lastRehashTime < HOLD_TIME)) {
274: return;
275: }
276: lastRehashTime = currentTime;
277: final Entry[] oldTable = table;
278: table = new Entry[capacity];
279: threshold = Math.round(capacity * LOAD_FACTOR);
280: for (int i = 0; i < oldTable.length; i++) {
281: for (Entry old = oldTable[i]; old != null;) {
282: final Entry e = old;
283: old = old.next; // On retient 'next' tout de suite car sa valeur va changer...
284: final Object key = e.key;
285: if (key != null) {
286: final int index = (key.hashCode() & 0x7FFFFFFF)
287: % table.length;
288: e.index = index;
289: e.next = table[index];
290: table[index] = e;
291: } else {
292: count--;
293: }
294: }
295: }
296: final Logger logger = Logging.getLogger("org.geotools.util");
297: final Level level = Level.FINEST;
298: if (logger.isLoggable(level)) {
299: final LogRecord record = new LogRecord(level,
300: "Rehash from " + oldTable.length + " to "
301: + table.length);
302: record.setSourceMethodName(augmentation ? "unique"
303: : "remove");
304: record.setSourceClassName(WeakValueHashMap.class.getName());
305: logger.log(record);
306: }
307: assert valid();
308: }
309:
310: /**
311: * Check if this {@code WeakValueHashMap} is valid. This method counts the
312: * number of elements and compare it to {@link #count}. If the check fails,
313: * the number of elements is corrected (if we didn't, an {@link AssertionError}
314: * would be thrown for every operations after the first error, which make
315: * debugging more difficult). The set is otherwise unchanged, which should
316: * help to get similar behaviour as if assertions hasn't been turned on.
317: */
318: private boolean valid() {
319: int n = 0;
320: for (int i = 0; i < table.length; i++) {
321: for (Entry e = table[i]; e != null; e = e.next) {
322: n++;
323: }
324: }
325: if (n != count) {
326: count = n;
327: return false;
328: } else {
329: return true;
330: }
331: }
332:
333: /**
334: * Returns the number of key-value mappings in this map.
335: */
336: public synchronized int size() {
337: assert valid();
338: return count;
339: }
340:
341: /**
342: * Returns {@code true} if this map maps one or more keys to this value.
343: *
344: * @param value value whose presence in this map is to be tested.
345: * @return {@code true} if this map maps one or more keys to this value.
346: */
347: public synchronized boolean containsValue(final Object value) {
348: return super .containsValue(value);
349: }
350:
351: /**
352: * Returns {@code true} if this map contains a mapping for the specified key.
353: *
354: * @param key key whose presence in this map is to be tested.
355: * @return {@code true} if this map contains a mapping for the specified key.
356: * @throws NullPointerException If key is {@code null}.
357: */
358: public boolean containsKey(final Object key) {
359: return get(key) != null;
360: }
361:
362: /**
363: * Returns the value to which this map maps the specified key. Returns
364: * {@code null} if the map contains no mapping for this key.
365: *
366: * @param key Key whose associated value is to be returned.
367: * @return The value to which this map maps the specified key.
368: * @throws NullPointerException if the key is {@code null}.
369: */
370: public synchronized Object get(final Object key) {
371: assert WeakCollectionCleaner.DEFAULT.isAlive();
372: assert valid() : count;
373: final int index = (key.hashCode() & 0x7FFFFFFF) % table.length;
374: for (Entry e = table[index]; e != null; e = e.next) {
375: if (key.equals(e.key)) {
376: return e.get();
377: }
378: }
379: return null;
380: }
381:
382: /**
383: * Implementation of {@link #put} and {@link #remove} operations.
384: */
385: private synchronized Object intern(final Object key,
386: final Object value) {
387: assert WeakCollectionCleaner.DEFAULT.isAlive();
388: assert valid() : count;
389: /*
390: * Check if {@code obj} is already contained in this
391: * {@code WeakValueHashMap}. If yes, clear it.
392: */
393: Object oldValue = null;
394: final int hash = key.hashCode() & 0x7FFFFFFF;
395: int index = hash % table.length;
396: for (Entry e = table[index]; e != null; e = e.next) {
397: if (key.equals(e.key)) {
398: oldValue = e.get();
399: e.clear();
400: }
401: }
402: if (value != null) {
403: if (count >= threshold) {
404: rehash(true);
405: index = hash % table.length;
406: }
407: table[index] = new Entry(key, value, table[index], index);
408: count++;
409: }
410: assert valid();
411: return oldValue;
412: }
413:
414: /**
415: * Associates the specified value with the specified key in this map.
416: * The value is associated using a {@link WeakReference}.
417: *
418: * @param key key with which the specified value is to be associated.
419: * @param value value to be associated with the specified key.
420: * @return previous value associated with specified key, or {@code null}
421: * if there was no mapping for key.
422: *
423: * @throws NullPointerException if the key or the value is {@code null}.
424: */
425: public Object put(final Object key, final Object value) {
426: if (value == null) {
427: throw new NullPointerException("Null value not allowed");
428: // TODO: localize this message.
429: }
430: return intern(key, value);
431: }
432:
433: /**
434: * Removes the mapping for this key from this map if present.
435: *
436: * @param key key whose mapping is to be removed from the map.
437: * @return previous value associated with specified key, or {@code null}
438: * if there was no entry for key.
439: */
440: public Object remove(final Object key) {
441: return intern(key, null);
442: }
443:
444: /**
445: * Removes all of the elements from this map.
446: */
447: public synchronized void clear() {
448: Arrays.fill(table, null);
449: count = 0;
450: }
451:
452: /**
453: * Returns a set view of the mappings contained in this map.
454: * Each element in this set is a {@link java.util.Map.Entry}.
455: * The current implementation thrown {@link UnsupportedOperationException}.
456: *
457: * @return a set view of the mappings contained in this map.
458: */
459: public Set entrySet() {
460: throw new UnsupportedOperationException();
461: }
462: }
|