source: osm/applications/editors/josm/plugins/opendata/includes/org/geotools/util/WeakHashSet.java@ 28000

Last change on this file since 28000 was 28000, checked in by donvip, 12 years ago

Import new "opendata" JOSM plugin
File size: 14.9 KB
Line 
1/*
2 * GeoTools - The Open Source Java GIS Toolkit
3 * http://geotools.org
4 *
5 * (C) 2001-2008, Open Source Geospatial Foundation (OSGeo)
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation;
10 * version 2.1 of the License.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 */
17package org.geotools.util;
18
19import java.lang.ref.WeakReference;
20import java.lang.reflect.Array;
21import java.util.AbstractSet;
22import java.util.Arrays;
23import java.util.Iterator;
24import java.util.logging.Level;
25import java.util.logging.LogRecord;
26import java.util.logging.Logger;
27
28import org.geotools.resources.XArray;
29import org.geotools.util.logging.Logging;
30
31
32/**
33 * A set of objects hold by weak references. An entry in a {@code WeakHashSet}
34 * will automatically be removed when it is no longer in ordinary use. More precisely,
35 * the presence of an entry will not prevent the entry from being discarded by the
36 * garbage collector, that is, made finalizable, finalized, and then reclaimed.
37 * When an entry has been discarded it is effectively removed from the set, so
38 * this class behaves somewhat differently than other {@link java.util.Set} implementations.
39 * <p>
40 * If you would like to use {@code WeakHashSet} as inside a factory to prevent creating
41 * duplicate immutable objects, please look at the {@link CanonicalSet} subclass.
42 * <p>
43 * The {@code WeakHashSet} class is thread-safe.
44 *
45 * @param <E> The type of elements in the set.
46 *
47 * @since 2.0
48 *
49 * @source $URL: http://svn.osgeo.org/geotools/branches/2.7.x/modules/library/metadata/src/main/java/org/geotools/util/WeakHashSet.java $
50 * @version $Id: WeakHashSet.java 37298 2011-05-25 05:16:15Z mbedward $
51 * @author Martin Desruisseaux (IRD)
52 *
53 * @see java.util.WeakHashMap
54 */
55public class WeakHashSet<E> extends AbstractSet<E> implements CheckedCollection<E> {
56 /**
57 * Minimal capacity for {@link #table}.
58 */
59 private static final int MIN_CAPACITY = 7;
60
61 /**
62 * Load factor. Control the moment
63 * where {@link #table} must be rebuild.
64 */
65 private static final float LOAD_FACTOR = 0.75f;
66
67 /**
68 * A weak reference to an element.
69 */
70 private final class Entry extends WeakReference<E> {
71 /**
72 * The next entry, or {@code null} if there is none.
73 */
74 Entry next;
75
76 /**
77 * Index for this element in {@link #table}. This index
78 * must be updated at every {@link #rehash} call.
79 */
80 int index;
81
82 /**
83 * Constructs a new weak reference.
84 */
85 Entry(final E obj, final Entry next, final int index) {
86 super(obj, WeakCollectionCleaner.DEFAULT.referenceQueue);
87 this.next = next;
88 this.index = index;
89 }
90
91 /**
92 * Clear the reference.
93 */
94 @Override
95 public void clear() {
96 super.clear();
97 removeEntry(this);
98 }
99 }
100
101 /**
102 * Table of weak references.
103 */
104 private Entry[] table;
105
106 /**
107 * The type of the elements in this set.
108 */
109 private final Class<E> type;
110
111 /**
112 * Number of non-nul elements in {@link #table}.
113 */
114 private int count;
115
116 /**
117 * The next size value at which to resize. This value should
118 * be <code>{@link #table}.length*{@link #loadFactor}</code>.
119 */
120 private int threshold;
121
122 /**
123 * The timestamp when {@link #table} was last rehashed. This information
124 * is used to avoid too early table reduction. When the garbage collector
125 * collected a lot of elements, we will wait at least 20 seconds before
126 * rehashing {@link #table}. Too early table reduction leads to many cycles
127 * like "reduce", "expand", "reduce", "expand", etc.
128 */
129 private long lastRehashTime;
130
131 /**
132 * Number of millisecond to wait before to rehash
133 * the table for reducing its size.
134 */
135 private static final long HOLD_TIME = 20*1000L;
136
137 /**
138 * Constructs a {@code WeakHashSet}.
139 *
140 * @deprecated Use {@link WeakHashSet(Class)}.
141 */
142 @SuppressWarnings("unchecked")
143 public WeakHashSet() {
144 this((Class) Object.class);
145 }
146
147 /**
148 * Constructs a {@code WeakHashSet}.
149 *
150 * @param type The type of the element to be included in this set.
151 *
152 * @since 2.5
153 */
154 public WeakHashSet(final Class<E> type) {
155 this.type = type;
156 newEntryTable(MIN_CAPACITY);
157 threshold = Math.round(table.length*LOAD_FACTOR);
158 lastRehashTime = System.currentTimeMillis();
159 }
160
161 /**
162 * Sets the {@link #table} array to the specified size. The content of the old array is lost.
163 *
164 * @todo Use the commented line instead if a future Java version supports generic arrays.
165 */
166 private void newEntryTable(final int size) {
167// table = new Entry[size];
168 table = (Entry[]) Array.newInstance(Entry.class, size);
169 }
170
171 /**
172 * Returns the element type.
173 *
174 * @since 2.5
175 */
176 public Class<E> getElementType() {
177 return type;
178 }
179
180 /**
181 * Invoked by {@link Entry} when an element has been collected by the garbage
182 * collector. This method will remove the weak reference from {@link #table}.
183 */
184 private synchronized void removeEntry(final Entry toRemove) {
185 assert valid() : count;
186 final int i = toRemove.index;
187 // Index 'i' may not be valid if the reference 'toRemove'
188 // has been already removed in a previous rehash.
189 if (i < table.length) {
190 Entry prev = null;
191 Entry e = table[i];
192 while (e != null) {
193 if (e == toRemove) {
194 if (prev != null) {
195 prev.next = e.next;
196 } else {
197 table[i] = e.next;
198 }
199 count--;
200 assert valid();
201
202 // If the number of elements has dimunished
203 // significatively, rehash the table.
204 if (count <= threshold/4) {
205 rehash(false);
206 }
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 assert valid();
216 /*
217 * If we reach this point, its mean that reference 'toRemove' has not
218 * been found. This situation may occurs if 'toRemove' has already been
219 * removed in a previous run of {@link #rehash}.
220 */
221 }
222
223 /**
224 * Rehash {@link #table}.
225 *
226 * @param augmentation
227 * {@code true} if this method is invoked for augmenting {@link #table},
228 * or {@code false} if it is invoked for making the table smaller.
229 */
230 private void rehash(final boolean augmentation) {
231 assert Thread.holdsLock(this);
232 assert valid();
233 final long currentTime = System.currentTimeMillis();
234 final int capacity = Math.max(Math.round(count/(LOAD_FACTOR/2)), count+MIN_CAPACITY);
235 if (augmentation ? (capacity<=table.length) :
236 (capacity>=table.length || currentTime-lastRehashTime<HOLD_TIME))
237 {
238 return;
239 }
240 lastRehashTime = currentTime;
241 final Entry[] oldTable = table;
242 newEntryTable(capacity);
243 threshold = Math.round(capacity*LOAD_FACTOR);
244 for (int i=0; i<oldTable.length; i++) {
245 for (Entry old=oldTable[i]; old!=null;) {
246 final Entry e=old;
247 old = old.next; // We keep 'next' right now because its value will change.
248 final E obj_e = e.get();
249 if (obj_e != null) {
250 final int index = (obj_e.hashCode() & 0x7FFFFFFF) % table.length;
251 e.index = index;
252 e.next = table[index];
253 table[index]=e;
254 } else {
255 count--;
256 }
257 }
258 }
259 final Logger logger = Logging.getLogger("org.geotools.util");
260 final Level level = Level.FINEST;
261 if (logger.isLoggable(level)) {
262 final LogRecord record = new LogRecord(level,
263 "Rehash from " + oldTable.length + " to " + table.length);
264 record.setSourceMethodName(augmentation ? "unique" : "remove");
265 record.setSourceClassName(WeakHashSet.class.getName());
266 record.setLoggerName(logger.getName());
267 logger.log(record);
268 }
269 assert valid();
270 }
271
272 /**
273 * Checks if this {@code WeakHashSet} is valid. This method counts the
274 * number of elements and compare it to {@link #count}. If the check fails,
275 * the number of elements is corrected (if we didn't, an {@link AssertionError}
276 * would be thrown for every operations after the first error, which make
277 * debugging more difficult). The set is otherwise unchanged, which should
278 * help to get similar behaviour as if assertions hasn't been turned on.
279 */
280 private boolean valid() {
281 int n = 0;
282 for (int i=0; i<table.length; i++) {
283 for (Entry e=table[i]; e!=null; e=e.next) {
284 n++;
285 }
286 }
287 if (n!=count) {
288 count = n;
289 return false;
290 } else {
291 return true;
292 }
293 }
294
295 /**
296 * Returns the count of element in this set.
297 */
298 public synchronized int size() {
299 assert valid();
300 return count;
301 }
302
303 /**
304 * Returns {@code true} if this set contains the specified element.
305 *
306 * @param obj Object to be checked for containment in this set.
307 * @return {@code true} if this set contains the specified element.
308 */
309 @Override
310 public synchronized boolean contains(final Object obj) {
311 return obj != null && intern(type.cast(obj), GET) != null;
312 }
313
314 /**
315 * Removes a single instance of the specified element from this set, if it is present
316 *
317 * @param obj element to be removed from this set, if present.
318 * @return {@code true} if the set contained the specified element.
319 */
320 @Override
321 public synchronized boolean remove(final Object obj) {
322 return intern(type.cast(obj), REMOVE) != null;
323 }
324
325 /**
326 * Adds the specified element to this set if it is not already present.
327 * If this set already contains the specified element, the call leaves
328 * this set unchanged and returns {@code false}.
329 *
330 * @param obj Element to be added to this set.
331 * @return {@code true} if this set did not already contain the specified element.
332 */
333 @Override
334 public synchronized boolean add(final E obj) {
335 return intern(obj, ADD) == null;
336 }
337
338 // Arguments for the {@link #intern} method.
339 /** The "remove" operation. */ static final int REMOVE = -1;
340 /** The "get" operation. */ static final int GET = 0;
341 /** The "add" operation. */ static final int ADD = +1;
342 /** The "intern" operation. */ static final int INTERN = +2;
343
344 /**
345 * Returns an object equals to {@code obj} if such an object already
346 * exist in this {@code WeakHashSet}. Otherwise, add {@code obj}
347 * to this {@code WeakHashSet}. This method is equivalents to the
348 * following code:
349 *
350 * <blockquote><pre>
351 * &nbsp; if (object!=null) {
352 * &nbsp; final Object current = get(object);
353 * &nbsp; if (current != null) {
354 * &nbsp; return current;
355 * &nbsp; } else {
356 * &nbsp; add(object);
357 * &nbsp; }
358 * &nbsp; }
359 * &nbsp; return object;
360 * </pre></blockquote>
361 */
362 final <T extends E> T intern(final T obj, final int operation) {
363 assert Thread.holdsLock(this);
364 assert WeakCollectionCleaner.DEFAULT.isAlive();
365 assert valid() : count;
366 if (obj != null) {
367 assert obj.equals(obj) : obj;
368 /*
369 * Check if {@code obj} is already contained in this
370 * {@code WeakHashSet}. If yes, returns the element.
371 */
372 final int hash = obj.hashCode() & 0x7FFFFFFF;
373 int index = hash % table.length;
374 for (Entry e=table[index]; e!=null; e=e.next) {
375 final E candidate = e.get();
376 if (candidate != null) {
377 if (candidate.equals(obj)) {
378 if (operation == REMOVE) {
379 e.clear();
380 }
381 assert candidate.getClass().equals(obj.getClass()) : candidate;
382 @SuppressWarnings("unchecked")
383 final T result = (T) candidate;
384 return result;
385 }
386 }
387 // Do not remove the null element; lets ReferenceQueue do its job
388 // (it was a bug to remove element here as an "optimization")
389 }
390 if (operation >= ADD) {
391 /*
392 * Check if the table need to be rehashed,
393 * and add {@code obj} to the table.
394 */
395 if (count >= threshold) {
396 rehash(true);
397 index = hash % table.length;
398 }
399 table[index] = new Entry(obj, table[index], index);
400 count++;
401 }
402 }
403 assert valid();
404 return (operation == INTERN) ? obj : null;
405 }
406
407 /**
408 * Removes all of the elements from this set.
409 */
410 @Override
411 public synchronized void clear() {
412 Arrays.fill(table, null);
413 count = 0;
414 }
415
416 /**
417 * Returns a view of this set as an array. Elements will be in an arbitrary
418 * order. Note that this array contains strong reference. Consequently, no
419 * object reclamation will occurs as long as a reference to this array is hold.
420 */
421 @Override
422 public synchronized E[] toArray() {
423 assert valid();
424 @SuppressWarnings("unchecked")
425 final E[] elements = (E[]) Array.newInstance(type, count);
426 int index = 0;
427 for (int i=0; i<table.length; i++) {
428 for (Entry el=table[i]; el!=null; el=el.next) {
429 if ((elements[index]=el.get()) != null) {
430 index++;
431 }
432 }
433 }
434 return XArray.resize(elements, index);
435 }
436
437 /**
438 * Returns an iterator over the elements contained in this collection.
439 * No element from this set will be garbage collected as long as a
440 * reference to the iterator is hold.
441 */
442 @Override
443 public Iterator<E> iterator() {
444 return Arrays.asList(toArray()).iterator();
445 }
446}
Note: See TracBrowser for help on using the repository browser.