001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.openide.util;
043:
044: import java.io.IOException;
045: import java.io.ObjectInputStream;
046: import java.io.ObjectOutputStream;
047: import java.io.Serializable;
048: import java.lang.ref.ReferenceQueue;
049: import java.lang.ref.WeakReference;
050: import java.util.AbstractSet;
051: import java.util.ArrayList;
052: import java.util.Collection;
053: import java.util.ConcurrentModificationException;
054: import java.util.Iterator;
055:
056: /** Set which holds its members by using of WeakReferences.
057: * MT level: unsafe.
058: * <p><strong>Note:</strong> as of JDK 6.0 (b51), you can instead use
059: * <pre>
060: * Set<T> s = Collections.newSetFromMap(new WeakHashMap<T, Boolean>());
061: * </pre>
062: *
063: * @author Ales Novak
064: */
065: public class WeakSet<E> extends AbstractSet<E> implements Cloneable,
066: Serializable {
067: static final long serialVersionUID = 3062376055928236721L;
068:
069: /** load factor */
070: private float loadFactor;
071:
072: /** Number of items. */
073: private int size;
074:
075: /** Modification count */
076: private long modcount;
077:
078: /** Reference queue of collected weak refs */
079: private transient ReferenceQueue<E> refq;
080:
081: /** Count of <tt>null</tt> in this set */
082: long nullCount;
083:
084: /** An array of Entries */
085: private transient Entry<E>[] entries;
086: transient Entry<E> iterChain;
087:
088: /** Constructs a new set. */
089: public WeakSet() {
090: this (11, 0.75f);
091: }
092:
093: /** Constructs a new set containing the elements in the specified collection.
094: * @param c a collection to add
095: */
096: public WeakSet(Collection<? extends E> c) {
097: this ();
098: addAll(c);
099: }
100:
101: /** Constructs a new, empty set;
102: * @param initialCapacity initial capacity
103: */
104: public WeakSet(int initialCapacity) {
105: this (initialCapacity, 0.75f);
106: }
107:
108: /** Constructs a new, empty set;
109: *
110: * @param initialCapacity initial capacity
111: * @param loadFactor load factor
112: */
113: public WeakSet(int initialCapacity, float loadFactor) {
114: if ((initialCapacity <= 0) || (loadFactor <= 0)) {
115: throw new IllegalArgumentException();
116: }
117:
118: size = 0;
119: modcount = 0;
120: this .loadFactor = loadFactor;
121: nullCount = 0;
122: refq = new ReferenceQueue<E>();
123: entries = Entry.createArray(initialCapacity);
124: iterChain = null;
125: }
126:
127: /** Adds the specified element to this set if it is not already present.
128: *
129: * @param o an Object to add
130: */
131: public boolean add(E o) {
132: if (o == null) {
133: size++;
134: nullCount++;
135: modcount++;
136:
137: return true;
138: }
139:
140: Entry e = object2Entry(o);
141:
142: if (e != null) {
143: return false;
144: }
145:
146: modcount++;
147: size++;
148:
149: int hash = hashIt(o);
150: Entry<E> next = entries[hash];
151: iterChain = entries[hash] = new Entry<E>(this , o, refq, next,
152: iterChain);
153: rehash();
154:
155: return true;
156: }
157:
158: /** Removes all of the elements from this set. */
159: public void clear() {
160: for (int i = 0; i < entries.length; i++) {
161: entries[i] = null;
162: }
163:
164: nullCount = 0;
165: modcount++;
166: size = 0;
167: iterChain = null;
168: }
169:
170: /** Returns a shallow copy of this WeakSet instance: the elements themselves are not cloned. */
171: public Object clone() {
172: WeakSet<E> nws = new WeakSet<E>(1, loadFactor);
173: nws.size = size;
174: nws.nullCount = nullCount;
175:
176: Entry<E>[] cloned = Entry.createArray(entries.length);
177: nws.entries = cloned;
178:
179: for (int i = 0; i < cloned.length; i++) {
180: Object ref;
181:
182: if ((entries[i] == null)
183: || ((ref = entries[i].get()) == null)) {
184: cloned[i] = null;
185: } else {
186: cloned[i] = ((entries[i] == null) ? null : entries[i]
187: .clone(nws.refq));
188: ref = null;
189: }
190:
191: // chains into nws iterator chain
192: Entry<E> entry = cloned[i];
193:
194: while (entry != null) {
195: entry.chainIntoIter(nws.iterChain);
196: nws.iterChain = entry;
197: entry = entry.next;
198: }
199: }
200:
201: return nws;
202: }
203:
204: /** Returns true if this set contains the specified element.
205: *
206: * @param o an Object to examine
207: */
208: public boolean contains(Object o) {
209: if (o == null) {
210: return nullCount > 0;
211: }
212:
213: return object2Entry(o) != null;
214: }
215:
216: /** Returns true if this set contains no elements.
217: */
218: public boolean isEmpty() {
219: return ((nullCount == 0) && (size() == 0));
220: }
221:
222: /** Returns an iterator over the elements in this set. */
223: public Iterator<E> iterator() {
224: return new WeakSetIterator();
225: }
226:
227: /** Removes the given element from this set if it is present.
228: *
229: * @param o an Object to remove
230: * @return <tt>true</tt> if and only if the Object was successfuly removed.
231: */
232: public boolean remove(Object o) {
233: if (o == null) {
234: if (nullCount > 0) {
235: nullCount--;
236: modcount++;
237: size--;
238: }
239:
240: return true;
241: }
242:
243: Entry e = object2Entry(o);
244:
245: if (e != null) {
246: modcount++;
247: size--;
248: e.remove();
249: rehash();
250:
251: return true;
252: }
253:
254: return false;
255: }
256:
257: /** @return the number of elements in this set (its cardinality). */
258: public int size() {
259: checkRefQueue();
260:
261: return size;
262: }
263:
264: public <T> T[] toArray(T[] array) {
265: ArrayList<E> list = new ArrayList<E>(array.length);
266: Iterator<E> it = iterator();
267:
268: while (it.hasNext()) {
269: list.add(it.next());
270: }
271:
272: return list.toArray(array);
273: }
274:
275: public Object[] toArray() {
276: ArrayList<E> list = new ArrayList<E>();
277: Iterator<E> it = iterator();
278:
279: while (it.hasNext()) {
280: list.add(it.next());
281: }
282:
283: return list.toArray();
284: }
285:
286: // #14772
287: public String toString() {
288: StringBuffer buf = new StringBuffer();
289: Iterator e = iterator();
290: buf.append("[");
291:
292: while (e.hasNext()) {
293: buf.append(String.valueOf(e.next()));
294:
295: if (e.hasNext()) {
296: buf.append(", ");
297: }
298: }
299:
300: buf.append("]");
301:
302: return buf.toString();
303: }
304:
305: /** Checks if the queue is empty if not pending weak refs are removed. */
306: void checkRefQueue() {
307: for (;;) {
308: Entry entry = Entry.class.cast(refq.poll());
309:
310: if (entry == null) {
311: break;
312: }
313:
314: entry.remove();
315: size--;
316: }
317: }
318:
319: /** @return modcount */
320: long modCount() {
321: return modcount;
322: }
323:
324: /** @return an index to entries array */
325: int hashIt(Object o) {
326: return (o.hashCode() & 0x7fffffff) % entries.length;
327: }
328:
329: /** rehashes this Set */
330: void rehash() {
331: /*
332: float currentLF = ((float) size) / ((float) entries.length);
333: if (currentLF < loadFactor) {
334: return;
335: }
336: */
337: }
338:
339: /** @return an Entry with given object */
340: private Entry object2Entry(Object o) {
341: checkRefQueue(); // clear ref q
342:
343: int hash = hashIt(o);
344: Entry e = entries[hash];
345:
346: if (e == null) {
347: return null;
348: }
349:
350: while ((e != null) && !e.equals(o)) {
351: e = e.next;
352: }
353:
354: return e;
355: }
356:
357: private void writeObject(ObjectOutputStream obtos)
358: throws IOException {
359: obtos.defaultWriteObject();
360: obtos.writeObject(toArray());
361: }
362:
363: @SuppressWarnings("unchecked")
364: private void readObject(ObjectInputStream obtis)
365: throws IOException, ClassNotFoundException {
366: obtis.defaultReadObject();
367:
368: Object[] arr = (Object[]) obtis.readObject();
369: entries = new Entry[(int) (size * 1.5)];
370: refq = new ReferenceQueue<E>();
371:
372: for (int i = 0; i < arr.length; i++) {
373: add((E) arr[i]);
374: }
375: }
376:
377: class WeakSetIterator implements Iterator<E> {
378: Entry<E> current;
379: Entry<E> next;
380: E currentObj;
381: E nextObj;
382: final long myModcount;
383: long myNullCount;
384:
385: WeakSetIterator() {
386: myModcount = modCount();
387: myNullCount = nullCount;
388: current = null;
389: next = null;
390:
391: Entry<E> ee = iterChain;
392:
393: if (ee == null) {
394: return;
395: }
396:
397: E o = ee.get();
398:
399: while (ee.isEnqueued()) {
400: ee = ee.iterChainNext;
401:
402: if (ee == null) {
403: return;
404: }
405:
406: o = ee.get();
407: }
408:
409: nextObj = o;
410: next = ee;
411: }
412:
413: public boolean hasNext() {
414: checkModcount();
415:
416: return ((myNullCount > 0) || (next != null));
417: }
418:
419: public E next() {
420: checkModcount();
421: checkRefQueue();
422:
423: if (myNullCount > 0) {
424: myNullCount--;
425:
426: return null;
427: } else {
428: if (next == null) {
429: throw new java.util.NoSuchElementException();
430: }
431:
432: current = next;
433: currentObj = nextObj;
434:
435: // move to next requested
436: do {
437: next = next.iterChainNext;
438:
439: if (next == null) {
440: break;
441: }
442:
443: nextObj = next.get();
444: } while (next.isEnqueued());
445:
446: return currentObj;
447: }
448: }
449:
450: public void remove() {
451: checkModcount();
452:
453: if (current == null) {
454: throw new IllegalStateException();
455: }
456:
457: current.remove();
458: size--;
459: }
460:
461: void checkModcount() {
462: if (myModcount != modCount()) {
463: throw new ConcurrentModificationException();
464: }
465: }
466: }
467:
468: /** Entries of this set */
469: static class Entry<E> extends WeakReference<E> {
470: /** reference to outer WeakSet */
471: private WeakSet<E> set;
472:
473: // double linked list
474: Entry<E> prev;
475: Entry<E> next;
476: private final int hashcode;
477: Entry<E> iterChainNext;
478: Entry<E> iterChainPrev;
479:
480: Entry(WeakSet<E> set, E referenced, ReferenceQueue<E> q,
481: Entry<E> next, Entry<E> nextInIter) {
482: super (referenced, q);
483: this .set = set;
484:
485: this .next = next;
486: this .prev = null;
487:
488: if (next != null) {
489: next.prev = this ;
490: }
491:
492: if (referenced != null) {
493: hashcode = set.hashIt(referenced);
494: } else {
495: hashcode = 0;
496: }
497:
498: chainIntoIter(nextInIter);
499: }
500:
501: @SuppressWarnings("unchecked")
502: static final <E> Entry<E>[] createArray(int size) {
503: return new Entry[size];
504: }
505:
506: void chainIntoIter(Entry<E> nextInIter) {
507: iterChainNext = nextInIter;
508:
509: if (nextInIter != null) {
510: nextInIter.iterChainPrev = this ;
511:
512: Object ref = nextInIter.get();
513:
514: if (ref == null) {
515: nextInIter.remove();
516: }
517: }
518: }
519:
520: /** deques itself */
521: void remove() {
522: if (prev != null) {
523: prev.next = next;
524: }
525:
526: if (next != null) {
527: next.prev = prev;
528: }
529:
530: if (iterChainNext != null) {
531: iterChainNext.iterChainPrev = iterChainPrev;
532: }
533:
534: if (iterChainPrev != null) {
535: iterChainPrev.iterChainNext = iterChainNext;
536: } else { // root
537: set.iterChain = iterChainNext;
538: }
539:
540: if (set.entries[hashcode] == this ) {
541: set.entries[hashcode] = next;
542: }
543:
544: prev = null;
545: next = null;
546: iterChainNext = null;
547: iterChainPrev = null;
548: }
549:
550: public int hashCode() {
551: return hashcode;
552: }
553:
554: public boolean equals(Object o) {
555: Object oo = get();
556:
557: if (oo == null) {
558: return false;
559: } else {
560: return oo.equals(o);
561: }
562: }
563:
564: public Entry<E> clone(ReferenceQueue<E> q) {
565: return new Entry<E>(set, get(), q, next != null ? next
566: .clone(q) : null, null);
567: }
568: }
569: }
|