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.AbstractSet;
022: import java.util.Arrays;
023: import java.util.Iterator;
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.XArray;
032: import org.geotools.util.logging.Logging;
033:
034: /**
035: * A set of objects hold by weak references. An entry in a {@code WeakHashSet}
036: * will automatically be removed when it is no longer in ordinary use. More precisely,
037: * the presence of an entry will not prevent the entry from being discarded by the
038: * garbage collector, that is, made finalizable, finalized, and then reclaimed.
039: * When an entry has been discarded it is effectively removed from the set, so
040: * this class behaves somewhat differently than other {@link Set} implementations.
041: * <p>
042: * If you would like to use {@code WeakHashSet} as inside a factory to prevent creating
043: * duplicate immutable objects, please look at the {@link CanonicalSet} subclass.
044: * <p>
045: * The {@code WeakHashSet} class is thread-safe.
046: *
047: * @since 2.0
048: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/WeakHashSet.java $
049: * @version $Id: WeakHashSet.java 27862 2007-11-12 19:51:19Z desruisseaux $
050: * @author Martin Desruisseaux
051: *
052: * @see WeakHashMap
053: */
054: public class WeakHashSet extends AbstractSet {
055: /**
056: * Minimal capacity for {@link #table}.
057: */
058: private static final int MIN_CAPACITY = 7;
059:
060: /**
061: * Load factor. Control the moment
062: * where {@link #table} must be rebuild.
063: */
064: private static final float LOAD_FACTOR = 0.75f;
065:
066: /**
067: * A weak reference to an element.
068: */
069: private final class Entry extends WeakReference {
070: /**
071: * The next entry, or {@code null} if there is none.
072: */
073: Entry next;
074:
075: /**
076: * Index for this element in {@link #table}. This index
077: * must be updated at every {@link #rehash} call.
078: */
079: int index;
080:
081: /**
082: * Construct a new weak reference.
083: */
084: Entry(final Object obj, final Entry next, final int index) {
085: super (obj, WeakCollectionCleaner.DEFAULT.referenceQueue);
086: this .next = next;
087: this .index = index;
088: }
089:
090: /**
091: * Clear the reference.
092: */
093: public void clear() {
094: super .clear();
095: removeEntry(this );
096: }
097: }
098:
099: /**
100: * Table of weak references.
101: */
102: private Entry[] table;
103:
104: /**
105: * Number of non-nul elements in {@link #table}.
106: */
107: private int count;
108:
109: /**
110: * The next size value at which to resize. This value should
111: * be <code>{@link #table}.length*{@link #loadFactor}</code>.
112: */
113: private int threshold;
114:
115: /**
116: * The timestamp when {@link #table} was last rehashed. This information
117: * is used to avoid too early table reduction. When the garbage collector
118: * collected a lot of elements, we will wait at least 20 seconds before
119: * rehashing {@link #table}. Too early table reduction leads to many cycles
120: * like "reduce", "expand", "reduce", "expand", etc.
121: */
122: private long lastRehashTime;
123:
124: /**
125: * Number of millisecond to wait before to rehash
126: * the table for reducing its size.
127: */
128: private static final long HOLD_TIME = 20 * 1000L;
129:
130: /**
131: * Constructs a {@code WeakHashSet}.
132: */
133: public WeakHashSet() {
134: table = new Entry[MIN_CAPACITY];
135: threshold = Math.round(table.length * LOAD_FACTOR);
136: lastRehashTime = System.currentTimeMillis();
137: }
138:
139: /**
140: * Invoked by {@link Entry} when an element has been collected
141: * by the garbage collector. This method will remove the weak reference
142: * from {@link #table}.
143: */
144: private synchronized void removeEntry(final Entry toRemove) {
145: assert valid() : count;
146: final int i = toRemove.index;
147: // Index 'i' may not be valid if the reference 'toRemove'
148: // has been already removed in a previous rehash.
149: if (i < table.length) {
150: Entry prev = null;
151: Entry e = table[i];
152: while (e != null) {
153: if (e == toRemove) {
154: if (prev != null) {
155: prev.next = e.next;
156: } else {
157: table[i] = e.next;
158: }
159: count--;
160: assert valid();
161:
162: // If the number of elements has dimunished
163: // significatively, rehash the table.
164: if (count <= threshold / 4) {
165: rehash(false);
166: }
167: // We must not continue the loop, since
168: // variable 'e' is no longer valid.
169: return;
170: }
171: prev = e;
172: e = e.next;
173: }
174: }
175: assert valid();
176: /*
177: * If we reach this point, its mean that reference 'toRemove' has not
178: * been found. This situation may occurs if 'toRemove' has already been
179: * removed in a previous run of {@link #rehash}.
180: */
181: }
182:
183: /**
184: * Rehash {@link #table}.
185: *
186: * @param augmentation {@code true} if this method is invoked
187: * for augmenting {@link #table}, or {@code false} if
188: * it is invoked for making the table smaller.
189: */
190: private void rehash(final boolean augmentation) {
191: assert Thread.holdsLock(this );
192: assert valid();
193: final long currentTime = System.currentTimeMillis();
194: final int capacity = Math.max(Math.round(count
195: / (LOAD_FACTOR / 2)), count + MIN_CAPACITY);
196: if (augmentation ? (capacity <= table.length)
197: : (capacity >= table.length || currentTime
198: - lastRehashTime < HOLD_TIME)) {
199: return;
200: }
201: lastRehashTime = currentTime;
202: final Entry[] oldTable = table;
203: table = new Entry[capacity];
204: threshold = Math.round(capacity * LOAD_FACTOR);
205: for (int i = 0; i < oldTable.length; i++) {
206: for (Entry old = oldTable[i]; old != null;) {
207: final Entry e = old;
208: old = old.next; // On retient 'next' tout de suite car sa valeur va changer...
209: final Object obj_e = e.get();
210: if (obj_e != null) {
211: final int index = (obj_e.hashCode() & 0x7FFFFFFF)
212: % table.length;
213: e.index = index;
214: e.next = table[index];
215: table[index] = e;
216: } else {
217: count--;
218: }
219: }
220: }
221: final Logger logger = Logging.getLogger("org.geotools.util");
222: final Level level = Level.FINEST;
223: if (logger.isLoggable(level)) {
224: final LogRecord record = new LogRecord(level,
225: "Rehash from " + oldTable.length + " to "
226: + table.length);
227: record.setSourceMethodName(augmentation ? "unique"
228: : "remove");
229: record.setSourceClassName(WeakHashSet.class.getName());
230: logger.log(record);
231: }
232: assert valid();
233: }
234:
235: /**
236: * Check if this {@code WeakHashSet} is valid. This method counts the
237: * number of elements and compare it to {@link #count}. If the check fails,
238: * the number of elements is corrected (if we didn't, an {@link AssertionError}
239: * would be thrown for every operations after the first error, which make
240: * debugging more difficult). The set is otherwise unchanged, which should
241: * help to get similar behaviour as if assertions hasn't been turned on.
242: */
243: private boolean valid() {
244: int n = 0;
245: for (int i = 0; i < table.length; i++) {
246: for (Entry e = table[i]; e != null; e = e.next) {
247: n++;
248: }
249: }
250: if (n != count) {
251: count = n;
252: return false;
253: } else {
254: return true;
255: }
256: }
257:
258: /**
259: * Returns the count of element in this set.
260: */
261: public synchronized int size() {
262: assert valid();
263: return count;
264: }
265:
266: /**
267: * Returns {@code true} if this set contains the specified element.
268: *
269: * @param obj Object to be checked for containment in this set.
270: * @return {@code true} if this set contains the specified element.
271: */
272: public boolean contains(final Object obj) {
273: return obj == null || get(obj) != null;
274: }
275:
276: /**
277: * Returns an object equals to the specified object, if present. If
278: * this set doesn't contains any object equals to {@code obj},
279: * then this method returns {@code null}.
280: *
281: * @deprecated Moved to the {@link CanonicalSet} subclass.
282: */
283: public synchronized Object get(final Object obj) {
284: return intern(obj, GET);
285: }
286:
287: /**
288: * Removes a single instance of the specified element from this set,
289: * if it is present
290: *
291: * @param obj element to be removed from this set, if present.
292: * @return {@code true} if the set contained the specified element.
293: */
294: public synchronized boolean remove(final Object obj) {
295: return intern(obj, REMOVE) != null;
296: }
297:
298: /**
299: * Adds the specified element to this set if it is not already present.
300: * If this set already contains the specified element, the call leaves
301: * this set unchanged and returns {@code false}.
302: *
303: * @param obj Element to be added to this set.
304: * @return {@code true} if this set did not already
305: * contain the specified element.
306: */
307: public synchronized boolean add(final Object obj) {
308: return intern(obj, ADD) == null;
309: }
310:
311: // Arguments for the {@link #intern} method.
312: /** The "remove" operation. */
313: static final int REMOVE = -1;
314: /** The "get" operation. */
315: static final int GET = 0;
316: /** The "add" operation. */
317: static final int ADD = +1;
318: /** The "intern" operation. */
319: static final int INTERN = +2;
320:
321: /**
322: * Returns an object equals to {@code obj} if such an object already
323: * exist in this {@code WeakHashSet}. Otherwise, add {@code obj}
324: * to this {@code WeakHashSet}. This method is equivalents to the
325: * following code:
326: *
327: * <blockquote><pre>
328: * if (object!=null) {
329: * final Object current = get(object);
330: * if (current != null) {
331: * return current;
332: * } else {
333: * add(object);
334: * }
335: * }
336: * return object;
337: * </pre></blockquote>
338: */
339: final Object intern(final Object obj, final int operation) {
340: assert Thread.holdsLock(this );
341: assert WeakCollectionCleaner.DEFAULT.isAlive();
342: assert valid() : count;
343: if (obj != null) {
344: /*
345: * Check if {@code obj} is already contained in this
346: * {@code WeakHashSet}. If yes, returns the element.
347: */
348: final int hash = obj.hashCode() & 0x7FFFFFFF;
349: int index = hash % table.length;
350: for (Entry e = table[index]; e != null; e = e.next) {
351: final Object candidate = e.get();
352: if (candidate != null) {
353: if (candidate.equals(obj)) {
354: if (operation == REMOVE) {
355: e.clear();
356: }
357: return candidate;
358: }
359: }
360: // Do not remove the null element; lets ReferenceQueue do its job
361: // (it was a bug to remove element here as an "optimization")
362: }
363: if (operation >= ADD) {
364: /*
365: * Check if the table need to be rehashed,
366: * and add {@code obj} to the table.
367: */
368: if (count >= threshold) {
369: rehash(true);
370: index = hash % table.length;
371: }
372: table[index] = new Entry(obj, table[index], index);
373: count++;
374: }
375: }
376: assert valid();
377: return (operation == INTERN) ? obj : null;
378: }
379:
380: /**
381: * Returns an object equals to {@code object} if such an object already exist in this
382: * {@code WeakHashSet}. Otherwise, adds {@code object} to this {@code WeakHashSet}.
383: * This method is equivalents to the following code:
384: *
385: * <blockquote><pre>
386: * if (object != null) {
387: * Object current = get(object);
388: * if (current != null) {
389: * return current;
390: * } else {
391: * add(object);
392: * }
393: * }
394: * return object;
395: * </pre></blockquote>
396: *
397: * @deprecated Moved to the {@link CanonicalSet} subclass.
398: */
399: public synchronized Object canonicalize(final Object object) {
400: return intern(object, INTERN);
401: }
402:
403: /**
404: * Iteratively call {@link #canonicalize(Object)} for an array of objects.
405: * This method is equivalents to the following code:
406: *
407: * <blockquote><pre>
408: * for (int i=0; i<objects.length; i++) {
409: * objects[i] = canonicalize(objects[i]);
410: * }
411: * </pre></blockquote>
412: *
413: * @deprecated Moved to the {@link CanonicalSet} subclass.
414: */
415: public synchronized void canonicalize(final Object[] objects) {
416: for (int i = 0; i < objects.length; i++) {
417: objects[i] = intern(objects[i], INTERN);
418: }
419: }
420:
421: /**
422: * Removes all of the elements from this set.
423: */
424: public synchronized void clear() {
425: Arrays.fill(table, null);
426: count = 0;
427: }
428:
429: /**
430: * Returns a view of this set as an array. Elements will be in an arbitrary
431: * order. Note that this array contains strong reference. Consequently, no
432: * object reclamation will occurs as long as a reference to this array is hold.
433: */
434: public synchronized Object[] toArray() {
435: assert valid();
436: final Object[] elements = new Object[count];
437: int index = 0;
438: for (int i = 0; i < table.length; i++) {
439: for (Entry el = table[i]; el != null; el = el.next) {
440: if ((elements[index] = el.get()) != null) {
441: index++;
442: }
443: }
444: }
445: return XArray.resize(elements, index);
446: }
447:
448: /**
449: * Returns an iterator over the elements contained in this collection.
450: * No element from this set will be garbage collected as long as a
451: * reference to the iterator is hold.
452: */
453: public Iterator iterator() {
454: return Arrays.asList(toArray()).iterator();
455: }
456: }
|