001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/tags/2.1/src/org/deegree/model/csct/resources/WeakHashSet.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001 by:
006 EXSE, Department of Geography, University of Bonn
007 http://www.giub.uni-bonn.de/exse/
008 lat/lon GmbH
009 http://www.lat-lon.de
010
011 It has been implemented within SEAGIS - An OpenSource implementation of OpenGIS specification
012 (C) 2001, Institut de Recherche pour le D�veloppement (http://sourceforge.net/projects/seagis/)
013 SEAGIS Contacts: Surveillance de l'Environnement Assist�e par Satellite
014 Institut de Recherche pour le D�veloppement / US-Espace
015 mailto:seasnet@teledetection.fr
016
017
018 This library is free software; you can redistribute it and/or
019 modify it under the terms of the GNU Lesser General Public
020 License as published by the Free Software Foundation; either
021 version 2.1 of the License, or (at your option) any later version.
022
023 This library is distributed in the hope that it will be useful,
024 but WITHOUT ANY WARRANTY; without even the implied warranty of
025 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
026 Lesser General Public License for more details.
027
028 You should have received a copy of the GNU Lesser General Public
029 License along with this library; if not, write to the Free Software
030 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
031
032 Contact:
033
034 Andreas Poth
035 lat/lon GmbH
036 Aennchenstr. 19
037 53115 Bonn
038 Germany
039 E-Mail: poth@lat-lon.de
040
041 Klaus Greve
042 Department of Geography
043 University of Bonn
044 Meckenheimer Allee 166
045 53115 Bonn
046 Germany
047 E-Mail: klaus.greve@uni-bonn.de
048
049
050 ---------------------------------------------------------------------------*/
051 package org.deegree.model.csct.resources;
052
053 // Collections
054 import java.lang.ref.ReferenceQueue;
055 import java.lang.ref.WeakReference;
056 import java.util.AbstractSet;
057 import java.util.Arrays;
058 import java.util.Iterator;
059
060 /**
061 * A set of object hold by weak references.
062 * This class is used to implements caches.
063 *
064 * @version 1.0
065 * @author Martin Desruisseaux
066 */
067 public class WeakHashSet extends AbstractSet {
068 /**
069 * A weak reference to an element.
070 *
071 * @version 1.0
072 * @author Martin Desruisseaux
073 */
074 private final class WeakElement extends WeakReference {
075 /**
076 * The next entry, or <code>null</code> if there is none.
077 */
078 WeakElement next;
079
080 /**
081 * Index for this element in {@link #table}. This index
082 * must be updated at every {@link #rehash} call.
083 */
084 int index;
085
086 /**
087 * Construct a new weak reference.
088 */
089 WeakElement( final Object obj, final WeakElement next, final int index ) {
090 super( obj, referenceQueue );
091 this.next = next;
092 this.index = index;
093 }
094
095 /**
096 * Clear the reference.
097 */
098 public void clear() {
099 super.clear();
100 remove( this );
101 }
102 }
103
104 /**
105 * Minimal capacity for {@link #table}.
106 */
107 private static final int MIN_CAPACITY = 7;
108
109 /**
110 * Load factor. Control the moment
111 * where {@link #table} must be rebuild.
112 */
113 private static final float LOAD_FACTOR = 0.75f;
114
115 /**
116 * List of reference collected by the garbage collector.
117 * Those elements must be removed from {@link #table}.
118 */
119 private static final ReferenceQueue referenceQueue = new ReferenceQueue();
120
121 /**
122 * Background thread removing references
123 * collected by the garbage collector.
124 */
125 private static final Thread thread = new Thread( "WeakHashSet" ) {
126 public void run() {
127 while ( true )
128 try {
129 referenceQueue.remove().clear();
130 } catch ( InterruptedException exception ) {
131 // Somebody doesn't want to lets
132 // us sleep... Go back to work.
133 } catch ( Exception exception ) {
134 exception.printStackTrace();
135 }
136 }
137 };
138 static {
139 thread.setDaemon( true );
140 thread.start();
141 }
142
143 /**
144 * Table of weak references.
145 */
146 private WeakElement[] table;
147
148 /**
149 * Number of non-nul elements in {@link #table}.
150 */
151 private int count;
152
153 /**
154 * The next size value at which to resize. This value should
155 * be <code>{@link #table}.length*{@link #loadFactor}</code>.
156 */
157 private int threshold;
158
159 /**
160 * The timestamp when {@link #table} was last rehashed. This information
161 * is used to avoir too early table reduction. When the garbage collector
162 * collected a lot of elements, we will wait at least 20 seconds before
163 * rehashing {@link #table} in order to avoir to many cycles "reduce",
164 * "expand", "reduce", "expand", etc.
165 */
166 private long lastRehashTime;
167
168 /**
169 * Number of millisecond to wait before to rehash
170 * the table for reducing its size.
171 */
172 private static final long HOLD_TIME = 20 * 1000L;
173
174 /**
175 * Construct a <code>WeakHashSet</code>.
176 */
177 public WeakHashSet() {
178 table = new WeakElement[MIN_CAPACITY];
179 threshold = Math.round( table.length * LOAD_FACTOR );
180 lastRehashTime = System.currentTimeMillis();
181 }
182
183 /**
184 * Invoked by {@link WeakElement} when an element has been collected
185 * by the garbage collector. This method will remove the weak reference
186 * from {@link #table}.
187 */
188 private synchronized void remove( final WeakElement toRemove ) {
189 final int i = toRemove.index;
190 // Index 'i' may not be valid if the reference 'toRemove'
191 // has been already removed in a previous rehash.
192 if ( i < table.length ) {
193 WeakElement prev = null;
194 WeakElement e = table[i];
195 while ( e != null ) {
196 if ( e == toRemove ) {
197 if ( prev != null )
198 prev.next = e.next;
199 else
200 table[i] = e.next;
201 count--;
202
203 // If the number of elements has dimunished
204 // significatively, rehash the table.
205 if ( count <= threshold / 4 )
206 rehash( false );
207 // We must not continue the loop, since
208 // variable 'e' is no longer valid.
209 return;
210 }
211 prev = e;
212 e = e.next;
213 }
214 }
215 /*
216 * If we reach this point, its mean that reference 'toRemove' has not
217 * been found. This situation may occurs if 'toRemove' has already been
218 * removed in a previous run of {@link #rehash}.
219 */
220 }
221
222 /**
223 * Rehash {@link #table}.
224 *
225 * @param augmentation <code>true</code> if this method is invoked
226 * for augmenting {@link #table}, or <code>false</code> if
227 * it is invoked for making the table smaller.
228 */
229 private void rehash( final boolean augmentation ) {
230 final long currentTime = System.currentTimeMillis();
231 final int capacity = Math.max( Math.round( count / ( LOAD_FACTOR / 2 ) ), count
232 + MIN_CAPACITY );
233 if ( augmentation ? ( capacity <= table.length )
234 : ( capacity >= table.length || currentTime - lastRehashTime < HOLD_TIME ) ) {
235 return;
236 }
237 lastRehashTime = currentTime;
238 final WeakElement[] oldTable = table;
239 table = new WeakElement[capacity];
240 threshold = Math.round( capacity * LOAD_FACTOR );
241 for ( int i = 0; i < oldTable.length; i++ ) {
242 for ( WeakElement old = oldTable[i]; old != null; ) {
243 final WeakElement e = old;
244 old = old.next; // On retient 'next' tout de suite car sa valeur va changer...
245 final Object obj_e = e.get();
246 if ( obj_e != null ) {
247 final int index = ( hashCode( obj_e ) & 0x7FFFFFFF ) % table.length;
248 e.index = index;
249 e.next = table[index];
250 table[index] = e;
251 } else
252 count--;
253 }
254 }
255 }
256
257 /**
258 * Returns <code>true</code> if this set contains the specified element.
259 *
260 * @param obj Object to be checked for containment in this set.
261 * @return <code>true</code> if this set contains the specified element.
262 */
263 public boolean contains( final Object obj ) {
264 return obj == null || get( obj ) != null;
265 }
266
267 /**
268 * Returns an object equals to the specified object, if present. If
269 * this set doesn't contains any object equals to <code>obj</code>,
270 * then this method returns <code>null</code>.
271 */
272 public synchronized final Object get( final Object obj ) {
273 if ( obj != null ) {
274 final int hash = hashCode( obj ) & 0x7FFFFFFF;
275 int index = hash % table.length;
276 for ( WeakElement e = table[index]; e != null; e = e.next ) {
277 final Object e_obj = e.get();
278 if ( e_obj != null ) {
279 if ( equals( obj, e_obj ) )
280 return e_obj;
281 }
282 }
283 }
284 return obj;
285 }
286
287 /**
288 * Adds the specified element to this set if it is not already present.
289 * If this set already contains the specified element, the call leaves
290 * this set unchanged and returns <code>false</code>.
291 *
292 * @param obj Element to be added to this set.
293 * @return <code>true</code> if this set did not already
294 * contain the specified element.
295 */
296 public synchronized boolean add( final Object obj ) {
297 return intern0( obj ) == null;
298 }
299
300 /**
301 * Returns an object equals to <code>obj</code> if such an object already
302 * exist in this <code>WeakHashSet</code>. Otherwise, add <code>obj</code>
303 * to this <code>WeakHashSet</code>. This method is equivalents to the
304 * following code:
305 *
306 * <blockquote><pre>
307 * if (object!=null)
308 * {
309 * final Object current=get(object);
310 * if (current!=null) return current;
311 * else add(object);
312 * }
313 * return object;
314 * </pre></blockquote>
315 */
316 private Object intern0( final Object obj ) {
317 if ( obj != null ) {
318 /*
319 * Check if <code>obj</code> is already contained in this
320 * <code>WeakHashSet</code>. If yes, returns the element.
321 */
322 final int hash = hashCode( obj ) & 0x7FFFFFFF;
323 int index = hash % table.length;
324 for ( WeakElement e = table[index]; e != null; e = e.next ) {
325 final Object e_obj = e.get();
326 if ( e_obj != null ) {
327 if ( equals( obj, e_obj ) )
328 return e_obj;
329 }
330 // Do not remove the null element; lets "remove" do its job
331 // (it was a bug to remove element here as an "optimization")
332 }
333 /*
334 * Check if the table need to be rehashed,
335 * and add <code>obj</code> to the table.
336 */
337 if ( count >= threshold ) {
338 rehash( true );
339 index = hash % table.length;
340 }
341 table[index] = new WeakElement( obj, table[index], index );
342 count++;
343 }
344 return obj;
345 }
346
347 /**
348 * Returns an object equals to <code>obj</code> if such an object already
349 * exist in this <code>WeakHashSet</code>. Otherwise, add <code>obj</code>
350 * to this <code>WeakHashSet</code>. This method is equivalents to the
351 * following code:
352 *
353 * <blockquote><pre>
354 * if (object!=null)
355 * {
356 * final Object current=get(object);
357 * if (current!=null) return current;
358 * else add(object);
359 * }
360 * return object;
361 * </pre></blockquote>
362 */
363 public synchronized final Object intern( final Object object ) {
364 return intern0( object );
365 }
366
367 /**
368 * Iteratively call {@link #intern(Object)} for an array of objects.
369 * This method is equivalents to the following code:
370 *
371 * <blockquote><pre>
372 * for (int i=0; i<objects.length; i++)
373 * objects[i] = intern(objects[i]);
374 * </pre></blockquote>
375 */
376 public synchronized final void intern( final Object[] objects ) {
377 for ( int i = 0; i < objects.length; i++ )
378 objects[i] = intern0( objects[i] );
379 }
380
381 /**
382 * Returns the count of element in this set.
383 */
384 public synchronized final int size() {
385 return count;
386 }
387
388 /**
389 * Removes all of the elements from this set.
390 */
391 public synchronized final void clear() {
392 Arrays.fill( table, null );
393 count = 0;
394 }
395
396 /**
397 * Returns a view of this set as an array. Elements will be in an arbitrary
398 * order. Note that this array contains strong reference. Consequently, no
399 * object reclamation will occurs as long as a reference to this array is hold.
400 */
401 public synchronized final Object[] toArray() {
402 final Object[] elements = new Object[count];
403 int index = 0;
404 for ( int i = 0; i < table.length; i++ ) {
405 for ( WeakElement el = table[i]; el != null; el = el.next ) {
406 if ( ( elements[index] = el.get() ) != null )
407 index++;
408 }
409 }
410 return XArray.resize( elements, index );
411 }
412
413 /**
414 * Returns an iterator over the elements contained in this collection.
415 * No element from this set will be garbage collected as long as a
416 * reference to the iterator is hold.
417 */
418 public Iterator iterator() {
419 return Arrays.asList( toArray() ).iterator();
420 }
421
422 /**
423 * Returns a hash code value for the specified object.
424 * Default implementation returns {@link Object#hashCode}.
425 * Override to compute hash code in a different way.
426 */
427 protected int hashCode( final Object object ) {
428 return ( object != null ) ? object.hashCode() : 0;
429 }
430
431 /**
432 * Check two objects for equality. This method should be overriden
433 * if {@link #hashCode(Object)} has been overriden.
434 */
435 protected boolean equals( final Object object1, final Object object2 ) {
436 return object1 == object2 || ( object1 != null && object1.equals( object2 ) );
437 }
438 }