KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > runtime > ReferenceHashSet


1 /*******************************************************************************
2  * Copyright (c) 2004, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/

11 package org.eclipse.core.internal.runtime;
12
13 import java.lang.ref.*;
14
15 /**
16  * A hashset whose values can be garbage collected.
17  * This API is EXPERIMENTAL and provided as early access.
18  * @since 3.1
19  */

20 public class ReferenceHashSet {
21
22     private interface HashedReference {
23         int hashCode();
24
25         Object JavaDoc get();
26     }
27
28     private class HashableWeakReference extends WeakReference implements HashedReference {
29         public int hashCode;
30
31         public HashableWeakReference(Object JavaDoc referent, ReferenceQueue queue) {
32             super(referent, queue);
33             this.hashCode = referent.hashCode();
34         }
35
36         public boolean equals(Object JavaDoc obj) {
37             if (!(obj instanceof HashableWeakReference))
38                 return false;
39             Object JavaDoc referent = super.get();
40             Object JavaDoc other = ((HashableWeakReference) obj).get();
41             if (referent == null)
42                 return other == null;
43             return referent.equals(other);
44         }
45
46         public int hashCode() {
47             return this.hashCode;
48         }
49
50         public String JavaDoc toString() {
51             Object JavaDoc referent = super.get();
52             if (referent == null)
53                 return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$ //$NON-NLS-2$
54
return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
55
}
56     }
57
58     private class HashableSoftReference extends SoftReference implements HashedReference {
59         public int hashCode;
60
61         public HashableSoftReference(Object JavaDoc referent, ReferenceQueue queue) {
62             super(referent, queue);
63             this.hashCode = referent.hashCode();
64         }
65
66         public boolean equals(Object JavaDoc obj) {
67             if (!(obj instanceof HashableWeakReference))
68                 return false;
69             Object JavaDoc referent = super.get();
70             Object JavaDoc other = ((HashableWeakReference) obj).get();
71             if (referent == null)
72                 return other == null;
73             return referent.equals(other);
74         }
75
76         public int hashCode() {
77             return this.hashCode;
78         }
79
80         public String JavaDoc toString() {
81             Object JavaDoc referent = super.get();
82             if (referent == null)
83                 return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$ //$NON-NLS-2$
84
return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
85
}
86     }
87
88     private class StrongReference implements HashedReference {
89         private Object JavaDoc referent;
90
91         public StrongReference(Object JavaDoc referent, ReferenceQueue queue) {
92             this.referent = referent;
93         }
94
95         public int hashCode() {
96             return referent.hashCode();
97         }
98
99         public Object JavaDoc get() {
100             return referent;
101         }
102
103         public boolean equals(Object JavaDoc obj) {
104             return referent.equals(obj);
105         }
106     }
107
108     HashedReference[] values;
109
110     public int elementSize; // number of elements in the table
111

112     int threshold;
113
114     ReferenceQueue referenceQueue = new ReferenceQueue();
115
116     public ReferenceHashSet() {
117         this(5);
118     }
119
120     public ReferenceHashSet(int size) {
121         this.elementSize = 0;
122         this.threshold = size; // size represents the expected
123
// number of elements
124
int extraRoom = (int) (size * 1.75f);
125         if (this.threshold == extraRoom)
126             extraRoom++;
127         this.values = new HashedReference[extraRoom];
128     }
129
130     /**
131      * Constant indicating that hard references should be used.
132      */

133     final public static int HARD = 0;
134
135     /**
136      * Constant indiciating that soft references should be used.
137      */

138     final public static int SOFT = 1;
139
140     /**
141      * Constant indicating that weak references should be used.
142      */

143     final public static int WEAK = 2;
144
145     private HashedReference toReference(int type, Object JavaDoc referent) {
146         switch (type) {
147             case HARD :
148                 return new StrongReference(referent, referenceQueue);
149             case SOFT :
150                 return new HashableSoftReference(referent, referenceQueue);
151             case WEAK :
152                 return new HashableWeakReference(referent, referenceQueue);
153             default :
154                 throw new Error JavaDoc();
155         }
156     }
157
158     /*
159      * Adds the given object to this set. If an object that is equals to the
160      * given object already exists, do nothing. Returns the existing object or
161      * the new object if not found.
162      */

163     public Object JavaDoc add(Object JavaDoc obj, int referenceType) {
164         cleanupGarbageCollectedValues();
165         int index = (obj.hashCode() & 0x7FFFFFFF) % this.values.length;
166         HashedReference currentValue;
167         while ((currentValue = this.values[index]) != null) {
168             Object JavaDoc referent;
169             if (obj.equals(referent = currentValue.get())) {
170                 return referent;
171             }
172             index = (index + 1) % this.values.length;
173         }
174         this.values[index] = toReference(referenceType, obj);
175
176         // assumes the threshold is never equal to the size of the table
177
if (++this.elementSize > this.threshold)
178             rehash();
179
180         return obj;
181     }
182
183     private void addValue(HashedReference value) {
184         Object JavaDoc obj = value.get();
185         if (obj == null)
186             return;
187         int valuesLength = this.values.length;
188         int index = (value.hashCode() & 0x7FFFFFFF) % valuesLength;
189         HashedReference currentValue;
190         while ((currentValue = this.values[index]) != null) {
191             if (obj.equals(currentValue.get())) {
192                 return;
193             }
194             index = (index + 1) % valuesLength;
195         }
196         this.values[index] = value;
197
198         // assumes the threshold is never equal to the size of the table
199
if (++this.elementSize > this.threshold)
200             rehash();
201     }
202
203     private void cleanupGarbageCollectedValues() {
204         HashedReference toBeRemoved;
205         while ((toBeRemoved = (HashedReference) this.referenceQueue.poll()) != null) {
206             int hashCode = toBeRemoved.hashCode();
207             int valuesLength = this.values.length;
208             int index = (hashCode & 0x7FFFFFFF) % valuesLength;
209             HashedReference currentValue;
210             while ((currentValue = this.values[index]) != null) {
211                 if (currentValue == toBeRemoved) {
212                     // replace the value at index with the last value with the
213
// same hash
214
int sameHash = index;
215                     int current;
216                     while ((currentValue = this.values[current = (sameHash + 1) % valuesLength]) != null && currentValue.hashCode() == hashCode)
217                         sameHash = current;
218                     this.values[index] = this.values[sameHash];
219                     this.values[sameHash] = null;
220                     this.elementSize--;
221                     break;
222                 }
223                 index = (index + 1) % valuesLength;
224             }
225         }
226     }
227
228     public boolean contains(Object JavaDoc obj) {
229         return get(obj) != null;
230     }
231
232     /*
233      * Return the object that is in this set and that is equals to the given
234      * object. Return null if not found.
235      */

236     public Object JavaDoc get(Object JavaDoc obj) {
237         cleanupGarbageCollectedValues();
238         int valuesLength = this.values.length;
239         int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
240         HashedReference currentValue;
241         while ((currentValue = this.values[index]) != null) {
242             Object JavaDoc referent;
243             if (obj.equals(referent = currentValue.get())) {
244                 return referent;
245             }
246             index = (index + 1) % valuesLength;
247         }
248         return null;
249     }
250
251     private void rehash() {
252         ReferenceHashSet newHashSet = new ReferenceHashSet(this.elementSize * 2); // double the number of expected elements
253
newHashSet.referenceQueue = this.referenceQueue;
254         HashedReference currentValue;
255         for (int i = 0, length = this.values.length; i < length; i++)
256             if ((currentValue = this.values[i]) != null)
257                 newHashSet.addValue(currentValue);
258
259         this.values = newHashSet.values;
260         this.threshold = newHashSet.threshold;
261         this.elementSize = newHashSet.elementSize;
262     }
263
264     /*
265      * Removes the object that is in this set and that is equals to the given
266      * object. Return the object that was in the set, or null if not found.
267      */

268     public Object JavaDoc remove(Object JavaDoc obj) {
269         cleanupGarbageCollectedValues();
270         int valuesLength = this.values.length;
271         int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
272         HashedReference currentValue;
273         while ((currentValue = this.values[index]) != null) {
274             Object JavaDoc referent;
275             if (obj.equals(referent = currentValue.get())) {
276                 this.elementSize--;
277                 this.values[index] = null;
278                 rehash();
279                 return referent;
280             }
281             index = (index + 1) % valuesLength;
282         }
283         return null;
284     }
285
286     public int size() {
287         return this.elementSize;
288     }
289
290     public String JavaDoc toString() {
291         StringBuffer JavaDoc buffer = new StringBuffer JavaDoc("{"); //$NON-NLS-1$
292
for (int i = 0, length = this.values.length; i < length; i++) {
293             HashedReference value = this.values[i];
294             if (value != null) {
295                 Object JavaDoc ref = value.get();
296                 if (ref != null) {
297                     buffer.append(ref.toString());
298                     buffer.append(", "); //$NON-NLS-1$
299
}
300             }
301         }
302         buffer.append("}"); //$NON-NLS-1$
303
return buffer.toString();
304     }
305
306     public Object JavaDoc[] toArray() {
307         cleanupGarbageCollectedValues();
308         Object JavaDoc[] result = new Object JavaDoc[elementSize];
309         int resultSize = 0;
310         for (int i = 0; i < values.length; i++) {
311             if (values[i] == null)
312                 continue;
313             Object JavaDoc tmp = values[i].get();
314             if (tmp != null)
315                 result[resultSize++] = tmp;
316         }
317         if (result.length == resultSize)
318             return result;
319         Object JavaDoc[] finalResult = new Object JavaDoc[resultSize];
320         System.arraycopy(result, 0, finalResult, 0, resultSize);
321         return finalResult;
322     }
323 }
324
Popular Tags